Efficiently verifiable quantum advantage on near-term analog quantum simulators
arXiv:2403.08195 · doi:10.1103/PRXQuantum.6.010341
Abstract
Existing schemes for demonstrating quantum computational advantage are subject to various practical restrictions, including the hardness of verification and challenges in experimental implementation. Meanwhile, analog quantum simulators have been realized in many experiments to study novel physics. In this work, we propose a quantum advantage protocol based on single-step Feynman-Kitaev verification of an analog quantum simulation, in which the verifier need only run an -time classical computation, and the prover need only prepare samples of a history state and perform single-qubit measurements, for a security parameter . We also propose a near-term feasible strategy for honest provers and discuss potential experimental realizations.
20 pages, 6 figures
References in corpus (66)
- Supplementary information for "Quantum supremacy using a programmable superconducting processor"
- Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
- Quantum algorithm for solving linear systems of equations
- Quantum Simulation
- Quantum computational advantage using photons
- Circuit Quantum Electrodynamics
- A Quantum Engineer's Guide to Superconducting Qubits
- The Dicke Quantum Phase Transition with a Superfluid Gas in an Optical Cavity
- Characterizing Quantum Supremacy in Near-Term Devices
- Strong quantum computational advantage using a superconducting quantum processor
- Many-Body Physics with Individually-Controlled Rydberg Atoms
- Logical quantum processor based on reconfigurable atom arrays
- Quantum Phases of Matter on a 256-Atom Programmable Quantum Simulator
- Demonstration of a neutral atom controlled-NOT quantum gate
- Programmable Quantum Simulations of Spin Systems with Trapped Ions
- Fluxonium: single Cooper pair circuit free of charge offsets
- Efficient quantum algorithms for simulating sparse Hamiltonians
- Parallel implementation of high-fidelity multi-qubit gates with neutral atoms
- Toward the first quantum simulation with quantum speedup
- A Theory of Trotter Error
- The randomized measurement toolbox
- All-Optical Switch and Transistor Gated by One Stored Photon
- Can One Trust Quantum Simulators?
- Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy
- Average-case complexity versus approximate simulation of commuting quantum computations
- Roton-type mode softening in a quantum gas with cavity-mediated long-range interactions
- Single-Photon Switch based on Rydberg Blockade
- Three-body interactions with cold polar molecules
- Randomized benchmarking of single qubit gates in a 2D array of neutral atom qubits
- Tunable-range, photon-mediated atomic interactions in multimode cavity QED
- Observation of Laughlin states made of light
- A single-photon switch and transistor enabled by a solid-state quantum memory
- Programmable Interactions and Emergent Geometry in an Atomic Array
- Two-dimensional transport and transfer of a single atomic qubit in optical tweezers
- Instantaneous Quantum Computation
- Security of practical private randomness generation
- Verification of quantum computation: An overview of existing approaches
- Cross-Platform Verification of Intermediate Scale Quantum Devices
- Universal simulation of Hamiltonian dynamics for qudits
- Digital-Analog Quantum Computation
- Security and Composability of Randomness Expansion from Bell Inequalities
- Universal Quantum Hamiltonians
- Architectures for quantum simulation showing a quantum speedup
- Post hoc verification of quantum computation
- Post hoc verification with a single prover
- Theoretical and Experimental Perspectives of Quantum Verification
- Superconducting switch for fast on-chip routing of quantum microwave fields
- How many qubits are needed for quantum computational supremacy?
- A Strongly Interacting Polaritonic Quantum Dot
- Direct certification of a class of quantum simulations
- Classically-Verifiable Quantum Advantage from a Computational Bell Test
- Continuous Symmetry Breaking in a Trapped-Ion Spin Chain
- Dipolar Spin Models with Arrays of Superconducting Qubits
- Coherence in a cold atom photon transistor
- Demonstration of tunable three-body interactions between superconducting qubits
- Closing gaps of a quantum advantage with short-time Hamiltonian dynamics
- Enhancing a Many-body Dipolar Rydberg Tweezer Array with Arbitrary Local Controls
- Universal 2-local Hamiltonian Quantum Computing
- Many-body decoherence dynamics and optimised operation of a single-photon switch
- Quantum Randomness Generation by Probability Estimation with Classical Side Information
- Complexity of decoupling and time-reversal for n spins with pair-interactions: Arrow of time in quantum control
- Randomized Benchmarking in the Analogue Setting
- Practical verification protocols for analog quantum simulators
- Nonadaptive fault-tolerant verification of quantum supremacy with noise
- Verifiable measurement-based quantum random sampling with trapped ions
- Accreditation of Analogue Quantum Simulators