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

Fang Gao, Guojian Wu, Mingyu Yang, Wei Cui, Feng Shuang

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\rangle$ 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.

Introduction

Solving linear systems of equations ($Ax=b$) is a cornerstone of computational science. While the HHL quantum algorithm offers exponential speedup over classical methods, its high qubit requirements and complex circuit depth make it unsuitable for current Noisy Intermediate-Scale Quantum (NISQ) devices. Furthermore, HHL typically produces a normalized quantum state, whereas many real-world applications require the full, unnormalized solution vector.

This paper introduces the Hybrid Iterative Phase Estimation Algorithm (HIPEA), a framework that trades quantum circuit width for classical iterative processing. By shifting complexity to classical registers, HIPEA reduces the hardware burden and enables the extraction of exact solutions.

Methodology

The HIPEA framework is based on Iterative Phase Estimation (IPEA), which resolves eigenvalues bit-by-bit. This approach allows for a significant reduction in ancillary qubits compared to standard quantum phase estimation.

The basic circuit for the first iteration of the HIPEA algorithm, utilizing a single ancillary qubit in the top register.

Three variants of the algorithm were developed to suit different resource constraints:

  • HIPEA-1: A minimalist approach using only one ancillary qubit. It differentiates eigenvalues through multiple successive experiments.
  • HIPEA-2: Uses $N$ ancillary qubits (where $N$ is the number of non-degenerate eigenvalues) to differentiate all eigenvalues in a single experiment, prioritizing speed over qubit count.
  • HIPEA-3: A flexible model that allows users to define the number of ancillary qubits, using a "traversing strategy" to balance hardware availability with experimental time.

Binary Tree Representation

To manage the iterative process, the authors employ a binary tree logic. As the algorithm resolves bits, it identifies where eigenvalues diverge. Once two eigenvalues differ at the $k$-th bit, the classical controller branches to track separate paths, as visualized in the iterative bit-extraction process.

Binary tree representation of the iterative process for extracting eigenvalue bits across different iterations.

Key Results

The algorithms were validated using a simulated $4 \times 4$ Hermitian matrix within the PyQPanda framework. The results confirmed that high-fidelity solutions can be obtained with very few qubits:

  • HIPEA-1 achieved a relative error of 0.0100 using only 3 total qubits.
  • HIPEA-2 achieved a relative error of 0.0141 using 6 total qubits.
  • HIPEA-3 demonstrated the highest precision with a relative error of 0.0048 using 3 ancillary qubits.

By utilizing classical post-selection on measurement results, the researchers bypassed the need for the controlled rotation steps that typically enforce normalization in quantum solvers, successfully obtaining unnormalized results.

Conclusion and Future Work

The HIPEA suite demonstrates that quantum "depth" and "width" can be effectively traded for classical repetition, a vital strategy for the NISQ era. While the current framework assumes eigenvalues can be perfectly represented by finite binary strings, future research will focus on handling irrational eigenvalues and optimizing the classical traversal schemes to reduce overhead for larger systems.

Summary updated

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 $\left| x \right\rangle $ 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.
BibTeX
@inproceedings{gao2022hybrid,
  author = {Fang Gao and Guojian Wu and Mingyu Yang and Wei Cui and Feng Shuang},
  title = {{Hybrid algorithms to solve linear systems of equations with limited qubit resources}},
  booktitle = {Quantum},
  year = {2022},
  doi = {10.1007/s11128-021-03388-3},
}
Figure