Fast-forwarding quantum evolution

Abstract

We investigate the problem of fast-forwarding quantum evolution, whereby the dynamics of certain quantum systems can be simulated with gate complexity that is sublinear in the evolution time. We provide a definition of fast-forwarding that considers the model of quantum computation, the Hamiltonians that induce the evolution, and the properties of the initial states. Our definition accounts for any asymptotic complexity improvement of the general case and we use it to demonstrate fast-forwarding in several quantum systems. In particular, we show that some local spin systems whose Hamiltonians can be taken into block diagonal form using an efficient quantum circuit, such as those that are permutation-invariant, can be exponentially fast-forwarded. We also show that certain classes of positive semidefinite local spin systems, also known as frustration-free, can be polynomially fast-forwarded, provided the initial state is supported on a subspace of sufficiently low energies. Last, we show that all quadratic fermionic systems and number-conserving quadratic bosonic systems can be exponentially fast-forwarded in a model where quantum gates are exponentials of specific fermionic or bosonic operators, respectively. Our results extend the classes of physical Hamiltonians that were previously known to be fast-forwarded, while not necessarily requiring methods that diagonalize the Hamiltonians efficiently. We further develop a connection between fast-forwarding and precise energy measurements that also accounts for polynomial improvements.

arXiv comment26 + 5 pages, 14 figures, accepted in Quantum

References in corpus (36)

• Quantum algorithm for solving linear systems of equations
• Quantum Algorithms Revisited
• Hamiltonian Simulation by Qubitization
• Optimal Hamiltonian Simulation by Quantum Signal Processing
• Simulating Hamiltonian dynamics with a truncated Taylor series
• Efficient quantum algorithms for simulating sparse Hamiltonians
• Quantum algorithm for systems of linear equations with exponentially improved dependence on precision
• Quantum Algorithms for Quantum Field Theories
• Quantum measurements and the Abelian Stabilizer Problem
• Quantum Simulation of Electronic Structure with Linear Depth and Connectivity
• On the relationship between continuous- and discrete-time quantum walk
• Hamiltonian simulation with nearly optimal dependence on all parameters
• Simulating Physical Phenomena by Quantum Networks
• A random compiler for fast Hamiltonian simulation
• Symmetrizing Evolutions
• Variational Fast Forwarding for Quantum Simulation Beyond the Coherence Time
• Exponential improvement in precision for simulating sparse Hamiltonians
• Optimal Quantum Measurements of Expectation Values of Observables
• Quantum circuits for strongly correlated quantum systems
• Efficient Quantum Circuits for Schur and Clebsch-Gordan Transforms
• Higher Order Decompositions of Ordered Operator Exponentials
• Quantum algorithms to simulate many-body physics of correlated fermions
• Time-dependent Hamiltonian simulation with $L^1$-norm scaling
• Hamiltonian simulation in the low-energy subspace
• Fast-forwarding of Hamiltonians and Exponentially Precise Measurements
• Faster Digital Quantum Simulation by Symmetry Protection
• Fixed Depth Hamiltonian Simulation via Cartan Decomposition
• Nearly tight Trotterization of interacting electrons
• The Quantum Alternating Operator Ansatz on Maximum k-Vertex Cover
• Numerical Contraction of the Tensor Network generated by the Algebraic Bethe Ansatz
• The Algebraic Bethe Ansatz and Tensor Networks
• Spectral Gap Amplification
• Efficient solvability of Hamiltonians and limits on the power of some quantum computational models
• The Quantum Schur Transform: I. Efficient Qudit Circuits
• Quantum Computation, Complexity, and Many-Body Physics
• Quantum circuit synthesis for generalized coherent states

Cited by in corpus (12)

• Ground state preparation and energy estimation on early fault-tolerant quantum computers via quantum eigenvalue transformation of unitary matrices
• Provably accurate simulation of gauge theories and bosonic systems
• Fixed Depth Hamiltonian Simulation via Cartan Decomposition
• Algebraic Compression of Quantum Circuits for Hamiltonian Evolution
• Efficient classical algorithms for simulating symmetric quantum systems
• On the complexity of implementing Trotter steps
• Numerical Evidence for Exponential Speed-up of QAOA over Unstructured Search for Approximate Constrained Optimization
• Importance sampling for stochastic quantum simulations
• What the foundations of quantum computer science teach us about chemistry
• Quantum differential equation solvers: limitations and fast-forwarding
• Parallel Quantum Algorithm for Hamiltonian Simulation
• Faster spectral density calculation using energy moments