Cost of Emulating a Small Quantum Annealing Problem in the Circuit-Model
arXiv:2402.17667 · doi:10.1103/PhysRevA.111.062606
Abstract
Demonstrations of quantum advantage for certain sampling problems have generated considerable excitement for quantum computing and have further spurred the development of circuit-model quantum computers, which represent quantum programs as a sequence of quantum gates acting on a finite number of qubits. Amongst this excitement, analog quantum computation has become less prominent, with the expectation that circuit-model quantum computers will eventually be sufficient for emulating analog quantum computation and thus rendering analog quantum computation obsolete. In this work we explore the basic requirements for emulating a specific analog quantum computation in the circuit model: the preparation of a biased superposition of degenerate ground states of an Ising Hamiltonian using an adiabatic evolution. We show that the overhead of emulation is substantial even for this simple problem. This supports using analog quantum computation for solving time-dependent Hamiltonian dynamics in the short term and midterm, assuming analog errors can be made low enough and coherence times long enough to solve problems of practical interest.
24 pages, 18 figures. v2: Updated to published version
References in corpus (90)
- Quantum Computing in the NISQ era and beyond
- Supplementary information for "Quantum supremacy using a programmable superconducting processor"
- Elementary gates for quantum computation
- Quantum Simulation
- Quantum Annealing in the Transverse Ising Model
- A Quantum Adiabatic Evolution Algorithm Applied to Random Instances of an NP-Complete Problem
- Adiabatic Quantum Computing
- The Magnus expansion and some of its applications
- Strong quantum computational advantage using a superconducting quantum processor
- Universal computation by quantum walk
- Exploring the many-body localization transition in two dimensions
- Probing Topological Spin Liquids on a Programmable Quantum Simulator
- Programmable Quantum Simulations of Spin Systems with Trapped Ions
- Hamiltonian Simulation by Qubitization
- Quantum annealing with more than one hundred qubits
- Optimal Hamiltonian Simulation by Quantum Signal Processing
- Simulating Hamiltonian dynamics with a truncated Taylor series
- Programmable quantum simulation of 2D antiferromagnets with hundreds of Rydberg atoms
- Theory of Quantum Annealing of an Ising Spin Glass
- Efficient quantum algorithms for simulating sparse Hamiltonians
- Quantum Annealing: A New Method for Minimizing Multidimensional Functions
- Defining and detecting quantum speedup
- Toward the first quantum simulation with quantum speedup
- Noise tailoring for scalable quantum computation via randomized compiling
- Perspectives of quantum annealing: Methods and implementations
- Robustness of adiabatic quantum computation
- A Theory of Trotter Error
- Digitized adiabatic quantum computing with a superconducting circuit
- Mathematical Foundation of Quantum Annealing
- A random compiler for fast Hamiltonian simulation
- Resilient Quantum Computation: Error Models and Thresholds
- Can One Trust Quantum Simulators?
- Experimental signature of programmable quantum annealing
- Quantum Adiabatic Markovian Master Equations
- Quantum simulation of time-dependent Hamiltonians and the convenient illusion of Hilbert space
- Quantum critical dynamics in a 5000-qubit programmable spin glass
- Variational Fast Forwarding for Quantum Simulation Beyond the Coherence Time
- Coherent quantum annealing in a programmable 2000-qubit Ising chain
- Simple proof of equivalence between adiabatic quantum computation and the circuit model
- Demonstration of a scaling advantage for a quantum annealer over simulated annealing
- Error corrected quantum annealing with hundreds of qubits
- Imaging magnetic polarons in the doped Fermi-Hubbard model
- String patterns in the doped Hubbard model
- Measurement-induced entanglement and teleportation on a noisy quantum processor
- Quantum Speedup by Quantum Annealing
- Probing for quantum speedup in spin glass problems with planted solutions
- Improved Fault-Tolerant Quantum Simulation of Condensed-Phase Correlated Electrons via Trotterization
- Decoherence in adiabatic quantum computation
- Characterizing errors on qubit operations via iterative randomized benchmarking
- Dynamical decoupling for superconducting qubits: a performance survey
- Quantum computers as universal quantum simulators: state-of-art and perspectives
- Consistency Tests of Classical and Quantum Models for a Quantum Annealer
- Quantum algorithm for simulating real time evolution of lattice Hamiltonians
- Hamiltonian Simulation Using Linear Combinations of Unitary Operations
- Time-dependent Hamiltonian simulation with -norm scaling
- Perturbative Gadgets at Arbitrary Orders
- Hamiltonian simulation in the low-energy subspace
- Classically optimized Hamiltonian simulation
- Benchmarking Quantum Annealing Controls with Portfolio Optimization
- Best-case performance of quantum annealers on native spin-glass benchmarks: How chaos can affect success probabilities
- Towards adiabatic quantum computing using compressed quantum circuits
- Hamiltonian Simulation Algorithms for Near-Term Quantum Hardware
- Fixed Depth Hamiltonian Simulation via Cartan Decomposition
- Time-dependent unbounded Hamiltonian simulation with vector norm scaling
- Coherence in logical quantum channels
- Adiabatic preparation of many-body states in optical lattices
- Efficient Fully-Coherent Quantum Signal Processing Algorithms for Real-Time Dynamics Simulation
- Adiabatic many-body state preparation and information transfer in quantum dot arrays
- First-Order Trotter Error from a Second-Order Perspective
- Analog Errors in Ising Machines
- Programmable Quantum Annealers as Noisy Gibbs Samplers
- Quantum algorithm for time-dependent Hamiltonian simulation by permutation expansion
- Characterization and Verification of Trotterized Digital Quantum Simulation via Hamiltonian and Liouvillian Learning
- Self-healing of Trotter error in digital adiabatic state preparation
- An -condensate of fermionic atom pairs via adiabatic state preparation
- An Algebraic Quantum Circuit Compression Algorithm for Hamiltonian Simulation
- Quantum state preparation by adiabatic evolution with customized gates
- Two-qubit gate operations in superconducting circuits with strong coupling and weak anharmonicity
- A quantum hamiltonian simulation benchmark
- Fast and Robust Geometric Two-Qubit Gates for Superconducting Qubits and beyond
- Quantum Algorithm for Simulating Hamiltonian Dynamics with an Off-diagonal Series Expansion
- Implementing two-qubit gates at the quantum speed limit
- Adiabatic state preparation of interacting two-level systems
- Signatures of Open and Noisy Quantum Systems in Single-Qubit Quantum Annealing
- Average-case Speedup for Product Formulas
- Diabatic Quantum Annealing for the Frustrated Ring Model
- Success of digital adiabatic simulation with large Trotter step
- Accuracy guarantees and quantum advantage in analogue open quantum simulation with and without noise
- Time-optimal universal quantum gates on superconducting circuits
- Perturbation Gadgets: Arbitrary Energy Scales from a Single Strong Interaction