Scalable Equivalence Checking and Verification of Shallow Quantum Circuits

Nengkun Yu, Xuan Du Trinh, Thomas Reps

Abstract

This paper concerns the problem of checking if two shallow (i.e., constant-depth) quantum circuits perform equivalent computations. Equivalence checking is a fundamental correctness question -- needed, e.g., for ensuring 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 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, is linear in $n$. Our critical insight is that local projections are precise enough to completely characterize the output state of a shallow quantum circuit. Instead of explicitly computing the output state of a circuit, we generate a set of local projections that serve as constraints on the output state. Moreover, the circuit's 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 show that on a server equipped with 2 x Intel® Xeon® Gold 6338 CPUs (128 threads total) and 1.0 TiB of RAM, running Ubuntu 20.04.6 LTS, the constraint representation of a random 100-qubit circuit of depth 6 can be computed in 19.8 seconds. For fixed inputs $|0\rangle^{\otimes 100}$, equivalence checking of random 100-qubit circuits of depth 3 takes 4.46 seconds; for arbitrary inputs, it takes no more than 31.96 seconds.

Introduction

As quantum computing moves into the Noisy Intermediate-Scale Quantum (NISQ) era, the complexity of quantum software increases, making verification a critical bottleneck. A primary challenge is equivalence checking: proving that two different quantum circuits (for instance, an original program and its optimized version) produce the same output.

Traditional classical simulation methods face an "exponential wall," where representing an $n$-qubit state requires $2^n$ complex numbers. This makes verifying even moderately sized circuits (e.g., 50-100 qubits) impossible for standard state-vector simulators. This paper introduces a scalable alternative for "shallow" or constant-depth circuits by moving away from explicit simulation and toward a constraint-based characterization.

Methodology: Constraint-Based Characterization

The authors propose that a shallow circuit's output state can be uniquely identified by a set of local projections. These are mathematical constraints that focus on a small, constant number of qubits at a time.

The Light Cone Approach

The efficiency of this method relies on the "light cone" property of shallow circuits. Because the depth $d$ is constant, the influence of any single gate can only spread to a limited number of nearby qubits. By tracking these localized interactions, the algorithm generates a tuple of local projections that serve as an exact specification of the output state. This bypasses the need to store the entire state vector, reducing the memory requirement significantly.

Equivalence Checking Strategies

The paper addresses two types of equivalence:

  1. Weak Equivalence: Proving two circuits produce the same output for a specific fixed input (usually $|0\rangle^{\otimes n}$). This is verified by checking if the composite circuit $U_1^\dagger U_2$ acts as the identity.
  2. Strong Equivalence: Proving equivalence for any possible input state. The authors utilize Choi states to reduce this problem to checking a single fixed input on a larger, yet still shallow, circuit.

Experimental Results

The methodology was evaluated using Haar random circuits and various qubit geometries (1D and 2D architectures).

Linear Scalability

Unlike traditional simulators that hit a memory wall at approximately 30–34 qubits, this constraint-based approach demonstrates linear scalability ($O(n)$) for a fixed depth. On a standard server, the tool characterized a 100-qubit circuit at depth 6 in just 19.8 seconds. For 100-qubit circuits at depth 3, weak equivalence was verified in 4.46 seconds, while strong equivalence was confirmed in under 32 seconds.

Numerical Precision

Despite relying on classical floating-point calculations, the method proved highly robust. The averaged error remained near $10^{-15}$, demonstrating that the local projection approach does not sacrifice accuracy for speed.

Applications: Quantum Assertions

Beyond equivalence checking, the constraint representation enables a robust system for quantum assertions. These assertions, expressed as conjunctions of local projections, can be checked statically during the development process or at runtime. Because the generated constraints naturally commute, they can be implemented as physical measurements on actual quantum hardware to debug programs in real-time.

Limitations and Future Work

The primary limitation of this approach is its exponential growth with respect to circuit depth ($d$). While highly effective for shallow NISQ circuits, it is not yet suitable for "deep" algorithms like Shor’s factoring algorithm. Future research directions include combining this method with Quantum Abstract Interpretation (QAI) to handle deeper circuits via partitioning and extending the framework to support noisy environments and circuits with measurement loops.

Summary updated

Abstract

This paper concerns the problem of checking if two shallow (i.e., constant-depth) quantum circuits perform equivalent computations. Equivalence checking is a fundamental correctness question -- needed, e.g., for ensuring 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 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, is linear in $n$. Our critical insight is that local projections are precise enough to completely characterize the output state of a shallow quantum circuit. Instead of explicitly computing the output state of a circuit, we generate a set of local projections that serve as constraints on the output state. Moreover, the circuit's 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 show that on a server equipped with 2 x Intel\textsuperscript{\textregistered} Xeon\textsuperscript{\textregistered} Gold 6338 CPUs (128 threads total) and 1.0~TiB of RAM, running Ubuntu 20.04.6 LTS, the constraint representation of a random 100-qubit circuit of depth 6 can be computed in 19.8 seconds. For fixed inputs $\ket{0}^{\otimes 100}$, equivalence checking of {random} 100-qubit circuits of depth 3 takes 4.46 seconds; for arbitrary inputs, it takes no more than 31.96 seconds.
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},
}
Figure