Quantum Portfolio Optimization

29 October 2021

Additional Info

  • Paper Title:

    NISQ-HHL: Portfolio Optimization for Near-Term Quantum Hardware

  • Paper Authors:

    Romina Yalovetzky, Pierre Minssen, Dylan Herman, Marco Pistoia (JPMorgan)

Quantum computing is currently being explored to target a wide variety of problems, with optimization-type problems being one of the primary applications. A specific type of optimization problem in finance, where it is believed that quantum computing could potentially have an advantage over classical computing, is portfolio optimization, due to its complex and time consuming nature in classical approaches. Portfolio optimization can be formulated in the language of quadratic program programming, which can in-turn be written in a feasible format for a quantum computer, with the cost function enforcing risk minimization for a targeted return.

Previous works have utilized the Harrow-Hassidim-Lloyd (HHL) algorithm for mean-variance portfolio optimization, which can be formulated as a linear quadratic-programming problem. However, multiple components of HHL are incompatible with the implementation on Noisy Intermediate Scale Quantum (NISQ) systems, which reflects the current state of quantum computers. For instance, eigenvalue inversion is an expensive subcircuit to run on such near-term devices, which suffer from prohibitively many errors over the course of the circuit execution.

The authors in this work introduce a classical/quantum hybrid HHL algorithm called NISQ-HHL, which is obtained by leveraging newly available hardware features and optimizing existing components of HHL. The objective is to execute and validate NISQ-HHL on real quantum hardware supporting mid-circuit measurement, qubit reset and reuse, and Quantum Conditional Logic (QCL). An enhanced formulation of the classical/quantum hybrid HHL algorithm is presented that integrates all the aforementioned features into the separate Quantum Phase Estimation (QPE) routine used for eigenvalue estimation. The end-to-end flow of NISQ-HHL consists of four steps:
i) The QCL-QPE procedure is used to construct a distribution over the estimates of the relevant eigenvalues with n-bit precision.
ii) Classical post-processing is performed on the resulting histogram to obtain the estimates of the relevant eigenvalues.
iii) The obtained n-bit estimates are used to determine rotation angles for the eigenvalue inversion circuit. The estimates are then mapped to a smaller number of bits (r) such that each rotation is conditioned on its corresponding r-bit estimate.
iv) A standard HHL procedure is executed using the circuit constructed in the above step for the eigenvalue inversion. In order to estimate the performance of NISQ-HHL on quantum hardware, in this work the Hamiltonian is simulated using classical algorithms instead of quantum algorithms and a circuit transpiler is used that decomposes it into basis gates relevant for e.g. superconducting-based NISQ hardware.

The first step of NISQ-HHL is to obtain estimates of the relevant eigenvalues using QCL-QPE. This variant of QPE uses mid-circuit measurement, qubit reset and reuse, and Quantum Conditional Logic (QCL). Implementing QCL-QPE has two advantages: i) It reduces the number of ancillas to just one for arbitrary bit precision and hence reduces the number of qubits required, which is important in the NISQ era where not that many logical qubits are available. ii) QCL-QPE replaces two-qubit gates with one-qubit gates controlled by classical bits, thereby reducing the requirement for qubit connectivity, SWAP gates or qubit transport. Also, an algorithm is proposed to optimize the scaling parameter γ for the Hamiltonian simulation required by QCL-QPE, that led to higher accuracy while resolving the eigenvalues. In comparison to the uniformly controlled rotation approach, the number of rotations in the NISQ-HHL implementation is smaller, and the circuit is therefore less deep.

In terms of an experimental implementation of the algorithm, the authors consider a portfolio-optimization problem with two S&P 500 assets. It is implemented on trapped-ion Honeywell System Model H1 after transpiling and optimizing the circuits from Qiskit to H1’s native gates using Cambridge Quantum’s pytket package. Experimental results show that QCL-QPE achieves high fidelity, between experimental and simulated measurement distributions, for three-bit precision. For four-bit estimations, QLC-QPE achieved a higher fidelity than the standard QPE. Also, the NISQ-HHL eigenvalue inversion circuit is shown to be more efficient than the uniformly controlled rotation gate method, mainly due to the reduced number of controlled rotations, and the circuit depth. Moreover, the work demonstrates that NISQ-HHL can scale to larger portfolios than those supported on current quantum hardware.

The total complexity of NISQ-HHL presented here is shown to be lower than the previously proposed methods for a low-qubit count, such as quantum arithmetic and uniformly controlled rotation gate, although the authors were unable to show asymptotic efficiency. Nevertheless, the presented methodology brings HHL implementation closer to current quantum hardware.

What's Interesting?

How can we help you?

Invalid Input

Invalid Input

Invalid Input

Invalid Input

Invalid Input

Invalid Input

Copyright © Qu & Co BV