Tight Bound for Estimating Expectation Values from a System of Linear Equations

Abstract

The System of Linear Equations Problem (SLEP) is specified by a complex invertible matrix $A$, the condition number $\kappa$ of $A$, a vector $b$, a Hermitian matrix $M$ and an accuracy $\epsilon$, and the task is to estimate $x^{†}Mx$, where $x$ is the solution vector to the equation $Ax=b$. We aim to establish a lower bound on the complexity of the end-to-end quantum algorithms for SLEP with respect to $\epsilon$, and devise a quantum algorithm that saturates this bound. To make lower bounds attainable, we consider query complexity in the setting in which a block encoding of $M$ is given, i.e., a unitary black box $U_M$ that contains $M/\alpha$ as a block for some $\alpha \in {\mathbb{R}}^{+}$. We show that the quantum query complexity for SLEP in this setting is $\Theta (\alpha /\epsilon )$. Our lower bound is established by reducing the problem of estimating the mean of a black box function to SLEP. Our $\Theta (\alpha /\epsilon )$ result tightens and proves the common assertion of polynomial accuracy dependence (poly$(1/\epsilon )$) for SLEP, and shows that improvement beyond linear dependence on accuracy is not possible if $M$ is provided via block encoding.

arXiv comment24 pages

References in corpus (23)

• Quantum Machine Learning
• Quantum algorithm for solving linear systems of equations
• Quantum support vector machine for big data classification
• Quantum principal component analysis
• Quantum fingerprinting
• Hamiltonian Simulation by Qubitization
• Efficient quantum algorithms for simulating sparse Hamiltonians
• Quantum algorithm for systems of linear equations with exponentially improved dependence on precision
• Quantum Data Fitting
• A Theory of Trotter Error
• Hamiltonian simulation with nearly optimal dependence on all parameters
• High-order quantum algorithm for solving linear differential equations
• Efficient quantum algorithm for dissipative nonlinear differential equations
• Exponential improvement in precision for simulating sparse Hamiltonians
• Optimal Quantum Measurements of Expectation Values of Observables
• Iterative Quantum Amplitude Estimation
• Quantum algorithms and the finite element method
• Sampling-based sublinear low-rank matrix arithmetic framework for dequantizing quantum machine learning
• Simulating Quantum Dynamics On A Quantum Computer
• The power of block-encoded matrix powers: improved regression techniques via faster Hamiltonian simulation
• Quantum Algorithms for Estimating Physical Quantities using Block-Encodings
• Nearly Optimal Quantum Algorithm for Estimating Multiple Expectation Values
• Variational quantum eigensolvers for sparse Hamiltonians

Cited by in corpus (5)

• Hamiltonian simulation for hyperbolic partial differential equations by scalable quantum circuits
• Quantum algorithms for computing observables of nonlinear partial differential equations
• Quantum and classical query complexities of functions of matrices
• The matrix permanent and determinant from a spin system
• Quantum Computation