PaperlayerView exact revision on arXiv

Source-linked AI summary

Verifiable Quantum Advantage and Computation via Quantum Circuit Obfuscation

Alexandru Gheorghiu, Aparna Gupte, Vojtěch Havlíček, Yunchao Liu

arXiv:2609.40289v1quant-phcs.CR

TL;DR

Near-term quantum-advantage tests seek both hardware feasibility and efficient classical verification, goals that existing approaches do not jointly meet. The paper uses qiO to construct a proof of quantumness and protocols for classical verification of BQP computations. Its proposed qiO construction framework remains uninstantiated.

  • Problem

    Near-term quantum-advantage tests aim to combine implementation on noisy hardware with efficient classical verification, but existing approaches described here do not satisfy both requirements.

    Source: §1 · p. 3

  • Method

    The paper uses qiO to construct proofs of quantumness and classical-verification protocols for BQP computations, and proposes a quantum adaptation of the local-mixing framework for qiO construction.

    Source: §1 · pp. 3–4, §2 · p. 4

  • Results

    The paper reports a qiO-based proof of quantumness secure against classical spoofing and a simple qiO-based BQP verification protocol that can be compiled with one-way functions into a publicly verifiable one.

    Source: §1 · p. 3

  • Takeaways & Limitations

    The results provide cryptographic applications of qiO while treating construction of the primitive as a separate problem for future study.

    Source: §2 · p. 4, §1 · p. 4

    The proposed local-mixing approach is a framework rather than an instantiation, and constructing general-purpose qiO from standard assumptions remains open.

    Source: §1 · p. 4

Abstract

from arXiv · show

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.

1 Introduction

Near-term quantum-advantage tests should be implementable on current hardware and efficiently verifiable classically, but existing approaches described here meet only one of those goals. The paper presents qiO-based protocols and separates those applications from the still-open problem of constructing qiO.

1 Introduction

  • Existing cryptographic proofs of quantumness allow efficient classical verification but are not implementable on present-day noisy devices, while random circuit sampling is feasible near-term but costly to verify classically.The verification cost for random circuit sampling scales exponentially with the number of qubits.Source: §1 · p. 3
  • Aaronson and Zhang’s peaked circuit sampling uses a hidden output string as a verification trapdoor, but leaves efficient generation and resistance to classical spoofing as questions.The auditor checks whether the claimed peak appears at the prescribed frequency.Source: §1 · p. 3
  • Heuristic circuit transformations have produced peaked-circuit candidates whose hidden peaks were later recovered classically, motivating security reductions to studied assumptions or primitives.The passage cites candidate constructions [SB09] and subsequent attacks.Source: §1 · p. 3
  • Assuming qiO and a slightly stronger variant of BQP ≠ BPP, the paper gives a proof of quantumness inspired by peaked circuit sampling and secure against classical spoofing.Source: §1 · p. 3
  • The same ideas yield a simple classical-verification protocol for BQP computations assuming qiO, which one-way functions can compile into a publicly verifiable protocol.Source: §1 · p. 4
  • The paper proposes adapting the local-mixing framework to quantum circuits but does not instantiate the resulting qiO construction.General-purpose qiO remains an extremely strong primitive whose construction from standard assumptions is open [BK21] [BKNY23a].Source: §1 · p. 4

2 Overview of main results

This section outlines how the paper uses quantum indistinguishability obfuscation (qiO) for proofs of quantumness and classical verification of BQP computations, alongside a local-mixing-inspired construction approach. It presents a reduction from ancilla-free qiO to qiO for tidy computations and a conditional worst-to-average-case route to ancilla-free qiO, relating these results to the verification applications and prior approaches.

2 Overview of main results

  • The paper’s second main contribution is an approach to constructing qiO inspired by the local-mixing framework.Source: §2 · p. 4

2.1 Proofs of quantumness and verification from quantum iO

  • Assuming BQP ⊄ i.o.BPP and classically secure qiO, the authors construct a publicly verifiable two-message proof of quantumness.The result gives a precise qiO-based realization of the hiding principle in peaked circuit sampling, but does not literally sample the Aaronson–Zhang circuit ensemble.Source: §2.1 · pp. 6–7
  • The one-way functions needed for public verification of quantumness follow from the same qiO and complexity assumptions, without an additional hardness assumption.The authors derive them from efficiently samplable distributions that are statistically far but computationally indistinguishable.Source: §2.1 · pp. 6–7
  • From qiO alone, they obtain computationally blind private classical verification for BQP decision problems, leaking at most the public circuit shape.The verifier hides a planted computation among test circuits; qiO hides planted locations, and a prover must guess them to cause a wrong output.Source: §2.1 · pp. 8–9
  • With qiO secure against nonuniform quantum adversaries and post-quantum one-way functions, BQP has publicly verifiable classical verification that is computationally blind up to circuit shape and answer.The paper identifies this as the first such result in the standard model; it makes no succinctness claim, and communication and verification may grow polynomially with circuit size.Source: §2.1 · pp. 9–10

2.2 Towards constructing quantum iO

  • qiO for ancilla-free unitary circuits implies qiO for tidy unitary computations, with classical or quantum nonuniform security, but the reduction preserves only single-state correctness.That correctness guarantee applies to the all-zero logical input; the security result is restricted to tidy computations, not arbitrary quantum channels.Source: §2.2 · p. 11
  • A clean-subspace compilation uses the circuit, its inverse, and a control qubit to remove dependence on behavior outside the clean-input subspace.Because a global phase becomes relative between control branches, the construction samples a phase during obfuscation to couple compilations of negligibly close logical channels.Source: §2.2 · p. 11
  • Quantum RIO and SCP imply exactly channel-preserving qiO for same-shape ancilla-free circuits; stability additionally gives robust qiO for widths N ≥ λ.The reduction extends restricted randomized-input security to arbitrary inputs; the robust guarantee assumes stability of postprocessed ideal distributions for negligibly close channels.Source: §2.2 · pp. 10, 13

2.3 Related work

  • The paper uses computational qiO with a classical circuit-description obfuscator, comparing same-shape circuits with negligibly close channels; verification needs quantum security, while proof of quantumness needs only classical security.This output lets the classical verifier generate obfuscations and the prover copy and evaluate them repeatedly.Source: Quantum indistinguishability obfuscation · p. 13

Quantum indistinguishability obfuscation.

  • The private-verification protocol uses qiO alone, while public verification uses qiO for CBQP and post-quantum one-way functions with a circuit-dependent classical challenge.The paper also derives a one-way-puzzle consequence and provides an efficient public verifier; communication and verification costs may grow polynomially with circuit size.Source: Quantum indistinguishability obfuscation · pp. 14–15
  • The local-mixing reduction carries random masks, inverse circuits, and joining arguments to quantum unitaries, handling exact equivalence first and relying on stability for negligibly close channels.The assumptions concern circuit descriptions and correlated side information, and establishing them for concrete local rewrites remains open.Source: Quantum indistinguishability obfuscation · pp. 14–15
  • Obfuscation realizes the hidden-output principle of peaked circuit sampling with polynomial-time public verification and negligible classical soundness error, under cryptographic and complexity assumptions.The guarantees do not establish security for either sampling ensemble; the construction also yields an efficient public verifier from qiO and the stated BQP hardness separation.Source: Quantum indistinguishability obfuscation · pp. 14–15

3 Preliminaries

The preliminaries fix a classical-description model for quantum circuits and define the obfuscation and verification notions used throughout. They distinguish private verification from public verification, including the information each protocol may reveal.

3.1 Quantum Circuits

  • CBQP circuits encode a decision bit as the identity or a bit flip on one logical qubit, and tidy circuits return ancillas to zero.Quantum circuits are modeled from classical descriptions; CBQP decision circuits can be evaluated on |0⟩ to reveal the bit.Source: §3.1 · pp. 15–16

3.2 Quantum Indistinguishability Obfuscation

  • Quantum iO is a classical efficient obfuscation of a circuit that preserves functionality and hides which equivalent circuit was obfuscated.Quantum circuit equivalence is based on negligibly close induced channels; security may be against classical or quantum adversaries.Source: §3.2 · pp. 16–17

3.3 Proofs of Quantumness

  • A proof of quantumness sends a classical challenge to a quantum prover, which returns a classical response checked by a classical verifier for completeness and classical soundness.The verifier retains no secret state needed to check the transcript; public verification additionally requires deterministic classical verification from public information.Source: §3.3 · p. 17

3.4 Classical Verification of BQP Computation

  • Private-verifier preprocessing for CBQP keeps secret state at setup and uses a quantum prover’s classical proof to let a classical verifier output the decision bit or reject.Soundness rules out the wrong output, while computational blindness hides the instance and answer from the prover’s view.Source: §3.4 · p. 18
  • Publicly verifiable preprocessing gives the prover and verifier a public key, so deterministic classical verification requires no secret state after setup.Its blindness guarantee allows leakage of the answer, and communication and verification are not claimed to be succinct.Source: §3.4 · pp. 18–19

4 Quantum advantage from Quantum iO and BQP-hardness

The section gives privately and publicly verifiable two-message proofs of quantumness from qiO, under a BQP hardness assumption stronger than BQP ≠ BPP. Its public protocol uses a one-way function, whose classical security follows from the same assumptions.

(Privately verifiable) Proof of Quantumness

  • Under BQP ⊈ i.o.BPP and classical-secure qiO for CBQP, the Figure 2 protocol is a secure two-message proof of quantumness.The section explains that this hardness assumption is stronger than BQP ≠ BPP because a successful adversary need only win on infinitely many input lengths.Source: (Privately verifiable) Proof of… · p. 20
  • The same-shape circuits C0,λ and C1,λ induce the identity and X channels, respectively, and their qiO obfuscations are computationally indistinguishable.For an input x, Dx computes L(x) into a target qubit and uncomputes its workspace, making it negligibly close to the corresponding circuit.Source: (Privately verifiable) Proof of… · p. 21
  • Parallel repetition with t = ω(log λ) makes soundness negligible: the hybrid endpoint leaves an unbounded prover at most 2^-t probability of guessing the verification bits.The hybrids replace challenge obfuscations one at a time; polynomially many replacements change success probability by at most a negligible amount.Source: (Privately verifiable) Proof of… · p. 22

4.2 Publicly verifiable proofs of quantumness

  • Publishing y = f(b) lets anyone verify a response by checking f(b′) = y, yielding a secure publicly verifiable two-message proof of quantumness.The public protocol retains the same BQP hardness and qiO assumptions as the private protocol.Source: §4.2 · pp. 22–24
  • The assumptions for the private proof already imply classically secure one-way functions, so the public quantum-advantage protocol adds no hardness assumption.The proof derives one-way functions from two obfuscation distributions that are classically indistinguishable but statistically far apart.Source: §4.2 · pp. 22–23

5 Classical Verification of BQP computation

The section constructs private and public protocols for classical verification of BQP computations using qiO. The private protocol is computationally blind up to circuit shape; the public protocol additionally uses a quantum-secure one-way function and does not hide the answer.

5.1 Private verification assuming qiO

  • With qiO secure against QPT adversaries, the private protocol classically verifies BQP computations and is computationally blind up to circuit shape.The construction assumes an amplified, tidy computation represented as a CBQP circuit.Source: §5.1 · p. 25, §5 · p. 25
  • The private protocol is sound: after qiO hybrids, a prover's probability of making the verifier output the wrong answer is at most 2^-λ.The bound uses cols^rows ≥ 2^λ and the independence of the planted locations in the final hybrid.Source: §5.1 · p. 25
  • Its real challenge is computationally indistinguishable from a simulation depending only on circuit shape, hiding the delegated circuit, hardcoded instance, and answer.Padding to common public gate-count and width bounds can make leakage depend only on those bounds.Source: §5.1 · pp. 25, 27

5.2 Public verification assuming qiO and quantum-secure OWFs

  • With nonuniform-QPT-secure qiO and a quantum-secure one-way function, the public protocol verifies CBQP circuits and is computationally blind up to circuit shape and answer.Row parities and one-way images let a public verifier check the claimed answer.Source: §5.2 · p. 27
  • The public protocol does not hide the answer: evaluating the row circuits and combining a second-column response with the row parity recovers it with overwhelming probability.One-wayness is used for soundness, not for the blindness argument.Source: §5.2 · p. 29

6 Constructions of Quantum Indistinguishability Obfuscation

This section develops an assumption-based local-mixing construction for robust qiO for ancilla-free circuits, including an exact-equivalence result and a route to robust security. It also describes lifting the construction to tidy and coherent-decision circuits for applications.

6.1 Definitions and Assumptions

  • Quantum RIO is presented as a weaker average-case analogue of ancilla-free qiO; with quantum split-circuit pseudorandomness and additional conditions, it supports a worst-to-average-case reduction.The split-circuit assumption allows a fresh random separator and its inverse to be removed from independently randomized circuit pieces, even with correlated surrounding circuits and side information.Source: §6.1 · pp. 31–32

6.2 Obfuscation for Ancilla-Free Circuits

  • Under quantum split-circuit pseudorandomness and quantum RIO, the authors construct quantum-secure qiO for exactly equivalent, same-shape ancilla-free unitary circuits.The obfuscator preserves channels exactly and outputs m · poly(λ, n) gates for an m-gate, n-qubit input. It recursively builds left, middle, and right blocks with random boundary masks, then reobfuscates adjacent boundaries when joining triples.Source: §6.2 · pp. 33–34
  • Extending the exact-equivalence result to robust qiO for negligibly close channels requires an additional stability assumption on the postprocessed ideal distributions.The exact-equivalence argument yields identical ideal distributions, whereas negligibly close but unequal channels have disjoint sets of exact implementations.Source: §6.2 · pp. 33, 35
  • Under Assumptions 6.3, 6.5, and 6.7, local mixing gives quantum-secure robust qiO for ancilla-free unitary families of width N ≥ λ, with exact global correctness.The stability hypothesis applies to families with width at least λ.Source: §6.2 · p. 36

6.3 Obfuscation for Tidy Circuits

  • Ancilla-free qiO implies tidy-circuit qiO through a classical polynomial-time compilation.The compilation isolates the circuit’s clean-input action, while a sampled random phase handles global-phase ambiguity; the proof requires tidiness and does not extend to arbitrary circuits with ancillas or channels.Source: §6.3 · pp. 36, 38, 39, 40
  • Classical-function circuits lift to tidy circuits, enabling coherent-function obfuscation; tidy qiO with bound 2√ηcls also implies robust qiO for CBQP.The lifted circuits preserve classical functionality in coherent form, not necessarily the original channel.Source: §6.3 · p. 40
  • Nonuniform qiO security extends to polynomial-size ensembles of same-shape, negligibly close circuits with correlated classical auxiliary input, retaining the assumed classical or quantum security.The guarantee uses fresh obfuscation randomness.Source: §6.3 · p. 41
  • Assumptions 6.3, 6.5, and 6.7 yield globally correct quantum-secure qiO for CBQP, with correlated classical auxiliary-input security, supporting the paper’s verification protocols.The passage identifies private verification, publicly verifiable proofs of quantumness under BQP̸ ⊆i.o.BPP, and public verification assuming post-quantum one-way functions.Source: §6.3 · p. 41
Loading 2609.40289v1…