Identifying Bottlenecks of NISQ-friendly HHL algorithms

Abstract

Quantum computing promises enabling solving large problem instances, e.g. large linear equation systems with HHL algorithm, once the hardware stack matures. For the foreseeable future quantum computing will remain in the so-called NISQ era, in which the algorithms need to account for the flaws of the hardware such as noise. In this work, we perform an empirical study to test scaling properties and directly related noise resilience of the the most resources-intense component of the HHL algorithm, namely QPE and its NISQ-adaptation Iterative QPE. We explore the effectiveness of noise mitigation techniques for these algorithms and investigate whether we can keep the gate number low by enforcing sparsity constraints on the input or using circuit optimization techniques provided by Qiskit package. Our results indicate that currently available noise mitigation techniques, such as Qiskit readout and Mthree readout packages, are insufficient for enabling results recovery even in the small instances tested here. Moreover, our results indicate that the scaling of these algorithms with increase in precision seems to be the most substantial obstacle. These insights allowed us to deduce an approximate bottleneck for algorithms that consider a similar time evolution as QPE. Such observations provide evidence of weaknesses of such algorithms on NISQ devices and help us formulate meaningful future research directions.

Copyright notice added, minor fixes are performed

References in corpus (14)

• Quantum algorithm for solving linear systems of equations
• Simulating Hamiltonian dynamics with a truncated Taylor series
• Quantum Error Mitigation
• Preconditioned quantum linear system algorithm
• Exponential improvement in precision for simulating sparse Hamiltonians
• Quantum algorithms for systems of linear equations inspired by adiabatic quantum computing
• CutQC: Using Small Quantum Computers for Large Quantum Circuit Evaluations
• Evaluating the noise resilience of variational quantum algorithms
• Hybrid quantum linear equation algorithm and its experimental test on IBM Quantum Experience
• Bayesian Deep Learning on a Quantum Computer
• Enhancing the Quantum Linear Systems Algorithm using Richardson Extrapolation
• Step-by-Step HHL Algorithm Walkthrough to Enhance the Understanding of Critical Quantum Computing Concepts
• Hybrid classical-quantum linear solver using Noisy Intermediate-Scale Quantum machines
• Hybrid algorithms to solve linear systems of equations with limited qubit resources