8
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ As far as I know IBM cannot do HHL because it involves doing things at a superposition of different times, but I would not be surprised if I am wrong. @James Woottoon might know the answer better. $\endgroup$ – user1271772 Jun 24 '18 at 7:44
  • $\begingroup$ @user1271772 I thought so too, but I'm a bit sceptic because someone told me in chat that they simulated the HHL for $4\times 4$ following this, on IBM. $\endgroup$ – Sanchayan Dutta Jun 24 '18 at 7:47
  • $\begingroup$ Well, maybe Fig 4 of Yudong Cao's paper (the one you linked) is all you need then. $\endgroup$ – user1271772 Jun 24 '18 at 8:10
  • $\begingroup$ @user1271772 Yes, but unfortunately, that would only work for that particular matrix. I'm looking for a general technique, for which I should probably read that paper more thoroughly. $\endgroup$ – Sanchayan Dutta Jun 24 '18 at 8:12
  • $\begingroup$ As John Watrous put it in one of his comments to a question where someone was asking for a specific circuit, "you're asking for people to do tedious yet conceptually un-interesting work". Yudong was an undergraduate engineering student when he made these circuits. He did not have any more training than you (in fact based on your rapid progress, you probably know more about quantum computing than he did at the time of writing that paper). If he could make this circuit, you should be able to make the corresponding circuit for any HHL example that comes in front of you. $\endgroup$ – user1271772 Jun 24 '18 at 8:22
3
$\begingroup$

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 error1 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)

1Here "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).

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ The problem with the 4x4 HHL implementation is not the number of qubits (7 qubits are needed) but the quantum gates error rates and the decoherence times. An implementation of a 4x4 system using QISKit is available here. The implementation follows arxiv.org/abs/1110.2232v2 . $\endgroup$ – Nelimee Jul 6 '18 at 9:36
  • $\begingroup$ Great implementation of a 4 x 4 HHL. $\endgroup$ – Bram Jul 6 '18 at 10:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.