`compile_cnot_circuit` can error or return wrong output on processors with restricted connectivity

[rileyjmurray]

The connectivity-adjusted CNOT compiler algorithms COiCAGE and OiCAGE are used by compile_cnot_circuit, and indirectly by compile_conditional_symplectic / compile_stabilizer_state / compile_clifford.

These algorithms frequently produce CNOT circuits whose symplectic representation does not match the requested s when compiling for a device with restricted connectivity (line/ring/grid). The error surfaces if the caller passes check=True (which is the default!), which raises AssertionError: Algorithm has failed!. If check=False, then the algorithm silently returns a wrong circuit.

Impact

• The DirectRB.ipynb example notebook errors.
• Any code path that calls compile_cnot_circuit/compile_conditional_symplectic with check=False on restricted geometry can silently get an incorrect circuit.

Reproduction

4-qubit ring, 300 random CNOT circuits, counting how many compiled outputs are wrong (caught by check=True):

import numpy as np
from pygsti.algorithms import compilers
from pygsti.processors import QubitProcessorSpec as QPS
from pygsti.tools import symplectic
from pygsti.circuits import Circuit
from pygsti.baseobjs import Label

ql = ['Q0', 'Q1', 'Q2', 'Q3']
ring = QPS(4, ['Gxpi2', 'Gxmpi2', 'Gypi2', 'Gympi2', 'Gcphase'], qubit_labels=ql, geometry='ring')
rng = np.random.RandomState(0)

def random_cnot_sym(nlayers=12):
    layers = [Label('CNOT', tuple(ql[i] for i in rng.choice(4, size=2, replace=False)))
              for _ in range(nlayers)]
    s, _ = symplectic.symplectic_rep_of_clifford_circuit(
        Circuit(layer_labels=layers, line_labels=ql).parallelize())
    return s

for alg in ['COiCAGE', 'OiCAGE', 'BGE']:
    fails, rng2 = 0, np.random.RandomState(0)
    for _ in range(300):
        s = random_cnot_sym()
        aargs = [ql] if alg == 'OiCAGE' else []
        try:
            compilers.compile_cnot_circuit(s, ring, compilation=None, qubit_labels=ql,
                                           algorithm=alg, compile_to_native=False,
                                           check=True, aargs=aargs, rand_state=rng2)
        except AssertionError:
            fails += 1
    print(alg, fails, "/ 300")

Observed:

COiCAGE  217 / 300   (72.3% wrong)
OiCAGE   130 / 300   (43.3% wrong)
BGE        0 / 300   (correct)

Notes / pointers

• The bug lives in _compile_cnot_circuit_using_oicage_algorithm (and the COiCAGE ordering wrapper) in pygsti/algorithms/compilers.py.
• Environment: pyGSTi builds-and-notebooks branch, Python 3.13.
• I'm getting DirectRB.ipynb to run correctly by adding a fallback to basic Gaussian elimination (BGE) when the COiCAGE output fails verification in compile_conditional_symplectic.