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 (323)

• 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
• Resilience of quantum random access memory to generic noise
• Probing quantum processor performance with pyGSTi
• Hamiltonian Simulation Algorithms for Near-Term Quantum Hardware
• Multicore Quantum Computing
• Applying quantum algorithms to constraint satisfaction problems
• Time-dependent unbounded Hamiltonian simulation with vector norm scaling
• Benchmarking quantum computers
• Time-marching based quantum solvers for time-dependent linear differential equations
• Scalable algorithm simplification using quantum AND logic
• Nearly tight Trotterization of interacting electrons
• Simulating Open Quantum Systems Using Hamiltonian Simulations
• Quantum algorithm for visual tracking
• Evaluating energy differences on a quantum computer with robust phase estimation
• 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
• Near- and long-term quantum algorithmic approaches for vibrational spectroscopy
• Quantum Analytic Descent
• Circuit optimization of Hamiltonian simulation by simultaneous diagonalization of Pauli clusters
• Probing ground-state phase transitions through quench dynamics
• Simulating key properties of lithium-ion batteries with a fault-tolerant quantum computer
• Hamiltonian simulation with random inputs
• Quantum natural gradient generalised to noisy and non-unitary circuits
• Constant-depth preparation of matrix product states with adaptive quantum circuits
• Noise-assisted digital quantum simulation of open systems
• Circuit Transformations for Quantum Architectures
• General quantum algorithms for Hamiltonian simulation with applications to a non-Abelian lattice gauge theory
• Compilation by stochastic Hamiltonian sparsification
• Computing Ground State Properties with Early Fault-Tolerant Quantum Computers
• qTorch: The Quantum Tensor Contraction Handler
• Spectral density estimation with the Gaussian Integral Transform
• Hunting for quantum-classical crossover in condensed matter problems
• Variational Hamiltonian simulation for translational invariant systems via classical pre-processing
• Imaginary Time Propagation on a Quantum Chip
• Low cost quantum circuits for classically intractable instances of the Hamiltonian dynamics simulation problem
• First-Order Trotter Error from a Second-Order Perspective
• QuESTlink -- Mathematica embiggened by a hardware-optimised quantum emulator
• Randomizing multi-product formulas for Hamiltonian simulation
• Robust and Efficient Hamiltonian Learning
• Destructive Error Interference in Product-Formula Lattice Simulation
• Optimized Lie-Trotter-Suzuki decompositions for two and three non-commuting terms
• 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
• Preparing Bethe Ansatz Eigenstates on a Quantum Computer
• Quantum dynamics simulations beyond the coherence time on NISQ hardware by variational Trotter compression
• Quantum Error Mitigated Classical Shadows
• 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
• Quantum-centric computation of molecular excited states with extended sample-based quantum diagonalization
• Quantum simulation of exact electron dynamics can be more efficient than classical mean-field methods
• Implementing any Linear Combination of Unitaries on Intermediate-term Quantum Computers
• Perturbative quantum simulation
• 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
• Twist: Sound Reasoning for Purity and Entanglement in Quantum Programs
• Quantum time dynamics of 1D-Heisenberg models employing the Yang-Baxter equation for circuit compression
• Quantum Phase Processing and its Applications in Estimating Phase and Entropies
• Exact gate decompositions for photonic quantum computing
• A Sparse Model of Quantum Holography
• Quantum Simulation of Z2 Lattice Gauge theory with minimal resources
• Quantum simulation of real-space dynamics
• Efficient Product Formulas for Commutators and Applications to Quantum Simulation
• Resource-Optimized Fermionic Local-Hamiltonian Simulation on Quantum Computer for Quantum Chemistry
• Benchmarking variational quantum eigensolvers for the square-octagon-lattice Kitaev model
• Hamiltonian operator approximation for energy measurement and ground state preparation
• Training variational quantum circuits with CoVaR: covariance root finding with classical shadows
• Simulating Effective QED on Quantum Computers
• Gradient-descent quantum process tomography by learning Kraus operators
• qSWIFT: High-order randomized compiler for Hamiltonian simulation
• Robust Majorana magic gates via measurements
• Tower: Data Structures in Quantum Superposition
• Stable factorization for phase factors of quantum signal processing
• Variational Gibbs State Preparation on NISQ devices
• Observation of high-order Mollow triplet by quantum mode control with concatenated continuous driving
• Resource estimate for quantum many-body ground-state preparation on a quantum computer
• A quantum hamiltonian simulation benchmark
• Exact and approximate continuous-variable gate decompositions
• Trotter errors from dynamical structural instabilities of Floquet maps in quantum simulation
• Hamiltonian simulation with nearly optimal dependence on spectral norm
• High-Fidelity Magic-State Preparation with a Biased-Noise Architecture
• 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
• Efficient Hamiltonian Simulation for Solving Option Price Dynamics
• Entanglement accelerates quantum simulation
• Optimal quantum dataset for learning a unitary transformation
• Prethermal quasiconserved observables in Floquet quantum systems
• Digital quantum simulation of NMR experiments
• Synthesizing efficient circuits for Hamiltonian simulation
• Importance sampling for stochastic quantum simulations
• Tailoring Term Truncations for Electronic Structure Calculations Using a Linear Combination of Unitaries
• Exploiting fermion number in factorized decompositions of the electronic structure Hamiltonian
• Testing a quantum annealer as a quantum thermal sampler
• HamLib: A library of Hamiltonians for benchmarking quantum algorithms and hardware
• Short-depth circuits for efficient expectation value estimation
• Circuit complexity of quantum access models for encoding classical data
• Variational Quantum Optimization of Nonlocality in Noisy Quantum Networks
• Quantum computation of thermal averages in the presence of a sign problem
• Probabilistic Interpolation of Quantum Rotation Angles
• Fault-tolerant quantum algorithms for quantum molecular systems: A survey
• Spacetime-Efficient Low-Depth Quantum State Preparation with Applications
• Variational dynamics as a ground-state problem on a quantum computer
• Quantum computation of molecular structure using data from challenging-to-classically-simulate nuclear magnetic resonance experiments
• Quantum Simulations of Chemistry in First Quantization with any Basis Set
• State Preparation in the Heisenberg Model through Adiabatic Spiraling
• Quantum State Tomography with Conditional Generative Adversarial Networks
• Mitigating crosstalk errors by randomized compiling: Simulation of the BCS model on a superconducting quantum computer
• Variational quantum Gibbs state preparation with a truncated Taylor series
• Infinite quantum signal processing
• Quantum Topological Data Analysis with Linear Depth and Exponential Speedup
• 2QAN: A quantum compiler for 2-local qubit Hamiltonian simulation algorithms
• Quantum differential equation solvers: limitations and fast-forwarding
• Experimental implementation of quantum algorithm for association rules mining
• Variational Approach to Quantum State Tomography based on Maximal Entropy Formalism
• Average-case Speedup for Product Formulas
• A Perspective on Quantum Computing Applications in Quantum Chemistry using 25--100 Logical Qubits
• Exponentially faster implementations of Select(H) for fermionic Hamiltonians
• 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
• Algebraic Reasoning of Quantum Programs via Non-idempotent Kleene Algebra
• Doubling the order of approximation via the randomized product formula
• Well-conditioned multiproduct Hamiltonian simulation
• Power-optimal, stabilized entangling gate between trapped-ion qubits
• Algorithmic Shadow Spectroscopy
• ERASER: Towards Adaptive Leakage Suppression for Fault-Tolerant Quantum Computing
• Quantifying $T$-gate-count improvements for ground-state-energy estimation with near-optimal state preparation
• Dissipative variational quantum algorithms for Gibbs state preparation
• Simple and high-precision Hamiltonian simulation by compensating Trotter error with linear combination of unitary operations
• Optimized noise-assisted simulation of the Lindblad equation with time-dependent coefficients on a noisy quantum processor
• Quantum Algorithms for Testing Hamiltonian Symmetry
• Adiabatic quantum algorithm for artificial graphene
• Trotter error with commutator scaling for the Fermi-Hubbard model
• Digital quantum simulation framework for energy transport in an open quantum system
• Quantum algorithm for linear non-unitary dynamics with near-optimal dependence on all parameters
• Efficient and practical Hamiltonian simulation from time-dependent product formulas
• The T-Complexity Costs of Error Correction for Control Flow in Quantum Computation
• Simulating spectroscopy experiments with a superconducting quantum computer
• Early Fault-Tolerant Quantum Algorithms in Practice: Application to Ground-State Energy Estimation
• Parallel Quantum Algorithm for Hamiltonian Simulation
• Calculating the many-body density of states on a digital quantum computer
• Toward hybrid quantum simulations with qubits and qumodes on trapped-ion platforms
• Representation of the Fermionic Boundary Operator
• Digital quantum simulation of non-perturbative dynamics of open systems with orthogonal polynomials
• Quantum Control Machine: The Limits of Control Flow in Quantum Programming
• Higher-order quantum transformations of Hamiltonian dynamics
• Selection and improvement of product formulae for best performance of quantum simulation
• Limitations of Classically-Simulable Measurements for Quantum State Discrimination
• 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
• Two-dimensional coherent spectrum of high-spin models via a quantum computing approach
• 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
• Symmetric Clifford twirling for cost-optimal quantum error mitigation in early FTQC regime
• Lower Bounds for the Trotter Error
• Exploiting anticommutation in Hamiltonian simulation
• Bounding the finite-size error of quantum many-body dynamics simulations
• An invitation to the sample complexity of quantum hypothesis testing
• Enhancing a Near-Term Quantum Accelerator's Instruction Set Architecture for Materials Science Applications
• Differentiable quantum computational chemistry with PennyLane
• 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
• Fault-tolerant simulation of Lattice Gauge Theories with gauge covariant codes
• High Performance Computing and Computational Intelligence Applications with MultiChaos Perspective
• Quantum simulation of time-dependent Hamiltonians via commutator-free quasi-Magnus operators
• Quantum computing quantum Monte Carlo algorithm
• Simulating Non-Markovian Dynamics in Multidimensional Electronic Spectroscopy via Quantum Algorithm
• Trotterization is substantially efficient for low-energy states
• Universal quantum processors in spin systems via robust local pulse sequences
• Theory of Quantum Path Computing with Fourier Optics and Future Applications for Quantum Supremacy, Neural Networks and Nonlinear Schrödinger Equations
• Tensor Network enhanced Dynamic Multiproduct Formulas
• Statistics of topological defects across a phase transition in a digital superconducting quantum processor
• Adaptive variational quantum computing approaches for Green's functions and nonlinear susceptibilities
• Quantum Algorithm for Estimating Betti Numbers Using Cohomology Approach
• Uniform observable error bounds of Trotter formulae for the semiclassical Schrödinger equation
• Partitioned Quantum Subspace Expansion
• Quantum Advantage in Variational Bayes Inference
• Quantum Extremal Learning
• Going Beyond Gadgets: The Importance of Scalability for Analogue Quantum Simulators
• Infinite quantum signal processing for arbitrary Szegő functions
• Quantum walk processes in quantum devices
• Parallel-in-time quantum simulation via Page and Wootters quantum time
• Quantum Dissipative Search via Lindbladians
• 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
• Recipes for the Digital Quantum Simulation of Lattice Spin Systems
• Optimal compression of constrained quantum time evolution
• Heisenberg-limited adaptive gradient estimation for multiple observables
• Clifford circuit based heuristic optimization of fermion-to-qubit mappings
• Efficiently verifiable quantum advantage on near-term analog quantum simulators
• Quantum Computational Complexity and Symmetry
• The Electronic Structure of the Hydrogen Molecule: A Tutorial Exercise in Classical and Quantum Computation
• Nonclassical correlations in subsystems of globally entangled quantum states
• Quantum eigenvalue processing
• Unifying framework for quantum simulation algorithms for time-dependent Hamiltonian dynamics
• Approximating exponentials of commutators by optimized product formulas
• Cost of Emulating a Small Quantum Annealing Problem in the Circuit-Model
• Digital simulation of convex mixtures of Markovian and non-Markovian single qubit Pauli channels on NISQ devices
• Prospects for NMR Spectral Prediction on Fault-Tolerant Quantum Computers
• Performance and scaling analysis of variational quantum simulation
• 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
• High-precision and low-depth quantum algorithm design for eigenstate problems
• Efficient Berry Phase Calculation via Adaptive Variational Quantum Computing Approach
• Quantum Regularized Least Squares Solver with Parameter Estimate
• Gibbs state sampling via cluster expansions
• Variational Quantum Algorithms for Gibbs State Preparation
• A Fractional Calculus Framework for Open Quantum Dynamics: From Liouville to Lindblad to Memory Kernels
• Correcting and extending Trotterized quantum many-body dynamics
• Sample-size-reduction of quantum states for the noisy linear problem
• Quantum natural gradient with thermal-state initialization
• Trotter error time scaling separation via commutant decomposition
• Hybrid quantum gap estimation algorithm using a filtered time series
• Halving the cost of quantum multiplexed rotations
• Efficient Online Quantum Circuit Learning with No Upfront Training
• Experimental Demonstration of Efficient High-dimensional Quantum Gates with Orbital Angular Momentum
• Co-Designing Spectral Transformation Oracles with Hybrid Oscillator-Qubit Quantum Processors: From Algorithms to Compilation
• 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
• Natural gradient and parameter estimation for quantum Boltzmann machines
• Quantum Chaos and Universal Trotterisation Behaviours in Digital Quantum Simulations
• Optimal Hamiltonian recognition of unknown quantum dynamics
• Accelerated spin-adapted ground state preparation with non-variational quantum algorithms
• Quantum Algorithm for a Convergent Series of Approximations towards the Exact Solution of the Lowest Eigenstates of a Hamiltonian
• Quantum Simulation via Stochastic Combination of Unitaries
• 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
• Error Interference in Quantum Simulation
• Efficient quantum simulation for translationally invariant systems
• Transversal architecture for megaquop-scale quantum simulation with neutral atoms
• Quantum Encoding of Structured Data with Matrix Product States