New Quantum Algorithm Enhances Solutions for Non-Square Linear Systems

A new quantum algorithm has been proposed for solving linear systems with non-square coefficient matrices, a significant advancement in the field of quantum computing. The paper, titled "Quantum multi-row iteration algorithm for linear systems with non-square coefficient matrices," authored by Weitao Lin, Guojing Tian, and Xiaoming Sun, introduces a method that builds on classical multi-row iteration techniques.

The authors highlight that while quantum computing has shown exponential advantages over classical methods, most existing quantum algorithms focus on square matrices. This new approach addresses the challenges posed by non-square matrices, which are common in various applications, including inconsistent systems and quadratic optimization problems.

The proposed quantum algorithm utilizes a quantum circuit that incorporates a quantum comparator and Quantum Random Access Memory (QRAM). The time complexity of this algorithm is noted as O(K log m), where K represents the number of iteration steps, indicating a substantial speedup compared to classical algorithms.

Additionally, the authors demonstrate that their quantum algorithm converges faster than previously established quantum one-row iteration algorithms. This improvement is particularly relevant for applications requiring efficient solutions to complex linear systems, potentially impacting fields such as optimization, machine learning, and data analysis.

The findings suggest that this algorithm could enhance the capabilities of quantum computers in solving practical problems that involve non-square matrices, broadening the scope of quantum applications in real-world scenarios. The paper can be accessed at arXiv:2409.04010.