arXiv:2610.03794 · SN Computer Science
Generalised Bit-Vector Abstractions for Formal Verification of Quantum Error-Detection and Entanglement Circuits over {H,X,C-NOT}: CSS Constructions, Soundness, and Mutation-Based Validation
Arun Govindankutty
Abstract
Formal verification of quantum circuits becomes difficult as circuit size grows because exhaustive reasoning over the Hilbert space is computationally expensive. In previous work [1], we introduced a bit-vector abstraction that separates superposition tracking from basis-state behavior, enabling SMT-based verification of fixed-size error-detection and entanglement circuits built from H, X, and C-NOT gates. This paper extends the framework in five directions. First, we generalise correctness properties to parametrised repetition and concatenated phase-flip codes with up to 101 logical elements. Second, we verify syndrome extraction for CSS codes specified by arbitrary parity-check matrices, including the Steane, [[15,7,3]] Hamming, [[15,1,3]] Reed-Muller, and rotated surface codes with distances up to 101. We consider arbitrary error patterns, detection up to a specified weight, and recovery using a classical decoder, with counterexamples beyond each code's correction or detection capability. Third, we characterize the {H,X,C-NOT} fragment for which the abstraction faithfully represents Hilbert-space semantics. We prove soundness, demonstrate necessity with counterexamples, validate the characterisation against state-vector simulation, and prove the six lemmas from the original work. Fourth, a mutation study using 13 operators identifies equivalent mutants and detects all 622 non-equivalent mutants within the evaluated fault model. Fifth, a direct Z3 implementation verifies GHZ circuits with up to 262,144 qubits across three topologies on a 16GB laptop. Random H+C-NOT networks show verification cost rises sharply with depth when outputs depend on many inputs. The approach does not target general stabilizer circuits, Y-type stabilizers, fault-tolerant protocols, or physical noise; we identify extensions needed to address these cases.
AI Summary
The paper asks when a compact bit-vector abstraction can support SMT-based verification of error-detection and entanglement circuits without tracking amplitudes. It extends an earlier encoding that separates computational-basis labels from Hadamard-count tags, with gate semantics for $H$, $X$, and CNOT, to parametrised repetition and concatenated phase-flip constructions, CSS syndrome extraction, and specified classical decoders followed by recovery. A syntactically defined circuit fragment restricts Hadamards to initial branch creation or paired frames containing only injected phase errors. An invariant-based proof establishes that the abstraction reproduces computational-basis support on this fragment, but not relative phases. Verification asserts the negated specification in Z3, covering all admissible symbolic inputs and error patterns. Repetition and block-level phase-flip circuits are checked through size 101; CSS examples include Steane, quantum Hamming, Reed–Muller, and rotated surface codes through distance 101, with 15,301 data-plus-ancilla qubits per extraction frame. Detection and recovery queries include counterexamples beyond specified capabilities. GHZ verification reaches 262,144 qubits across three topologies, requiring 9–13 seconds of solving; the largest star instance additionally takes about 46 seconds to build and 1.4 GiB peak memory. Differential simulation agrees on 12,000 circuits within the fragment, and mutation testing detects all 622 abstractly non-equivalent evaluated mutants. The stated scope excludes general stabilizer circuits, phase-sensitive properties, physical noise, faults during extraction, repeated syndrome rounds, and fault tolerance. Favourable scaling depends on sparse parity structure: dense random CNOT networks and weight-based decoder queries become substantially harder.
Central claim may not hold: The unrestricted soundness corollary is false because universally varying an abstract branch variable does not justify treating that variable as a fixed physical input in specifications or correlated preconditions. The assertion that all evaluated circuits belong to fragment F excludes some evaluated mutants, including an ancilla Hadamard immediately before measurement, so the soundness theorem does not cover every mutant. The Reed–Muller weight-2 bit-error recovery counterexample demonstrates failure of the chosen single-error lookup decoder, not the correction limit implied by the stated bit-error distance 7. The conclusion reports 120 mutants instead of 622 detected non-equivalent mutants and describes multiple-error recovery as future work despite its earlier implementation and evaluation.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.
- DOI
- 10.1007/s42979-026-05395-6
- Comments
- Accepted for publication in SN Computer Science, final version will be available through journal once published. Abstract is modified to account for arXiv character count