pipette
ENEnglish

Verifiable Quantum Advantage and Computation via Quantum Circuit Obfuscation

Alexandru Gheorghiu, Aparna Gupte, Vojt\v{e}ch Havl\'i\v{c}ek, Yunchao Liu

PreprintDice ser un gran avance

En palabras de los autores

We construct protocols for classically verifiable quantum advantage and classical verification of computations using quantum indistinguishability obfuscation (qiO). Specifically, given qiO and assuming a slightly stronger version of , 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 peaked random circuit sampling of Aaronson and Zhang (arXiv:2404.14493). We also construct two simple protocols for classically verifying arbitrary 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 publicly verifiable. To our knowledge, this is the first publicly verifiable protocol for classical verification of 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.

Resultado principalLimitación que admiten los autores

Apareció: jueves, 1 de octubre. arXiv. Preprint, todavía sin revisión por pares.