Scalable Equivalence Checking and Verification of Shallow Quantum Circuits

Nengkun Yu, Xuan Du Trinh, Thomas Reps

TL;DR

This paper introduces a classical algorithm for verifying the equivalence of "shallow" (constant-depth) quantum circuits that scales linearly with the number of qubits. By representing quantum states as a set of local constraints rather than massive state vectors, the researchers can verify 100-qubit circuits in seconds—tasks that are impossible for traditional classical simulators.

What Problem Does This Paper Address?

Verifying quantum software is a massive bottleneck. To ensure a compiler hasn't broken a program during optimization, we need equivalence checking: proving that two different circuits produce the same output.

The fundamental challenge is the "exponential wall." A quantum state for $n$ qubits requires $2^n$ complex numbers to describe fully. For 100 qubits, this is more than the number of atoms in the observable universe. While some specific classes of circuits (like Clifford circuits) can be simulated efficiently, general shallow circuits—which are critical for the current Noisy Intermediate-Scale Quantum (NISQ) era—are often classically intractable to simulate, yet they still need to be verified.

Methods

The authors move away from explicit simulation (calculating the state) and toward constraint-based characterization.

  • Local Projections: The core idea is that a shallow circuit’s output state is uniquely defined by a set of "local projections." These are mathematical constraints that only look at a small, constant number of qubits at a time.
  • The "Light Cone" Approach: Because the circuits are shallow, information from any single gate can only spread to a limited number of nearby qubits. The algorithm tracks these "light cones" to generate a tuple of local projections that serve as an exact specification of the output state.
  • Identity Reduction: To check if two circuits $U_1$ and $U_2$ are equivalent, the authors check if the composite circuit $U_1^\dagger U_2$ acts as the identity (mapping the $|0\rangle$ state back to itself).
  • Choi States: To prove "strong equivalence" (equivalence for any possible input state), they use a technique involving Choi states, which effectively reduces the problem to checking a single fixed input on a larger (but still shallow) circuit.

Datasets

The authors evaluated their method using:

  • Haar Random Circuits: Randomly generated circuits with 2-qubit gates, varying from 10 to 200 qubits and depths 1 to 7.
  • 1D and 2D Architectures: Testing how qubit geometry affects performance.
  • Micro-benchmarks: Specific functional tests including the Deutsch gate (a 3-qubit controlled-controlled-U gate) and a specific 3-qubit gate implementation from prior literature.

Key Insights and Ideas

  • Verification $\neq$ Simulation: You don't need to know every amplitude in a quantum state to know if it's the correct state. By focusing on local properties that uniquely identify the state, the authors bypass the exponential memory requirements of state-vector simulation.
  • Fixed-Parameter Tractability: The algorithm's complexity is $O(f(d) \cdot n)$. While it is exponential in the circuit depth ($d$), it is linear in the number of qubits ($n$). For the "shallow" circuits used in NISQ devices where $d$ is small and constant, this makes the approach incredibly scalable.
  • Commuting Constraints: The generated local projections naturally commute. This is a "free" benefit that makes the constraints much easier to implement as physical measurements on actual quantum hardware for runtime debugging.

Key Results

  • Linear Scalability: On a standard server, the tool computed the constraint representation of a 100-qubit circuit (depth 6) in just 19.8 seconds.
  • Speedup over Simulation: Traditional state-vector simulators (like Qiskit Aer) hit a memory wall at around 30–34 qubits. The proposed method handled 200 qubits with ease, maintaining a linear time increase.
  • Equivalence Checking: For 100-qubit circuits at depth 3, weak equivalence (fixed input) took ~4.5 seconds, while strong equivalence (all inputs) took ~32 seconds.
  • High Precision: Despite using classical floating-point math, the "Averaged Error" remained miniscule (around $10^{-15}$), showing the method is numerically robust.

Limitations and Future Work

  • The Depth Limit: The "exponential in depth" nature means this tool cannot verify "deep" circuits like those used for Shor’s factoring algorithm. It is strictly optimized for shallow, NISQ-style computations.
  • Gate Complexity: The current implementation focuses on 2-qubit gates. While the theory supports $k$-qubit gates, the computational cost grows rapidly as the number of qubits per gate increases.
  • Future Directions: The authors suggest combining this method with Quantum Abstract Interpretation (QAI) to handle deeper circuits by partitioning them. They also aim to extend the logic to handle measurements, loops, and noisy environments.

Summary updated

Abstract

This paper concerns the problem of checking whether two shallow (i.e., constant-depth) quantum circuits perform equivalent computations. Equivalence checking is a fundamental correctness question—needed, for example, to ensure that transformations applied to a quantum circuit do not alter its behavior. For quantum circuits, the problem is challenging because a straightforward representation on a classical computer of each circuit’s quantum state can require time and space that are exponential in the number of qubits n . The paper presents Projection-Based Equivalence Checking (PBEC), which provides decision procedures for two variants of the equivalence-checking problem. Both can be carried out on a classical computer in time and space that, for any fixed depth, are linear in n . Our key insight is that local projections can serve as constraints that fully characterize the output state of a shallow quantum circuit. The output state is the unique quantum state that satisfies all the constraints. Beyond equivalence checking, we show how to use the constraint representation to check a class of assertions, both statically and at run time. Our assertion-checking methods are sound and complete for assertions expressed as conjunctions of local projections. Our experiments showed that computing the constraint representation of a random 100-qubit 1D circuit of depth 6 takes 129.64 seconds. Equivalence checking between two random 100-qubit 1D circuits of depth 3 requires 4.46 seconds for fixed input 0 ⊗ 100 , and no more than 31.96 seconds for arbitrary inputs. Computing the constraint representation for a random 100-qubit circuit of depth 3 takes 6.99 seconds for a 2D structure, compared to 10.67 seconds for a circuit with arbitrary connectivity. At depth 2, equivalence checking takes 0.20 seconds for fixed input and 0.44 seconds for arbitrary input, with similar performance for both 2D and arbitrary-connectivity circuits.
BibTeX
@inproceedings{yu2025scalable,
  author = {Nengkun Yu and Xuan Du Trinh and Thomas Reps},
  title = {{Scalable Equivalence Checking and Verification of Shallow Quantum Circuits}},
  booktitle = {Proceedings of the ACM on Programming Languages},
  year = {2025},
  doi = {10.1145/3763153},
}

Loading related content...

Figure