Fragmented imaginary-time evolution for early-stage quantum signal processors

Abstract

Simulating quantum imaginary-time evolution (QITE) is a major promise of quantum computation. However, the known algorithms are either probabilistic (repeat until success) with impractically small success probabilities or coherent (quantum amplitude amplification) but with circuit depths and ancillary-qubit numbers unrealistically large in the mid term. Our main contribution is a new generation of deterministic, high-precision QITE algorithms significantly more amenable experimentally. These are based on a surprisingly simple idea: partitioning the evolution into several fragments that are sequentially run probabilistically. This causes a huge reduction in wasted circuit depth every time a run fails. Indeed, the resulting overall runtime is asymptotically better than in coherent approaches and the hardware requirements even milder than in probabilistic ones, remarkably. More technically, we present two QITE-circuit sub-routines with excellent complexity scalings. One of them is optimal in ancillary-qubit overhead (one single ancillary qubit throughout) whereas the other one is optimal in runtime for small inverse temperature or high precision. The latter is shown by noting that the runtime saturates a cooling-speed limit that is the imaginary-time counterpart of the no fast-forwarding theorem of real-time simulations, which we prove. Moreover, we also make two technical contributions to the quantum signal processing formalism for operator-function synthesis (on which our sub-routines are based) that are useful beyond QITE. Our findings are specially relevant for the early fault-tolerance stages of quantum hardware.

arXiv commentFull rigorous proof that fragmented QITE outperforms coherent QITE for general Hamiltonians added

References in corpus (41)

• Quantum Machine Learning
• A variational eigenvalue solver on a quantum processor
• Quantum Amplitude Amplification and Estimation
• An adaptive variational algorithm for exact molecular simulations on a quantum computer
• Hamiltonian Simulation by Qubitization
• Optimal Hamiltonian Simulation by Quantum Signal Processing
• Simulating Hamiltonian dynamics with a truncated Taylor series
• Determining eigenstates and thermal states on a quantum computer using quantum imaginary time evolution
• Efficient quantum algorithms for simulating sparse Hamiltonians
• Quantum algorithm for systems of linear equations with exponentially improved dependence on precision
• Variational ansatz-based quantum simulation of imaginary time evolution
• Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics
• Quantum Approximate Optimization of Non-Planar Graph Problems on a Planar Superconducting Processor
• Hamiltonian simulation with nearly optimal dependence on all parameters
• A random compiler for fast Hamiltonian simulation
• Quantum Metropolis Sampling
• Anderson localization casts clouds over adiabatic quantum optimization
• The Quantum Approximate Optimization Algorithm and the Sherrington-Kirkpatrick Model at Infinite Size
• Exponential improvement in precision for simulating sparse Hamiltonians
• Sampling from the thermal quantum Gibbs state and evaluating partition functions with a quantum computer
• A Limit on the Speed of Quantum Computation in Determining Parity
• Faster quantum simulation by randomization
• Tomography and Generative Data Modeling via Quantum Boltzmann Training
• Hardware-efficient variational quantum algorithms for time evolution
• A Quantum-Quantum Metropolis Algorithm
• Efficient phase-factor evaluation in quantum signal processing
• Variational Quantum Boltzmann Machines
• Implementation of quantum imaginary-time evolution method on NISQ devices: Nonlocal approximation
• Quantum SDP-Solvers: Better upper and lower bounds
• Efficient step-merged quantum imaginary time evolution algorithm for quantum chemistry
• Clustering of conditional mutual information for quantum Gibbs states above a threshold temperature
• Product Decomposition of Periodic Functions in Quantum Signal Processing
• One qubit as a Universal Approximant
• Low depth algorithms for quantum amplitude estimation
• Preparing thermal states of quantum systems by dimension reduction
• The Sherrington-Kirkpatrick model: an overview
• Efficient Quantum Walk Circuits for Metropolis-Hastings Algorithm
• Quantum imaginary time evolution steered by reinforcement learning
• Computing partition functions in the one clean qubit model
• Resource estimate for quantum many-body ground-state preparation on a quantum computer
• Fragmented imaginary-time evolution for early-stage quantum signal processors

Cited by in corpus (18)

• Fragmented imaginary-time evolution for early-stage quantum signal processors
• Quantum state preparation for multivariate functions
• Double-bracket quantum algorithms for quantum imaginary-time evolution
• Halving the Cost of Quantum Algorithms with Randomization
• First-quantized adiabatic time evolution for the ground state of a many-electron system and the optimal nuclear configuration
• Gate-based quantum simulation of Gaussian bosonic circuits on exponentially many modes
• Randomized semi-quantum matrix processing
• Exact block encoding of imaginary time evolution with universal quantum neural networks
• Quantum simulation of the phase transition of the massive Thirring model
• Double-bracket algorithm for quantum signal processing without post-selection
• Quantum circuits for partial differential equations in Fourier space
• Quantum many-body simulation of finite-temperature systems with sampling a series expansion of a quantum imaginary-time evolution
• Quantum Computing Beyond Ground State Electronic Structure: A Review of Progress Toward Quantum Chemistry Out of the Ground State
• Scalable Quantum Computational Science: A Perspective from Block-Encodings and Polynomial Transformations
• Gibbs state sampling via cluster expansions
• Role of Riemannian geometry in double-bracket quantum imaginary-time evolution
• Beyond asymptotic reasoning: the practicalities of a quantum ground state projector based on the wall-Chebyshev expansion
• Quantum Imaginary-Time Evolution with Polynomial Resources in Evolution Time