Scalable Verification for Quantum Advantage

This direction is split into other directions: mirror circuit verification, quantum verification gap. Its last version stays readable and citable here.

Version 1 of 1153 papers202 conceptsfrozen 2026-10-04

The defining promise of quantum computing is "quantum advantage"—the moment a quantum processor performs a task that would take a classical supercomputer thousands of years. However, this milestone carries a fundamental paradox: if a classical computer cannot simulate the quantum device, how can we possibly verify that the quantum device is telling the truth?

As researchers like Scott Aaronson and Alex Arkhipov noted in their seminal work on BosonSampling, the very complexity that makes quantum systems powerful also makes them uncheckable. This "verification bottleneck" means that as we scale from dozens to hundreds of qubits, we risk building "black boxes" whose outputs we must take on faith.

The Classical Simulation Bottleneck

To understand why verification is hard, we must look at the state space. A quantum system with $n$ qubits requires $2^n$ complex numbers to describe its state. For 50 qubits, this is roughly $10^{15}$ numbers—the limit of today's largest supercomputers. When processors like Zuchongzhi reach 66 qubits, the state space expands to a regime where full classical simulation is computationally intractable.

Traditional benchmarking relies on "cross-entropy benchmarking" (XEB), which compares the quantum output to a classically calculated ideal distribution. But as Timothy Proctor and Jordan Hines argue, this approach hits a "complexity ceiling." Once we pass the point of quantum advantage, the "ground truth" disappears.

Mirroring: Verification Without Simulation

One of the most elegant solutions to this paradox is Mirror Randomized Benchmarking (MRB). Developed by researchers including Timothy Proctor, Stefan Seritan, and Kevin Young, this technique bypasses the need for supercomputers by designing circuits that "undo" themselves.

In a mirror circuit, a sequence of random quantum gates is followed by its mathematical inverse. If the hardware were perfect, the final state would always return to the starting state (e.g., all zeros). By measuring how often the device fails to return to zero, researchers can estimate the fidelity of the computation without ever needing to simulate the complex intermediate quantum states. This allows for the benchmarking of hundreds of qubits simultaneously, revealing errors like "crosstalk" that traditional methods miss.

Cryptographic Anchors and Interactive Proofs

While mirroring checks if a device is consistent, it doesn't necessarily prove it is performing a specific hard task. To solve this, researchers are turning to "interactive proofs of quantumness."

Daiwei Zhu and Gregory D. Kahanamoku–Meyer demonstrated experimental protocols where a classical verifier "challenges" a quantum prover. These protocols often rely on the Learning With Errors (LWE) assumption—a mathematical problem that is easy for a quantum computer to solve but hard for a classical one.

By using classical commitments to quantum states, as proposed by Sam Gunn and Yael Kalai, we can "lock" a quantum device into a specific state using only classical communication. This creates a "succinct" verification: the classical computer's effort remains small even as the quantum state it is verifying becomes massive.

From Random Noise to Structured Utility

The final frontier of verification is moving from random sampling (which is easy to verify but hard to use) to structured algorithms (which are useful but hard to verify). Timothy Proctor has shown that structured programs fail much faster than randomized ones, meaning our current error metrics are often too optimistic.

To bridge this gap, Stefan Seritan introduced Subcircuit Volumetric Benchmarking (SVB). Instead of trying to verify an entire "impossible" circuit, SVB "snips" and tests small subcircuits from a target algorithm. By measuring the performance of these manageable pieces, we can statistically infer whether the full-scale machine is capable of achieving "quantum utility" for real-world problems.

Through these combined efforts—mirroring, cryptographic proofs, and subcircuit analysis—the field is moving toward a regime where we can trust the answers of machines that we can no longer simulate.

Papers in this version

Showing 60 of 153 papers.

History & citationVersion 1 · 2026-10-04

Split into other directions · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_scalable_verification_for_quantum_advant_c69cc29b,
  title = {Scalable Verification for Quantum Advantage},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/scalable-verification-for-quantum-advantage/rdr_c69cc29b58084dff8cdab6edc8c253ac},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-21},
}

This exact version (version 1, frozen text):

@misc{lacuna_scalable_verification_for_quantum_advant_c69cc29b_v1,
  title = {Scalable Verification for Quantum Advantage},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/scalable-verification-for-quantum-advantage/rdr_c69cc29b58084dff8cdab6edc8c253ac/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-21},
}