Verifiable Quantum Advantage and Computation via Quantum Circuit Obfuscation
Abstract
We construct protocols for classically verifiable quantum advantage and classical verification of BQP computations using \emph{quantum indistinguishability obfuscation} (qiO). Specifically, given qiO and assuming a slightly stronger version of BQP≠BPP, we construct a two-message quantum-advantage protocol that is efficiently and publicly verifiable. Our result can be viewed as a rigorous cryptographic foundation for the heuristic quantum advantage proposals based on \emph{peaked random circuit sampling} of Aaronson and Zhang (arXiv:2404.14493). We also construct two simple protocols for classically verifying arbitrary BQP computations. The first protocol is privately verifiable and assumes only the existence of qiO. This gives a rare example of a nontrivial cryptographic application of (quantum) iO that does not make additional computational hardness assumptions. The second protocol additionally assumes post-quantum one-way functions and is \emph{publicly verifiable}. To our knowledge, this is the first publicly verifiable protocol for classical verification of BQP computations under computational assumptions in the standard model. As qiO is the basis for our results, we propose an approach to constructing qiO by adapting the local-mixing framework of Canetti--Chamon--Mucciolo--Ruckenstein.
Related
- Verifiable quantum advantage in extremely low depth
- Towards verifiable quantum advantage with random circuits: Observables that survive concentration
- Verifiable quantum advantage based on polynomials with planted structures
- Quantum computational advantage in random-circuit sampling on IBM superconducting quantum computers
- Parallel Circuit Execution for Scalable Quantum Computation
BibTeX
@misc{gheorghiu2026verifiable,
title = {{Verifiable Quantum Advantage and Computation via Quantum Circuit Obfuscation}},
author = {Alexandru Gheorghiu and Aparna Gupte and Vojtěch Havlíček and Yunchao Liu},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2609.40289},
eprint = {2609.40289},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.40289},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Verifiable Quantum Advantage and Computation via Quantum Circuit Obfuscation
AU - Alexandru Gheorghiu
AU - Aparna Gupte
AU - Vojtěch Havlíček
AU - Yunchao Liu
PY - 2026
DA - 2026/10/02
PB - arXiv
DO - 10.48550/arxiv.2609.40289
UR - https://arxiv.org/abs/2609.40289
AB - We construct protocols for classically verifiable quantum advantage and classical verification of BQP computations using \emph{quantum indistinguishability obfuscation} (qiO). Specifically, given qiO and assuming a slightly stronger version of BQP≠BPP, we construct a two-message quantum-advantage protocol that is efficiently and publicly verifiable. Our result can be viewed as a rigorous cryptographic foundation for the heuristic quantum advantage proposals based on \emph{peaked random circuit sampling} of Aaronson and Zhang (arXiv:2404.14493). We also construct two simple protocols for classically verifying arbitrary BQP computations. The first protocol is privately verifiable and assumes only the existence of qiO. This gives a rare example of a nontrivial cryptographic application of (quantum) iO that does not make additional computational hardness assumptions. The second protocol additionally assumes post-quantum one-way functions and is \emph{publicly verifiable}. To our knowledge, this is the first publicly verifiable protocol for classical verification of BQP computations under computational assumptions in the standard model. As qiO is the basis for our results, we propose an approach to constructing qiO by adapting the local-mixing framework of Canetti--Chamon--Mucciolo--Ruckenstein.
ER -