Verification of quantum computations beyond classical polynomial limits
Classical Verification of Quantum Computation Beyond the Polynomial Hierarchy
Computational ComplexityCryptography and Security
Summary
The paper deals with the problem of checking that quantum computers produce the right answers using only a classical computer verifier. The authors show a theoretical way, using a special type of oracle, to verify quantum computations that are beyond traditional classical complexity limits. They design a protocol where a classical verifier interacts with a quantum prover to confirm the computation with good confidence. This protocol can handle complex problems that ordinary classical systems cannot verify, advancing how we understand trusted quantum computations.
What this means in practice
- •For quantum algorithm designers: Identify limits and possibilities of classical verification for complex quantum computations using oracle-based protocols.
- •For cryptography engineers: Explore new proof techniques potentially informing quantum-resistant verification methods in cryptographic systems.
A theory result. No direct application yet.
Authors
Atul Mantri
Abstract
It is not known whether a classical polynomial-time verifier can verify arbitrary polynomial-time quantum computations with an efficient quantum honest prover without computational assumptions. We show that, relative to a classical oracle, such verification is possible for a language beyond the polynomial hierarchy that is decided exactly in quantum polynomial time. The protocol is public-coin, with perfect completeness and soundness error at most 1/4. To our knowledge, no language with such a proof system was previously proved to lie outside AM relative to an oracle. For every unbounded polynomial-time computable function, the oracle can be chosen so that the message count and the oracle query counts of the quantum algorithm, verifier, and honest prover are bounded by this function of the input length. The message count is optimal up to a constant factor, since for a suitable oracle every interactive proof system for the language uses at least a constant fraction of the messages of our protocol on infinitely many lengths, with a constant depending on its verifier. The language is a variant of recursive Fourier sampling in which code tables encode secrets that address data tables. The tables are evaluated recursively, and the oracle stores only the leaves. The quantum algorithm recovers every secret exactly, and the verifier checks the prover's secrets recursively against random code entries. The recursion restricts the input in a correlated way, as the same secret fixes the code bits and chooses the free coordinate, so Håstad's switching lemma does not apply. We prove a switching theorem for these restrictions, which may be of independent interest. For instances of sufficient height, no constant-depth circuit of size $2^{\mathrm{poly}(n)}$ changes its output with probability above $2^{-Ω(n)}$ when the answer of a random instance is flipped by changing a single leaf.