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 , we want to find x = such as .

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 operations (i.e, ) for finding the solutions, however this quantum algorithm (Grover’s search algorithm) needs only .

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 = |〉 |〉 … |〉 = |+〉 |+〉 … |+〉 = |〉. And we assume |〉 can be written as the following format, where |〉 is the transformed state by i iterations. (Later we define this transformation. But for now, we assume that all of x which satisfies has the same coefficients in |〉.)

|〉 = |x〉 + |x〉

As you can see, . i.e, , is on a unit circle as follows.

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

Now we consider the transformation to increase as follows :

- First, we reflect , across B-axis.
- Next, we reflect across .

The former one is very easy, because we can use phase kickback (which is reversible and unitary) : |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

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 |〉 ⟨| – I .

We repeat this transformation (the former one and latter one) until |〉 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 : |x〉 |-〉 -> |x〉 |-〉 by the following transformation |x〉 |0〉 -> |x〉 |0〉 with ancilla quibit |0〉, which is implemented by the twice 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 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 : |x,0〉 -> |x,〉 in the final step. However this is on purpose ! (It has meaning !)

By the finial : |x,0〉 -> |x,〉, the ancilla qubit is to be close to |1〉 if 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, |〉 |〉 … |〉 = |+〉 … |+〉) 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 : |x,0〉 -> |x,〉 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 : |x,0〉 -> |x,〉 where has a unique solution x = (1,1, … ,1) for . (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 |〉 can also be written using with ancilla qubit, where is a function such as 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 ).

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

Categories: Uncategorized

## 2 replies »