Complexity of quantum state verification in the quantum linear systems problem

Abstract

We analyze the complexity of quantum state verification in the context of solving systems of linear equations of the form $A\vec{x}=\vec{b}$. We show that any quantum operation that verifies whether a given quantum state is within a constant distance from the solution of the quantum linear systems problem requires $q=\Omega (\kappa )$ uses of a unitary that prepares a quantum state $|b⟩$, proportional to $\vec{b}$, and its inverse in the worst case. Here, $\kappa$ is the condition number of the matrix $A$. For typical instances, we show that $q=\Omega (\sqrt{\kappa })$ with high probability. These lower bounds are almost achieved if quantum state verification is performed using known quantum algorithms for the quantum linear systems problem. We also analyze the number of copies of $|b⟩$ required by verification procedures of the prepare and measure type. In this case, the lower bounds are quadratically worse, being $\Omega ({\kappa }^2)$ in the worst case and $\Omega (\kappa )$ in typical instances with high probability. We discuss the implications of our results to known variational and related approaches to this problem, where state preparation, gate, and measurement errors will need to decrease rapidly with $\kappa$ for worst-case and typical instances if error correction is not used, and present some open problems.

arXiv comment15 pages, 3 figures, corrected typos, minor changes to presentation

References in corpus (21)

• Supplementary information for "Quantum supremacy using a programmable superconducting processor"
• Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
• A variational eigenvalue solver on a quantum processor
• Quantum Computing
• Quantum algorithm for solving linear systems of equations
• Quantum Simulation
• A Quantum Approximate Optimization Algorithm
• Strengths and Weaknesses of Quantum Computing
• Quantum fingerprinting
• Characterizing Quantum Supremacy in Near-Term Devices
• Quantum algorithm for systems of linear equations with exponentially improved dependence on precision
• Quantum Computation by Adiabatic Evolution
• Quantum-assisted quantum compiling
• Quantum algorithms for systems of linear equations inspired by adiabatic quantum computing
• Variational algorithms for linear algebra
• Quantum Simulations of Classical Annealing Processes
• Quantum Speedup by Quantum Annealing
• Efficient Verification of Pure Quantum States in the Adversarial Scenario
• Different Strategies for Optimization Using the Quantum Adiabatic Algorithm
• Near-term quantum algorithms for linear systems of equations
• Quantum linear system solver based on time-optimal adiabatic quantum computing and quantum approximate optimization algorithm

Cited by in corpus (10)

• Quantum Interior Point Methods for Semidefinite Optimization
• Quantum differential equation solvers: limitations and fast-forwarding
• Quantum Gram-Schmidt Processes and Their Application to Efficient State Read-out for Quantum Algorithms
• Qsun: an open-source platform towards practical quantum machine learning applications
• Accelerating Quantum Algorithms with Precomputation
• Quantum and classical query complexities of functions of matrices
• Noise tailoring for Robust Amplitude Estimation
• On solving classes of positive-definite quantum linear systems with quadratically improved runtime in the condition number
• Reducing runtime and error in VQE using deeper and noisier quantum circuits
• Quantum linear system algorithm with optimal queries to initial state preparation