Quantum circuit obfuscation enables verifiable quantum advantage protocols
Verifiable Quantum Advantage and Computation via Quantum Circuit Obfuscation
Cryptography and Security
Summary
Showing that quantum computers can do tasks beyond classical ones is a key goal, but verifying these tasks using only classical computers is hard. The authors build protocols that let classical computers verify quantum computations under assumptions about quantum circuit obfuscation and computational hardness. Their work provides cryptographic guarantees for quantum advantage experiments and offers ways to check any quantum computation classically with either private or public verification. They also support their assumptions by proving technical results about the difficulty of obfuscating certain quantum circuits.
What this means in practice
- •For quantum software engineers: Develop protocols that allow classical computers to verify quantum computations, improving trust in quantum cloud computing services.
- •For cryptography system designers: Design cryptographic schemes based on quantum circuit obfuscation to enable secure and verifiable quantum information processing.
A theory result. No direct application yet.
Authors
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. 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.