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 – What is 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)}$〉. As I mentioned earlier, only one $x = (x^{\prime}_1, x^{\prime}_2, \ldots x^{\prime}_n)$ satisfies $f(x) = 1$, and the other $2^n - 1$ satisfies $f(x) = 0$. Then 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.)

| $\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 and we repeat. :

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.

nDatabaseQubits = 6;
nIterations = 3;

using ((markedQubit, databaseRegister) = (Qubit(), Qubit[nDatabaseQubits])) {
QuantumSearch(nIterations, markedQubit, databaseRegister);
...

}

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

operation StatePreparationOracle (markedQubit : Qubit, databaseRegister : Qubit[]) : Unit is Adj + Ctl {
UniformSuperpositionOracle(databaseRegister);
...
}

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

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 “Adj + Ctl” 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 is Adj + Ctl {
UniformSuperpositionOracle(databaseRegister);
DatabaseOracle(markedQubit, databaseRegister);
}

operation DatabaseOracle (markedQubit : Qubit, databaseRegister : Qubit[]) : Unit is Adj + Ctl {
Controlled X(databaseRegister, markedQubit);
}

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.

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 {
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);
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 ((markedQubit, databaseRegister) = (Qubit(), Qubit[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.
Reset(markedQubit);
for (idxResult in 0 .. nDatabaseQubits - 1) {
Reset(databaseRegister[idxResult]);
}
}

The completed sample is here :

C# (.cs)

using Microsoft.Quantum.Simulation.Core;
using Microsoft.Quantum.Simulation.Simulators;
using System;
using System.Linq;
...

static void Main(string[] args)
{

var sim = new QuantumSimulator(throwOnReleasingQubitsNotInZeroState: true);

var nDatabaseQubits = 6;
var nIterations = 3;

var results = ApplyQuantumSearch.Run(sim, nIterations, nDatabaseQubits).Result;

var markedQubit = results.Item1;
var databaseRegister = results.Item2.ToArray();

if (markedQubit == Result.One)
{
Console.WriteLine("Succeed !");
Console.WriteLine(\$"Found database index {string.Join(", ", databaseRegister.Select(x => x.ToString()).ToArray())}");
}
else
{
Console.WriteLine("Failed !");
}

}

Q# (.qs)

open Microsoft.Quantum.Intrinsic;
open Microsoft.Quantum.Math;
open Microsoft.Quantum.Measurement;

operation ApplyQuantumSearch (nIterations : Int, nDatabaseQubits : Int) : (Result, Result[]) {
using ((markedQubit, databaseRegister) = (Qubit(), Qubit[nDatabaseQubits])) {
QuantumSearch(nIterations, markedQubit, databaseRegister);

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

// Measure the state of the database register.
// On success, this should be |1〉 |1〉 ... |1〉.
let resultElement = MultiM(databaseRegister);

// Reset all qubits to the |0〉 state.
Reset(markedQubit);
for (idxResult in 0 .. nDatabaseQubits - 1) {
Reset(databaseRegister[idxResult]);
}

return (resultSuccess, resultElement);
}
}

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

for (idx in 0 .. nIterations - 1) {
ReflectMarked(markedQubit);
ReflectStart(markedQubit, databaseRegister);
}

}

operation StatePreparationOracle (markedQubit : Qubit, databaseRegister : Qubit[]) : Unit is Adj + Ctl{
UniformSuperpositionOracle(databaseRegister);
DatabaseOracle(markedQubit, databaseRegister);
}

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

operation DatabaseOracle (markedQubit : Qubit, databaseRegister : Qubit[]) : Unit is Adj + Ctl {
Controlled X(databaseRegister, markedQubit);
}

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

operation ReflectStart (markedQubit : Qubit, databaseRegister : Qubit[]) : Unit {
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);
for (idxQubit in 0 .. nQubits - 1) {
X(databaseRegister[idxQubit]);
}
} In this post we saw Grover’s algorithm’s example which is manually implemented using primitive operators. However Q# has built-in Microsoft.Quantum.AmplitudeAmplification.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 original source code, please see the following official example, which is also including AmpAmpByOracle sample.

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