arXiv:2509.26494 · v5

A parity obstruction to degree-optimal syndrome extraction in bivariate bicycle codes

首次提交 2025-10-01 00:36

版本更新 2026-11-03 16:07

雷达观测 2026-11-04 23:39

摘要

Syndrome extraction for a CSS code has depth at least the Tanner-graph degree $Δ$, attained by edge colouring if gate order is ignored; correctness adds a parity constraint. We prove three general obstructions to depth-$Δ$ extraction and show that, for every two-block group-algebra code with weight-three polynomials whose checks overlap in at most two qubits, no correct single-round circuit with one ancilla per check and one CNOT per Tanner edge has depth six: the minimum is seven, so the seven-layer cycle of Bravyi \emph{et al.} is optimal for their seven bivariate bicycle codes. This is the first analytic, family-wide impossibility result, extending prior instance-specific solver-based infeasibility results. The hypothesis cannot be dropped: a single orbit of four-qubit overlaps with a collision element of even order and $2$-height at most eight makes depth six attainable, and a $[[72,8,6]]$ code of this kind has a verified six-layer circuit. The refutations carry DRAT certificates. As a further application of the same scheduling scheme, we construct Stab-QRAM, a quantum random access memory for affine Boolean data that uses only CNOT and $X$ gates and has the minimum depth possible for this gate set.