Quantum Linear System Algorithms: Direct Methods

Osama M. Raisuddin, Suvranu De

V Shwetha, Abinaya Selvarajan, A Aarthi +1 more

One of the most significant developments in quantum computing is the Harrow-Hassidim-Lloyd (HHL) method, which can solve linear equation systems at exponential speedup. Because linear systems are essential to many scientific fields, including physics, engineering, and machine learning, this approach has great potential to revolutionize computational paradigms. The HHL algorithm is thoroughly examined in this work, with particular attention paid to its theoretical framework, real-world application utilizing IBM's Qiskit platform, and the difficulties in simulating quantum algorithms on noisy intermediate-scale quantum (NISQ) devices. Using parameters like fidelity, time complexity, and scalability, the research further evaluates the HHL algorithm's performance in comparison to traditional methods. According to the findings, quantum simulations work well for small-scale matrices like 2x2 and 4x4, but expanding the approach to bigger systems is still difficult because of hardware and software constraints. Finally, the research emphasizes the key directions for advancing quantum hardware and algorithms to overcome current scalability challenges, enabling broader applicability of the HHL algorithm in solving complex linear systems.

Yunah Choi, Jeihee Cho, Shiho Kim

Parikshit Pareek, Abhijith Jayakumar, Carleton Coffrin +1 more

Quantum computers hold promise for solving problems intractable for classical computers, especially those with high time or space complexity. Practicalquantum advantagecan be said to exist for such problems when the end-to-end time for solving such a problem using a classical algorithm exceeds that required by a quantum algorithm. Reducing the power flow (PF) problem into a linear system of equations allows for the formulation of quantum PF (QPF) algorithms, which are based on solving methods for quantum linear systems such as the Harrow-Hassidim-Lloyd (HHL) algorithm. Speedup from using QPF algorithms is often claimed to be exponential when compared to classical PF solved by state-of-the-art algorithms. We investigate the potential for practical quantum advantage in solving QPF compared to classical methods on gate-based quantum computers. Notably, this paper does not present a new QPF solving algorithm but scrutinizes the end-to-end complexity of the QPF approach, providing a nuanced evaluation of the purported quantum speedup in this problem. Our analysis establishes a best-case bound for the HHL-based quantum power flow complexity, conclusively demonstrating that the HHL-based method has higher runtime complexity compared to the classical algorithm for solving the direct current power flow (DCPF) and fast decoupled load flow (FDLF) problem. Notably, our analysis and conclusions can be extended to any quantum linear system solver with rigorous performance guarantees, based on the known complexity lower bounds for this problem. Additionally, we establish that for potential practical quantum advantage (PQA) to exist it is necessary to consider DCPF-type problems with a very narrow range of condition number values and readout requirements.

Farshad Amani, Amin Kargarian

This paper presents three quantum interior-point methods (QIPMs) tailored to tackle the DC optimal power flow (DCOPF) problem using noisy intermediate-scale quantum devices. The optimization model is redefined as a linearly constrained quadratic optimization. By incorporating the Harrow-Hassidim-Lloyd (HHL) quantum algorithm into the IPM framework, Newton's direction is determined through the resolution of linear equation systems. To mitigate the impact of HHL error and quantum noise on Newton's direction calculation, we present a noise-tolerant quantum IPM (NT-QIPM) approach. This approach provides high-quality OPF solutions even in scenarios where inexact solutions to the linear equation systems result in approximated Newton's directions. Moreover, to enhance performance in cases of slow convergence and uphold the feasibility of OPF outcomes upon convergence, we propose a hybrid strategy, classically augmented NT-QIPM. This technique is designed to expedite convergence relative to classical IPM while maintaining the solution accuracy. The efficacy of the proposed quantum IPM variants is studied through comprehensive simulations and error analyses on 3-bus, 5-bus, 118-bus, and 300-bus systems, highlighting their potential and promise in addressing challenging OPF scenarios. By modeling the errors and incorporating quantum computer noise, we simulate the proposed algorithms on both Qiskit and classical computers to gain a deeper understanding of the effectiveness and feasibility of our methods under realistic conditions.

Ivan B. Djordjević