Abstract
We present a verifier of quantum programs called AutoQ 2.0. Quantum programs extend quantum circuits (the domain of AutoQ 1.0) by classical control flow constructs, which enable users to describe advanced quantum algorithms in a formal and precise manner. The extension is highly non-trivial, as we needed to tackle both theoretical challenges (such as the treatment of measurement, the normalization problem, and lifting techniques for verification of classical programs with loops to the quantum world), and engineering issues (such as extending the input format with a support for specifying loop invariants). We have successfully used AutoQ 2.0 to verify two types of advanced quantum programs that cannot be expressed using only quantum circuits: the repeat-until-success (RUS) algorithm and the weak-measurement-based version of Grover’s search algorithm. AutoQ 2.0 can efficiently verify all our benchmarks: all RUS algorithms were verified instantly and, for the weak-measurement-based version of Grover’s search, we were able to handle the case of 100 qubits in approximately 20 minutes.
Introduction
In the current landscape of quantum computing, there is a significant conceptual gap between a quantum circuit and a quantum program. While a circuit is a static, fixed sequence of gates, a program incorporates classical control flow—loops and conditional branches—often driven by the results of quantum measurements.
Verifying these programs is notoriously difficult due to two primary factors:
- State Collapse and Normalization: Measuring a qubit causes the quantum state to collapse. Mathematically, this often results in "non-normalized" states where probabilities do not sum to one, breaking standard verification tools that expect physical, normalized states.
- State Space Explosion: The complexity of quantum states grows exponentially with the number of qubits, making traditional deductive verification techniques (common in classical software) difficult to scale.
AutoQ 2.0 addresses these challenges by moving beyond static circuit verification to a full-fledged program verification framework.
Methodology
AutoQ 2.0 introduces several novel techniques to handle the complexities of quantum programs:
Level-Synchronized Tree Automata (LSTAs)
Instead of relying on massive, unwieldy matrices, AutoQ 2.0 represents quantum states using a specialized tree automata model. This approach allows for the compact encoding of quantum states and the efficient application of gate operations.
Entailment Testing "Up to Scaling"
A key innovation in AutoQ 2.0 is the "scaling-invariant" entailment test. Rather than performing computationally expensive normalization after every measurement, the tool checks if one quantum state is a linearly scaled version of another. This bypasses the normalization problem entirely, allowing the verifier to maintain logical consistency without the overhead of physical state correction.
Hoare-style Deductive Verification
The tool adopts the classic "Pre-condition, Loop Invariant, Post-condition" framework. By lifting classical logic to the quantum domain, AutoQ 2.0 uses the SMT solver Z3 to automatically prove that the program logic holds true against user-provided specifications.
Experimental Evaluation
The authors evaluated AutoQ 2.0 using advanced quantum algorithms that require classical control flow:
- Repeat-Until-Success (RUS) Algorithms: Used for synthesizing specific quantum gates (like the T-gate) by looping until a desired measurement outcome is achieved.
- Weakly Measured Grover’s Search: A variation of Grover's algorithm that uses measurement-based loops to eliminate the need for prior knowledge of the number of solutions.
- Scaling Benchmarks: The tool was tested on Grover's implementations ranging from 7 to 101 qubits.
Key Results
- Instant Verification: All Repeat-Until-Success (RUS) benchmarks were verified in 0.0 seconds.
- High Scalability: For the weakly measured Grover’s search, AutoQ 2.0 handled 101 qubits (involving nearly 850 gates) in approximately 11 seconds for the verification of the loop body.
- Efficiency: Even the most complex 100-qubit cases, representing a state space of $2^{100}$, were handled in roughly 20 minutes, demonstrating a significant leap in automated quantum verification.
Limitations and Future Work
While AutoQ 2.0 represents a major advancement, it still requires users to manually provide loop invariants, which remains a bottleneck in formal verification. Future iterations may explore automated invariant generation via symbolic execution. Additionally, the current model focuses on "pure" quantum states; extending the framework to "mixed states" (density matrices) will be essential for reasoning about noise and decoherence in real-world hardware.
Summary updated