We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
A hybrid algorithm to solve linear systems of equations with limited qubit resources.
- Authors
Gao, Fang; Wu, Guojian; Yang, Mingyu; Cui, Wei; Shuang, Feng
- 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, the hybrid iterative phase estimation algorithm (HIPEA) is 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 algorithm. 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 variants of HIPEA are different. The first variant only needs one single ancillary qubit. The number of ancillary qubits in the second variant is equal to the number of nondegenerate eigenvalues of the coefficient matrix of linear systems of equations. The third variant is designed with a flexible number of ancillary qubits. The HIPEA algorithm 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.
- Subjects
LINEAR equations; LINEAR systems; QUANTUM computing; QUBITS; ALGORITHMS; SUPPLY &; demand
- Publication
Quantum Information Processing, 2022, Vol 21, Issue 3, p1
- ISSN
1570-0755
- Publication type
Article
- DOI
10.1007/s11128-021-03388-3