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 (17)

• Quantum algorithm for solving linear systems of equations
• The Kernel Polynomial Method
• Even more efficient quantum computations of chemistry through tensor hypercontraction
• Is there evidence for exponential quantum advantage in quantum chemistry?
• Heisenberg-limited ground state energy estimation for early fault-tolerant quantum computers
• Ground state preparation and energy estimation on early fault-tolerant quantum computers via quantum eigenvalue transformation of unitary matrices
• 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
• Quantum algorithm for ground state energy estimation using circuit depth with exponentially improved dependence on precision
• Towards near-term quantum simulation of materials
• 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
• Fragmented imaginary-time evolution for early-stage quantum signal processors
• Qubit-Efficient Randomized Quantum Algorithms for Linear Algebra
• 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