Qubit-Efficient Randomized Quantum Algorithms for Linear Algebra

Abstract

We propose a class of randomized quantum algorithms for the task of sampling from matrix functions, without the use of quantum block encodings or any other coherent oracle access to the matrix elements. As such, our use of qubits is purely algorithmic, and no additional qubits are required for quantum data structures. Our algorithms start from a classical data structure in which the matrix of interest is specified in the Pauli basis. For $N\times N$ Hermitian matrices, the space cost is $\log (N)+1$ qubits and depending on the structure of the matrices, the gate complexity can be comparable to state-of-the-art methods that use quantum data structures of up to size $O(N^2)$, when considering equivalent end-to-end problems. Within our framework, we present a quantum linear system solver that allows one to sample properties of the solution vector, as well as algorithms for sampling properties of ground states and Gibbs states of Hamiltonians. As a concrete application, we combine these sub-routines to present a scheme for calculating Green's functions of quantum many-body systems.

20+31 pages, 2+1 figures, 4 tables. Updated to published version

References in corpus (55)

• Quantum Computing in the NISQ era and beyond
• Quantum algorithm for solving linear systems of equations
• Variational Quantum Algorithms
• Noisy intermediate-scale quantum (NISQ) algorithms
• Improved Simulation of Stabilizer Circuits
• Quantum algorithms: an overview
• Quantum random access memory
• Hamiltonian Simulation by Qubitization
• Quantum algorithms for quantum chemistry and quantum materials science
• Simulating Hamiltonian dynamics with a truncated Taylor series
• Quantum algorithm for systems of linear equations with exponentially improved dependence on precision
• Recovering low-rank matrices from few coefficients in any basis
• 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
• Stim: a fast stabilizer circuit simulator
• Encoding Electronic Spectra in Quantum Circuits with Linear T Complexity
• Hamiltonian simulation with nearly optimal dependence on all parameters
• A random compiler for fast Hamiltonian simulation
• Quantum Metropolis Sampling
• Even more efficient quantum computations of chemistry through tensor hypercontraction
• Preconditioned quantum linear system algorithm
• Solving strongly correlated electron models on a quantum computer
• Hybrid quantum-classical approach to correlated materials
• Accelerated Variational Quantum Eigensolver
• Qubitization of Arbitrary Basis Quantum Chemistry Leveraging Sparsity and Low Rank Factorization
• Exponential improvement in precision for simulating sparse Hamiltonians
• Optimal Quantum Measurements of Expectation Values of Observables
• Heisenberg-limited ground state energy estimation for early fault-tolerant quantum computers
• Quantum algorithms for systems of linear equations inspired by adiabatic quantum computing
• Variational algorithms for linear algebra
• Near-optimal ground state preparation
• Faster quantum simulation by randomization
• Quantum State Preparation with Optimal Circuit Depth: Implementations and Applications
• Hardware-efficient quantum random access memory with hybrid quantum acoustic systems
• A Quantum-Quantum Metropolis Algorithm
• 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
• Quantum Power Method by a Superposition of Time-Evolved States
• A randomized quantum algorithm for statistical phase estimation
• Fast inversion, preconditioned quantum linear system solvers, and fast evaluation of matrix functions
• Fault tolerant resource estimation of quantum random-access memories
• Calculation of the Green's function on near-term quantum computers
• Quantum SDP-Solvers: Better upper and lower bounds
• Resilience of quantum random access memory to generic noise
• Quantum inverse iteration algorithm for programmable quantum simulators
• Computing Ground State Properties with Early Fault-Tolerant Quantum Computers
• An improved quantum-inspired algorithm for linear regression
• Few-qubit quantum-classical simulation of strongly correlated lattice fermions
• Non-linear quantum-classical scheme to simulate non-equilibrium strongly correlated fermionic many-body dynamics
• Construction of Green's functions on a quantum computer: applications to molecular systems
• Randomizing multi-product formulas for Hamiltonian simulation
• Quantum Circulant Preconditioner for Linear System of Equations
• Hamiltonian operator approximation for energy measurement and ground state preparation
• Exponentially faster implementations of Select(H) for fermionic Hamiltonians

Cited by in corpus (14)

• Implementing any Linear Combination of Unitaries on Intermediate-term Quantum Computers
• Fault-tolerant quantum algorithms for quantum molecular systems: A survey
• Continuous Hamiltonian dynamics on digital quantum computers without discretization error
• Quantum algorithm for linear non-unitary dynamics with near-optimal dependence on all parameters
• Quantum Computed Green's Functions using a Cumulant Expansion of the Lanczos Method
• In the shadow of the Hadamard test: Using the garbage state for good and further modifications
• Efficient ground-state energy estimation and certification on early fault-tolerant quantum computers
• Randomized semi-quantum matrix processing
• Quantum many-body simulation of finite-temperature systems with sampling a series expansion of a quantum imaginary-time evolution
• High-precision and low-depth quantum algorithm design for eigenstate problems
• Expanding Hardware-Efficiently Manipulable Hilbert Space via Hamiltonian Embedding
• Simulating quantum collision models with Hamiltonian simulations using early fault-tolerant quantum computers
• Short-time simulation of quantum dynamics by Pauli measurements
• Recurrence in discrete-time quantum stochastic walks