Near-term quantum algorithms for linear systems of equations
Open accessAbstract
Solving linear systems of equations is essential for many problems in science and technology, including problems in machine learning. Existing quantum algorithms have demonstrated the potential for large speedups, but the required quantum resources are not immediately available on near-term quantum devices. In this work, we study near-term quantum algorithms for linear systems of equations of the form $Ax = b$. We investigate the use of variational algorithms and analyze their optimization landscapes. There exist types of linear systems for which variational algorithms designed to avoid barren plateaus, such as properly-initialized imaginary time evolution and adiabatic-inspired optimization, suffer from a different plateau problem. To circumvent this issue, we design near-term algorithms based on a core idea: the classical combination of variational quantum states (CQS). We exhibit several provable guarantees for these algorithms, supported by the representation of the linear system on a so-called Ansatz tree. The CQS approach and the Ansatz tree also admit the systematic application of heuristic approaches, including a gradient-based search. We have conducted numerical experiments solving linear systems as large as $2^{300} \times 2^{300}$ by considering cases where we can simulate the quantum algorithm efficiently on a classical computer. These experiments demonstrate the algorithms' ability to scale to system sizes within reach in near-term quantum devices of about $100$-$300$ qubits.
Integrity signals
Registry
Cites
Statistics
Claims the paper makes
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
For matrix-vector multiplication, one constructs Hamiltonian H_M = I - A|b><b|A†/||A|b>||^2 whose ground state is |x> with zero energy.
“Similar to solving the QLSP, one constructs the Hamiltonian H M = ✶ -A | b 〉 〈 b | A † / ‖ A | b 〉 ‖ 2 , whose ground state is | x 〉 with zero energy [140].”
From Variational quantum algorithms (2021) · cites this paper as [140]
Refs [139-141] considered the Hamiltonian H_G = A(I - |b><b|)A†.
“Refs. [139-141] considered the Hamiltonian H G = A ( ✶ -| b 〉 〈 b | ) A † (which was also considered outside of the variational setting [142]).”
From Variational quantum algorithms (2021) · cites this paper as [140]
For a Pauli string, the number of measurement samples N_s needed to estimate the expectation value with an additive error of at most epsilon and a failure probability of at most delta is bounded by Hoeffding's inequality.
“For a Pauli string ˆ P , the number of measurement samples N s needed to estimate the expectation value ⟨ ˆ P ⟩ U with an additive error of at most ϵ with a failure probability of at most δ is bounded by Hoeffding's inequality (Huang et al. , 2019)”
From Noisy intermediate-scale quantum algorithms (2022) · cites this paper as Huang et al., 2019
Almost all VQAs update a PQC's parameters in a feedback loop, but there exist alternative algorithms that circumvent this approach with an ansatz that is a linear combination of quantum states.
“Almost all of the VQAs update a PQC's parameters in a feedback loop. However, there exist alternative algorithms that can circumvent this approach with the ansatz given by (Bharti and Haug, 2021a; Huang et al. , 2019; McClean et al. , 2017)”
From Noisy intermediate-scale quantum algorithms (2022) · cites this paper as Huang et al., 2019
The citation lists haven’t been fetched yet
References 1 · Cited by 62
- Authors
- Huang, H.-Y., Bharti, K., & Rebentrost, P.
- Venue
- arXiv
- Publisher
- arXiv
- Published
- 2019
- ISSN
- 2331-8422 (ISSN-L)
- arXiv
- 1909.07344
- OpenAlex
- W2972969431
- Cited by
- 62
- References
- 1
- Citations by year
- 2025: 3 · 2024: 5 · 2023: 5 · 2022: 12 · 2021: 28 · 2020: 9
- Type
- posted content
- Language
- en
- Open access
- green
- arxiv.org
- Locations
- arXiv (Cornell University) (submittedVersion)
- arXiv (Cornell University)
- Topics
- Physical Sciences › Computer Science › Artificial Intelligence › Quantum Computing Algorithms and Architecture
- Physical Sciences › Physics and Astronomy › Atomic and Molecular Physics, and Optics › Quantum many-body systems
- Physical Sciences › Computer Science › Artificial Intelligence › Quantum Information and Cryptography
- Keywords
- quantum algorithms, systems of linear equations, variational quantum algorithms, barren plateaus, imaginary time evolution, gradient-based optimization, near-term quantum devices
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
