Quantum algorithm for linear systems of equations (HHL09): Step 2 - Preparation of the initial states $|\Psi_0\rangle$ and $|b\rangle$

Question

^{This is a continuation of Quantum algorithm for linear systems of equations (HHL09): Step 2 - What is $|\Psi_0\rangle$?}

---

In the paper: Quantum algorithm for linear systems of equations (Harrow, Hassidim & Lloyd, 2009), the details of the actual implementation of the algorithm is not given. How exactly the states $|\Psi_0\rangle$ and $|b\rangle$ are created, is sort of a "black-box" (see pages 2-3).

$$|\Psi_0\rangle = \sqrt{\frac{2}{T}}\sum_{\tau = 0}^{T-1}\sin \frac{\pi (\tau+\frac{1}{2})}{T}|\tau\rangle$$

and $$|b\rangle = \sum_{1}^{N}b_i|i\rangle$$

where $|\Psi_0\rangle$ is the initial state of the clock register and $|b\rangle$ is the initial state of the Input register.

(Say) I want to carry out their algorithm on the IBM $16$-qubit quantum computer. And I want to solve a certain equation $\mathbf{Ax=b}$ where $\mathbf{A}$ is a $4\times 4$ Hermitian matrix with real entries and $\mathbf{b}$ is a $4\times 1$ column vector with real entries.

Let's take an example:

$$\mathbf{A} = \begin{bmatrix} 1 & 2 & 3 & 4 \\ 2 & 1 & 5 & 6 \\ 3 & 5 & 1 & 7 \\ 4 & 6 & 7 & 1 \end{bmatrix}$$

and

$$\mathbf{b}=\begin{bmatrix} 1 \\ 2 \\ 3 \\ 4 \end{bmatrix}$$

Given the dimensions of $\mathbf{A}$ and $\mathbf{b}$, we should need $\lceil{\log_2 4\rceil}=2$ qubits for the input register and another $6$ qubits for the clock register assuming we want the eigenvalues to be represented with $90\%$ accuracy and up to $3$-bit precision for the eigenvalues (this has been discussed here previously). So total $2+6+1=9$ qubits will be needed for this purpose (the extra $1$ qubit is the ancilla).

Questions:

1. Using this information, is it possible to create the initial states $|\Psi_0\rangle$ and $|b\rangle$ on the IBM $16$ qubit version?

2. If you think $4\times 4$ is too large to be implemented on the IBM quantum computers you could even show an example of initial state preparation for a $2\times 2$ Hermitian matrix $\mathbf{A}$ (or just give a reference to such an example).

I simply want to get a general idea about whether this can be done (i.e. whether it is possible) on the IBM 16-qubit quantum computer, and for that which gates will be necessary. If not the IBM 16-qubit quantum computer, can the QISKit simulator used for recreating the initial state preparation of $|\Psi_0\rangle$ and $|b\rangle$ in the HHL algorithm? Is there any other better alternative to go about this?

Answer 1

It's not possible to create the initial states $\left| \Psi_0\right>$ and $\left|b\right>$ on the IBM 16 qubits version. On the other hand, it is possible to approximate them with an arbitrarily low error¹ as the gates implemented by the IBM chips offer this possibility.

Here you ask for 2 different quantum states:

1. $\left| b \right>$ is not restricted at all. The state $\left| b \right>$ is represented by a vector of $N$ complex numbers that can be anything (as long as the vector has unitary norm).
2. $\left| \Psi_0 \right>$ can be seen as a special case of $\left| b \right>$, where the coefficients $b_i$ are more constrained.

With this analysis, any method that can be used for creating $\left|b\right>$ can also be used to create $\left| \Psi_0 \right>$. On the other hand, as $\left| \Psi_0 \right>$ is more constrained, we can hope that there exists more efficient algorithms to produce $\left| \Psi_0 \right>$.

Useful for $\left|b\right>$ and $\left|\Psi_0\right>$: Based on Synthesis of Quantum Logic Circuits (Shende, Bullock & Markov, 2006), the QISKit Python SDK implements a generic method to initialize an arbitrary quantum state.

Useful for $\left|\Psi_0\right>$: Creating superpositions that correspond to efficiently integrable probability distributions (Grover & Rudolph, 2002) presents quickly an algorithm to initialise a state whose amplitudes represents a probability distribution respecting some constraints. These constraints are respected for $\left|\Psi_0\right>$ according to Quantum algorithm for solving linear systems of equations (Harrow, Hassidim & Lloyd, 2009), last line of page 5.

For the implementation on QISKit, here is a sample to initialise a given quantum state:

import qiskit

statevector_backend = qiskit.get_backend('local_statevector_simulator')

###############################################################
# Make a quantum program for state initialization.
###############################################################
qubit_number = 5
Q_SPECS = {
    "name": "StatePreparation",
    "circuits": [
        {
            "name": "initializerCirc",
            "quantum_registers": [{
                "name": "qr",
                "size": qubit_number
            }],
            "classical_registers": [{
                "name": "cr",
                "size": qubit_number
            }]},
    ],
}
Q_program = qiskit.QuantumProgram(specs=Q_SPECS)

## State preparation
import numpy as np
from qiskit.extensions.quantum_initializer import _initializer

def psi_0_coefficients(qubit_number: int):
    T = 2**qubit_number
    tau = np.arange(T)
    return np.sqrt(2 / T) * np.sin(np.pi * (tau + 1/2) / T)

def get_coeffs(qubit_number: int):
    # Can be changed to anything, the initialize function will take
    # care of the initialisation.
    return np.ones((2**qubit_number,)) / np.sqrt(2**qubit_number)
    #return psi_0_coefficients(qubit_number)

circuit_prep = Q_program.get_circuit("initializerCirc")
qr = Q_program.get_quantum_register("qr")
cr = Q_program.get_classical_register('cr')
coeffs = get_coeffs(qubit_number)
_initializer.initialize(circuit_prep, coeffs, [qr[i] for i in range(len(qr))])

res = qiskit.execute(circuit_prep, statevector_backend).result()
statevector = res.get_statevector("initializerCirc")
print(statevector)

---

¹Here "error" refers to the error between the ideal state and the approximation when dealing with a perfect quantum computer (i.e. no decoherence, no gate error).

Answer 2

HHL algorithm with a 4 x 4 matrix A might be to large for the IBM computer. I tried a smaller toy version of the algorithm according with arXiv 1302.1210 link Solving systems of linear equations

I explained a little bit about this circuit here at stackexchange: https://cs.stackexchange.com/questions/76525/could-a-quantum-computer-perform-linear-algebra-faster-than-a-classical-computer/77036#77036

Unfortunately it is only a 1 qubit input with A = 2 x 2 matrix, in the answer a link to the IBM circuit is given.