Classically-Verifiable Quantum Advantage from a Computational Bell Test
arXiv:2104.00687 · doi:10.1038/s41567-022-01643-7
Abstract
We propose and analyze a novel interactive protocol for demonstrating quantum computational advantage, which is efficiently classically verifiable. Our protocol relies upon the cryptographic hardness of trapdoor claw-free functions (TCFs). Through a surprising connection to Bell's inequality, our protocol avoids the need for an adaptive hardcore bit, with essentially no increase in the quantum circuit complexity and no extra cryptographic assumptions. Crucially, this expands the set of compatible TCFs, and we propose two new constructions: one based upon the decisional Diffie-Hellman problem and the other based upon Rabin's function, . We also describe two independent innovations which improve the efficiency of our protocol's implementation: (i) a scheme to discard so-called "garbage bits", thereby removing the need for reversibility in the quantum circuits, and (ii) a natural way of performing post-selection which significantly reduces the fidelity needed to demonstrate quantum advantage. These two constructions may also be of independent interest, as they may be applicable to other TCF-based quantum cryptography such as certifiable random number generation. Finally, we design several efficient circuits for and describe a blueprint for their implementation on a Rydberg-atom-based quantum computer.
arXiv comment12 pages, 4 figures, 1 table (main text); 12 pages, 1 table (methods + supplementary information). v2: improved notation and clarity, and fixed small errors/typos; no changes to results
References in corpus (32)
- Supplementary information for "Quantum supremacy using a programmable superconducting processor"
- Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
- Elementary gates for quantum computation
- Quantum computational advantage using photons
- Characterizing Quantum Supremacy in Near-Term Devices
- Many-Body Physics with Individually-Controlled Rydberg Atoms
- Observation of a Many-Body Dynamical Phase Transition with a 53-Qubit Quantum Simulator
- Quantum Phases of Matter on a 256-Atom Programmable Quantum Simulator
- Quantum Computational Supremacy
- Programmable quantum simulation of 2D antiferromagnets with hundreds of Rydberg atoms
- Quantum computing with atomic qubits and Rydberg interactions: Progress and challenges
- Parallel implementation of high-fidelity multi-qubit gates with neutral atoms
- A blueprint for demonstrating quantum supremacy with superconducting qubits
- Quantum advantage with shallow circuits
- High-Fidelity Entanglement and Detection of Alkaline-Earth Rydberg Atoms
- Rydberg mediated entanglement in a two-dimensional neutral atom qubit array
- Average-case complexity versus approximate simulation of commuting quantum computations
- Quantum Supremacy and the Complexity of Random Circuit Sampling
- Fast quantum logic gates with trapped-ion qubits
- An experimental and theoretical guide to strongly interacting Rydberg gases
- Analysis of imperfections in the coherent optical excitation of single atoms to Rydberg states
- Bias-preserving gates with stabilized cat qubits
- Quantum Sampling Problems, BosonSampling and Quantum Supremacy
- An omniscient Maxwell's demon
- Universal gates based on targeted phase shifts in a 3D neutral atom array
- Quantum advantage with noisy shallow circuits in 3D
- Coherent addressing of individual neutral atoms in a 3D optical lattice
- Influence of ground-Rydberg coherence in two-qubit gate based on Rydberg blockade
- Improved reversible and quantum circuits for Karatsuba-based integer multiplication
- Realization of real-time fault-tolerant quantum error correction
- Classical Verification of Quantum Computations
- A Cryptographic Test of Quantumness and Certifiable Randomness from a Single Quantum Device
Cited by in corpus (19)
- Computational advantage of quantum random sampling
- Interactive Protocols for Classically-Verifiable Quantum Advantage
- A Practical Introduction to Benchmarking and Characterization of Quantum Computers
- Networked Quantum Services
- Depth-efficient proofs of quantumness
- Off-resonant modulated driving gate protocols for two-photon ground-Rydberg transition and finite Rydberg blockade strength
- Extended two-body Rydberg blockade interaction with off-resonant modulated driving
- Forging quantum data: classically defeating an IQP-based quantum test
- On Certified Randomness from Fourier Sampling or Random Circuit Sampling
- Efficiently verifiable quantum advantage on near-term analog quantum simulators
- Lattice-Based Quantum Advantage from Rotated Measurements
- A computational test of quantum contextuality, and even simpler proofs of quantumness
- Experimental Implementation of an Efficient Test of Quantumness
- Test of Quantumness with Small-Depth Quantum Circuits
- Entropy Accumulation under Post-Quantum Cryptographic Assumptions
- Secret extraction attacks against obfuscated IQP circuits
- Instantaneous Quantum Polynomial-Time Sampling and Verifiable Quantum Advantage: Stabilizer Scheme and Classical Security
- Zero-Knowledge Proofs of Quantumness
- Cryptographic Characterization of Quantum Advantage