Solving linear systems on quantum hardware with hybrid HHL+

Abstract

The limited capabilities of current quantum hardware significantly constrain the scale of experimental demonstrations of most quantum algorithmic primitives. This makes it challenging to perform benchmarking of the current hardware using useful quantum algorithms, i.e., application-oriented benchmarking. In particular, the Harrow-Hassidim-Lloyd (HHL) algorithm is a critical quantum linear algebra primitive, but the majority of the components of HHL are far out of the reach of noisy intermediate-scale quantum devices, which has led to the proposal of hybrid classical-quantum variants. The goal of this work is to further bridge the gap between proposed near-term friendly implementations of HHL and the kinds of quantum circuits that can be executed on noisy hardware. Our proposal adds to the existing literature of hybrid quantum algorithms for linear algebra that are more compatible with the current scale of quantum devices. Specifically, we propose two modifications to the Hybrid HHL algorithm proposed by Lee et al., leading to our algorithm Hybrid ${\text{HHL}}^{++}$ : (1) propose a novel algorithm for determining a scaling factor for the linear system matrix that maximizes the utility of the amount of ancillary qubits allocated to the phase estimation component of HHL, and (2) introduce a heuristic for compressing the HHL circuit. We demonstrate the efficacy of our work by running our modified Hybrid HHL on Quantinuum System Model H-series trapped-ion quantum computers to solve different problem instances of small-scale portfolio optimization problems, leading to the largest experimental demonstrations of HHL for an application to date.

Figure 1

End-to-End Flow of Hybrid ${\text{HHL}}^{++}$: highlights the integration of the two proposed modifications, the spectral scaling algorithm (section “Spectral acaling algorithm for optimizing γ”) in Step 1 and the HHL circuit compression (section “Heuristic for compressing HHL circuit”) techniques in Step 3 and Step 4, into the original Hybrid HHL flow.

Algorithm 1: Optimize the selection of γ using m-bit estimations of eigenvalues.

Algorithm 2: Verify if α is a n-bit overestimation of λ_max.

Figure 2

Circuits for estimating the eigenvalues of the unitary operator $\mathbf{U}$ to three bits using semiclassical QPE (a) or QPE (b). S is the register that $\mathbf{U}$ is applied to, and j is a classical register. $\mathsf{H}$ refers to the Hadamard gate and ${\mathsf{R}}_{\mathsf{k}}$, for $\mathsf{k}=2,3$, are the phase gates.

Algorithm 3: Semiclassical Phase Estimation^,.

Figure 3

Probability distributions over the four-bit eigenvalue estimates from the semiclassical QPE executions using $e^{i\mathbf{A}2\pi \mathrm{\Gamma }}$ for $\mathrm{\Gamma }=50·2^{-4}$ (a) and $\mathrm{\Gamma }=200$ (b). The blue bars represent the experimental results on the trapped-ion device with 2000 shots. The theoretical (classically calculated) eigenvalues are represented with the red dots and the results from the noiseless simulator, Qiskit QASM simulator, are represented with the orange dots. As shown on (b), as the theoretical eigenvalues exceed the values we can encode, the distribution we observed shows that values overflowed.

Figure 4

Probability distributions over the four-bit eigenvalue estimates from the semiclassical QPE run using $e^{iA2\pi \gamma }$ for $\gamma =50$ (a) and $\gamma =100$.The blue bars represent the experimental results on the trapped-ion device - 2000 shots (a), 1000 shots (b). The theoretical (classically calculated) eigenvalues are represented with the red dots and the results from noiseless simulation with the Qiskit QASM simulator are represented with the orange dots.

Figure 5

Fidelity between the output distribution of the semiclassical QPE executed on both the hardware and its emulator with 400 shots and the output distribution obtained in noiseless simulation, respectively, as a function of the portfolio-optimization problem instances. The semiclassical QPE is performed to the unitary corresponding to the optimal scaling parameter obtained with the proposed algorithms using the output of the circuits on the emulator. We utilized this number of shots as it has been seen on the noisy emulator of the hardware that for a higher number, there are no significant changes. It is displayed the median and standard deviation, as error bars, of the bootstrap distributions.

Figure 6

Inner product between the output quantum state of the HHL circuit and the analytical solution loaded as a quantum state for each of the portfolio-optimization problem instances with two assets. This metric quantifies the quality of the solution obtained. It is displayed the inner product corresponding to the execution of the circuits on hardware, its emulator with approximated noise and in noiseless simulation with 1000 shots. We utilized this number of shots as it has been seen on the noisy emulator of the hardware that for a higher number, there are no significant changes. The error bars correspond to the sampling error $ϵ$ corresponding to $\mathcal{O}(1/{ϵ}^2)$ shots.

Figure 7

Benchmark metrics as a function of the value of the two-qubit fault probability (“p2”) utilized to simulate the noise in the emulator. Each color plots a different portfolio-optimization problem instance consisting of six assets ($8\times 8$ linear systems of equations). The metric in (a) is the fidelity between the output distribution obtained from executing the semiclassical QPE circuit on emulator with the given noise and the distribution obtained in noiseless simulation. The metric in (b) is the inner product between the output quantum state of the HHL circuit executed on the emulator with the given level of noise and the analytical solution loaded as a quantum state.