Uncategorized

Programming Quantum Search (Grover’s Algorithm)

Following my previous post (primitive example), here I explain another quantum programming example with Q#, which is also one of the official examples.

Here we start to implement a quantum search algorithm.

Problem Statement and Solution (Grover’s Search algorithm)

For some f : \{0,1\}^n \to \{0, 1\} , we want to find x = (x_1, ... , x_n) such as f(x) = 1 .
In this problem, the number of solutions can be larger than 1, but here we assume this equation has a unique solution in order to simplify our explanation.

In the classical approach, it is needed 2^n operations (i.e, \Omega(2^n) ) for finding the solutions, however this quantum algorithm (Grover’s search algorithm) needs only O(\sqrt{2^n}) .
As you can see, this Grover’s algorithm might be used for optimizing brute force search to obtain a valid assignment.

The idea of this algorithm is below. (See “Lecture 6: Quantum Search” (CS 880 – Quantum Information Processing in University of Wisconsin-Madison) for details.)

First we start x = |x_1 〉 |x_2 〉 … |x_n 〉 = |+〉 |+〉 … |+〉 = |\psi^{(0)} 〉. And we assume |\psi^{(i)} 〉 can be written as the following format, where |\psi^{(i)} 〉 is the transformed state by i iterations. (Later we define this transformation. But for now, we assume that all of x which satisfies f(x) = 0 has the same coefficients in |\psi^{(i)} 〉.)

|\psi^{(i)} 〉 = \displaystyle \beta_i \frac{1}{\sqrt{2^n - 1}} \sum_{x:f(x) = 0} |x〉 + \displaystyle \gamma_i \sum_{x:f(x) = 1} |x〉

As you can see, \beta_i^2 + \gamma_i^2 = 1 . i.e, \beta_i , \gamma_i is on a unit circle as follows.

Here we want to try to increase above \theta_i by iteration i, and if we get sufficiently enough to close C-axis, this state (\beta_i, \gamma_i) might be close to our expecting solution x. Then we measure x to get a solution.

Now we consider the transformation to increase \theta_i as follows :

  1. First, we reflect (\beta_i , \gamma_i) across B-axis.
  2. Next, we reflect across \psi^{(0)} .

The former one is very easy, because we can use phase kickback (which is reversible and unitary) U_f : |x〉 |-〉 -> (-1)^{f(x)} |x〉 |-〉 with ancilla qubit |-〉, as I explained in my previous post. (See “Lecture 4: Elementary Quantum Algorithms“.)
Only the item |x〉 which satisfies f(x) = 1 is multiplied by -1.

The latter one is complicated and here we use the well-known diffusion operator as follows. (Sorry, but please let me skip the proof due to avoid description too much …)

H {Reflection across |0〉 … |0〉} H
\displaystyle = H \begin{pmatrix} 1 & 0 & \cdots & 0 \\ 0 & -1 & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & -1 \end{pmatrix} H

As you can see below (by the straightforward algebraic calculation), this operator is the same as the reflection across average. (See the following illustrated.)
That is, this transformation (combination with the former one and the latter one) is amplifying amplitude.

Note : As you can see below, this transformation is also written as : 2 |\psi 〉 ⟨\psi | – I .

\displaystyle = H (\begin{pmatrix} 2 & 0 & \cdots & 0 \\ 0 & 0 & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & 0 \end{pmatrix} - I) H \\ = \begin{pmatrix} \frac{2}{2^n} & \frac{2}{2^n} & \cdots & \frac{2}{2^n} \\ \frac{2}{2^n} & \frac{2}{2^n} & \cdots & \frac{2}{2^n} \\ \vdots & \vdots & \ddots & \vdots \\ \frac{2}{2^n} & \frac{2}{2^n} & \cdots & \frac{2}{2^n} \end{pmatrix} - I \\ = -(I - \frac{1}{2^n} \begin{pmatrix} 1 & \cdots & 1 \\ \vdots & \ddots & \vdots \\ 1 & \cdots & 1 \end{pmatrix}) + \frac{1}{2^n} \begin{pmatrix} 1 & \cdots & 1 \\ \vdots & \ddots & \vdots \\ 1 & \cdots & 1 \end{pmatrix}

 

We repeat this transformation (the former one and latter one) until |\psi^{(i)} 〉 is close to C-axis.

The entire transformation is designed as follows.

Q# Programming for Grover’s Search algorithm

In this example, we assume (1, 1, … , 1) is a unique solution for equation f(x) = 1.

Before starting, we replace above phase kickback U_f : |x〉 |-〉 -> (-1)^{f(x)} |x〉 |-〉 by the following transformation |x〉 |0〉 -> (-1)^f(x) |x〉 |0〉 with ancilla quibit |0〉, which is implemented by the twice U_f and rotate as follows. (See “Lecture 04: Elementary Quantum Algorithms” for details.)
The ancilla quibit is changed into |0〉, but the result’s state of |x〉 are not changed.

As a result, we will implement the following circuit.

In this programming example, we generate and use the following operations (StatePreparationOracle(), ReflectMarked(), ReflectStart(), and ReflectZero()) corresponding to each logics. (Note that StatePreparationOracle^{-1} is an adjoint conjunction of StatePreparationOracle.)

But just a moment. With these entire circuit, one little thing is different from the original circuit. As you can see, this has extra U_f : |x,0〉 -> |x,f(x) \oplus 0 〉 in the final step. However this is on purpose ! (It has meaning !)
By the finial U_f : |x,0〉 -> |x,f(x) \oplus 0 〉, the ancilla qubit is to be close to |1〉 if f(x) is close to |1〉. (On the contrary, the state of |x〉 is not changed.) Therefore we can figure out whether we could have reached to the solution (f(x) = 1) by measuring this ancilla qubit. This ancilla qubit is not “garbage” !

Now here we start our programming.

First we generate the superposition |+〉 … |+〉 and |0〉 (ancilla qubit) as follows. |x〉 (i.e, |x_1 〉 |x_2 〉 … |x_n 〉 = |+〉 … |+〉) is in “databaseRegister” and ancilla qubit (=|0〉) is in “markedQubit“.
Here we assume n = 6 and the number of iterations is fixed as 3.

open Microsoft.Quantum.Primitive;

nDatabaseQubits = 6;
nIterations = 3;

using (qubits = Qubit[nDatabaseQubits + 1]) {
  let markedQubit = qubits[0];
  let databaseRegister = qubits[1 .. nDatabaseQubits];
  QuantumSearch(nIterations, markedQubit, databaseRegister);
  ...

}

operation QuantumSearch (nIterations : Int, markedQubit : Qubit, databaseRegister : Qubit[]) : Unit {    
  StatePreparationOracle(markedQubit, databaseRegister);
  ...
}

operation StatePreparationOracle (markedQubit : Qubit, databaseRegister : Qubit[]) : Unit {    
  body (...) {
    UniformSuperpositionOracle(databaseRegister);
    ...
  }
  adjoint invert;
}

operation UniformSuperpositionOracle (databaseRegister : Qubit[]) : Unit {    
  body (...) {
    let nQubits = Length(databaseRegister);
    for (idxQubit in 0 .. nQubits - 1) {
      H(databaseRegister[idxQubit]);
    }
  }
  adjoint invert;
}

Next we implement U_f : |x,0〉 -> |x,f(x) \oplus 0 〉 by adding the following DatabaseOracle() operation in StatePreparationOracle().

By the following “Controlled X(databaseRegister, markedQubit)“, gate X is applied when all of the control qubits in databaseRegister are in the computational state |1〉. That is, this entanglement is equivalent to U_f : |x,0〉 -> |x,f(x) \oplus 0 〉 where f(x) has a unique solution x = (1,1, … ,1) for f(x) = 1 . (Suppose we have blackbox access to this oracle.)

Following “adjoint invert” indicates that the compiler should implement the adjoint specialization by inverting the body. (Later we use the adjoint for StatePreparationOracle.)

operation StatePreparationOracle (markedQubit : Qubit, databaseRegister : Qubit[]) : Unit {    
  body (...) {
    UniformSuperpositionOracle(databaseRegister);
    DatabaseOracle(markedQubit, databaseRegister);
  }
  adjoint invert;
}

operation DatabaseOracle (markedQubit : Qubit, databaseRegister : Qubit[]) : Unit {    
  body (...) {
    Controlled X(databaseRegister, markedQubit);
  }
  adjoint invert;
}

Now we implement the iteration loop by adding the following code in QuantumSearch(). This logic is equivalent to the repeated block, which is marked in gray in the following picture.

The first qubit in argument on ReflectZero() operation is ancilla qubit (markedQubit, which is |0〉) and others are databaseRegister.
The multi-qubit controlled gate works on |1…1〉. Then we flip both this ancilla qubit (|0〉 -> |1〉) and databaseRegister, and turn into -1 when it’s |0…0〉. (After that, we reset ancilla qubit to |0〉.)
Reflection across |0^n 〉 can also be written using U_{f^{\prime}} with ancilla qubit, where f^{\prime}(x) is a function such as f^{\prime}(0, ... , 0) is equal to 0 and others are 1.

open Microsoft.Quantum.Extensions.Math;

operation QuantumSearch (nIterations : Int, markedQubit : Qubit, databaseRegister : Qubit[]) : Unit {
  StatePreparationOracle(markedQubit, databaseRegister);
  for (idx in 0 .. nIterations - 1) {
    ReflectMarked(markedQubit);
    ReflectStart(markedQubit, databaseRegister);
  }
}

operation ReflectMarked (markedQubit : Qubit) : Unit {
  R1(PI(), markedQubit);
}

operation ReflectStart (markedQubit : Qubit, databaseRegister : Qubit[]) : Unit {
  Adjoint StatePreparationOracle(markedQubit, databaseRegister);
  ReflectZero([markedQubit] + databaseRegister);
  StatePreparationOracle(markedQubit, databaseRegister);
}

operation ReflectZero (databaseRegister : Qubit[]) : Unit {
  let nQubits = Length(databaseRegister);    
  for (idxQubit in 0 .. nQubits - 1) {
    X(databaseRegister[idxQubit]);
  }
  Controlled Z(databaseRegister[1 .. nQubits - 1], databaseRegister[0]);
  for (idxQubit in 0 .. nQubits - 1) {
    X(databaseRegister[idxQubit]);
  }
}

Finally we measure the results as follows.
On success, databaseRegister must be close to |1〉 |1〉 … |1〉 (which is a solution for f(x) = 1 ).
As I explained above, markedQubit should also be close to |1〉 on success.

using (qubits = Qubit[nDatabaseQubits + 1]) {
  let markedQubit = qubits[0];
  let databaseRegister = qubits[1 .. nDatabaseQubits];
  QuantumSearch(nIterations, markedQubit, databaseRegister);

  // Measure the marked qubit.
  // On success, this should be |1〉.
  set resultSuccess = M(markedQubit);

  // Measure the state of the database register.
  // On success, this should be |1〉 |1〉 ... |1〉.
  set resultElement = MultiM(databaseRegister);
      
  // Reset all qubits to the |0〉 state.
  if (resultSuccess == One) {
    X(markedQubit);
  }
  for (idxResult in 0 .. nDatabaseQubits - 1) {
    if (resultElement[idxResult] == One) {
      X(databaseRegister[idxResult]);
    }
  }
}

 

In this post we saw Grover’s algorithm’s example which is manually implemented using primitive operators. However Q# has built-in Microsoft.Quantum.Canon.AmpAmpByOracle() operation, which implements the amplitude amplification algorithm itself. (See “Q# document – Quantum Algorithms“.)
Using this high-level operation, you’ll be able to implement quantum search with a few lines of code.

For the entire source code, please see the following official example, which is also including AmpAmpByOracle sample.

https://github.com/Microsoft/Quantum/tree/master/Samples/src/DatabaseSearch

Advertisements

Categories: Uncategorized

Tagged as:

2 replies »

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s