TE-PAI: Exact Time Evolution by Sampling Random Circuits

Abstract

Simulating time evolution under quantum Hamiltonians is one of the most natural applications of quantum computers. We introduce TE-PAI, which simulates time evolution exactly by sampling random quantum circuits for the purpose of estimating observable expectation values at the cost of an increased circuit repetition. The approach builds on the Probabilistic Angle Interpolation (PAI) technique and we prove that it simulates time evolution without discretisation or algorithmic error while achieving shallow circuit depths with optimal scaling that saturates the Lieb-Robinson bound. Another significant advantage of TE-PAI is that it only requires executing random circuits that consist of Pauli rotation gates of only two kinds of rotation angles $\pm \Delta$ and $\pi$, along with measurements. While TE-PAI is highly beneficial for NISQ devices, we additionally develop an optimised early fault-tolerant implementation using catalyst circuits and repeat-until-success teleportation, concluding that the approach requires orders of magnitude fewer T-states than conventional techniques, such as Trotterization -- we estimate $3\times 10^5$ T states are sufficient for the fault-tolerant simulation of a $100$-qubit Heisenberg spin Hamiltonian. Furthermore, TE-PAI allows for a highly configurable trade-off between circuit depth and measurement overhead by adjusting the rotation angle $\Delta$ arbitrarily. We expect that the approach will be a major enabler in the late NISQ and early fault-tolerant periods as it can compensate circuit-depth and qubit-number limitations through an increased circuit repetition.

23 pages, 13 figures

References in corpus (42)

• Quantum computational chemistry
• The Magnus expansion and some of its applications
• Predicting Many Properties of a Quantum System from Very Few Measurements
• Many-body localization edge in the random-field Heisenberg chain
• Hamiltonian Simulation by Qubitization
• Quantum algorithms for quantum chemistry and quantum materials science
• Optimal Hamiltonian Simulation by Quantum Signal Processing
• Simulating Hamiltonian dynamics with a truncated Taylor series
• Elucidating Reaction Mechanisms on Quantum Computers
• Quantum Error Mitigation
• 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
• On the relationship between continuous- and discrete-time quantum walk
• A random compiler for fast Hamiltonian simulation
• Even more efficient quantum computations of chemistry through tensor hypercontraction
• Halving the cost of quantum addition
• QuEST and High Performance Simulation of Quantum Computers
• Exponential improvement in precision for simulating sparse Hamiltonians
• Heisenberg-limited ground state energy estimation for early fault-tolerant quantum computers
• Efficient quantum measurement of Pauli operators in the presence of finite sampling error
• Improved Fault-Tolerant Quantum Simulation of Condensed-Phase Correlated Electrons via Trotterization
• Efficient synthesis of universal Repeat-Until-Success circuits
• Efficient magic state factories with a catalyzed |CCZ> to 2|T> transformation
• Quantum algorithm for simulating real time evolution of lattice Hamiltonians
• Time-dependent Hamiltonian simulation with $L^1$-norm scaling
• A randomized quantum algorithm for statistical phase estimation
• Simulating the dynamics of time-dependent Hamiltonians with a truncated Dyson series
• Quantum algorithm for ground state energy estimation using circuit depth with exponentially improved dependence on precision
• Efficient synthesis of probabilistic quantum circuits with fallback
• Compilation by stochastic Hamiltonian sparsification
• QuESTlink -- Mathematica embiggened by a hardware-optimised quantum emulator
• Simultaneous estimation of multiple eigenvalues with short-depth quantum circuit on early fault-tolerant quantum computers
• Time-dependent Hamiltonian Simulation of Highly Oscillatory Dynamics and Superconvergence for Schrödinger Equation
• Quantum Error Mitigated Classical Shadows
• Accelerated quantum Monte Carlo with mitigated error on noisy quantum computer
• Shorter quantum circuits via single-qubit gate approximation
• Probabilistic Interpolation of Quantum Rotation Angles
• Optimal quantum circuit cuts with application to clustered Hamiltonian simulation
• Algorithmic Shadow Spectroscopy
• Can shallow quantum circuits scramble local noise into global white noise?
• Sparse Probabilistic Synthesis of Quantum Operations

Cited by in corpus (5)

• Exponential distillation of dominant eigenproperties
• Phase estimation with partially randomized time evolution
• Space-time tradeoff in networked virtual distillation
• Simulating sparse SYK model with a randomized algorithm on a trapped-ion quantum computer
• Nontrivial multi-product commutation relation toward reducing T-count in sequential Pauli-based computation