Near-term quantum algorithms for linear systems of equations
read the original abstract
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.
This paper has not been read by Pith yet.
Forward citations
Cited by 6 Pith papers
-
Quantum Simulation of Differential-Algebraic Equations with Applications to Unsteady Stokes Flow
Introduces a dilation framework for quantum simulation of linear DAEs, applied to structure-preserving discretizations of unsteady Stokes flow yielding simulation cost scaling as O(h^{-2} sqrt(t)).
-
Bias Analysis and Regularization of Sequential Minimal Optimization in Variational Quantum Eigensolvers
Bias in SMO-VQE can be estimated without extra measurements; a regularization method that mimics error accumulation while preserving unbiased estimates improves performance across system sizes and Hamiltonians.
-
Quantum Simulation of Differential-Algebraic Equations with Applications to Unsteady Stokes Flow
A new dilation embeds non-Hermitian DAE evolution into projected Hermitian quantum dynamics, enabling block encodings and QSVT for simulation of constrained systems like unsteady Stokes flow.
-
A hybrid quantum-classical algorithm for Bayes-optimal quantum state discrimination using the source code
A hybrid algorithm reduces the SDP dimension for Bayes-optimal state discrimination from dL to NL via Gram matrix reformulation and quantum preprocessing from source circuits, enabling solutions for large changepoint ...
-
From barren plateaus through fertile valleys: Conic extensions of parameterised quantum circuits
Conic extensions of parameterized quantum circuits enable jumps from barren plateaus to fertile valleys via non-unitary operations and ancilla, reducing optimal jump selection to a generalized eigenvalue problem and i...
-
A Review of Variational Quantum Algorithms: Insights into Fault-Tolerant Quantum Computing
A literature review of VQAs covering ansatz design, classical optimization, barren plateaus, error mitigation strategies, and theoretical adaptations for fault-tolerant quantum computing.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.