Hamiltonian simulation with nearly optimal dependence on all parameters
arXiv:1501.01715 · doi:10.1109/FOCS.2015.54
Abstract
We present an algorithm for sparse Hamiltonian simulation whose complexity is optimal (up to log factors) as a function of all parameters of interest. Previous algorithms had optimal or near-optimal scaling in some parameters at the cost of poor scaling in others. Hamiltonian simulation via a quantum walk has optimal dependence on the sparsity at the expense of poor scaling in the allowed error. In contrast, an approach based on fractional-query simulation provides optimal scaling in the error at the expense of poor scaling in the sparsity. Here we combine the two approaches, achieving the best features of both. By implementing a linear combination of quantum walk steps with coefficients given by Bessel functions, our algorithm's complexity (as measured by the number of queries and 2-qubit gates) is logarithmic in the inverse error, and nearly linear in the product of the evolution time, the sparsity, and the magnitude of the largest entry of the Hamiltonian. Our dependence on the error is optimal, and we prove a new lower bound showing that no algorithm can have sublinear dependence on .
arXiv comment21 pages, corrects minor error in Lemma 7 in FOCS version
References in corpus (15)
- Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
- Quantum algorithm for solving linear systems of equations
- Exponential algorithmic speedup by quantum walk
- Simulating Hamiltonian dynamics with a truncated Taylor series
- Synthesis of Quantum Logic Circuits
- Efficient quantum algorithms for simulating sparse Hamiltonians
- On the relationship between continuous- and discrete-time quantum walk
- Quantum simulation of time-dependent Hamiltonians and the convenient illusion of Hilbert space
- Exponential improvement in precision for simulating sparse Hamiltonians
- A Limit on the Speed of Quantum Computation in Determining Parity
- Quantum query complexity of state conversion
- Simulating Quantum Dynamics On A Quantum Computer
- A Quantum Algorithm for the Hamiltonian NAND Tree
- Discrete-query quantum algorithm for NAND trees
- Symmetry-assisted adversaries for quantum state generation
Cited by in corpus (199)
- Quantum computational chemistry
- Quantum Chemistry in the Age of Quantum Computing
- Quantum algorithms: an overview
- Hamiltonian Simulation by Qubitization
- Quantum algorithms for quantum chemistry and quantum materials science
- Optimal Hamiltonian Simulation by Quantum Signal Processing
- Determining eigenstates and thermal states on a quantum computer using quantum imaginary time evolution
- Quantum algorithm for systems of linear equations with exponentially improved dependence on precision
- Toward the first quantum simulation with quantum speedup
- Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics
- A Theory of Trotter Error
- Quantum speedup of Monte Carlo methods
- Variational Quantum Linear Solver
- Quantum algorithms and the finite element method
- Heisenberg-limited ground state energy estimation for early fault-tolerant quantum computers
- Nearly optimal lattice simulation by product formulas
- Emerging quantum computing algorithms for quantum chemistry
- Standard Model Physics and the Digital Quantum Revolution: Thoughts about the Interface
- Near-optimal ground state preparation
- Faster quantum simulation by randomization
- Quantum Algorithm for Simulating the Wave Equation
- Efficient phase-factor evaluation in quantum signal processing
- Quantum Algorithm for Linear Regression
- Quantum algorithm for simulating real time evolution of lattice Hamiltonians
- Noisy intermediate-scale quantum computers
- Applications of Near-Term Photonic Quantum Computers: Software and Algorithms
- Quantum Complexity of Time Evolution with Chaotic Hamiltonians
- Grover Mixers for QAOA: Shifting Complexity from Mixer Design to State Preparation
- Black-box quantum state preparation without arithmetic
- Quantum Simulation of Quantum Field Theory in the Light-Front Formulation
- Time-dependent Hamiltonian simulation with -norm scaling
- Sampling-based sublinear low-rank matrix arithmetic framework for dequantizing quantum machine learning
- Optimal polynomial based quantum eigenstate filtering with application to solving quantum linear systems
- Linear Response on a Quantum Computer
- Lowering qubit requirements for quantum simulations of fermionic systems
- Digital Quantum Simulation, Trotter Errors, and Quantum Chaos of the Kicked Top
- Universal Quantum Hamiltonians
- Biology and medicine in the landscape of quantum advantages
- Quantum SDP-Solvers: Better upper and lower bounds
- Hamiltonian Simulation with Optimal Sample Complexity
- Quantum algorithm for association rules mining
- Quantum algorithm for association rules mining
- Product Decomposition of Periodic Functions in Quantum Signal Processing
- Linear combination of Hamiltonian simulation for nonunitary dynamics with optimal state preparation cost
- Quantum algorithm for calculating molecular vibronic spectra
- Concrete resource analysis of the quantum linear system algorithm used to compute the electromagnetic scattering cross section of a 2D target
- Quantum Simulation of the Sachdev-Ye-Kitaev Model by Asymmetric Qubitization
- Concentration for random product formulas
- Hamiltonian Simulation Algorithms for Near-Term Quantum Hardware
- Simulating the dynamics of time-dependent Hamiltonians with a truncated Dyson series
- Time-dependent unbounded Hamiltonian simulation with vector norm scaling
- Time-marching based quantum solvers for time-dependent linear differential equations
- Bayesian Deep Learning on a Quantum Computer
- Nearly tight Trotterization of interacting electrons
- Quantum linear systems algorithms: a primer
- Quantum Algorithms for Estimating Physical Quantities using Block-Encodings
- Simulating Hadronic Physics on NISQ devices using Basis Light-Front Quantization
- Centrality measure based on continuous-time quantum walks and experimental realization
- Review on Quantum Walk Computing: Theory, Implementation, and Application
- Enhancing the Quantum Linear Systems Algorithm using Richardson Extrapolation
- Experimental quantum processing enhancement in modelling stochastic processes
- Practical Quantum Computing: solving the wave equation using a quantum approach
- Block-encoding structured matrices for data input in quantum computing
- Hybrid quantum algorithms for flow problems
- Fast-forwarding quantum evolution
- Variational quantum eigensolvers for sparse Hamiltonians
- Machine learning \& artificial intelligence in the quantum domain
- Hamiltonian Simulation by Uniform Spectral Amplification
- Randomizing multi-product formulas for Hamiltonian simulation
- First-Order Trotter Error from a Second-Order Perspective
- Quantum phase estimation for a class of generalized eigenvalue problems
- Time-dependent Hamiltonian Simulation of Highly Oscillatory Dynamics and Superconvergence for Schrödinger Equation
- Finding Angles for Quantum Signal Processing with Machine Precision
- Quantum Computing for Fusion Energy Science Applications
- Optimal (controlled) quantum state preparation and improved unitary synthesis by quantum circuits with any number of ancillary qubits
- Random circuit block-encoded matrix and a proposal of quantum LINPACK benchmark
- FABLE: Fast Approximate Quantum Circuits for Block-Encodings
- Approximate Quantum Circuit Synthesis using Block-Encodings
- New Quantum Algorithms for Computing Quantum Entropies and Distances
- Quantum Computing: Lecture Notes
- Implementing any Linear Combination of Unitaries on Intermediate-term Quantum Computers
- Efficient quantum circuits for Szegedy quantum walks
- Quantum processing by remote quantum control
- Combinatorial Optimization on Gate Model Quantum Computers: A Survey
- Symmetry breaking/symmetry preserving circuits and symmetry restoration on quantum computers: A quantum many-body perspective
- Efficient Quantum Algorithms for Simulating Lindblad Evolution
- Superdiffusive quantum stochastic walk definable of arbitrary directed graph
- Efficient simulation of sparse Markovian quantum dynamics
- An Algebraic Quantum Circuit Compression Algorithm for Hamiltonian Simulation
- Fast Black-Box Quantum State Preparation
- State preparation and measurement in a quantum simulation of the O(3) sigma model
- Hybrid Oscillator-Qubit Quantum Processors: Instruction Set Architectures, Abstract Machine Models, and Applications
- Quantum Circuits for partial differential equations via Schrödingerisation
- Toward simulating Superstring/M-theory on a quantum computer
- A quantum hamiltonian simulation benchmark
- Fragmented imaginary-time evolution for early-stage quantum signal processors
- Composite Quantum Simulations
- Wave Matrix Lindbladization I: Quantum Programs for Simulating Markovian Dynamics
- Quantum Speed-ups for Semidefinite Programming
- Qubit-Efficient Randomized Quantum Algorithms for Linear Algebra
- Efficient quantum circuits for continuous-time quantum walks on composite graphs
- Simulating nonnative cubic interactions on noisy quantum machines
- Tailoring Term Truncations for Electronic Structure Calculations Using a Linear Combination of Unitaries
- Fault-tolerant quantum algorithms for quantum molecular systems: A survey
- Quantum Simulation of Second-Quantized Hamiltonians in Compact Encoding
- Quantum linear system solver based on time-optimal adiabatic quantum computing and quantum approximate optimization algorithm
- Spacetime-Efficient Low-Depth Quantum State Preparation with Applications
- Holographic fluctuations and the principle of minimal complexity
- Analysis of quantum Krylov algorithms with errors
- Quantum Gradient Algorithm for General Polynomials
- Pauli path simulations of noisy quantum circuits beyond average case
- QED driven QAOA for network-flow optimization
- Quantum differential equation solvers: limitations and fast-forwarding
- Optimal Hamiltonian simulation for time-periodic systems
- Encoding trade-offs and design toolkits in quantum algorithms for discrete optimization: coloring, routing, scheduling, and other problems
- Quantum Gaussian filter for exploring ground-state properties
- Effects of Cosine Tapering Window on Quantum Phase Estimation
- Complexity of Supersymmetric Systems and the Cohomology Problem
- Well-conditioned multiproduct Hamiltonian simulation
- Quantum Error Correction from Complexity in Brownian SYK
- Simple and high-precision Hamiltonian simulation by compensating Trotter error with linear combination of unitary operations
- Classical and Quantum Algorithms for Tensor Principal Component Analysis
- Quantum Merlin Arthur with Exponentially Small Gap
- Implementing smooth functions of a Hermitian matrix on a quantum computer
- Quantum algorithms for escaping from saddle points
- Asymptotically Optimal Circuit Depth for Quantum State Preparation and General Unitary Synthesis
- Parallel Quantum Algorithm for Hamiltonian Simulation
- Quantum algorithm for linear non-unitary dynamics with near-optimal dependence on all parameters
- Classical-Quantum Noise Mitigation for NISQ Hardware
- Selection and improvement of product formulae for best performance of quantum simulation
- Quantum simulation of discrete linear dynamical systems and simple iterative methods in linear algebra via Schrodingerisation
- Tight Bound for Estimating Expectation Values from a System of Linear Equations
- A quantum algorithm for simulating non-sparse Hamiltonians
- Fast quantum simulation of electronic structure by spectrum amplification
- An Improved Method for Quantum Matrix Multiplication
- Duality in Quantum Quenches and Classical Approximation Algorithms: Pretty Good or Very Bad
- Improved amplitude amplification strategies for the quantum simulation of classical transport problems
- Review of a Quantum Algorithm for Betti Numbers
- Graph Optimization Perspective for Low-Depth Trotter-Suzuki Decomposition
- Succinct Description and Efficient Simulation of Non-Markovian Open Quantum Systems
- Generalising quantum imaginary time evolution to solve linear partial differential equations
- Quantum Algorithms for Boolean Equation Solving and Quantum Algebraic Attack on Cryptosystems
- Quantum Finite Volume Method for Computational Fluid Dynamics with Classical Input and Output
- Halving the Cost of Quantum Algorithms with Randomization
- Polynomial Equivalence of Complexity Geometries
- Time-dependent Hamiltonian Simulation via Magnus Expansion: Algorithm and Superconvergence
- Quantum advantage from energy measurements of many-body quantum systems
- Translationally-Invariant Universal Quantum Hamiltonians in 1D
- Compressed variational quantum eigensolver for the Fermi-Hubbard model
- Quantum algorithms for powering stable Hermitian matrices
- Lower bound for simulation cost of open quantum systems: Lipschitz continuity approach
- Approximating Hamiltonian dynamics with the Nyström method
- Quantum Algorithm for Estimating Betti Numbers Using Cohomology Approach
- Molecular Properties from Quantum Krylov Subspace Diagonalization
- Ladder Operator Block-Encoding
- On the equivalence between quantum and random walks on finite graphs
- On estimating the entropy of shallow circuit outputs
- Going Beyond Gadgets: The Importance of Scalability for Analogue Quantum Simulators
- Quantum-Inspired Algorithms from Randomized Numerical Linear Algebra
- Modular quantum signal processing in many variables
- Toward simulating quantum field theories with controlled phonon-ion dynamics: A hybrid analog-digital approach
- Digital simulation of convex mixtures of Markovian and non-Markovian single qubit Pauli channels on NISQ devices
- Faster Coherent Quantum Algorithms for Phase, Energy, and Amplitude Estimation
- Empirical determination of the simulation capacity of a near-term quantum computer
- Heisenberg-limited adaptive gradient estimation for multiple observables
- Choco-Q: Commute Hamiltonian-based QAOA for Constrained Binary Optimization
- The Short Path Algorithm Applied to a Toy Model
- Quantum Register Machine: Efficient Implementation of Quantum Recursive Programs
- Quantum Simulation of Nonlinear Dynamical Systems Using Repeated Measurement
- Some Error Analysis for the Quantum Phase Estimation Algorithms
- Security of quantum position-verification limits Hamiltonian simulation via holography
- Efficient quantum circuits for dense and non-unitary operators
- Resource-Dependent Complexity of Quantum Channels
- Quantum simulation of quantum mechanical system with spatial noncommutativity
- Quantum Realization of the Finite Element Method
- Quantum and classical algorithms for nonlinear unitary dynamics
- Quantum Calculation for Two-Stream Instability and Advection Test of Vlasov-Maxwell Equations: Numerical Evaluation of Hamiltonian Simulation
- Universal Hamiltonians for Exponentially Long Simulation
- Parallel Quantum Signal Processing Via Polynomial Factorization
- Quantum implementation of non-unitary operations with biorthogonal representations
- A quantum algorithm for linear autonomous differential equations via Padé approximation
- Digital Simulation of Single Qubit Markovian Open Quantum Systems: A Tutorial
- Implications of Quantum Computing for Artificial Intelligence alignment research
- Quantum Machine Learning For Classical Data
- Quantum algorithms based on quantum trajectories
- Quantum Algorithm For Solving Nonlinear Algebraic Equations
- Fast algorithm for quantum polar decomposition, pretty-good measurements, and the Procrustes problem
- Unitarization Through Approximate Basis
- Improving quantum linear system solvers via a gradient descent perspective
- Benchmarking Quantum Simulators
- Quantum amplitude damping for solving homogeneous linear differential equations: A noninterferometric algorithm
- Quantum Merlin-Arthur proof systems for synthesizing quantum states
- Quantum Heaviside Eigen Solver
- Quantum Algorithm for a Convergent Series of Approximations towards the Exact Solution of the Lowest Eigenstates of a Hamiltonian
- Quantum memory assisted observable estimation
- Quantum Money from Quaternion Algebras
- Quantum Algorithm to Cubic Spline Interpolation
- An adversary bound for quantum signal processing
- Extremal jumps of circuit complexity of unitary evolutions generated by random Hamiltonians