TL;DR
This paper introduces "Hybrid HHL++," an optimized quantum algorithm for solving linear systems, designed for current noisy quantum hardware. By introducing a novel spectral scaling technique and a circuit compression heuristic, the authors enable larger-scale experimental demonstrations of the HHL algorithm for a practical portfolio optimization problem, achieving high fidelity on trapped-ion quantum computers.
What Problem Does This Paper Address?
The Harrow-Hassidim-Lloyd (HHL) algorithm is a powerful quantum algorithm for solving linear systems, with potential applications in various fields. However, its practical implementation is severely hindered by the limitations of current Noisy Intermediate-Scale Quantum (NISQ) devices. The algorithm requires a significant number of qubits and deep quantum circuits, making it infeasible for near-term hardware. To bridge this gap, hybrid classical-quantum variants of HHL have been proposed. This paper aims to further improve these hybrid approaches, making them more compatible with existing hardware and enabling application-oriented benchmarking. Specifically, they address the challenge of efficiently utilizing limited quantum resources for phase estimation and reducing the overall circuit complexity.
Methods
The authors propose two key modifications to the existing Hybrid HHL algorithm, resulting in their "Hybrid HHL++" approach:
- Spectral Scaling Algorithm: This novel algorithm optimizes a scaling parameter ($\gamma$) for the linear system matrix. This optimization ensures that the eigenvalues are distributed in a way that maximizes the utility of the allocated ancillary qubits for phase estimation, leading to more accurate eigenvalue determination. It iteratively refines $\gamma$ by using quantum phase estimation (QPE) and classical post-processing.
- Heuristic for Compressing HHL Circuit: This technique reduces the complexity of the eigenvalue inversion step in the HHL algorithm. It leverages a semiclassical QPE variant that requires fewer qubits and one-qubit gates controlled by classical registers, making it more suitable for NISQ devices. This heuristic aims to reduce the circuit depth and the number of required qubits for the inversion process.
They also utilize a semiclassical QPE variant, which is more resource-efficient than standard QPE, requiring only one ancillary qubit and replacing two-qubit gates with one-qubit gates controlled by classical registers.
Datasets
The paper uses data from S&P 500 stock data to construct the covariance matrix for portfolio optimization problems. They create six different problem instances for a 44x44 matrix (representing 2 assets) and five problem instances for an 88x88 matrix (representing 6 assets). These instances are used for simulations and experimental runs on quantum hardware.
Key Insights and Ideas
- Optimizing $\gamma$ is Crucial: The spectral scaling algorithm highlights that the choice of the scaling parameter $\gamma$ is not arbitrary but critical for efficient phase estimation and accurate eigenvalue determination on NISQ devices. A well-chosen $\gamma$ can stretch the spectrum to utilize the available bit precision effectively.
- Semiclassical QPE is a Game-Changer for NISQ: The adoption of semiclassical QPE is a significant step towards making quantum algorithms practical on current hardware. Its reduced qubit and gate requirements, especially the elimination of deep two-qubit gate chains, directly address the limitations of NISQ devices.
- Heuristic Compression Works: The heuristic for compressing the HHL circuit, by reducing the precision of QPE in the inversion step based on eigenvalue distribution, demonstrates that not all parts of the HHL algorithm require the same high precision, allowing for resource savings.
- Application-Oriented Benchmarking is Key: The paper emphasizes the importance of using application-oriented problems like portfolio optimization to benchmark quantum algorithms on real hardware, providing a more meaningful evaluation than abstract algorithm tests.
Key Results
- Largest Experimental Demonstrations: The authors report the largest experimental demonstrations of HHL for an application to date, solving small-scale portfolio optimization problems on Quantinuum H-series trapped-ion quantum computers.
- High Fidelity Achieved: The semiclassical QPE implementation achieved high fidelity (up to 98.1% median for 3-bit precision) on hardware, comparable to noiseless simulations, especially for lower bit precisions. Even with increased precision (4 and 5 bits), the fidelity remained competitive, with the semiclassical approach showing higher median fidelity due to its shallower circuits.
- Inner Product Close to Analytical Solution: For portfolio optimization problems, the HHL circuit output, when compared to the analytically calculated solution using a controlled-SWAP test, yielded high inner product values (around 0.92-0.96 on hardware), indicating that the algorithm produces accurate solutions.
- Resource Reduction: The Hybrid HHL++ approach significantly reduces the number of qubits and two-qubit gates compared to standard QPE implementations, making it more feasible for NISQ devices. For example, the semiclassical QPE uses only 3 qubits for up to 5-bit precision, while standard QPE requires up to 7 qubits.
Limitations and Future Work
- Heuristic Nature: The authors acknowledge that the circuit compression heuristic is not a guaranteed optimal solution but rather a well-motivated approach.
- Noise Impact: While the paper investigates the impact of noise on emulator results, the performance on actual hardware is still affected by noise, particularly mid-circuit measurements and resets. The fidelity drops significantly for higher bit precisions due to circuit depth limitations.
- No Asymptotic Speedup: The Hybrid HHL++ algorithm, like its predecessor, sacrifices the asymptotic speedup of the original HHL algorithm for near-term feasibility.
- Future Work: The authors suggest that future work could involve applying Hybrid HHL++ to larger portfolio optimization problems and exploring its application to other linear algebra tasks. They also aim to further investigate the impact of noise on larger systems and explore more advanced error mitigation techniques.
Summary updated