arXiv:2609.40289
Verifiable Quantum Advantage and Computation via Quantum Circuit Obfuscation
Alexandru Gheorghiu, Aparna Gupte, Vojtěch Havlíček, Yunchao Liu
Abstract
We construct protocols for classically verifiable quantum advantage and classical verification of $\mathsf{BQP}$ computations using \emph{quantum indistinguishability obfuscation} (qiO). Specifically, given qiO and assuming a slightly stronger version of $\mathsf{BQP}\neq\mathsf{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 $\mathsf{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 $\mathsf{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.
AI Summary
The paper asks whether quantum indistinguishability obfuscation (qiO) can provide a cryptographic foundation for efficiently classically verifiable quantum advantage and verification of $\mathsf{BQP}$. It requires a classical polynomial-time obfuscator producing classical quantum-circuit descriptions, with security for same-shape circuits whose channels are negligibly close in diamond norm. Assuming classically secure qiO and $\mathsf{BQP}\not\subseteq\mathrm{i.o.}\mathsf{BPP}$, it constructs a publicly verifiable two-message proof of quantumness with negligible classical soundness error. The challenge consists of obfuscated identity or bit-flip circuits. A reduction from worst-case $\mathsf{BQP}$ hardness establishes that classical algorithms cannot distinguish these obfuscations; parallel repetition hides a response string. Public verification checks its one-way-function image, with classical one-way functions derived from the same assumptions. Quantum-secure qiO alone yields private, computationally blind classical verification of arbitrary $\mathsf{BQP}$ decision computations. Randomly masked computation circuits are hidden among test circuits using qiO hybrids. With $r$ rows and $c$ possible planted locations per row, wrong-output probability is at most $c^{-r}$ plus a negligible term. Adding post-quantum one-way functions gives public verification, retaining blindness up to circuit shape and answer. A conditional construction framework adapts local mixing using split-circuit pseudorandomness, random-input obfuscation, and stability assumptions. A clean-workspace compilation with randomized phases lifts ancilla-free qiO to tidy computations. These assumptions are not instantiated, qiO remains unavailable from standard assumptions, and no near-term implementation is established. Public verification requires honestly generated, circuit-dependent preprocessing and is not plain-model non-interactive verification.
Error found: The abstract's claim of the first publicly verifiable classical verification of BQP under computational assumptions in the standard model is not supported, because the body credits prior publicly verifiable QMA arguments, hence BQP verification, from quantum null-iO and additional classical cryptographic tools.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.