Inputs

This schematic shows that HHL accepts two sets of input registers, and a matrix (via a quantum simulation):

Scratch register

This contains a number of scratch qubits used by various primitives within HHL, all prepared in the ∣0⟩ state. Because HHL deals with fixed-point (or floating-point) data and involves nontrivial arithmetic operations (such as taking the square root), we require a lot of scratch qubits. This makes HHL difficult to simulate for even the simplest cases.

Amplitude encoding of $\overrightarrow{b}$

We also need to provide HHL with the vector $\overrightarrow{b}$ from Equation 13-2, amplitude-encoded in a QPU register (in the sense we discussed in Chapter 9). We will denote the state of a register amplitude encoding $\overrightarrow{b}$ as ∣$\overrightarrow{b}$〉. Note that to prepare an amplitude encoding of $\overrightarrow{b}$ we will need to use QRAM. Thus, HHL fundamentally relies on the existence of QRAM.

QPU operation representing A

Naturally, HHL also needs access to the matrix encapsulating the system of linear equations we wish to solve. The bottom of Figure 13-1 illustrates how HHL requires us to represent A as a QPU operation, which we can achieve via the process of quantum simulation outlined in Chapter 9. This means that the matrix A must meet the requirements we noted for performing quantum simulation.

Outputs

Figure 13-1 also shows that two registers are output from HHL.

Solution register

The solution vector $\overrightarrow{x}$ is amplitude-encoded within a single output QPU register (we denote this state as ∣$\overrightarrow{x}$〉). As we’ve already stressed, this implies that we cannot access the individual solutions, since they’re hidden in the amplitudes of a quantum superposition that we cannot hope to efficiently extract with READ operations.

Scratch register

The scratch qubits are returned to their starting state of ∣0⟩, allowing us to continue using them elsewhere in our QPU.

Here are some examples of ways in which the quantum output from HHL can still be incredibly useful despite its inaccessible nature:

1. Rather than a specification of solutions for all n variables in $\overrightarrow{x}$, we may only wish to know some derived property, such as their sum, mean value, or perhaps even whether or not they contain a certain frequency component. In such cases we may be able to apply an appropriate quantum circuit to ∣$\overrightarrow{x}$〉, allowing us to READ the derived value.

2. If we are satisfied with checking only whether or not the solution vector $\overrightarrow{x}$ is equal to one particular suspected vector, then we can employ the swap test introduced in Chapter 3 between ∣$\overrightarrow{x}$〉 and another register encoding the suspected vector.

3. If, for example, we plan to use the HHL algorithm as a component in a larger algorithm, ∣$\overrightarrow{x}$〉 may be sufficient for our needs as is.

Since systems of linear equations are fundamental in many areas of machine learning, HHL is the starting point for many other QML applications, such as regression³ and data fitting.⁴

Speed and fine print

The HHL algorithm has a runtime⁵ of $O({\kappa }^2{s}^2{ϵ}^{-1}logn)$.

In comparison with the conventional method of conjugate gradient descent and its runtime of $O(ns\kappa log(1/ϵ))$, HHL clearly offers an exponential improvement in the dependence on the size of the problem (n).

One could argue that this is an unfair comparison, since conventional conjugate gradient descent reveals the full set of solutions to us, unlike the quantum answer generated by HHL. We could instead compare HHL to the best conventional algorithms for determining derived statistics from solutions to systems of linear equations (sum, mean, etc.), which have n and κ dependencies of $O\left(n\sqrt{\kappa }\right)$, but HHL still affords an exponential improvement in the dependence on n.

Although it’s tempting to focus solely on how algorithms scale with the problem size n, other parameters are equally important. Though offering an impressive exponential speedup in terms of n, HHL’s performance is worse than conventional competitors once we consider poorly conditioned or less sparse problems (where κ or s becomes important).⁶ HHL also suffers if we demand more precision and place importance on the parameter $ϵ$.

For these reasons, we have the following fine print:

The HHL algorithm is suited to solving systems of linear equations represented by sparse, well-conditioned matrices.

Additionally, since HHL leverages a quantum simulation primitive, we need to take note of any requirements particular to whichever quantum simulation technique we employ.

Having done our best to give a realistic impression of HHL’s usage, let’s break down how it works.

1. Quantum simulation, QRAM, and phase estimation

We already know that the phase estimation primitive can efficiently find the eigenstates and eigenphases of a QPU operation. You might suspect that this could help us in using the eigendecomposition approach to inverting a matrix—and you’d be right!

Figure 13-2 shows that we begin by using QRAM to produce a register with an amplitude encoding of $\overrightarrow{b}$ and quantum simulation to produce a QPU operation representing A. We then feed both of these resources into the phase estimation primitive as shown in Figure 13-3.

Figure 13-3. Recap of phase estimation primitive, where we have identified the eigenphase obtained in the output register as the eigenvalue of A

Figure 13-3 helps us recall that two input registers are passed to the phase estimation primitive. The lower eigenstate register takes an input specifying an eigenstate of the QPU operation for which we would like the associated eigenphase. The upper output register (initialized in state ∣0⟩) produces a representation of the eigenphase, which in our case is an eigenvalue of A.

So phase estimation provides an eigenvalue of A. But how do we get all n eigenvalues?

Running phase estimation n separate times would reduce HHL’s runtime to O(n)—no better than its conventional counterparts. We could input a uniform superposition in the eigenstate register and calculate the eigenvalues in parallel, producing a uniform superposition of them in the output register. But suppose we take a slightly different approach and instead send the amplitude encoding of $\overrightarrow{b}$ in the eigenstate register? This results in the output register being a superposition of A’s eigenvalues, but one that is entangled with the amplitude encoding of $\overrightarrow{b}$ produced in the output register.

This will be far more useful to us than just a uniform superposition of the eigenvalues, since now each ∣${\lambda }_i$〉 within the entangled state of eigenstate and output registers has an amplitude of ${\tilde{b}}_i$ (thanks to the eigenstate register). This isn’t quite what we want to produce the solution as shown in Equation 13-6, however. The output register’s state represents the eigenvalues of A. What we really want is to invert these eigenvalues and—instead of them being held in another (entangled) register—move them into values multiplying the amplitudes of the eigenstate register. The next steps in HHL achieve this inversion and transfer.

2. Invert values

The second primitive in Figure 13-2 inverts each ${\lambda }_i$ value stored in the (entangled) superposition of the output and eigenstate registers.

At the end of this step the output register encodes a superposition of ∣$1/{\lambda }_i$〉 states, still entangled with the eigenstate register. To invert numerical values encoded in a quantum state we actually utilize a number of the arithmetic primitives introduced in Chapter 5. There are many different ways we could build a QPU numerical inversion algorithm from these primitives. One possibility is to use the Newton method for approximating the inverse. Whatever approach we take, as we noted in Chapter 12, division is hard. This seemingly simple operation requires a significant overhead in qubit numbers. Not only will the constituent operations require scratch qubits, but dealing with inverses means that we have to encode the involved numerical values in either fixed- or floating-point representations (as well as dealing with overflow, etc.). In fact, the overheads required by this step are a contributing factor to why a full code sample of even the simplest HHL implementation currently falls outside the scope (and capabilities!) of what we can reasonably present here.⁹

Regardless, at the end of this step, the eigenstate register will contain a superposition of $1/{\lambda }_i$ values.

3. Move inverted values into amplitudes

We now need to move the state-encoded inverted eigenvalues of A into the amplitudes of this state. Don’t forget that the amplitude-encoded state of $\overrightarrow{b}$ is still entangled with all this, so getting those inverted eigenvalues into the state amplitudes would yield the final line in Equation 13-6, and therefore an amplitude encoding of the solution vector ∣$\overrightarrow{x}$〉.

The key to achieving this is applying a C-ROTY (i.e., a conditional ROTY operation; see Chapter 2). Specifically, we set the target of this conditional operation to a new single scratch qubit (labeled ROTY scratch in Figure 13-2), initially in state ∣0⟩. It’s possible to show (although not without resorting to much more mathematics) that if we condition this ROTY on the inverse cosine of the $1/{\lambda }_i$ values stored in the output register, then the amplitudes of all parts of the entangled output and eigenstate registers where ROTY scratch is in the ∣1⟩ state acquire precisely the $1/{\lambda }_i$ factors that we’re after.

Consequently, this transfer step of the algorithm consists of two parts:

1. Calculate $arccos(1/{\lambda }_i)$ in superposition on each state in the output register. This can be achieved in terms of our basic arithmetic primitives,¹⁰ although again with a significant overhead in the number of additional qubits required.

2. Perform a C-ROTY between the first register and the ROTY scratch (prepared in ∣0⟩).

At the end of this we will have the state we want if ROTY scratch is in state ∣1⟩. We can ensure this if we READ the ROTY scratch and get a 1 outcome. Unfortunately, this only occurs with a certain probability. To increase the likelihood that we get the needed 1 outcome we can employ another of our QPU primitives, performing amplitude amplification on the ROTY scratch.

4. Amplitude amplification

Amplitude amplification allows us to increase the probability of getting an outcome of 1 when we READ the single-qubit ROTY register. This then increases the chance that we end up with the eigenstate register having the desired ${\tilde{b}}_i/{\lambda }_i$ amplitudes.

If despite the amplitude amplification a READ of ROTY scratch still produces the undesired 0 outcome, we have to discard the states of the registers and rerun the whole HHL algorithm from the beginning.

5. Uncompute

Assuming success in our previous READ, the eigenstate register now contains an amplitude encoding of the solutions $\overrightarrow{x}$. But we’re not quite done. The eigenstate register is still entangled not only with the output register, but also with the many other scratch qubits we’ve introduced along the way. As mentioned in Chapter 5, having our desired state entangled with other registers is troublesome for a number of reasons. We therefore apply the uncomputation procedure (also outlined in Chapter 5) to disentangle the eigenstate register.

Bingo! The eigenstate register now contains a disentangled amplitude encoding of $\overrightarrow{x}$ ready to be used in any of the ways suggested at the start of this section.

HHL is a complex and involved QPU application. Don’t feel intimidated if it takes more than one parse to get to grips with; it’s well worth the effort to see how a more substantial algorithm masters our QPU primitives.

Concern 1: Is F suitable for HHL?

It’s not too tricky to see that the matrix F is Hermitian, and so we can potentially represent it as a QPU operation using the quantum simulation techniques from Chapter 9. As we previously noted, being Hermitian, although necessary, is not sufficient for a matrix to be efficiently used in quantum simulation. However, it’s also possible to see that a matrix of the form F can be decomposed into a sum of matrices, each of which satisfies all the requirements of quantum simulation techniques. So it turns out that we can use quantum simulation to find a QPU operation representing F. Note, however, that the nontrivial elements of F consist of inner products between the training data points. To efficiently use quantum simulation for representing F as a QPU operation we will need to be able to access the training data points using QRAM.

Concern 2: How can we act F^–1 on $[0,\overrightarrow{y}]$?

If we’re using HHL to find F^–1 then we can take care of this concern during the phase estimation stage of the algorithm. We input an amplitude encoding of the vector of training data classes, ∣${\overrightarrow{y}}^{\text{'}}$〉, into the phase estimation’s eigenstate register. Here we use ∣${\overrightarrow{y}}^{\text{'}}$〉 to denote a QPU register state amplitude-encoding the vector $[0,\overrightarrow{y}]$. This, again, assumes that we have QRAM access to the training data classes. By the same logic we described when originally explaining HHL in “Solving Systems of Linear Equations”, ∣${\overrightarrow{y}}^{\text{'}}$〉 can be thought of as a superposition of the eigenstates of F. As a consequence, when we follow through the HHL algorithm we will find that ∣$F^{-1}\overrightarrow{y}$〉 is contained in the final output register, which is equal to precisely the solutions that we desire: ∣$b,\overrightarrow{\alpha }$〉. So we don’t have to do anything fancy—HHL can output F^–1 acted on the required vector, just as it did when we originally used it for solving systems of linear equations more generally.

Concern 3: How do we classify data?

Suppose we are given a new data point $\overrightarrow{x}$, which we want to classify with our trained QSVM. Recall that a “trained QSVM” is really just access to the state ∣$b,\overrightarrow{\alpha }$〉. We can perform this classification efficiently so long as we have QRAM access to the new data point $\overrightarrow{x}$. Classifying the new point requires computing the sign given by Equation 13-8. This, in turn, involves determining the inner products of $\overrightarrow{x}$ with all the training data points ${\overrightarrow{x}}_i$, weighted by the LS-SVM dual hyperplane parameters $\alpha$_i. We can calculate the requisite inner products in superposition and assess Equation 13-8 as follows. First we use our trained LS-SVM state ∣$b,\overrightarrow{\alpha }$〉 in the address register of a query to the QRAM holding the training data. This gives us a superposition of the training data with amplitudes containing the $\alpha$_i. In another register we perform a query to the QRAM containing the new data point $\overrightarrow{x}$.

Having both of these states, we can perform a special swap-test subroutine. Although we won’t go into full detail, this subroutine combines the states resulting from our two QRAM queries into an entangled superposition and then performs a carefully constructed swap test (see Chapter 3). Recall that as well as telling us whether the states of two QPU registers are equal or not, the exact success probability p of the READ involved in the swap test is dependent on the fidelity of the two states—a quantitative measure of precisely how close they are. The swap test we use here is carefully constructed so that the probability p of READing a 1 reflects the sign we need in Equation 13-8. Specifically, p < 1/2 if the sign is +1 and p >= 1/2 if the sign is –1. By repeating the swap test and counting 0 and 1 outcomes, we can estimate the value of the probability p to a desired accuracy, and classify the data point $\overrightarrow{x}$ accordingly.

Thus, we are able to train and use a quantum LS-SVM model according to the schematic shown in Figure 13-8.

Without delving into mathematical details, like those of the swap-test subroutine, Figure 13-8 gives only a very general overview of how LS-SVM training proceeds. Note that many details of the swap-test subroutine are not shown, although the key input states are highlighted. This gives some idea of the key roles the QPU primitives we’ve introduced throughout the book play.

Our QSVM summary also provides an important take-home message. A key step was recasting the SVM problem in a format that is amenable to techniques a QPU is well suited for (in particular, matrix inversion). This exemplifies a central ethos of this book—through awareness of what a QPU can do well, domain expertise may allow the discovery of new QPU applications simply by casting existing problems in QPU-compatible forms.

Figure 13-8. Schematic showing the stages in training and classifying with a QSVM