JPMorgan Chase proposed the first portfolio optimization algorithm suitable for recent quantum hardware

Portfolio optimization is an important use case in the financial field, but its computational complexity forces financial institutions to obtain only an approximate solution when they spend a lot of time. Therefore, the scientific community is studying how to use quantum computing for efficient and accurate portfolio optimization.

Portfolio optimization can be expressed as a quadratic programming, and the cost function forces risk minimization to obtain the target return. Especially the mean variance portfolio optimization problem. Using Lagrange multiplier method, quadratic programming can be transformed into linear equations and may benefit from the exponential acceleration provided by HHL quantum algorithm. HHL algorithm was first proposed by harrow, Hassidim and Lloyd in 2009. It is the first quantum algorithm to solve linear equations.

However, multiple components in HHL are not suitable for execution on noisy medium scale quantum (nisq) hardware. Therefore, JPMorgan applied research and engineering future laboratory proposed a hybrid algorithm nisq-hhl, which is the first HHL hybrid algorithm suitable for end-to-end implementation of small-scale portfolio optimization problems on nisq equipment.

In 2009, harrow, Hassidim and Lloyd introduced HHL algorithm to solve quantum linear system problem (QLSP). This involves solving a linear system a picture, where A ∈ n × N. Picture ∈ n, so as to return the corresponding quantum state | x ＞ to the solution of the linear system until the normalization factor. In 2019, a Korean team introduced the classic / quantum hybrid HHL variant. The nisq-hhl introduced in this paper is an enhanced version of this variant.

Nisq-hhl extends hybrid HHL variants with new available quantum hardware capabilities, including intermediate circuit measurement, quantum conditional logic (QCL), and qubit reset and reuse. Nisq-hhl is the first QCL enhanced version of the algorithm that combines phase estimation performed on real hardware.

The advantages of nisq-hhl are as follows:
1) An enhanced version of the classical / quantum hybrid HHL algorithm, which integrates the functions of intermediate circuit measurement, quantum conditional logic (QCL), and quantum bit reset and reuse into an independent quantum phase estimation (QPE) routine for eigenvalue estimation. This has two main advantages that make the generated algorithm more suitable for nisq computers:

a) The number of auxiliary qubits is reduced to only one. A single auxiliary qubit can be frequently measured, reset and reused as needed, which greatly reduces the number of qubits used for computing.

b) Although the standard QPE requires controlled gates between various auxiliary qubits, QCL allows the application of gates conditional on classical registers. This reduces the requirements for quantum bit connection, switching gate (SWAP) or quantum bit transmission.

c) A new and effective method for determining the value of scale a, which allows eigenvalues to be solved with significantly higher accuracy.

d) By implementing nisq-hhl on the real quantum hardware Honeywell ion trap system model H1 to solve the portfolio optimization problem, an empirical evaluation is obtained. Its benchmark includes the S & P 500 portfolio. The evaluation includes a comparative analysis of the results.

Nisq-hhl replaces the standard QPE with the QPE for eigenvalue estimation using QCL, which enhances the hybrid HHL algorithm introduced by the Korean team. QPE enhanced by QCL is called qcl-qpe.

As shown in the figure below, nisq-hhl consists of four steps:

Nisq-hhl end-to-end process

In order to prove the effectiveness of nisq-hhl, the researchers considered a portfolio optimization problem with two S & P 500 assets. The experimental results are obtained on Honeywell ion trap system model H1 and QCL. Model H1 supports intermediate circuit measurement, qubit reset and reuse. The pytket package of Cambridge quantum company is used to transfer the circuit from qiskit to the local gate of H1, compile and optimize it.

Among the components that need Hamiltonian simulation, they calculate u classically. Then, it is passed to qiskit, which decomposes it into basic gates.

They benchmark the performance of standard QPE and qcl-qpe to estimate the eigenvalue of A. The scale parameter of a is set to γ= 100。 They compared the number of gates and qubits required for two QPE implementations to estimate eigenvalues with different accuracy: 3 bits, 4 bits and 5 bits. As shown in the table below, qcl-qpe uses fewer qubits and gates.

With the improvement of precision, the number of double qubit gates implemented by the two QPEs is increasing. However, the number of double qubit gates required to use qcl-qpe (rather than standard implementation) increases to the quadratic power of n (n-1), and N is the bit accuracy.

In addition, even if the bit accuracy increases, the number of qubits in QCL implementation will not change. This is in sharp contrast to the linear growth of standard QPE.

In order to quantify the performance of the two implementations, the researchers compared the fidelity of three accuracies in the two implementations, as shown in the table below.

It can be seen that the computational fidelity of the two implementations is similar for 3-bit estimation. When they increase the accuracy to 4 bits and 5 bits, the circuits in both implementations will deepen, so the fidelity will decrease. However, due to the above advantages, qcl-qpe circuit is shallower than the standard implementation. Therefore, the fidelity of qcl-qpe is still higher than that of standard QPE. As for the fidelity attenuation of 5-bit accuracy, it can be explained by the fact that the number of gates is close to the limit supported by the current device.

By executing nisq-hhl on Honeywell H1 system, the researchers obtained the optimal allocation vector of the portfolio optimization problem with two S & P 500 assets in quantum state. They also show that the nisq-hhl eigenvalue inversion circuit is more effective than the uniformly controlled revolving gate method. This is because the number of controlled rotations is reduced and the circuit depth is reduced. The following table compares:

In addition, the researchers calculated the inner product between the quantum combined state and the classical quantum loaded solution. When executed on hardware and qiskit state vector simulators, using nisq-hhl, they obtained higher inner product than the uniform controlled rotation method. Finally, they demonstrated that nisq-hhl can be easily applied to any given size portfolio.

They considered two portfolio optimization problems including 6 and 14 S & P 500 assets respectively. For these two portfolios, the inner product calculated using nisq-hhl is significantly higher (very close to 1). In addition, compared with the uniformly controlled rotation circuit, the number of rotations and the resulting circuit depth in the nisq-hhl implementation are one order of magnitude less. These results show that nisq-hhl will get very good results when the hardware can support a specified number of qubits and circuit depth in the near future. As shown in the following table: