Interactive Quantum Circuits

Algorithm Overview

The HHL algorithm is a quantum circuit that inverts a Hermitian matrix, , and encodes the dot product of the inverted matrix and a vector into a quantum state, hence finding the solution, , to the linear system of equations .

Circuit Explanation

In the following, consider the system of linear equations in matrix form: , where is an square matrix, is an -dimensional vector, and is the solution vector.

The HHL circuit spans three quantum registers: the state register, with qubits; the eigenvalue register, with qubits; and an auxiliary register with a single qubit, also known as the ancilla qubit. The state register is initialised to encode into a quantum state . All other qubits are initialised to . The precision of the algorithm is defined by , as the eigenvalues are encoded in binary form into the eigenvalue register.

The circuit displayed above is for a system of linear equations (), with precision eigenvalue qubits.

The first operation in the circuit, labelled , represents an initialize instruction, which initialises the state register to the quantum state (equivalent to the normalised form of ).

Next, the HHL algorithm uses Quantum Phase Estimation (QPE) as a subroutine to find the eigenvalues, , of the given matrix , as shown in the circuit above.

It then uses controlled rotations to invert the eigenvalues in a process called Ancilla Quantum Encoding (AQE), and uses inverse QPE (that's the second QPE gate, with the dagger to indicate inverse) to "uncompute" the inverted eigenvalues, such that the final quantum state encodes in the amplitudes of the state register.

At the end of the algorithm, an observable constructed for the specific application is applied to the state to learn some information from it. The observable is a subcircuit that manipulates the state before measurement. In the vast majority of cases HHL will be executed many times, with the measurements sampling a probability distrubtion, which is generally what is wanted as output.

If the full solution, , to the equation is needed, then the observable changes nothing (is just the identity matrix) and measurements of the state and ancilla qubits from many executions of the circuit are required.

If all goes well, the final state of the clock register should be all zeroes. Measurements of these qubits may be used to verify that the circuit worked correctly, and get an estimate of the error due to noise.

Mathematical Proofs

Let be the eigenvector basis of , such that , where are the eigenvalues of .

can be written as a sum of eigenvectors, . is diagonal in its eigenvector basis, so its inverse can be written as .

The vector, , and its corresponding quantum state can also be represented in the eigenvector basis of , as below:

The values are the components of the transformed vector in 's eigenvector basis.

It follows that the solution state, , can be encoded as follows:

The goal of the HHL algorithm is to convert the state into in a quantum circuit, using the aforementioned mathematical relationships [Reference "HHL step-by-step walkthrough"].

The total HHL state, , is initialised such that the state register is in the initial state :

Where the subscripts , , and are labels to keep track of the state, eigenvalue, and auxiliary (ancilla) registers, respectively.

Using equation 1, this state may be written as:

The HHL algorithm uses Quantum Phase Estimation (QPE) as a subroutine to find the eigenvalues, , of the given matrix . During QPE, each eigenvalue of is encoded into a phase, , theoretically defined as:

However, in practice, the phases are rounded to a precision defined by :

Thus, the precision of the algorithm is defined by , as the phases are encoded into the eigenvalue register in binary form.

After QPE, the register contains the binary-encoded eigenvalues of :

HHL then uses controlled rotations to encode the eigenvalues into the amplitude of the ancilla qubit in a process called Ancilla Quantum Encoding (AQE):

Where is a constant with the restriction .

The HHL algorithm succeeds if the ancilla qubit collapses to a during measurement. Thus, the theoretical success rate of the algorithm can be derived from equation 3:

is hence chosen to be as large as possible, to maximise the success rate of the algorithm.

Finally, inverse QPE is used to disentangle the and registers, such that (by equation 2) the final quantum state encodes in the amplitudes of the quantum state. For simplicity, the following equation only shows the post-selected state where the ancilla qubit is 1 (hence, this is not a complete state).

Literature

Quantum algorithm for linear systems of equations

[citation]

Use Cases

Extra Information

Theoretical problems

Implementation problems