A key issue with existing quantum advantage experiments is that their verification requires exponential classical time. In this work, we address this challenge by designing a new proposal---Hidden Code Sampling---with efficient classical verification. We use properties of quantum error correction to build an experiment that is "conditionally peaked": conditioned on a subset of qubits, the distribution on another subset is peaked. We give evidence for the classical intractability of this protocol by showing complexity-theoretic hardness of classical simulation, putting our scheme on par with other quantum advantage schemes. A major hurdle in instantiating the scheme concerns distinguishing between two noise channels, one involving local coherent noise and the other involving local Pauli noise. We identify algebraic properties of the underlying codes that enable an efficient distinguisher and construct an explicit code family satisfying these properties while preserving the hardness guarantees. We provide further evidence for soundness of our verification tests by proving an exponential query lower bound for classical algorithms that pass our verification tests in a black-box model.
A key issue with existing quantum advantage experiments is that their verification requires exponential classical time. In this work, we address this challenge by designing a new proposal---Hidden Code Sampling---with efficient classical verification. We use properties of quantum error correction to build an experiment that is "conditionally peaked": conditioned on a subset of qubits, the distribution on another subset is peaked. We give evidence for the classical intractability of this protocol by showing complexity-theoretic hardness of classical simulation, putting our scheme on par with other quantum advantage schemes. A major hurdle in instantiating the scheme concerns distinguishing between two noise channels, one involving local coherent noise and the other involving local Pauli noise. We identify algebraic properties of the underlying codes that enable an efficient distinguisher and construct an explicit code family satisfying these properties while preserving the hardness guarantees. We provide further evidence for soundness of our verification tests by proving an exponential query lower bound for classical algorithms that pass our verification tests in a black-box model.
A key issue of current quantum advantage experiments is that their verification requires a full classical simulation of the ideal computation. This limits the regime in which the experiments can be verified to precisely the regime in which they are also simulatable. An important outstanding question is therefore to find quantum advantage schemes that are also classically verifiable. We make progress on this question by designing a new quantum advantage proposal--Hidden Code Sampling--whose output distribution is conditionally peaked. These peaks enable verification in far less time than it takes for full simulation. At the same time, we show that exactly sampling from the output distribution is classically hard unless the polynomial hierarchy collapses, and we propose a plausible conjecture regarding average-case hardness. Our scheme is based on ideas from quantum error correction. The required quantum computations are closely related to quantum fault-tolerant circuits and can potentially be implemented transversally. Our proposal may thus give rise to a next generation of quantum advantage experiments en route to full quantum fault tolerance.
A central question in the theory of quantum advantage is whether there are quantum advantage protocols with similar resource requirements as random circuit sampling that are also verifiable just from the classical outputs of the quantum computation. Here, we develop the idea of simulation secrets for verifiable advantage. A verifier can use a simulation secret to evaluate a cross-entropy test faster than it would take a classical adversary to pass the test. We instantiate this idea using IQP circuits described by cubic polynomials with planted independent spaces. These correspond to the largest independent set in the orbit of a polynomial under the general linear group and yield a low-rank stabilizer decomposition of the corresponding state. We conjecture that large independent spaces are invisible to a computationally bounded adversary, and therefore they cannot exploit them to pass the protocol. A second conjecture regards the fine-grained complexity of producing samples that pass the cross-entropy test for uniformly random polynomials. Under these conjectures, our scheme results in a polynomial gap between the verification time and the time a classical adversary would need to pass the protocol---both are exponential. It has a potential application to generating classically certifiable randomness, since the output distributions have high min-entropy. We estimate that the planted polynomial scheme is implementable using 100 logical qubits at logical error rates around 10−6.
Over a decade after its proposal, the idea of using quantum computers to sample hard distributions has remained a key path to demonstrating quantum advantage. Yet a severe drawback remains: verification seems to require classical computation exponential in the system size, n. As an attempt to overcome this difficulty, we propose a new candidate for quantum advantage experiments with otherwise random "peaked circuits", i.e., quantum circuits whose outputs have high concentrations on a computational basis state. Naturally, the heavy output string can be used for classical verification. In this work, we analytically and numerically study an explicit model of peaked circuits, in which τr layers of uniformly random gates are augmented by τp layers of gates that are optimized to maximize peakedness. We show that getting 1/poly(n) peakedness from such circuits requires τp=Ω((τr/n)0.19) with overwhelming probability. However, we also give numerical evidence that nontrivial peakedness is possible in this model -- decaying exponentially with the number of qubits, but more than can be explained by any approximation where the output of a random quantum circuit is treated as a Haar-random state. This suggests that these peaked circuits have the potential for future verifiable quantum advantage experiments. Our work raises numerous open questions about random peaked circuits, including how to generate them efficiently, and whether they can be distinguished from fully random circuits in classical polynomial time.
Sampling problems demonstrating beyond classical computing power with noisy intermediate-scale quantum devices have been experimentally realized. In those realizations, however, our trust that the quantum devices faithfully solve the claimed sampling problems is usually limited to simulations of smaller-scale instances and is, therefore, indirect. The problem of verifiable quantum advantage aims to resolve this critical issue and provides us with greater confidence in a claimed advantage. Instantaneous quantum polynomial-time (IQP) sampling has been proposed to achieve beyond classical capabilities with a verifiable scheme based on quadratic-residue codes (QRC). Unfortunately, this verification scheme was recently broken by an attack proposed by Kahanamoku-Meyer. In this work, we revive IQP-based verifiable quantum advantage by making two major contributions. Firstly, we introduce a family of IQP sampling protocols called the , which builds on results linking IQP circuits, the stabilizer formalism, coding theory, and an efficient characterization of IQP-circuit correlation functions. This construction extends the scope of existing IQP-based schemes while maintaining their simplicity and verifiability. Secondly, we introduce the (HSC) problem as a well-defined mathematical challenge that underlies the stabilizer scheme. To assess classical security, we explore a class of attacks based on secret extraction, including Kahanamoku-Meyer’s attack as a special case. We provide evidence of the security of the stabilizer scheme, assuming the hardness of the HSC problem. We also point out that the vulnerability observed in the original QRC scheme is primarily attributed to inappropriate parameter choices, which can be naturally rectified with proper parameter settings.
We construct protocols for classically verifiable quantum advantage and classical verification of BQP computations using \emph{quantum indistinguishability obfuscation} (qiO). Specifically, given qiO and assuming a slightly stronger version of BQP=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 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 BQP computations under computational assumptions in the standard model.
As qiO is the basis for our results, we propose an approach to constructing qiO by adapting the local-mixing framework of Canetti--Chamon--Mucciolo--Ruckenstein.
Achieving quantum computational advantage requires solving a classically intractable problem on a quantum device. Natural proposals rely upon the intrinsic hardness of classically simulating quantum mechanics; however, verifying the output is itself classically intractable. On the other hand, certain quantum algorithms (e.g. prime factorization via Shor's algorithm) are efficiently verifiable, but require more resources than what is available on near-term devices. One way to bridge the gap between verifiability and implementation is to use "interactions" between a prover and a verifier. By leveraging cryptographic functions, such protocols enable the classical verifier to enforce consistency in a quantum prover's responses across multiple rounds of interaction. In this work, we demonstrate the first implementation of an interactive quantum advantage protocol, using an ion trap quantum computer. We execute two complementary protocols -- one based upon the learning with errors problem and another where the cryptographic construction implements a computational Bell test. To perform multiple rounds of interaction, we implement mid-circuit measurements on a subset of trapped ion qubits, with subsequent coherent evolution. For both protocols, the performance exceeds the asymptotic bound for classical behavior; maintaining this fidelity at scale would conclusively demonstrate verifiable quantum advantage.