Hybrid quantum linear equation algorithm and its experimental test on IBM Quantum Experience
Yonghae Lee Jaewoo Joo Soojoon Lee






Department of Mathematics and Research Institute for Basic Sciences,
Kyung Hee University, Seoul 02447, Korea



School of Computational Sciences, Korea Institute for Advanced Study, Seoul 02455, Korea

Clarendon Laboratory, University of Oxford, Parks Road, Oxford OX1 3PU, United Kingdom


Department of Mathematics and Research Institute for Basic Sciences,
Kyung Hee University, Seoul 02447, Korea


School of Mathematical Sciences and Centre for the Mathematics
and Theoretical Physics of Quantum Non-Equilibrium Systems,
University of Nottingham, University Park, Nottingham NG7 2RD, United Kingdom



03.67.Hk, 
89.70.Cf, 
03.67.Mn  









We propose a hybrid quantum algorithm based on the Harrow-Hassidim-Lloyd (HHL) algorithm for solving a system of linear equations. In our hybrid scheme, a classical information feed-forward is required from the quantum phase estimation algorithm to reduce a circuit depth from the original HHL algorithm. 
In this paper,
we show that this hybrid algorithm is functionally identical to the HHL algorithm
under the assumption that the number of qubits used in algorithms is large enough.
In addition,
it is experimentally examined with four qubits in the IBM Quantum Experience setups,
and the experimental results of our algorithm
show higher accurate performance on specific systems of linear equations
than that of the HHL algorithm.


Hybrid quantum linear equation algorithm 

and its experimental test on IBM Quantum Experience
    Soojoon Lee
    December 30, 2023
==============================================================================================








§ INTRODUCTION

A quantum computer is a physical machine based on quantum physics.
Since the Shor's algorithm was known to be a method
for factoring a very large number with exponential speed-up on a quantum computer <cit.>,
various quantum algorithms have been theoretically introduced under the assumption of noiseless quantum computers. However, the performance of quantum algorithms in practice suffers from physical errors in noisy quantum devices under technical limitations (e.g., decoherence).
Thus,
it is of great importance to find more efficient and error-robust methods
for existing quantum algorithms within physical error thresholds for near-term future applications.

The Harrow-Hassidim-Lloyd (HHL) algorithm <cit.> is a well-known and quantum algorithm
for finding the solution x⃗ of a given system of linear equations
represented by an input matrix Â and a vector b⃗.
Intuitively,
the HHL algorithm performs the inverse of the matrix Â on the vector b⃗ in a heralded way and is more efficiently operated with sparse matrix Â.
Because the HHL algorithm demonstrates how to use quantum computers for fundamental mathematical problems, it provides important impact on other quantum applications in other quantum applications such as the quantum machine learning algorithm <cit.>
and the high-order quantum algorithm <cit.> for solving differential equations.

The purpose of this paper is to provide a modified version
of the original HHL algorithm <cit.> to be efficiently operated on both classical and quantum computers in sequential steps.
The main idea of our hybrid algorithm is
to remove an unnecessary quantum part of the original HHL algorithm
with prior classical information, so we call it the hybrid HHL algorithm.
This makes the shortened circuit depth of the original algorithm 
without losing quantum advantages dependent to the original algorithm.
We also demonstrate the hybrid HHL algorithm compared with the original one
with different eigenvalues of Â in the IBM Quantum eXperience (IBMQX) setups,
and show that our hybrid algorithm has more enhanced performance than the other.

This paper is organized as follows.
In Sec. <ref>
we introduce the definitions and details of the original HHL algorithm theoretically.
In Sec. <ref>,
we describe the hybrid HHL algorithm coped with our specific linear system. 
In Sec. <ref>,
we verify that the hybrid algorithm has reduced the effect of the errors from the HHL algorithm tested on the IBMQX setups.
Finally, in Sec. <ref>, we make a summary of our results and a further discussion.









§ PRELIMINARIES
 






 §.§ Definitions

A general form of linear systems of equations is given in

    Âx⃗=b⃗,

where Â is a matrix and b⃗ is a vector.
Throughout this paper,
it is assumed that the matrix Â is Hermitian and the vector b⃗ is unit.
Then the matrix Â has a spectral decomposition <cit.>

    Â=∑_j=1^lλ_j|u_j⟩⟨u_j|,

where
λ_j is an eigenvalue of Â corresponding to the eigenstate |u_j⟩.
From this decomposition,
a unitary operator U_Â 
is defined as follows:

    U_Â=e^2π i Â=∑_j=1^l e^2π iλ_j|u_j⟩⟨u_j|.

It is easy to see that
for any non-zero eigenvalue λ_j of Â
there exists λ'_j∈(0,1) such that e^2π iλ'_j=e^2π iλ_j.
Thus,
for convenience,
we may assume that the eigenvalues of Â are in (0,1).

We then introduce three definitions to explain the main idea of this work.
 
Let λ be a positive real number with the range of (0,1),
then its binary representation is given by

    λ=0.b_1b_2b_3⋯,
 
where b_k∈{0,1} is a k-th bit of the binary representation.
For n∈ℕ,
the n-binary estimation of λ,
say λ(n),
is given by

    λ(n):=b_1b_2b_3⋯ b_n ≈ 2^nλ.



 
Let {λ_j}_j=1^l be the set of all non-zero eigenvalues
of a Hermitian matrix Â.
For k∈ℕ,
define a constant m̅_k as

    m̅_k:=1  l(∑_j=1^lb_k^j),

where b_k^j is the k-th bit of the binary representation of λ_j.
We call m̅_k the k-th eigenmean of Â.
Moreover,
if m̅_k=0 or 1, m̅_k is called fixed.


In Definition <ref>,
we remark that
if the k-th eigenmean of Â is fixed
then every k-th bits of the binary representations of {λ_j}_j=1^l
is equal,
that is,
if m̅_k is fixed then b_k^j_1=b_k^j_2 for any 1≤ j_1,j_2≤ l.



Let λ be an eigenvalue of a Hermitian matrix Â and let n∈ℕ.

(i) λ is called perfectly n-estimated,
if λ satisfies 2^nλ =λ(n),
where λ(n) is the n-binary estimation of λ in Definition <ref>.

(ii) The matrix Â is called perfectly n-estimated,
if all the eigenvalues of Â are perfectly n-estimated.







 §.§ HHL algorithm
 
For a given Âx⃗=b⃗,
the HHL algorithm <cit.> was devised
to figure out the approximation of the expectation value x⃗^†Mx⃗
for some operator M.
In the algorithm,
b⃗ is represented as a quantum state
|b⟩_V=∑_j=1^lα_j|u_j⟩_V,
where |u_j⟩_V is an eigenstate of Â
and α_j∈ℂ such that ∑_j=1^l|α_j|^2=1,
and the solution is given as a quantum state 

    |x⟩_V=Â^-1|b⟩_V/Â^-1|b⟩_V,

where Â^-1 is the inverse matrix of Â.
As shown in Fig. <ref>,
the HHL algorithm with n-qubit register consists of three main parts:
the quantum phase estimation (QPE) algorithm <cit.>
without the final measurement part (we call it as QPE part),
the ancilla quantum encoding (AQE) part,
in which the ancillary qubit A conditionally operates on the state of the register qubits,
and the inverse QPE part.






We first describe the QPE part of the HHL algorithm and assume that the initial state 
is prepared in |0⟩_A⊗|0⟩_R^⊗ n⊗|b⟩_V with a n-qubit register.
After finishing the QPE part,
the state at step (a) in Fig. <ref> is written
by the superposition of the state (see details in Eq. (<ref>))
with index j and the ancillary qubit |0⟩_A such that

    |0⟩_A⊗∑_j=1^l∑_x=0^2^n-1α_jβ_x|j|x⟩_R⊗|u_j⟩_V,

where β_x|j=1/2^n∑_y=0^2^n-1 e^2π i y(λ_j-x/2^n).
Then
the estimated value x in Eq. (<ref>) can be relabeled
with λ_x=x/2^n such as

    |0⟩_A
    ⊗∑_j=1^l∑_x=0^2^n-1α_jβ_x|j|λ_x⟩_R
    ⊗|u_j⟩_V.





In the AQE part,
a quantum encoding operation about the ancillary qubit A is performed,
and the the controlled AQE in Fig. <ref> is given by

    |0⟩_A
    ⊗|λ_x⟩_R
    ↦(√(1-c^2/λ_x^2)|0⟩_A+c/λ_x|1⟩_A)
    ⊗|λ_x⟩_R,

where c=1/Â^-1|b⟩.
In practice,
the value c in Eq. (<ref>)
has to be chosen with O(1/κ) as in <cit.>,
where κ is called the condition number of Â.
Then
the state at step (b) in Fig. <ref> is equal to

    ∑_j=1^l∑_x=0^2^n-1(√(1-c^2/λ_x^2)|0⟩_A+c/λ_x|1⟩_A)
    ⊗α_jβ_x|j|λ_x⟩_R⊗|u_j⟩_V.





If all the eigenvalues λ_j are perfectly n-estimated
then β_x|j = δ_x,2^nλ_j,
and the state in Eq. (<ref>) becomes

    ∑_j=1^l(√(1-c^2/λ_j^2)|0⟩_A+c/λ_j|1⟩_A)
    ⊗α_j|λ_j⟩_R
    ⊗|u_j⟩_V.

Then after performing the inverse QPE part,
the state at step (c) in Fig. <ref> is represented as

    ∑_j=1^l(√(1-c^2/λ_j^2)|0⟩_A+c/λ_j|1⟩_A)
    ⊗|0⟩_R^⊗ n⊗α_j|u_j⟩_V,

in which all the register qubits are reseted in |0⟩_R^⊗ n.
The normalized solution of the linear equation appears
when the measurement of the ancillary qubit A is performed in Z-axis.
In other words,
if the outcome state of A is |1⟩_A,
the state describing the qubit system V successfully represents
the solution of the linear equation as follows:

    1/Â^-1|b⟩∑_j=1^lα_j/λ_j|u_j⟩_V,

where Â^-1|b⟩^2=∑_j=1^l |α_j|^2/λ_j^2.
On the other hand,
if there exists an eigenvalue of Â which is not perfectly n-estimated,
then the total state of Eq. (<ref>) becomes a pure entangled state.
In this case,
the pure state in Eq. (<ref>) turns into
a mixed state which is not the solution of the linear equation.








§ HYBRID HHL ALGORITHM
 






 §.§ Motivation: specific linear equations

For 0<λ<1,
let us now consider the following linear system of equations

    Â_λx⃗=b⃗,

where

    Â_λ=
    (
    [   1/2 λ-1/2; λ-1/2   1/2;       ]),
      b⃗=
    (
    [ 1; 0;   ])=|0⟩.

Then one can readily check that Â_λ is Hermitian,
and can obtain the solution of the equation Â_λx⃗=b⃗
which is given by

    x⃗
    =1/√(2)λ|+⟩+1/√(2)(1-λ)|-⟩,

where 
|±⟩=(|0⟩±|1⟩)/√(2).


From the original HHL algorithm with Â_λ and b⃗ in Eq. (<ref>), we can obtain the fidelity <cit.> between the results of the algorithm with a k-qubit register
(k=1,2,3) and analytical results given by 

    F_k(λ)≡ F(ρ_k,λ,ψ_λ),

where F(·,·) indicates the quantum fidelity,
the final state ρ_k,λ is the solution state describing the qubit system V
obtained at the end of algorithm performance,
and ψ_λ is the normalized solution of x⃗ in Eq. (<ref>).
In Fig. <ref> (a),
the fidelities F_k(λ) are presented with k=1,2,3
(details in Appendix <ref>).
It indicates that more register qubits make a better and larger window
for higher fidelity between outcome states and the analytical solutions. 
From the curves,
we gain two features on the performance of the original HHL algorithm
which have not appeared in any previous literature.
The first feature is that
we can find an exact solution of the linear system of equations
only when the matrix Â_λ is perfectly n-estimated.
In particular,
note that the fidelities reach to 1 with both 2- and 3-qubit registers
for λ = 1/4, 1/2,  3/4.
In other words,
additional register qubits can increase the fidelity
if Â_λ is not perfectly n-estimated.
The second one is that in the HHL algorithm
the use of a smaller size of register provides more precise solutions
at neighborhoods of the perfectly n-estimated eigenvalues.
For example,
we can verify that F_3 <F_2 <F_1 for λ = 0.475 in Fig. <ref> (a).

From the fact that F_2(0.5)=F_3(0.5)=1,
one may think that, for some restriction of λ,
circuit implementations for the HHL algorithm with 3-qubit register can be simplified
by using 2 qubits as register of the algorithm.
For example, the algorithm may be implemented by using a smaller number of gates,
and could have more efficient performance with the reduced amount of errors.
The idea motivates us to devise a quantum linear equation algorithm
whose circuit implementation is more simplified than that of the original HHL algorithm.






 §.§ Description of hybrid HHL algorithm


We here present the hybrid HHL algorithm, which mainly consists of the blocks of the quantum phase estimation algorithm (QPEA), classical computing, and a reduced HHL algorithm to test the original and hybrid HHL algorithms with a two-qubit register as described in Fig. <ref>. In particular, the third part of the hybrid algorithm is called the reduced HHL part because the part is not an independent quantum algorithm.





  * QPEA:
Repeatedly perform the QPEA to obtain k-bit classical information of eigenvalues with Â_λ and |b⟩.


  * Classical Computing:
Analyze measurement outcomes from the first step
by means of classical computers.
Based on the analyzed data,
such as an estimation of the probability distribution in Fig. <ref> (b),
one determines which simpler circuit implementation of the original AQE part,
called the reduced AQE part,
is applicable.
The circuit of the reduced AQE part is implemented by the classical analysis.


  * Reduced HHL: 
Perform 
the HHL algorithm with the reduced AQE part instead of the original AQE part.


Importantly, if the reduced AQE part is not applicable from the second step of the hybrid algorithm due to the lack of capability to distinguish different eigenvalues, the user of the algorithm should restart the first step with more register qubits to perform the reduced HHL part.






 §.§ How does hybrid HHL algorithm work?

Let us consider that our hybrid HHL algorithm is applied
to the linear equation Â_λx⃗=b⃗ in Eq. (<ref>)
when λ=1/4,2/4,3/4,
and that we use only 2 qubits as register of the hybrid HHL algorithm.
Assume that λ=1/4,2/4,3/4 is unknown.

In the first step of the hybrid HHL algorithm,
the QPEA with 2-qubit register is repeatedly performed
on the matrix Â_λ and the state b⃗.
Then as depicted in Fig. <ref> (b),
we may obtain a probability distribution for the measurement outcomes of the QPEA given by

    (j0)
       =   1/16e^-6π iλ ( 1+e^4π iλ)^2 ( (-1)^j + e^2π iλ)^2, 
    
    (01)
       =   (11)
    =-1/8e^-4π iλ( -1+e^4π iλ)^2,

where j=0,1.

In the second step of the algorithm,
we can know what the eigenvalues of Â_λ are
from the probability distribution in Fig. <ref> (b).
In addition,
we can also know that Â_λ is perfectly 2-estimated,
m̅_2 (=1) is a fixed eigenmean
for the matrices Â_1/4 and Â_3/4,
and the matrix Â_2/4 has fixed eigenmeans
m̅_1 (=1) and m̅_2 (=0).
From the classical information,
the AQE part of the HHL algorithm can be simply implemented.
In detail,
the AQE parts for the matrices Â_1/4 and Â_3/4
are given by a controlled-unitary operation

    |0⟩_A|0⟩_r_1   ↦   (√(1-c^2)|0⟩_A+c|1⟩_A)|0⟩_r_1
    |0⟩_A|1⟩_r_1   ↦   (√(1-(c/3)^2)|0⟩_A +c/3|1⟩_A)|1⟩_r_1,

and the AQE for the matrix Â_2/4 is given by a single-qubit unitary operation

    |0⟩_A ↦√(1-(c/2)^2)|0⟩_A+c/2|1⟩_A.


One of the practical drawbacks in the HHL algorithm is that we anyway need to know some partial information of the matrix Â to setup the value c in Eq. (<ref>)
in the physical circuit of the AQE. Our main purpose is to extract this information with QPEA, and then the approximated value c is now known for AQE and reduced AQE.
To implement the original and reduced AQE parts, we employ a specific conditional phase gate R_y(θ_n), where R_y(·) is the rotation gate about the ŷ axis
and θ_n:=2arccos(√(1-c_λ^2/n^2)) 
with c_λ = ∥Â_λ^-1|b⟩∥^-1 for n≥1.

In the third step,
by performing the reduced HHL part on the linear equation Â_λx⃗=b⃗,
whose reduced AQE part is reconstructed
based on Eqs. (<ref>) and (<ref>),
we can obtain the normalized solution of the linear equation in the qubit system V.

In these examples,
our hybrid algorithm solves the linear equation under the condition that 
the matrix Â_λ is perfectly 2-estimated and it has fixed eigenmeans.
In fact,
this condition is indispensable for reducing the AQE part of the original HHL algorithm.
More generally,
the following theorem shows that
if a matrix Â in Eq. (<ref>) is perfectly n-estimated,
and it has fixed eigenmeans,
then we can implement the AQE part by using smaller size of register
when the eigenvalues are known as follows.

 
Let n,k∈ℕ with k≤ n.
If a matrix Â is perfectly n-estimated,
and the matrix Â has k fixed eigenmeans,
then the AQE part can be implemented by (n-k)-qubit register.



Since each eigenvalue λ_j of Â is perfectly n-estimated,
its binary representation can be expressed as

    λ_j=0.b_1^jb_2^j⋯ b_n^j

for some b_i^j∈{0,1}.
Then since β_x|j in Eq. (<ref>) becomes

    β_x|j=1/2^n∑_y=0^2^n-1 e^2π i y(2^nλ_j-x)/2^n=1

if x=2^nλ_j, and β_x|j=0 otherwise,
the state in Eq. (<ref>) must be

    |0⟩_A⊗∑_j=1^lα_j|b_1^jb_2^j⋯ b_n^j⟩_R⊗|u_j⟩_V.


Since the positions of the fixed eigenmeans of Â do not affect this process,
without loss of generality, we may assume that
the k fixed eigenmeans of the matrix Â
are m̅_1,⋯,m̅_k.
Then the state in Eq. (<ref>) becomes

    |0⟩_A
    ⊗|m̅_1⋯m̅_k⟩_r_1⋯ r_k⊗∑_j=1^lα_j|b_k+1^j⋯ b_n^j⟩_r_k+1⋯ r_n⊗|u_j⟩_V,

since m̅_i=b_i^j holds for all j and 1≤ i≤ k.
Thus the AQE part can be implemented
by using (n-k)-qubit register as follows:

    |0⟩_A|y⟩_r_k+1⋯ r_n↦(√(1-c^2/(y'+y)^2)|0⟩_A+c/y'+y|1⟩_A)
    |y⟩_r_k+1⋯ r_n,

where 0≤ y≤2^n-k-1 and y'=∑_i=1^k2^(n-i)m̅_i.


Remark that Theorem <ref>
is useful for our hybrid algorithm as follows.
First of all,
the eigenvalues of Â can be perfectly n-estimated
when a sufficiently large number of qubits are used as register of the HHL algorithm.
Secondly,
since the HHL algorithm deals with positive semidefinite matrices
whose eigenvalues are between 0 and 1 in our case,
the matrix Â can have at least a fixed eigenmean.
Thus, by Theorem <ref>, 
the AQE part can be implemented with the reduced number of qubit register, 
depending on the number of fixed eigenmeans. 
In our hybrid algorithm 
we can correctly guess the eigenvalues of Â with high probability
by means of the QPEA in advance of the HHL algorithm, 
and hence we can in practice implement the reduced AQE part.








§ CIRCUIT IMPLEMENTATION AND EXPERIMENT
 






 §.§ IBM Quantum Experience

The IBMQX is the name of online facilities for general public
who can test their own experimental protocols in five (or sixteen) superconducting qubits.
Although its physical setup consists of a complex architecture built
by superconducting qubits and readout resonators in a single chip,
the user interface is designed with simple diagrams,
which represent single- and two-qubit gates, and 
is easy to understand and to write the programs
without much prior knowledge of quantum information theory and experimental setups.

We in particular use four qubits in the five-qubit systems (called IBMQX2 and IBMQX4)
and they have a different topology of connectivity for two-qubit gates.
For example,
they provide a controlled-NOT (CNOT) gate at the end-user level
but the physical two-qubit gate is actually performed by a cross-resonance gate <cit.>, which implies that additional single-qubit gates are required to match the desired CNOT gate.
Fortunately,
single-qubit gates in their transmon qubits are very accurate
and the fidelity of gate operations mostly depends on that of the cross-resonance gate
and the readout errors after the total quantum operation. For example, we utilize single-qubit R_z gates for the algorithms as much as we can because this can be realized without applying any microwave but with only shifting the phase of the next applied microwave <cit.>. 

Because the IBMQX setup shows the daily small fluctuation of parameters,
they provide average device calibrations,
which might be useful for understanding the imperfection of the experimental data.
For example,
the transmons energy frequency (between |0⟩ and |1⟩) is roughly about 5 GHz,
which is fit to the microwave frequency with 6 cm wavelength.
Importantly,
one of the important measures for coherence time is T_1 ≈ 50 μs,
and it approximately limits the total operation time t in performance of quantum processing
such as |1⟩⟨1|→ e^-t/T_1|1⟩⟨1| for a single-qubit decay rate.
For example,
the CNOT gate (consisting of a cross-resonance gate and a few single-qubit gates) takes
around 200 ns,
and it roughly indicates that 50 times of CNOT gates might not exceed the fidelity 0.82
because e^-1/5≈ 0.82 at the current IBMQX setup.
Therefore,
the hybrid quantum algorithm might be beneficial
for experimental demonstrations under practical circumstances
because it has simpler quantum gates with the support of classical information processing.







 §.§ Setups for circuit implementations on IBMQX

We now describe experimental setups of the hybird HHL algorithm
compared with the original HHL algorithm with two qubit register
to solve the linear equation given
by the parameterized matrix Â_λ in Eq. (<ref>).
In addition,
we only deal with the matrices Â_1/4 and Â_2/4,
since Â_1/4 and Â_3/4 have the same eigenvalues.
In the IBMQX setups, it is also possible to test the algorithms by using a three-qubit register.
However, the complex circuit implementations dramatically decrease
the fidelities of the solutions beyond the analysis scope.
More importantly,
because the original and hybrid HHL algorithms exactly find
the same solution of Â_λx⃗=b⃗
for the ideal (no-error) cases that λ=1/4, 2/4,
it is crucial to compare the performance of the original and hybrid HHL algorithms
under the IBMQX setups under error-propagating circumstances. Note that a similar experimental investigation has been recently shown
with fixed matrix Â, which cannot cover the class of our parameterized matrix in Eq. (<ref>) <cit.>. 

As explained in Section <ref> and Fig. <ref>,
the original HHL algorithm consists of the QPE, the AQE,
and the inverse QPE with a qubit measurement on the ancillary qubit,
as shown in the top of Fig. <ref>.
The QPE part is mainly decomposed by the parts (a) and (b)
in Fig. <ref> or Fig. <ref>.
The first part (a) consists of two controlled unitary gates
whose circuit implementations <cit.> are found in Fig. <ref> (a).
The second part (b) is the inverse of the two-qubit QFT,
which is a combination of a SWAP gate, two CNOT gates, and some single-qubit gates 
shown in Fig. <ref> (b).
After the inverse QPE part,
if the ancillary qubit is measured in |1⟩_A,
the register qubits always become |00⟩_r_1 r_2 in principle.
However,
the propagated errors during the whole operation time might cause the other outcomes (≠|00⟩_r_1 r_2) in real experiments. This can be verified by setting the measurements of register qubits in Fig. <ref> (c) to post-select successful outcomes.  

For the hybrid HHL algorithm in Fig. <ref>,
classical computing is sandwiched between two quantum computing parts.
The first part of the quantum algorithm is called QPEA
similar to the QPE part in the original HHL.
After the measurement of the two-qubit register (step 1), 
the analysis from classical computing decides the operation angles (θ_j) in the reduced AQE circuit (AQE) with respect to the measured first two digits in r_1 and r_2 (step 2). Finally, the chosen angles from the classical imformation are applied in the lightened circuit of AQE (step 3). The original and reduced AQE circuits are shown in Fig. <ref> (c) and (d), respectively.

Therefore,
we will show the experimental results of QPEA and the reduced HHL parts with λ=1/4,1/2
compared with the original HHL algorithm in the next subsection.
If we consider a general case that λ≠  k/4 with k=1,2,3,
we cannot exactly estimate the eigenvalues of Â_λ
from the probability distribution given in Fig. <ref> (b) and request more register qubits for the algorithm, however,
it also indicates that a small variance of eigenvalues
(|λ - k/4| = δ with small δ)
would give us a high fidelity of the solution state (even better than using a three-qubit register in principle) as shown in Fig. <ref> (a).







 §.§ Experimental results for QPEA and Reduced HHL parts

We here examine the original and hybrid HHL algorithms at the setups of IBMQX4. 
The experiments of QPEA are performed by using six CNOTs,
and the original HHL algorithm requires 28 CNOT gates
while the reduced HHL algorithm now has 14 CNOT gates.
Thus,
this indicates the reduction of 14 CNOT gates from the original HHL algorithm.
Note that ten sets of experimental data are used for each λ
with 1024 single-shot readouts per set for individual algorithms.

The QPE in the original HHL and QPEA in the hybrid HHL commonly have (a) a set of controlled unitary operations with U_λ^m=(e^2πÂ_λ)^m
and (b) the inverse QFT for two qubits shown in Fig. <ref>. The only difference between them is the measurement part in QPEA.
The hybrid scheme first accepts the results of QPEA to estimate partial information of eigenvalues
in two bits used for building the QAE circuit
as shown in Fig. <ref> (d).
From the results depicted in Fig. <ref> (a),
we can verify that the performance of the QPEA on IBMQX is quite useful to confirm the first two bits of the eigenvalues of Â_λ even with some unavoidable errors in the IBMQX circuit.






In Fig. <ref> (b),
the probabilities of theoretical and two experimental cases are depicted
for both the original and reduced HHL algorithms.
The solution state |x⟩_V is measured in observable X
in the basis set of {|+⟩,|-⟩}
to verify the experimental solution state for both algorithms.
We also perform ten sets of data with 1024 single shots per set.
Since |x⟩_V is represented by c_+|+⟩+c_-|-⟩,
where c_±∈ℂ such that |c_+|^2+|c_-|^2=1,
probabilities |c_+|^2 and |c_-|^2 tell us
how close |x⟩_V is to the theoretical solution.
As mentioned earlier,
the solution of the linear equation is obtained
when the ancillary qubit is |1⟩ after measured by Z.
Theoretically,
this probability of the post-measurement state |1⟩ is quit small
in the case of the linear equation in Eq. (<ref>). 
This means that only the minority data contribute to plot
the probabilities |c_+|^2 and |c_-|^2.

From Fig. <ref>,
we can know that the solution of the reduced HHL part is more accurate than
that of the original HHL algorithm.
The figure shows that,
if we accept to use the first two bits of QPEA for the reduced AQE circuit,
we can conclude that the results of the hybrid algorithm are closer to the theoretical results
than that of the original HHL algorithm in the IBMQX setups.









§ CONCLUSION
 

We have described the HHL algorithm which solves a quantized version of given linear equations.
We have especially analyzed the QPE part of the HHL algorithm,
and have devised the hybrid version of the HHL algorithm. Under the IBMQX setups,
we have shown that the hybrid algorithm can reduce the number of two-qubit gates, and thus has more enhanced performance than that of the HHL algorithm for some specific linear equations.


The hybrid HHL algorithm stems from the fact
that the QPE part of the HHL algorithm is identical to the QPEA without measurement.
It follows that the AQE part of the original HHL algorithm can be reconstructed
if we are able to obtain classical information from measurement outcomes of the prior QPEA
to solve a linear equation.
We remark that
an iterative QPEA <cit.> can be used as the first step of our hybrid algorithm.
Since the iterative QPEA does not need the quantum Fourier transform for its implementation,
the small number of qubits is required.
So the use of the iterative QPEA would improve the resource efficiency of the hybrid algorithm. 
In addition,
there have been some results in literature <cit.>
which generalize or improve the QPEA,
and we expect that combining these results with the hybrid algorithm
leads to other new hybrid quantum linear equation algorithms.
Finally,
there have been developed some quantum algorithms,
such as the quantum counting algorithm <cit.>,
the quantum machine learning algorithm <cit.>,
and the high-order quantum algorithm <cit.>,
which have relevance to the QPEA or the HHL algorithm.
Hence, it would be interesting to find out hybrid versions for these algorithms.

Regarding quantum supremacy <cit.>,
IBM has currently announced a new term, quantum volume <cit.>,
which measures the useful amount of quantum computing done
by a quantum device with specific number of qubits and error rate.
In addition,
error mitigation approaches <cit.>
have shown a new direction of managing the error accuracy for specific cases.
In order to apply this extrapolation scheme,
the amount of errors should be sufficiently small to claim
that the error-propagation curve is linear.
As mentioned earlier, 
the reduced HHL part of our hybrid algorithm can be implemented
by a smaller number of quantum gates,
which reduces the total error rate from the gates.
Hence,
we expect that the technique in the hybrid algorithm can be adopted in quantum algorithms
to show quantum supremacy.








§ ACKNOWLEDGMENTS

This research was supported 
by Basic Science Research Program 
through the National Research Foundation of Korea (NRF) funded 
by the Ministry of Science and ICT (NRF-2016R1A2B4014928) and the MSIT (Ministry of Science and ICT), Korea, under the ITRC (Information Technology Research Center) support program (IITP-2018-2018-0-01402) supervised by the IITP (Institute for Information & communications Technology Promotion).
JJ acknowledges support from the EPSRC National Quantum Technology Hub in Networked Quantum Information Technology
(EP/M013243/1).
We acknowledge use of the IBMQX for this work.
The views expressed are those of the authors 
and do not reflect the official policy or position of IBM 
or the IBMQX team.














§ QUANTUM PHASE ESTIMATION ALGORITHM
 

Suppose that a matrix Â is Hermitian
with an eigenvalue λ in (0,1) with respect to the corresponding eigenstate |u⟩.
For the unitary operation U_Â defined as in Eq. (<ref>),
we obtain

    U_Â|u⟩=e^2π i Â|u⟩=e^2π i λ|u⟩.

The aim of the QPEA is to find out an estimated value of λ,
which is given by a binary string.
The QPEA is performed with the input eigenstate |u⟩ and n-qubit register.
Then the estimated value of λ is obtained by measuring this n-qubit register
as described in Fig. <ref>.

Specifically,
let us explain a process of the QPEA on Â in Eq. (<ref>)
and its eigenstate |u_j⟩ in Eq. (<ref>).
The total input state of the QPEA is initialized
in a quantum state |0⟩_R^⊗ n⊗|u_j⟩_V
and Hadamard operations are firstly performed in n-qubit register,
as shown in Fig. <ref>.
After n controlled unitary gates, controlled-U_Â^2^n-1,
the state (a) in Fig. <ref> is given in 

    1/√(2^n)∑_y=0^2^n-1 e^2π i λ_j y|y⟩_R⊗|u_j⟩_V.

Then,
the inverse of quantum Fourier transform is applied in the register qubits,
and the state (b) in Fig. <ref> can be written in

    1/2^n∑_x,y=0^2^n-1
    e^2π i y(λ_j-x/2^n)|x⟩_R⊗|u_j⟩_V.

Finally, each qubit in the register system R is measured with observable Z.
For large n,
if the measured outcome x in register qubits is close to λ_j(n),
we find that (x) is also close to one.
Otherwise,
if x is close to another n-bit string which is not λ_j(n),
(x) is close to zero. 
Therefore for sufficiently large n, 
we are able to obtain the n-binary estimation λ_j(n) of λ_j
from the probability distribution of the measurement outcomes.








§ FIDELITIES IN FIG. <REF> (A)
 
We here present explicit expressions of the fidelities in Fig. <ref> (a).
For i=1,2,3 and λ∈(0,1),
denote F_i(λ) as the fidelity
between an exact normalized solution and the solution obtained
from the HHL algorithm with i-qubit register.
Let t_λ=e^2 i πλ, and t_λ^* be the complex conjugate of t_λ.
Then


    F_1(λ)=
    1/2(
    1 + (t_λ+t_λ^*)
     (-1 + λ) λ/1 - 2 λ + 2 λ^2).


Let X_λ=(40 + 32 i) - (129 + 64 i) λ + 129 λ^2
and Y_λ=(9 + 32 i) - (146 + 64 i) λ + 146 λ^2.
Then

    F_2(λ)   =   
    (t_λ^*)^3
    [(
    25 + 80 t_λ + 171 t_λ^2 + 171 t_λ^8 + 80 t_λ^9
    + 25 t_λ^10) (-1 + λ) λ +  4 t_λ^4 X_λ
    + 4 t_λ^6 X_λ^* + 2 t_λ^3 Y_λ + 2 t_λ^7 Y_λ^*
     
          + 4 t_λ^5 (89 - 170 λ + 170 λ^2)]/
    [4 (9 + 80 t_λ + 178 t_λ^2
    + 80 t_λ^3 + 9 t_λ^4) (1 - 2 λ + 2 λ^2)].


Let A=140+105i,
B=(208+128i)√(2),
C=8(35 + 52√(2)),
D=8(-35 + 52√(2)),
E=2(105 + 128√(2)),
F=-210 + 256√(2),
G=11025 + 76672√(2),
and H=-11025 + 76672√(2),
and let
α_λ=-(t_λ^*)^14/(128(1 - 2 λ + 2 λ^2)),
β_λ=α_λ(-1 + t_λ^8)^2,
γ_λ=350 + 608i - 700λ,
ϕ_λ=315 + 420i + (384 - 624i)√(2) - 3Eλ,
ξ_λ=-304 + 175i + 608λ.
Then we have the fidelity

    F_3(λ)=∑_j=1^8 N_j(λ)/D(λ),

where

    N_1(λ)   =   α_λ[
    A^*+ B - 1276it_λ^3
    + 8712it_λ^7 - 1276it_λ^11- Cλ
    + (6t_λ^5+2t_λ^13)ξ_λ^*
    - (2t+6t_λ^9)ξ_λ
           + (5t_λ^4+3t_λ^12)
    (A^* - B +Dλ)- (3t_λ^2+5t_λ^10)
    (A -B^* +Dλ) - 7t_λ^8(-A^* - B +Cλ) 
          + (7t_λ^6+t_λ^14)
    (-A -B^* +Cλ) 
    ]^2, 
    
    N_2(λ)   =   β_λ[
    A^*i + Bi + Fλ + t_λ^5γ_λ^*
    + tγ_λ -1276t_λ^3(-1 + 2 λ) + t_λ^4ϕ_λ
    + t_λ^2ϕ_λ^* + t_λ^6(-Ai -B^*i + Fλ)
    ]^2, 
    
    N_3(λ)   =   β_λ[
    A^*i +Bi + Fλ
    + t_λ^5γ_λ^*
    + t_λγ_λ
    + t_λ^4(A^*i -Bi -Eλ)
    + t_λ^2(-Ai +B^*i -Eλ)
    + t_λ^6(-Ai -B^*i + Fλ)
    ]^2, 
    
    N_4(λ)   =   β_λ[
    -A^* - B + Cλ
    + 2t_λ^5ξ_λ^*
    + 2t_λξ_λ
    + t_λ^4(A^* - B +Dλ)
    + t_λ^2(A -B^* +Dλ)
    + t_λ^6(-A -B^* +Cλ)
    ]^2, 
    
    N_5(λ)   =   β_λ[
    A^*i +Bi + Fλ
    + t_λ^4(A^*i -Bi -Eλ)
    + t_λ^2(-Ai +B^*i -Eλ)
    + t_λ^6(-Ai -B^*i + Fλ)
    ]^2, 
    
    N_6(λ)   =   β_λ[
    -A^* - B + Cλ
    + t_λ^4(A^* - B +Dλ)
    + t_λ^2(A -B^* +Dλ)
    + t_λ^6(-A -B^* +Cλ)
    ]^2, 
    
    N_7(λ)   =   β_λ[
    -A^* - B + Cλ
    + t_λ^4(-A^* + B -Dλ)
    - t_λ^2(A -B^* +Dλ)
    + t_λ^6(-A -B^* +Cλ)
    ]^2, 
    
    N_8(λ)   =   β_λ[
    A^*i +Bi + Fλ
    + t_λ^6(-Ai -B^*i + Fλ)
    + t_λ^2(A^*i -B^*i + 2Eλ)
    + t_λ^4(-A^*i +Bi + 2Eλ)
    ]^2, 
    
    D(λ)   =   
    (t_λ^*)^7[
    H - 75950t_λ -3Gt_λ^2
    - 586524t_λ^3 -5Gt_λ^4
    - 227850t_λ^5 +7Ht_λ^6
          +2133448t_λ^7 +7Ht_λ^8
    - 227850t_λ^9 -5Gt_λ^10
    - 586524t_λ^11 -3Gt_λ^12
    - 75950t_λ^13 + Ht_λ^14
    ].




