Verifiable Quantum Advantage and Computation via Quantum Circuit Obfuscation
Cryptographers show quantum indistinguishability obfuscation yields publicly verifiable quantum advantage and classical BQP verification.
The paper constructs classically verifiable quantum advantage and classical verification of BQP computations from quantum indistinguishability obfuscation. Given qiO and a slightly stronger BQP not equal to BPP assumption, it gives an efficient, publicly verifiable two-message quantum-advantage protocol, grounding heuristic peaked random circuit sampling proposals. A second protocol privately verifies arbitrary BQP computations from qiO alone, and a third is publicly verifiable if post-quantum one-way functions also exist. All results hold when qiO is assumed only for ancilla-free unitary circuits, supported by a worst-to-average-case reduction.
- With qiO and a stronger BQP not equal to BPP, they give a two-message publicly verifiable quantum-advantage protocol.
- One BQP verification protocol assumes only qiO and is privately verifiable.
- A second protocol adds post-quantum one-way functions and is publicly verifiable.
- Results hold for ancilla-free unitary circuits, with a worst-to-average-case obfuscation reduction.
Full article200 words · extracted from arxiv.org · click to collapse
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. We show that all our results hold when qiO is assumed only for ancilla-free unitary circuits. As evidence supporting this assumption, we prove a worst-to-average-case reduction for obfuscating such circuits. This reduction extends the local-mixing framework of Canetti, Chamon, Mucciolo and Ruckenstein (TCC 2024) under quantum analogues of their assumptions.
Text extracted automatically; images, tables and formatting may be missing. Original: https://arxiv.org/abs/2609.40289