🐛 Crash when running qmap.optimize_clifford() for large clifford circuits integrated with `qiskit`'s `TransformationPass`

[gluonhiggs]

System Information

• OS

NAME="Linux Mint"
VERSION="22.1 (Xia)"
ID=linuxmint
ID_LIKE="ubuntu debian"
PRETTY_NAME="Linux Mint 22.1"
VERSION_ID="22.1"
HOME_URL="https://www.linuxmint.com/"
SUPPORT_URL="https://forums.linuxmint.com/"
BUG_REPORT_URL="http://linuxmint-troubleshooting-guide.readthedocs.io/en/latest/"
PRIVACY_POLICY_URL="https://www.linuxmint.com/"
VERSION_CODENAME=xia
UBUNTU_CODENAME=noble

• mqt-qmap:3.1.3
• Python version: 3.12.3
• Dependencies:

dependencies = [
    "cirq-core>=1.4.1,<2.0.0",
    "mitiq>=0.45.1",
    "mqt-qmap>=3.1.3",
    "ply>=3.11,<4.0.0",
    "pytket>=1.40.0,<3.0.0",
    "qbraid>=0.9.3,<1.0.0",
    "qiskit>=1.4.2,<3.0.0",
    "qiskit-qasm3-import>=0.5.1,<1.0.0",
]

Bug Description

My PC crash. I expect the script would be running normally.

Steps to Reproduce

1. Setup env:
   For ease, clone the following repo
   https://github.com/unitaryfoundation/ucc.git
   and https://github.com/unitaryfoundation/ucc-bench. Then cd to the directories in different windows.

In ucc dir, install uv https://docs.astral.sh/uv/getting-started/installation/
Then run

uv sync --all-extras --all-groups
uv add mqt-qmap
uv sync --all-extras --all-groups

In ucc-bench, run

uv sync --all-groups

2. Create the following script

import os

from qbraid.transpiler import transpile as translate
from qiskit import transpile as qiskit_transpile

def random_clifford_circuit(num_qubits, seed=12345):
    """Generate a random clifford circuit
    Parameters:
        num_qubits (int): Number of qubits
        seed (int): Optional. Seed the random number generator, default=12345

    Returns:
        QuantumCircuit: Clifford circuit
    """
    # This code is used to generate the QASM file
    from qiskit.circuit.random import random_clifford_circuit

    gates = ["cx", "cz", "cy", "swap", "x", "y", "z", "s", "sdg", "h"]
    qc = random_clifford_circuit(
        num_qubits,
        gates=gates,
        num_gates=200 * num_qubits * num_qubits,
        seed=seed,
    )
    return qc



def write_qasm(
    circuit,
    circuit_name,
    version="2",
    basis_gates=[],
    folder="../qasm_circuits",
):
    qiskit_circuit = translate(circuit, "qiskit")
    if basis_gates:
        decomp_circuit = qiskit_transpile(
            qiskit_circuit, basis_gates=basis_gates, optimization_level=0
        )
    else:
        decomp_circuit = qiskit_circuit

    # Generate QASM string
    qasm_string = translate(decomp_circuit, "qasm" + version)

    # Get the absolute path of the current script
    script_dir = os.path.dirname(os.path.abspath(__file__))

    # Create the absolute path for the folder where QASM files will be saved
    abs_folder = os.path.abspath(os.path.join(script_dir, folder))

    # Construct the filename with the given circuit name and version
    filename = os.path.join(abs_folder, f"qasm{version}/ucc/{circuit_name}")

    # Append basis gates to the filename if they are provided
    if basis_gates:
        filename += f"_basis_{'_'.join(basis_gates)}"

    os.makedirs(os.path.dirname(filename), exist_ok=True)

    with open(filename + ".qasm", "w") as file:
        file.write(qasm_string)

circuit = random_clifford_circuit(10)
filename = f"random_clifford_circuit_N{10}"

write_qasm(circuit, circuit_name=filename, version="2")

Then run this uv run python <path-to-the-above-script>
Add the following content to benchmarks/scripts/run_benchmarks.py

from qiskit import QuantumCircuit
from qiskit.transpiler import PassManager, TransformationPass
from qiskit.converters import dag_to_circuit, circuit_to_dag
from qiskit.dagcircuit import DAGCircuit
from mqt import qmap

# Define the custom optimization pass
class QMAPCliffordOptimization(TransformationPass):
    def run(self, dag):
        circuit = dag_to_circuit(dag)
        circ_opt, results = qmap.optimize_clifford(circuit)
        dag_opt = circuit_to_dag(circ_opt)
        return dag_opt

# Function to count two-qubit gates
def count_gates(circuit: QuantumCircuit):
    return circuit.num_nonlocal_gates()

# Load your circuit from a QASM file
qasm_file = 'benchmarks/circuits/ucc/random_clifford_circuit_N10.qasm' # The path to the file
circuit = QuantumCircuit.from_qasm_file(qasm_file)

# Apply the optimization pass
pm = PassManager([QMAPCliffordOptimization()])
optimized_circuit = pm.run(circuit)  # Pass the QuantumCircuit directly

# Count gates before and after optimization
original_gate_count = count_gates(circuit)
optimized_gate_count = count_gates(optimized_circuit)

print(f"Original two-qubit gate count: {original_gate_count}")
print(f"Optimized two-qubit gate count: {optimized_gate_count}")

Run uv run python benchmarks/scripts/run_benchmarks.py
3. Gate counts should be printed, but the system is crashed.

[burgholzer]

Hey @gluonhiggs 👋🏼

Thanks for reaching out and for providing such detailed steps to replicate your issue.
If I understand it correctly, you are trying to synthesize a 10-qubit circuit with 20k gates.
This is far away from anything that can reasonably be synthesis by the optimal Clifford synthesis approach available in QMAP.
The underlying SAT encoding has 20k layers, each having O(n^2) variables and constraints.
The search space for Clifford synthesis grows as O(2^(n^2)). On a desktop computer that remains feasible for 5-6 qubits, but hardly any further; except for very shallow circuits.

So it's essentially a hardware limitation. After briefly thinking about it, I have a hard time to derive some a-priori analysis for whether a given circuit can still be encoded on a certain hardware platform. I'd be open for suggestions though.