⚛️ quantum physics

Validating Quantum State Preparation Programs (Extended Version)

This paper introduces Pqasm, a high-assurance framework implemented in Coq that validates quantum state preparation programs by reducing their correctness to non-superposition states, thereby enabling effective property-based testing on classical computers for algorithms that are otherwise beyond the reach of current quantum simulators.

Original authors: Liyi Li, Anshu Sharma, Zoukarneini Difaizi Tagba, Sean Frett, Alex Potanin

Published 2026-02-24

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Liyi Li, Anshu Sharma, Zoukarneini Difaizi Tagba, Sean Frett, Alex Potanin

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to bake a very complex, magical cake. This isn't just any cake; it's a Quantum Cake.

In the world of quantum computing, the "ingredients" aren't flour and sugar; they are qubits (quantum bits). Unlike regular bits that are either 0 or 1 (like a light switch being off or on), a qubit can be in a superposition—a magical state where it is both 0 and 1 at the same time, like a spinning coin that is neither heads nor tails until you catch it.

The problem? Writing the recipe (the program) for this cake is incredibly hard. If you make a tiny mistake in the recipe, the whole cake collapses into a mess. And because quantum computers are expensive and rare, you can't just bake it a thousand times to see if it works. You need to be sure the recipe is perfect before you ever step foot in the kitchen.

This is where the paper introduces QSV (Quantum State Validation). Think of QSV as a Super-Inspector that lives on your regular computer and checks your quantum recipe before you try to bake it.

The Core Problem: The "Exponential Explosion"

Imagine you have a deck of cards. If you have 1 card, there are 2 possibilities (Heads or Tails). If you have 2 cards, there are 4 possibilities. If you have 60 cards, there are more possibilities than there are atoms in the universe.

This is the "Exponential Explosion." A quantum program with 60 qubits has $2^{60}$ different states happening at once. Trying to check every single one of those states on a normal computer is impossible. It would take longer than the age of the universe.

The QSV Solution: The "One-Card" Trick

The authors of this paper came up with a clever trick to solve this. They realized that even though the quantum cake has $2^{60}$ layers, the recipe usually starts with a very simple step: shuffling the deck (applying Hadamard gates) to create a uniform mix of all possibilities.

Instead of trying to check the whole $2^{60}$ -layer cake at once, QSV says:

"Let's pretend we only have one single card from that deck. Let's see if our recipe works correctly for this one card. If it works for this one, and the recipe is consistent, it will work for all of them."

They call this determinizing the program. They turn a probabilistic, magical quantum problem into a simple, logical puzzle that a regular computer can solve instantly.

How QSV Works (The Analogy)

The Language (PQASM):
Imagine you are writing a recipe in a language that only chefs understand. The authors created a new language called PQASM. It's like a high-level cooking language where you say "Mix the batter" instead of "Rotate the whisk 45 degrees clockwise." It hides the scary, low-level math so programmers can focus on the big picture.
The Inspector (QuickChick):
Once you write your recipe in PQASM, QSV uses a tool called QuickChick. Think of QuickChick as a robot taste-tester.
- It doesn't bake the whole cake.
- Instead, it grabs a random "slice" (a single basis state) from the theoretical deck of cards.
- It runs your recipe on that single slice.
- It checks: "Did the slice turn out the way the recipe promised?"
- It does this 10,000 times with different random slices in a few seconds.
If the robot finds a mistake even once, it yells, "Your recipe is broken!" If it runs 10,000 tests and they all pass, you can be 99.9% sure your recipe is perfect.
The Compiler:
Once the recipe passes the robot's inspection, QSV translates it into a real, physical set of instructions (a quantum circuit) that can be sent to a real quantum computer.

Why This is a Big Deal

The paper tested QSV on some of the most difficult quantum recipes ever written, including ones that require 60 qubits.

Old Way: If you tried to simulate these recipes on a normal computer to check them, your computer would crash, or it would take years.
QSV Way: The robot taste-tester checked these massive recipes in less than 5 minutes.

The Real-World Impact

The authors didn't just build a tool; they used it to find bugs in existing famous quantum algorithms.

They found that some famous algorithms for finding "distinct elements" (like finding unique items in a giant list) had a hidden flaw: the initial "mixing" step was so inefficient that the algorithm might never actually work in practice.
Without QSV, no one would have known this because the recipes were too complex to check manually.

Summary

QSV is like a spell-checker for quantum magic.
Before, writing quantum code was like trying to write a novel in a language you don't speak, without a dictionary, and hoping you don't accidentally summon a demon.
With QSV, you write your story in a simple language, and a super-smart robot reads a few random pages to ensure the story makes sense. If it passes, you can be confident that when you finally run the story on a real quantum computer, it will work perfectly.

This tool bridges the gap between the impossible math of quantum physics and the practical reality of writing software, making quantum computing safer and more accessible for everyone.

1. Problem Statement

Quantum algorithms rely heavily on the preparation of specific initial quantum superposition states. However, developing and validating these state preparation programs is notoriously difficult due to several factors:

Exponential State Space: A quantum state with $m$ qubits involves $2^m$ basis vectors. Simulating or testing these states on classical computers requires exponential resources, making direct verification impossible for large-scale programs (e.g., 60+ qubits).
Probabilistic Nature: Quantum measurements are probabilistic, requiring repeated trials to validate correctness, which is expensive on actual hardware and difficult to simulate classically.
Lack of Tools: Existing frameworks (like Qiskit) lack high-level abstractions for state preparation and property-based testing (PBT) capabilities. They often fail to simulate large circuits or provide tools to verify program logic before execution.
Complexity of Patterns: Many algorithms use complex patterns like "repeat-until-success" loops or intricate arithmetic oracles, which are unintuitive to write in circuit-based languages and hard to debug.

2. Methodology: The QSV Framework

The authors propose QSV (Quantum State Preparation Program Validation), a high-assurance framework implemented in the Rocq proof assistant (formerly Coq). The core methodology involves reducing the validation of a complex superposition state to the validation of individual basis-ket transitions.

A. Language Design: PQASM

The framework introduces PQASM (Preparation Quantum Assembly Language), an extension of OQASM.

High-Level Abstraction: PQASM allows users to define state preparation programs using high-level constructs like quantum oracles, arithmetic operations, and control flow, abstracting away low-level gate details.
Type System: A novel type system tracks qubit states, classifying them into three types:
- Had: Qubits in a superposition state (source of superposition).
- Nor: Qubits in the computational basis (standard $|0\rangle$ or $|1\rangle$ ).
- Rot: Qubits in a rotated basis (e.g., $Y$ -rotated).
No-Cloning Enforcement: The type system enforces the "no-cloning" theorem by ensuring control qubits are distinct from target qubits in controlled operations.

B. Validation Strategy: Property-Based Testing (PBT)

QSV utilizes QuickChick (a property-based testing tool for Rocq) to validate programs. The key innovation is the determinization of superposition:

Reduction to Basis-Kets: Instead of simulating the entire superposition, QSV treats the initial Hadamard operations as a source of random inputs. It selects a single representative basis-ket (a specific bitstring $j$ ) from the superposition.
Transition Validation: The validator checks if the program correctly transforms this single basis-ket $|j\rangle$ to the expected output state.
Property Transformation: Global properties (e.g., "the output is a uniform superposition of $n$ $n$ states") are transformed into universal quantification over individual basis-kets:
- Global: $\sum z_j |j\rangle \to \sum g(z_j |j\rangle)$
- Local (Validated): $\forall j, z_j |j\rangle \to g'(z_j |j\rangle)$
Repeat-Until-Success Handling: For probabilistic programs, QSV validates a single loop iteration. It calculates the success probability based on the ratio of valid basis-kets to total possible basis-kets, rather than simulating the full probabilistic loop.

C. Certified Compilation

QSV includes a certified compiler that translates PQASM programs to SQIR (a quantum circuit language in Rocq) and subsequently to OpenQASM. The translation correctness is formally proven, ensuring that the validated high-level program behavior is preserved in the generated quantum circuit.

3. Key Contributions

QSV Framework: A complete ecosystem for developing, validating, and compiling quantum state preparation programs on classical computers.
PQASM Language: A typed language with a sound type system that enforces quantum constraints (like no-cloning) and facilitates the identification of superposition sources.
Reduction Technique: A novel method to reduce the verification of exponential superposition states to the testing of polynomial-sized basis-ket transitions using property-based testing.
Formal Guarantees: Mechanized proofs in Rocq for type soundness (progress and preservation) and compiler correctness.
Case Studies: Implementation and validation of five complex state preparation programs:
- $n$ -basis-ket superposition.
- Modular Exponentiation (core of Shor's algorithm).
- Amplitude Amplification.
- Hamming Weight superposition.
- Distinct Element superposition.

4. Results and Evaluation

The authors evaluated QSV against state-of-the-art simulators (Qiskit, DDSim) and compared performance on programs ranging from 8 to 60 qubits.

Scalability:
- QSV: Successfully validated programs with up to 361 qubits (Distinct Element case) and 60-qubit registers within seconds to minutes.
- Qiskit/DDSim: Failed to execute or simulate the 60-qubit versions of these programs (often running out of memory or taking hours/days without completion).
Efficiency:
- Running 10,000 random test cases for 60-qubit programs took less than 5.5 minutes in QSV.
- In contrast, Qiskit could not even run a single test for many of the large-scale cases.
Bug Detection: The framework successfully identified bugs in original algorithm implementations (e.g., in the Distinct Element and Hamming Weight algorithms) and caught injected faults via mutation testing.
Utility: The framework revealed that the initial state preparation for certain algorithms (like Distinct Element) has a very low success probability, casting doubt on the practical advantage of those algorithms without optimized state preparation.

5. Significance

Bridging the Gap: QSV addresses the critical gap between high-level quantum algorithm design and low-level circuit implementation, providing a toolchain that works on classical hardware for large-scale problems.
Shift in Verification Paradigm: By moving from "simulating the whole state" to "validating basis-ket transitions," the authors overcome the exponential barrier that has historically prevented the testing of large quantum programs.
Foundation for Future Tools: The work establishes a blueprint for future quantum validation frameworks, demonstrating that property-based testing combined with formal type systems is a viable path for ensuring the correctness of quantum software before it is deployed on expensive quantum hardware.
Algorithmic Insight: The framework's ability to analyze success probabilities of state preparation has already provided new insights into the feasibility of specific quantum algorithms, suggesting that some proposed algorithms may be less efficient than theoretically assumed due to poor initialization strategies.

In conclusion, this paper presents a robust, formally verified framework that enables the development and rigorous testing of complex quantum state preparation programs, solving a problem previously considered intractable on classical computers.