Skip to content
Open access

Generalised Bit-Vector Abstractions for Formal Verification of Quantum Error-Detection and Entanglement Circuits over \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \set

Oct 2026 · SN Computer Science · Vol 7 · 0 citations · 65 references
Physics Computer Science

TL;DR

A bit-vector abstraction that separates the tracking of superposition from basis-state behaviour is introduced, enabling SMT-based verification of fixed-size error-detection and entanglement circuits constructed from H, X, and C-NOT gates.

Abstract

Formal verification of quantum circuits becomes increasingly difficult as circuit size increases, since exhaustive reasoning over the underlying Hilbert space is computationally expensive. In previous work [1], we introduced a bit-vector abstraction that separates the tracking of superposition from basis-state behaviour, enabling SMT-based verification of fixed-size error-detection and entanglement circuits constructed from H, X, and C-NOT gates. This paper extends that framework in five directions. First, we generalise the 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 code, the [[15, 7, 3]] quantum Hamming code, the [[15, 1, 3]] quantum Reed–Muller code, and rotated surface codes with distances up to 101. The verification considers arbitrary error patterns, error detection up to a specified weight, and recovery using a classical decoder. Counterexamples are obtained for errors beyond the correction or detection capability of the respective codes. Third, we characterise the fragment of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\{H,X,\text {C-NOT}\}$$\end{document} circuits for which the abstraction faithfully represents the corresponding Hilbert-space semantics. We prove soundness for this fragment, demonstrate the necessity of the stated conditions through counterexamples, validate the characterisation by differential testing against state-vector simulation, and prove the six lemmas established in the original work. Fourth, we conduct a mutation study using 13 mutation operators and automatically identify equivalent mutants. Within the evaluated fault model, the approach detects all 622 non-equivalent mutants. Fifth, we implement the approach directly using the Z3 API and verify GHZ circuits with up to 262,144 qubits across three topologies on a 16 GB laptop. The evaluation includes repeated measurements and a controlled ablation of the encoding pipeline and solver version. Experiments with random H+C-NOT networks show that verification cost increases steeply with circuit depth when outputs depend on a large number of inputs. The approach is not intended to cover general stabiliser circuits, Y-type stabilisers, fault-tolerant protocols, or physical noise. We identify the extensions required to address these cases.

Read PDF

Similar papers

Sep 2026

Verifiable Quantum Advantage and Computation via Quantum Circuit Obfuscation

We construct protocols for classically verifiable quantum advantage and classical verification of $\mathsf{BQP}$ computations using \emph{quantum indistinguishability obfuscation} (qiO). Specifically, given qiO and assuming a slightly stronger version of $\mathsf{BQP}\neq\mathsf{BPP}$, we construct a two-message quantu...

Alexandru Gheorghiu, A. Gupte, Vojtěch Havlíček et al. · 0 citations
Preprint Nov 2026

Quantum Advantage with Sign-Free Proofs: An Oracle Separation between $\mathsf{StoqMA}$ and $\mathsf{MA}$

Several landmark oracle results (FOCS 2000, FOCS 2025, STOC 2026) establish strict separations along the chain $\mathsf{MA} \subseteq \mathsf{QCMA} \subseteq \mathsf{QMA}$, showing that quantum verification and quantum witnesses can each provide additional power over classical proof systems. These separations, however,...

Yassine Hamoudi, Y. Le Borgne, S. Sridhara · 0 citations
Preprint Oct 2026

Below-threshold execution of fault-tolerant ripple-carry addition on a trapped-ion quantum computer

We deploy a universal fault-tolerant quantum computing (FTQC) architecture based on error-detecting $[\![8,3,2]\!]$ and $[\![4,2,2]\!]$ codes on Quantinuum's Helios-1 trapped-ion quantum computer. We compile and execute ripple-carry adder (RCA) circuits for classical inputs up to five bits on this architecture. Uncompu...

Jacob S. Nelson, A. Landahl, A. Baczewski · 1 citation
Preprint Oct 2026

Logical-Space Theory of Ordered-Statistics Decoding for Quantum LDPC Codes

A framework guides OSD list construction and compression by identifying coverage requirements and distinguishing coverage losses from failures of representative selection, and separating absent-class from wrong-selection failures.

Yun Shang · 0 citations
#machine learning Preprint Oct 2026

Where Quantum Fourier Sampling Stops Short: A Three-Gate Audit Protocol for Delay-PUF Security Models

Quantum Fourier sampling may help audit the spectral learnability of delay-based physical unclonable functions (PUFs). We ask whether that promise survives access matching, a strong classical comparator, and oracle synthesis. Three gates structure the evaluation. Structure: low degree is not small support at reachable...

Owen Friedewald, Ali Shiri Sichani, Chi-Ren Shyu · 0 citations
Sep 2026

Towards Block-Level Fault-Tolerant Quantum Simulation on Small High-Rate Non-CSS Codes

The results demonstrate the potential of block-level logical constructions for non-CSS codes without rich native transversal gate sets and the joint protection of the parity network, analog rotation, and recovery required to preserve fault-tolerant distance.

Zhuang-Zhuang Chen, Narayanan Rengaswamy · 0 citations

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.