Low-depth syndrome extraction for Calderbank-Shor-Steane (CSS) quantum low-density parity-check codes can be formulated as a proper ordered edge-coloring problem subject to quantum parity constraints. A proper edge-coloring of the CSS Tanner graph ensures that each data or ancilla qubit participates in at most one two-qubit gate per layer, but does not guarantee a valid interleaving of the X- and Z-check measurements as for every overlapping X/Z check pair, the number of shared data qubits on which the X interaction precedes the Z interaction must be even. The minimum number of colors in a proper ordered edge-coloring satisfying the quantum parity constraints equals the minimum two-qubit depth when each stabilizer check is measured with a single ancilla.
We introduce local automorphism-aware syndrome compilation (LocalASC), which reduces the constraint system to edge-orbit variables under a subgroup of the Tanner graph automorphisms and lifts each feasible orbit assignment to the full graph. Although the 6-layer degree lower bound is unattainable for the published weight-6 IBM bivariate bicycle codes, we show that this is not universal among two-block CSS codes. Among code instances for which the maximum check weight equals the maximum Tanner graph degree, LocalASC finds depth-optimal syndrome-extraction schedules for several two-block CSS codes with odd component weights, including instances with unequal odd weights. We also obtain lower-bound-saturating syndrome-extraction schedules for several quantum Tanner codes satisfying the same degree condition. To obtain the subgroups used by LocalASC without computing the full automorphism group of the Tanner graph, we construct translation subgroups for two-block group-algebra CSS codes over abelian groups. For quantum Tanner codes, we give conditions under which square-complex symmetries extend to Tanner graph automorphisms.
This work shows that minimizing the depth of a quantum circuit composed of commuting operations reduces to a vertex coloring problem on an appropriately constructed graph, where gates correspond to vertices and edges encode non-parallelizability. The reduction leads to algorithms for circuit optimization by adopting any vertex coloring solver as an optimization backend. The approach is validated by numerical experiments as well as applications to known quantum circuits, including finite field multiplication and QFT-based addition.
Testing and verifying imperfect multi-qubit quantum devices are important as such noisy quantum devices are widely available today. Bell inequalities are known to be useful for testing and verifying the quality of the quantum devices from their nonlocal quantum states and local measurements. There have been many experiments demonstrating the violations of Bell inequalities, but they are limited in the number of qubits and the types of quantum states. We report violations of Bell inequalities on IBM Quantum devices based on the scalable and robust inequalities maximally violated by graph states as proposed by Baccari et al.. The violations are obtained from the quantum states of path graphs up to 57 and 21 qubits on a 65-qubit and two 27-qubit IBM Quantum devices, respectively, and from those of star graphs up to 11 qubits with quantum readout error mitigation (QREM). We are able to show violations of the inequalities on various graph states by constructing low-depth quantum circuits and by applying the QREM technique. We also point out that quantum circuits for star graph states of sizeNcan be realized with circuits of depthO(N)on subdivided honeycomb lattices which are the topology of the 65-qubit IBM Quantum device. Our experiments show encouraging results on the ability of existing quantum devices to prepare entangled quantum states and provide experimental evidence on the benefit of scalable Bell inequalities for testing them.