Hybrid algorithms to solve linear systems of equations with limited qubit resources

Abstract

The solution of linear systems of equations is a very frequent operation and thus important in many fields. The complexity using classical methods increases linearly with the size of equations. The HHL algorithm proposed by Harrow et al. achieves exponential acceleration compared with the best classical algorithm. However, it has a relatively high demand for qubit resources and the solution $|x⟩$ is in a normalized form. Assuming that the eigenvalues of the coefficient matrix of the linear systems of equations can be represented perfectly by finite binary number strings, three hybrid iterative phase estimation algorithms (HIPEA) are designed based on the iterative phase estimation algorithm in this paper. The complexity is transferred to the measurement operation in an iterative way, and thus the demand of qubit resources is reduced in our hybrid algorithms. Moreover, the solution is stored in a classical register instead of a quantum register, so the exact unnormalized solution can be obtained. The required qubit resources in the three HIPEA algorithms are different. HIPEA-1 only needs one single ancillary qubit. The number of ancillary qubits in HIPEA-2 is equal to the number of nondegenerate eigenvalues of the coefficient matrix of linear systems of equations. HIPEA-3 is designed with a flexible number of ancillary qubits. The HIPEA algorithms proposed in this paper broadens the application range of quantum computation in solving linear systems of equations by avoiding the problem that quantum programs may not be used to solve linear systems of equations due to the lack of qubit resources.

arXiv comment22 pages, 6 figures, 6 tables, 48 equations

References in corpus (21)

• Quantum Computing in the NISQ era and beyond
• Quantum algorithm for solving linear systems of equations
• Quantum Algorithms Revisited
• Quantum random access memory
• Optimal Hamiltonian Simulation by Quantum Signal Processing
• Efficient quantum algorithms for simulating sparse Hamiltonians
• Architectures for a quantum random access memory
• Preconditioned quantum linear system algorithm
• The General Quantum Interference Principle and the Duality Computer
• Witnessing eigenstates for quantum simulation of Hamiltonian spectra
• Arbitrary accuracy iterative phase estimation algorithm as a two qubit benchmark
• Efficient Bayesian Phase Estimation
• Quantum phase estimation of multiple eigenvalues for small-scale (noisy) experiments
• Experimental Quantum Computing to Solve Systems of Linear Equations
• Universal simulation of Hamiltonian dynamics for qudits
• Hybrid quantum linear equation algorithm and its experimental test on IBM Quantum Experience
• Calculating Unknown Eigenvalues with a Quantum Algorithm
• Black-box Hamiltonian simulation and unitary implementation
• Iterative phase estimation
• Collapse-in and Collapse-out in Partial Measurement in Quantum Mechanics and its WISE Interpretation
• A Query-based Quantum Eigensolver

Cited by in corpus (3)

• Application of a variational hybrid quantum-classical algorithm to heat conduction equation
• Step-by-Step HHL Algorithm Walkthrough to Enhance the Understanding of Critical Quantum Computing Concepts
• Identifying Bottlenecks of NISQ-friendly HHL algorithms