THE QUANTUM INTELLIGENCER

LONDON, 25 AUGUST — A paper of considerable consequence has appeared, demonstrating that the classical verification of quantum computation, when conducted without interaction after a fixed setup, cannot be founded upon any falsifiable assumption. The authors prove that no quantum black-box reduction of such a non-interactive scheme to a falsifiable assumption, of which the Learning-with-Errors problem is the leading instance, can exist; the separation holds conditional on the existence of a complexity-theoretic gap between the classes QMA and QCMA. This result draws a firm boundary around a programme that began with Mahadev’s four-message interactive protocol, and the prudent engineer will note its bearing upon the design of verification schemes intended for the coming quantum era. For the reader unfamiliar with the idiom, a falsifiable assumption is one that admits an efficient test: given a candidate solution, an algorithm can verify whether it is correct. The Learning-with-Errors problem, the leading instance, asks one to recover a secret vector from a set of noisy linear equations, and a proposed answer can be checked directly. A black-box reduction treats the adversary as an oracle, consulting it without examining its internal design; it demonstrates that any efficient adversary against the scheme could be converted into an algorithm solving the underlying problem. The complexity classes QMA and QCMA are the quantum counterparts of NP. QMA contains the problems for which a quantum state serves as a proof that a quantum verifier checks in polynomial time; QCMA restricts the proof to a classical string. The relation between them is unsettled, though the authors support the needed gap by constructing a situation relative to a quantum unitary oracle in which it holds. To fix the idea, consider a locksmith and a lock. If the smith may converse with the owner, testing key against lock repeatedly, he may be convinced of the key's fitness. But if the owner presents a single key and asks that it be pronounced genuine, the smith's only recourse is to some property of the metal that can be tested in isolation, such as its hardness. A falsifiable assumption is precisely such a testable property. Yet the hardness of the metal, however reliably measured, cannot ensure that the key's cuts align with the lock's tumblers; a key of proper hardness may still be the wrong shape. And a black-box reduction, which regards the key-cutting process as a closed engine, cannot show that a key which fails to turn the lock implies an ability to defeat the hardness test. So it is with classical verification of a quantum computation: when only a single message is allowed after the fixed setup, no testable property that can be checked in isolation will suffice to certify the computation's correctness, unless the complexity classes QMA and QCMA differ. The prudent engineer will therefore treat the one-message scheme as a narrower instrument than the interactive one, and continue to rely on conversation where conversation is possible. Mahadev's four-message protocol, published in the SIAM Journal on Computing in 2022, stands as the benchmark from which the present inquiry departs. The paper before us proves that the reduction to a single message after setup cannot rest on any falsifiable assumption, and it does so by a theorem conditional upon the existence of a QMA-QCMA gap problem. The year 2022 thus marks the origin of the interactive scheme; the intervening period, over which the question of fewer messages remained open, is now closed by a proof rather than by a counterexample. The theorem's reach deserves to be stated with some exactness, for it is narrower than it might at first appear. What is proved is that no quantum black-box reduction of a non-interactive classical verification protocol for QMA to a falsifiable assumption can exist, conditional on the existence of a QMA-QCMA gap problem. That is a statement about the manner of proof and the class of assumptions, and it leaves several doors open. A reduction that inspects the adversary's program rather than merely consulting it as an oracle is not touched; a protocol that allows a second message after the setup is not touched; and the question whether QMA and QCMA are in truth distinct is not decided, only assumed for the sake of the argument. Nor does the theorem say that a one-message scheme is impossible. It says that such a scheme cannot be obtained from a falsifiable assumption by a black-box reduction. The distinction is material. The four-message protocol of Mahadev remains standing; the single-message corridor is closed to the traveller who insists on a falsifiable assumption and a black-box reduction, but the surrounding terrain is not surveyed. The result is also conditional, and the oracle construction offered in support of the required gap is not a proof that the gap obtains in the unrelativised world. A narrow result, in short, but a precisely drawn one, and the prudent engineer will file it as such. Let the record note the paper's standing. It is a preprint: a document circulated for the scrutiny of the field, not a finding certified by the refereeing process. The proof it contains may well survive that scrutiny; it may equally fail it. The prudent reader will therefore distinguish between what the paper claims and what the field has accepted, and will not yet write its theorem into the ledger as settled. The distinction is not pedantry. A result that has not been examined is a claim under examination. —Ada H. Pemberley Dispatch from The Prepared E0