Tight Quantum Depth Lower Bound for Solving Systems of Linear Equations

Abstract

Since Harrow, Hassidim, and Lloyd (2009) showed that a system of linear equations with $N$ variables and condition number $\kappa$ can be solved on a quantum computer in $\mathrm{poly}(\log (N),\kappa )$ time, exponentially faster than any classical algorithms, its improvements and applications have been extensively investigated. The state-of-the-art quantum algorithm for this problem is due to Costa, An, Sanders, Su, Babbush, and Berry (2022), with optimal query complexity $\Theta (\kappa )$. An important question left is whether parallelism can bring further optimization. In this paper, we study the limitation of parallel quantum computing on this problem. We show that any quantum algorithm for solving systems of linear equations with time complexity $\mathrm{poly}(\log (N),\kappa )$ has a lower bound of $\Omega (\kappa )$ on the depth of queries, which is tight up to a constant factor.

arXiv commentMinor corrections to references in [v1]. 22 pages, 1 table. Close to the official version

References in corpus (24)

• Quantum Computing in the NISQ era and beyond
• Quantum Machine Learning
• Quantum algorithm for solving linear systems of equations
• Quantum Chemistry in the Age of Quantum Computing
• Quantum Algorithms Revisited
• Simulating Hamiltonian dynamics with a truncated Taylor series
• Quantum computing for finance: overview and prospects
• Quantum algorithm for systems of linear equations with exponentially improved dependence on precision
• Grover's quantum searching algorithm is optimal
• Quantum advantage with shallow circuits
• Efficient Distributed Quantum Computing
• Optimal Quantum Clocks
• Quantum algorithms for systems of linear equations inspired by adiabatic quantum computing
• Quantum State Preparation with Optimal Circuit Depth: Implementations and Applications
• Quantum advantage with noisy shallow circuits in 3D
• Parallelizing Quantum Circuits
• Optimal polynomial based quantum eigenstate filtering with application to solving quantum linear systems
• Quantum Circuits with Unbounded Fan-out
• Low depth algorithms for quantum amplitude estimation
• Generalized Quantum Search with Parallelism
• Optimal (controlled) quantum state preparation and improved unitary synthesis by quantum circuits with any number of ancillary qubits
• Multivariate trace estimation in constant quantum depth
• On the Need for Large Quantum Depth
• Parallel Quantum Algorithm for Hamiltonian Simulation