Halving the Cost of Quantum Algorithms with Randomization

Abstract

Quantum signal processing (QSP) provides a systematic framework for implementing a polynomial transformation of a linear operator, and unifies nearly all known quantum algorithms. In parallel, recent works have developed randomized compiling, a technique that promotes a unitary gate to a quantum channel and enables a quadratic suppression of error (i.e., $\epsilon \to O({\epsilon }^2)$) at little to no overhead. Here we integrate randomized compiling into QSP through Stochastic Quantum Signal Processing. Our algorithm implements a probabilistic mixture of polynomials, strategically chosen so that the average evolution converges to that of a target function, with an error quadratically smaller than that of an equivalent individual polynomial. Because nearly all QSP-based algorithms exhibit query complexities scaling as $O(\log (1/\epsilon ))$ -- stemming from a result in functional analysis -- this error suppression reduces their query complexity by a factor that asymptotically approaches $1/2$. By the unifying capabilities of QSP, this reduction extends broadly to quantum algorithms, which we demonstrate on algorithms for real and imaginary time evolution, phase estimation, ground state preparation, and matrix inversion.

References in corpus (38)

• Supplementary information for "Quantum supremacy using a programmable superconducting processor"
• Randomized Benchmarking of Quantum Gates
• Hamiltonian Simulation by Qubitization
• Optimal Hamiltonian Simulation by Quantum Signal Processing
• Simulating Hamiltonian dynamics with a truncated Taylor series
• 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
• Noise tailoring for scalable quantum computation via randomized compiling
• Random Quantum Circuits
• Hamiltonian simulation with nearly optimal dependence on all parameters
• Evenly distributed unitaries: on the structure of unitary designs
• The randomized measurement toolbox
• A random compiler for fast Hamiltonian simulation
• Random Quantum Circuits are Approximate 2-designs
• Local random quantum circuits are approximate polynomial-designs
• Probabilistic error cancellation with sparse Pauli-Lindblad models on noisy quantum processors
• Exponential improvement in precision for simulating sparse Hamiltonians
• Heisenberg-limited ground state energy estimation for early fault-tolerant quantum computers
• Near-optimal ground state preparation
• Faster quantum simulation by randomization
• Efficient phase-factor evaluation in quantum signal processing
• Ground state preparation and energy estimation on early fault-tolerant quantum computers via quantum eigenvalue transformation of unitary matrices
• Optimal polynomial based quantum eigenstate filtering with application to solving quantum linear systems
• Early Fault-Tolerant Quantum Computing
• A randomized quantum algorithm for statistical phase estimation
• Fast inversion, preconditioned quantum linear system solvers, and fast evaluation of matrix functions
• Product Decomposition of Periodic Functions in Quantum Signal Processing
• Shorter gate sequences for quantum computing by mixing unitaries
• Compilation by stochastic Hamiltonian sparsification
• qSWIFT: High-order randomized compiler for Hamiltonian simulation
• Stable factorization for phase factors of quantum signal processing
• Fragmented imaginary-time evolution for early-stage quantum signal processors
• Efficient quantum imaginary time evolution by drifting real time evolution: an approach with low gate and measurement complexity
• Doubling Efficiency of Hamiltonian Simulation via Generalized Quantum Signal Processing
• Doubling the order of approximation via the randomized product formula
• Probabilistic state synthesis based on optimal convex approximation
• Randomized semi-quantum matrix processing
• Probabilistic unitary synthesis with optimal accuracy

Cited by in corpus (4)

• Scalable Quantum Computational Science: A Perspective from Block-Encodings and Polynomial Transformations
• Quantum Computing Beyond Ground State Electronic Structure: A Review of Progress Toward Quantum Chemistry Out of the Ground State
• Parallel Quantum Signal Processing Via Polynomial Factorization
• An adversary bound for quantum signal processing