Randomized semi-quantum matrix processing

Abstract

We present a hybrid quantum-classical framework for simulating generic matrix functions more amenable to early fault-tolerant quantum hardware than standard quantum singular-value transformations. The method is based on randomization over the Chebyshev approximation of the target function while keeping the matrix oracle quantum, and is assisted by a variant of the Hadamard test that removes the need for post-selection. The resulting statistical overhead is similar to the fully quantum case and does not incur any circuit depth degradation. On the contrary, the average circuit depth is shown to get smaller, yielding equivalent reductions in noise sensitivity, as explicitly shown for depolarizing noise and coherent errors. We apply our technique to partition-function estimation, linear system solvers, and ground-state energy estimation. For these cases, we prove advantages on average depths, including quadratic speed-ups on costly parameters and even the removal of the approximation-error dependence.

Accepted for publication in NPJ Quantum Information

References in corpus (37)

• Quantum algorithm for solving linear systems of equations
• Quantum computational chemistry
• The Kernel Polynomial Method
• Hamiltonian Simulation by Qubitization
• Optimal Hamiltonian Simulation by Quantum Signal Processing
• Elucidating Reaction Mechanisms on Quantum Computers
• Quantum algorithm for systems of linear equations with exponentially improved dependence on precision
• Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics
• A random compiler for fast Hamiltonian simulation
• Even more efficient quantum computations of chemistry through tensor hypercontraction
• Open-System Dynamics of Entanglement
• Is there evidence for exponential quantum advantage in quantum chemistry?
• A quantum linear system algorithm for dense matrices
• Qubitization of Arbitrary Basis Quantum Chemistry Leveraging Sparsity and Low Rank Factorization
• Sampling from the thermal quantum Gibbs state and evaluating partition functions with a quantum computer
• Heisenberg-limited ground state energy estimation for early fault-tolerant quantum computers
• Quantum algorithms for systems of linear equations inspired by adiabatic quantum computing
• Near-optimal ground state preparation
• Ground state preparation and energy estimation on early fault-tolerant quantum computers via quantum eigenvalue transformation of unitary matrices
• Efficient magic state factories with a catalyzed |CCZ> to 2|T> transformation
• The electronic complexity of the ground-state of the FeMo cofactor of nitrogenase as relevant to quantum simulations
• Preparing ground states of quantum many-body systems on a quantum computer
• Quantum Computation of Finite-Temperature Static and Dynamical Properties of Spin Systems Using Quantum Imaginary Time Evolution
• Fault-tolerant resource estimate for quantum chemical simulations: Case study on Li-ion battery electrolyte molecules
• A randomized quantum algorithm for statistical phase estimation
• Fast-forwarding of Hamiltonians and Exponentially Precise Measurements
• Quantum algorithm for ground state energy estimation using circuit depth with exponentially improved dependence on precision
• Towards near-term quantum simulation of materials
• Efficient Quantum Walk Circuits for Metropolis-Hastings Algorithm
• Block-encoding structured matrices for data input in quantum computing
• Quantum Resources Required to Block-Encode a Matrix of Classical Data
• On the complexity of quantum partition functions
• Computing partition functions in the one clean qubit model
• Fragmented imaginary-time evolution for early-stage quantum signal processors
• Qubit-Efficient Randomized Quantum Algorithms for Linear Algebra
• Postponing the orthogonality catastrophe: efficient state preparation for electronic structure simulations on quantum devices
• Partition Function Estimation: Quantum and Quantum-Inspired Algorithms

Cited by in corpus (4)

• Complete quantum-inspired framework for computational fluid dynamics
• Halving the Cost of Quantum Algorithms with Randomization
• Parallel Quantum Signal Processing Via Polynomial Factorization
• Quantum many-body simulation of finite-temperature systems with sampling a series expansion of a quantum imaginary-time evolution