Toward the first quantum simulation with quantum speedup

Abstract

With quantum computers of significant size now on the horizon, we should understand how to best exploit their initially limited abilities. To this end, we aim to identify a practical problem that is beyond the reach of current classical computers, but that requires the fewest resources for a quantum computer. We consider quantum simulation of spin systems, which could be applied to understand condensed matter phenomena. We synthesize explicit circuits for three leading quantum simulation algorithms, employing diverse techniques to tighten error bounds and optimize circuit implementations. Quantum signal processing appears to be preferred among algorithms with rigorous performance guarantees, whereas higher-order product formulas prevail if empirical error estimates suffice. Our circuits are orders of magnitude smaller than those for the simplest classically-infeasible instances of factoring and quantum chemistry.

63 pages, 13 figures, 2 tables

References in corpus (17)

• Probing many-body dynamics on a 51-atom quantum simulator
• Many-body localization edge in the random-field Heisenberg chain
• Quantum Computational Supremacy
• Simulating Hamiltonian dynamics with a truncated Taylor series
• Synthesis of Quantum Logic Circuits
• Experimental Comparison of Two Quantum Computing Architectures
• Simulating chemistry using quantum computers
• Digital quantum simulation of fermionic models with a superconducting circuit
• Automated optimization of large quantum circuits with continuous parameters
• Chemical Basis of Trotter-Suzuki Errors in Quantum Chemistry Simulation
• Interferometric probes of many-body localization
• Efficient synthesis of universal Repeat-Until-Success circuits
• Simulating sparse Hamiltonians with star decompositions
• Quantum Algorithms for Fermionic Quantum Field Theories
• Shor's algorithm on a nearest-neighbor machine
• Reducing the quantum computing overhead with complex gate distillation
• Pareto-Efficient Quantum Circuit Simulation Using Tensor Contraction Deferral

Cited by in corpus (322)

• Quantum computational chemistry
• Quantum Chemistry in the Age of Quantum Computing
• The Variational Quantum Eigensolver: a review of methods and best practices
• Quantum algorithms for quantum chemistry and quantum materials science
• Many-body localization: an introduction and selected topics
• A Theory of Trotter Error
• Exponential suppression of bit or phase flip errors with repetitive error correction
• t$|$ket$⟩$ : A Retargetable Compiler for NISQ Devices
• Encoding Electronic Spectra in Quantum Circuits with Linear T Complexity
• A random compiler for fast Hamiltonian simulation
• The Future of Quantum Computing with Superconducting Qubits
• A Race Track Trapped-Ion Quantum Processor
• Stabilizer Rényi entropy
• Learning-based quantum error mitigation
• Quantum Computer Systems for Scientific Discovery
• Qubitization of Arbitrary Basis Quantum Chemistry Leveraging Sparsity and Low Rank Factorization
• Scalable error mitigation for noisy quantum circuits produces competitive expectation values
• A perspective on the current state-of-the-art of quantum computing for drug discovery applications
• Strategies for solving the Fermi-Hubbard model on near-term quantum computers
• Review on novel methods for lattice gauge theories
• Nearly optimal lattice simulation by product formulas
• Emerging quantum computing algorithms for quantum chemistry
• Quantum Hopfield neural network
• Standard Model Physics and the Digital Quantum Revolution: Thoughts about the Interface
• Near-optimal ground state preparation
• Faster quantum simulation by randomization
• Quantum State Preparation with Optimal Circuit Depth: Implementations and Applications
• Low rank representations for quantum simulation of electronic structure
• Improved Fault-Tolerant Quantum Simulation of Condensed-Phase Correlated Electrons via Trotterization
• Quantum Machine Learning for Chemistry and Physics
• Resource-efficient digital quantum simulation of $d$-level systems for photonic, vibrational, and spin-$s$ Hamiltonians
• Circuit-Based Quantum Random Access Memory for Classical Data
• Efficient phase-factor evaluation in quantum signal processing
• Focus beyond quadratic speedups for error-corrected quantum advantage
• Application-Oriented Performance Benchmarks for Quantum Computing
• Quantum Algorithms for Simulating the Lattice Schwinger Model
• Exponential Error Suppression for Near-Term Quantum Devices
• Quantum algorithm for simulating real time evolution of lattice Hamiltonians
• Machine learning method for state preparation and gate synthesis on photonic quantum computers
• Fault-Tolerant Quantum Simulations of Chemistry in First Quantization
• Quantum Software Engineering: Landscapes and Horizons
• Observation of Floquet prethermalization in dipolar spin chains
• Time-dependent Hamiltonian simulation with $L^1$-norm scaling
• Collision models can efficiently simulate any multipartite Markovian quantum dynamics
• Digital-Analog Quantum Computation
• Efficiently computable bounds for magic state distillation
• Quantum Computing for Neutrino-nucleus Scattering
• Achieving a quantum smart workforce
• Biology and medicine in the landscape of quantum advantages
• Fault tolerant resource estimation of quantum random-access memories
• Quantum-centric Supercomputing for Materials Science: A Perspective on Challenges and Future Directions
• Early fault-tolerant simulations of the Hubbard model
• Locality and digital quantum simulation of power-law interactions
• Product Decomposition of Periodic Functions in Quantum Signal Processing
• Trading T gates for dirty qubits in state preparation and unitary synthesis
• Mitigating algorithmic errors in Hamiltonian simulation
• Quantum algorithm for calculating molecular vibronic spectra
• Quantum Simulation of the Sachdev-Ye-Kitaev Model by Asymmetric Qubitization
• A general quantum algorithm for open quantum dynamics demonstrated with the Fenna-Matthews-Olson complex
• Quantum simulation of electronic structure with a transcorrelated Hamiltonian: improved accuracy with a smaller footprint on the quantum computer
• Hamiltonian Simulation Algorithms for Near-Term Quantum Hardware
• Probing quantum processor performance with pyGSTi
• Resilience of quantum random access memory to generic noise
• Multicore Quantum Computing
• Benchmarking quantum computers
• Time-dependent unbounded Hamiltonian simulation with vector norm scaling
• Applying quantum algorithms to constraint satisfaction problems
• Time-marching based quantum solvers for time-dependent linear differential equations
• Scalable algorithm simplification using quantum AND logic
• Nearly tight Trotterization of interacting electrons
• Evaluating energy differences on a quantum computer with robust phase estimation
• Simulating Open Quantum Systems Using Hamiltonian Simulations
• Quantum algorithm for visual tracking
• On applications of quantum computing to plasma simulations
• Efficient Fully-Coherent Quantum Signal Processing Algorithms for Real-Time Dynamics Simulation
• Holographic dynamics simulations with a trapped ion quantum computer
• On the energy landscape of symmetric quantum signal processing
• Variational quantum eigensolver for the Heisenberg antiferromagnet on the kagome lattice
• Probing ground-state phase transitions through quench dynamics
• Near- and long-term quantum algorithmic approaches for vibrational spectroscopy
• Simulating key properties of lithium-ion batteries with a fault-tolerant quantum computer
• Circuit optimization of Hamiltonian simulation by simultaneous diagonalization of Pauli clusters
• Quantum Analytic Descent
• General quantum algorithms for Hamiltonian simulation with applications to a non-Abelian lattice gauge theory
• Noise-assisted digital quantum simulation of open systems
• Constant-depth preparation of matrix product states with adaptive quantum circuits
• Circuit Transformations for Quantum Architectures
• Quantum natural gradient generalised to noisy and non-unitary circuits
• Compilation by stochastic Hamiltonian sparsification
• Hamiltonian simulation with random inputs
• Computing Ground State Properties with Early Fault-Tolerant Quantum Computers
• Spectral density estimation with the Gaussian Integral Transform
• Imaginary Time Propagation on a Quantum Chip
• Variational Hamiltonian simulation for translational invariant systems via classical pre-processing
• Hunting for quantum-classical crossover in condensed matter problems
• Low cost quantum circuits for classically intractable instances of the Hamiltonian dynamics simulation problem
• Randomizing multi-product formulas for Hamiltonian simulation
• Robust and Efficient Hamiltonian Learning
• First-Order Trotter Error from a Second-Order Perspective
• QuESTlink -- Mathematica embiggened by a hardware-optimised quantum emulator
• Optimized Lie-Trotter-Suzuki decompositions for two and three non-commuting terms
• Destructive Error Interference in Product-Formula Lattice Simulation
• Realization of quantum signal processing on a noisy quantum computer
• Constant-Depth Circuits for Dynamic Simulations of Materials on Quantum Computers
• Time-dependent Hamiltonian Simulation of Highly Oscillatory Dynamics and Superconvergence for Schrödinger Equation
• Digital quantum simulation of molecular dynamics and control
• Quantum dynamics simulations beyond the coherence time on NISQ hardware by variational Trotter compression
• Quantum Error Mitigated Classical Shadows
• Preparing Bethe Ansatz Eigenstates on a Quantum Computer
• Finding Angles for Quantum Signal Processing with Machine Precision
• Quantum State Preparation of Normal Distributions using Matrix Product States
• An Algorithm for Quantum Computation of Particle Decays
• Quantum dynamical speedup in correlated noisy channels
• Probing many-body localization on a noisy quantum computer
• symQV: Automated Symbolic Verification of Quantum Programs
• Quantum Computation for Periodic Solids in Second Quantization
• Perturbative quantum simulation
• Quantum-centric computation of molecular excited states with extended sample-based quantum diagonalization
• Implementing any Linear Combination of Unitaries on Intermediate-term Quantum Computers
• Quantum simulation of exact electron dynamics can be more efficient than classical mean-field methods
• Well-conditioned multi-product formulas for hardware-friendly Hamiltonian simulation
• Exact solution for the quantum and private capacities of bosonic dephasing channels
• On the complexity of implementing Trotter steps
• Quantum time dynamics of 1D-Heisenberg models employing the Yang-Baxter equation for circuit compression
• Twist: Sound Reasoning for Purity and Entanglement in Quantum Programs
• Resource-Optimized Fermionic Local-Hamiltonian Simulation on Quantum Computer for Quantum Chemistry
• Quantum Phase Processing and its Applications in Estimating Phase and Entropies
• Quantum Simulation of Z2 Lattice Gauge theory with minimal resources
• Exact gate decompositions for photonic quantum computing
• Quantum simulation of real-space dynamics
• A Sparse Model of Quantum Holography
• Efficient Product Formulas for Commutators and Applications to Quantum Simulation
• Hamiltonian operator approximation for energy measurement and ground state preparation
• Benchmarking variational quantum eigensolvers for the square-octagon-lattice Kitaev model
• Gradient-descent quantum process tomography by learning Kraus operators
• Simulating Effective QED on Quantum Computers
• Training variational quantum circuits with CoVaR: covariance root finding with classical shadows
• qSWIFT: High-order randomized compiler for Hamiltonian simulation
• Robust Majorana magic gates via measurements
• Tower: Data Structures in Quantum Superposition
• Resource estimate for quantum many-body ground-state preparation on a quantum computer
• Variational Gibbs State Preparation on NISQ devices
• Observation of high-order Mollow triplet by quantum mode control with concatenated continuous driving
• Stable factorization for phase factors of quantum signal processing
• Exact and approximate continuous-variable gate decompositions
• Trotter errors from dynamical structural instabilities of Floquet maps in quantum simulation
• A quantum hamiltonian simulation benchmark
• High-Fidelity Magic-State Preparation with a Biased-Noise Architecture
• Hamiltonian simulation with nearly optimal dependence on spectral norm
• Preparing quantum many-body scar states on quantum computers
• Quantum Simulation of the Radical Pair Dynamics of the Avian Compass
• Quantum computing of reacting flows via Hamiltonian simulation
• Low-depth Hamiltonian Simulation by Adaptive Product Formula
• Qubit-Efficient Randomized Quantum Algorithms for Linear Algebra
• Entanglement accelerates quantum simulation
• Efficient Hamiltonian Simulation for Solving Option Price Dynamics
• Exploiting fermion number in factorized decompositions of the electronic structure Hamiltonian
• Importance sampling for stochastic quantum simulations
• Synthesizing efficient circuits for Hamiltonian simulation
• Short-depth circuits for efficient expectation value estimation
• Variational Quantum Optimization of Nonlocality in Noisy Quantum Networks
• Tailoring Term Truncations for Electronic Structure Calculations Using a Linear Combination of Unitaries
• Digital quantum simulation of NMR experiments
• Optimal quantum dataset for learning a unitary transformation
• HamLib: A library of Hamiltonians for benchmarking quantum algorithms and hardware
• Circuit complexity of quantum access models for encoding classical data
• Testing a quantum annealer as a quantum thermal sampler
• Prethermal quasiconserved observables in Floquet quantum systems
• Fault-tolerant quantum algorithms for quantum molecular systems: A survey
• Probabilistic Interpolation of Quantum Rotation Angles
• Quantum computation of thermal averages in the presence of a sign problem
• Spacetime-Efficient Low-Depth Quantum State Preparation with Applications
• Quantum computation of molecular structure using data from challenging-to-classically-simulate nuclear magnetic resonance experiments
• Variational dynamics as a ground-state problem on a quantum computer
• Quantum Simulations of Chemistry in First Quantization with any Basis Set
• Quantum State Tomography with Conditional Generative Adversarial Networks
• Mitigating crosstalk errors by randomized compiling: Simulation of the BCS model on a superconducting quantum computer
• State Preparation in the Heisenberg Model through Adiabatic Spiraling
• Variational quantum Gibbs state preparation with a truncated Taylor series
• Quantum Topological Data Analysis with Linear Depth and Exponential Speedup
• Variational Approach to Quantum State Tomography based on Maximal Entropy Formalism
• 2QAN: A quantum compiler for 2-local qubit Hamiltonian simulation algorithms
• Average-case Speedup for Product Formulas
• Infinite quantum signal processing
• A Perspective on Quantum Computing Applications in Quantum Chemistry using 25--100 Logical Qubits
• Experimental implementation of quantum algorithm for association rules mining
• Quantum differential equation solvers: limitations and fast-forwarding
• SimuQ: A Framework for Programming Quantum Hamiltonian Simulation with Analog Compilation
• Overhead-constrained circuit knitting for variational quantum dynamics
• Rise of conditionally clean ancillae for efficient quantum circuit constructions
• Exponentially faster implementations of Select(H) for fermionic Hamiltonians
• Algebraic Reasoning of Quantum Programs via Non-idempotent Kleene Algebra
• Power-optimal, stabilized entangling gate between trapped-ion qubits
• Algorithmic Shadow Spectroscopy
• Doubling the order of approximation via the randomized product formula
• Well-conditioned multiproduct Hamiltonian simulation
• Dissipative variational quantum algorithms for Gibbs state preparation
• Quantifying $T$-gate-count improvements for ground-state-energy estimation with near-optimal state preparation
• ERASER: Towards Adaptive Leakage Suppression for Fault-Tolerant Quantum Computing
• Simple and high-precision Hamiltonian simulation by compensating Trotter error with linear combination of unitary operations
• Adiabatic quantum algorithm for artificial graphene
• Trotter error with commutator scaling for the Fermi-Hubbard model
• Quantum Algorithms for Testing Hamiltonian Symmetry
• Optimized noise-assisted simulation of the Lindblad equation with time-dependent coefficients on a noisy quantum processor
• Digital quantum simulation framework for energy transport in an open quantum system
• Calculating the many-body density of states on a digital quantum computer
• Quantum algorithm for linear non-unitary dynamics with near-optimal dependence on all parameters
• The T-Complexity Costs of Error Correction for Control Flow in Quantum Computation
• Simulating spectroscopy experiments with a superconducting quantum computer
• Efficient and practical Hamiltonian simulation from time-dependent product formulas
• Parallel Quantum Algorithm for Hamiltonian Simulation
• Early Fault-Tolerant Quantum Algorithms in Practice: Application to Ground-State Energy Estimation
• Digital quantum simulation of non-perturbative dynamics of open systems with orthogonal polynomials
• Selection and improvement of product formulae for best performance of quantum simulation
• Quantum Control Machine: The Limits of Control Flow in Quantum Programming
• Toward hybrid quantum simulations with qubits and qumodes on trapped-ion platforms
• Representation of the Fermionic Boundary Operator
• Limitations of Classically-Simulable Measurements for Quantum State Discrimination
• Higher-order quantum transformations of Hamiltonian dynamics
• A quantum computing concept for 1-D elastic wave simulation with exponential speedup
• Digital quantum simulation of the BCS model with a central-spin-like quantum processor
• Toward Super-polynomial Quantum Speedup of Equivariant Quantum Algorithms with SU($d$) Symmetry
• Two-level Quantum Walkers on Directed Graphs II: An Application to qRAM
• Variational quantum computing for quantum simulation: principles, implementations, and challenges
• Lower Bounds for the Trotter Error
• Two-dimensional coherent spectrum of high-spin models via a quantum computing approach
• Exploiting anticommutation in Hamiltonian simulation
• An invitation to the sample complexity of quantum hypothesis testing
• Bounding the finite-size error of quantum many-body dynamics simulations
• Complexity of Digital Quantum Simulation in the Low-Energy Subspace: Applications and a Lower Bound
• A Comprehensive Cross-Model Framework for Benchmarking the Performance of Quantum Hamiltonian Simulations
• Enhancing a Near-Term Quantum Accelerator's Instruction Set Architecture for Materials Science Applications
• Symmetric Clifford twirling for cost-optimal quantum error mitigation in early FTQC regime
• TE-PAI: Exact Time Evolution by Sampling Random Circuits
• Super-resolution of Green's functions on noisy quantum computers
• Quantum algorithm for the Vlasov simulation of the large-scale structure formation with massive neutrinos
• Differentiable quantum computational chemistry with PennyLane
• High Performance Computing and Computational Intelligence Applications with MultiChaos Perspective
• Quantum Algorithm for Estimating Betti Numbers Using Cohomology Approach
• Trotterization is substantially efficient for low-energy states
• Quantum computing quantum Monte Carlo algorithm
• Theory of Quantum Path Computing with Fourier Optics and Future Applications for Quantum Supremacy, Neural Networks and Nonlinear Schrödinger Equations
• Adaptive variational quantum computing approaches for Green's functions and nonlinear susceptibilities
• Quantum simulation of time-dependent Hamiltonians via commutator-free quasi-Magnus operators
• Uniform observable error bounds of Trotter formulae for the semiclassical Schrödinger equation
• Simulating Non-Markovian Dynamics in Multidimensional Electronic Spectroscopy via Quantum Algorithm
• Statistics of topological defects across a phase transition in a digital superconducting quantum processor
• Fault-tolerant simulation of Lattice Gauge Theories with gauge covariant codes
• Universal quantum processors in spin systems via robust local pulse sequences
• Tensor Network enhanced Dynamic Multiproduct Formulas
• Quantum Extremal Learning
• Partitioned Quantum Subspace Expansion
• Mixed-Dimensional Qudit State Preparation Using Edge-Weighted Decision Diagrams
• Error mitigation and circuit division for early fault-tolerant quantum phase estimation
• General, efficient, and robust Hamiltonian engineering
• Going Beyond Gadgets: The Importance of Scalability for Analogue Quantum Simulators
• Quantum walk processes in quantum devices
• Recipes for the Digital Quantum Simulation of Lattice Spin Systems
• Parallel-in-time quantum simulation via Page and Wootters quantum time
• Quantum Dissipative Search via Lindbladians
• Quantum Advantage in Variational Bayes Inference
• Infinite quantum signal processing for arbitrary Szegő functions
• Optimal compression of constrained quantum time evolution
• Unifying framework for quantum simulation algorithms for time-dependent Hamiltonian dynamics
• Quantum eigenvalue processing
• Quantum Computational Complexity and Symmetry
• Heisenberg-limited adaptive gradient estimation for multiple observables
• Efficiently verifiable quantum advantage on near-term analog quantum simulators
• Nonclassical correlations in subsystems of globally entangled quantum states
• The Electronic Structure of the Hydrogen Molecule: A Tutorial Exercise in Classical and Quantum Computation
• Clifford circuit based heuristic optimization of fermion-to-qubit mappings
• Approximating exponentials of commutators by optimized product formulas
• Digital simulation of convex mixtures of Markovian and non-Markovian single qubit Pauli channels on NISQ devices
• Cost of Emulating a Small Quantum Annealing Problem in the Circuit-Model
• Prospects for NMR Spectral Prediction on Fault-Tolerant Quantum Computers
• Performance and scaling analysis of variational quantum simulation
• High-precision and low-depth quantum algorithm design for eigenstate problems
• Theory of quantum error mitigation for non-Clifford gates
• A direct interferometric test of the nonlinear phase shift gate
• Quantum Calculation for Two-Stream Instability and Advection Test of Vlasov-Maxwell Equations: Numerical Evaluation of Hamiltonian Simulation
• Faster Algorithmic Quantum and Classical Simulations by Corrected Product Formulas
• Platform tailored co-design of gate-based quantum simulation
• Evolved Quantum Boltzmann Machines
• Space-time tradeoff in networked virtual distillation
• Phase estimation with partially randomized time evolution
• Simulating quantum collision models with Hamiltonian simulations using early fault-tolerant quantum computers
• Digital Quantum Simulation of the Lindblad Master Equation and Its Nonlinear Extensions via Quantum Trajectory Averaging
• On the Trotter Error in Many-body Quantum Dynamics with Coulomb Potentials
• Scalable Quantum Computational Science: A Perspective from Block-Encodings and Polynomial Transformations
• Digital Simulation of Single Qubit Markovian Open Quantum Systems: A Tutorial
• Batched quantum state exponentiation and quantum Hebbian learning
• Simulating quantum dynamics: Evolution of algorithms in the HPC context
• Variational Quantum Algorithms for Gibbs State Preparation
• A Fractional Calculus Framework for Open Quantum Dynamics: From Liouville to Lindblad to Memory Kernels
• Sample-size-reduction of quantum states for the noisy linear problem
• Efficient Online Quantum Circuit Learning with No Upfront Training
• Halving the cost of quantum multiplexed rotations
• Hybrid quantum gap estimation algorithm using a filtered time series
• Correcting and extending Trotterized quantum many-body dynamics
• Gibbs state sampling via cluster expansions
• Quantum Regularized Least Squares Solver with Parameter Estimate
• Quantum natural gradient with thermal-state initialization
• Trotter error time scaling separation via commutant decomposition
• Efficient Berry Phase Calculation via Adaptive Variational Quantum Computing Approach
• Natural gradient and parameter estimation for quantum Boltzmann machines
• Quantum Chaos and Universal Trotterisation Behaviours in Digital Quantum Simulations
• Quantum Algorithm for a Convergent Series of Approximations towards the Exact Solution of the Lowest Eigenstates of a Hamiltonian
• Efficient quantum simulation for translationally invariant systems
• Quantum Encoding of Structured Data with Matrix Product States
• Quantum Simulation via Stochastic Combination of Unitaries
• Co-Designing Spectral Transformation Oracles with Hybrid Oscillator-Qubit Quantum Processors: From Algorithms to Compilation
• Accelerated spin-adapted ground state preparation with non-variational quantum algorithms
• Benchmarking fault-tolerant quantum computing hardware via QLOPS
• Quantum Imaginary-Time Evolution with Polynomial Resources in Evolution Time
• Constrained free energy minimization for the design of thermal states and stabilizer thermodynamic systems
• Transversal architecture for megaquop-scale quantum simulation with neutral atoms
• Optimal Hamiltonian recognition of unknown quantum dynamics
• Error Interference in Quantum Simulation
• Experimental Demonstration of Efficient High-dimensional Quantum Gates with Orbital Angular Momentum
• Non-normality and dissipation in Markovian quantum dynamics: Implications for quantum simulation
• Diagonal-Budgeted Trotterization for Efficient Quantum Hamiltonian Simulation
• Optimising Trotter-Suzuki Simulations of Markovian Open Quantum Systems via Classical Search