In order to solve the real problem with quantum computing, it’s also important to take advantage of a variety of algorithms as well as quantum logic gates.

In this post I show you primitive programming sample (using Q#) with Bernstein-Vazirani algorithm to solve some specific problem for your very beginning and introduction.

I note, in the practical problems, quantum parts and classical parts will generally be mixed for solving a problem unlike this example. (Quantum logic is beneficial for some kind of problems, but not always.) But this example will be helpful for your first start.

Here we use Q# and this sample is one of Q# examples (official examples) in GitHub repo.

When you run Q# in your local machine, it runs on local simulator and doesn’t have the same speed as real quantum computing utilities. But it will still be a good place to examine (debug) your quantum programming very quickly.

Here we start.

## Problem Statement and Solution (Bernstein-Vazirani algorithm)

Here we suppose (i = 0, 1, 2, …, n-1) is given and consider the following equation . ( is a classical logic gate.)

Here we suppose is unknown values.

where

Note : In the paper, is used for , but here we omitted without losing generality.

When you look for these unknown values (), you would give the following and check result for this equation .

Here we’re fixing n = 4 to simplify explanation.

As you know, if there’s 1000 unknown variables, 1000 trials will be needed.

That is, it will need polynomial frequency of calculation to solve this problem using classical algorithms.

It is known that you can solve this problem with only one calculation by Bernstein-Vazirani quantum algorithm as follows.

Bernstein-Vazirani algorithm

- Suppose we initialize n qubits |〉 = |+〉, |〉 = |+〉, … |〉 = |+〉 (i.e, initialize |0〉 and apply Hadamard), and initialize 1 qubit y = |-〉 (i.e, initialize |1〉 and apply Hadamard)
- We apply transformation : |x〉|y〉 -> |x〉|y f(x)〉 where is equivalent to classical bitwise XOR. ( is reversible and unitary.)

As you see later in this post, is implemented by quantum CNOT operation. - Apply Hadamard gate again for x. Then x will be our expecting s.

Here I don’t explain why this algorithm solves this problem (we suppose it’s a given algorithm without any proof), but the article “Lecture 4: Elementary Quantum Algorithms” (CS 880 – Quantum Information Processing in University of Wisconsin-Madison) is a good reading for describing background ideas for phase kickback and derived Bernstein-Vazirani algorithm.

This idea uses the characteristics for |+〉, |-〉 generated by Hadamard gate (). I note that Hadamard gate is not just for creating superposition, but this gate is a special transformation. (Hadamard has much of interesting properties and is most used for various algorithms.)

As you can see below, when you apply Hadamard twice, it turns into the original position. (Here I’m showing the result for , but you get the same result for general .) It means, |+〉 and |-〉 have the same outcome for measurements and the difference is not visible (observable) for humans, but you can find the difference by applying Hadamard again.

Note : See here for geometric meaning of with Bloch sphere representation (which is a single qubit representation).

If and (where |x〉 = |0〉 + |1〉) are real, this transformation is the reflection across line in 2-dimension space with basis -axis and -axis . (The point (, ) is on a unit circle, because .)

Now we implement this simple algorithm with Q# below.

## Q# Programming for Bernstein-Vazirani algorithm

As I explained above, you can get this complete code (Q#) from official GitHub repo. In this post, I describe the outline for your understanding.

First we generate unknown as follows.

To simplify explanation, here we’re fixing i = 0 … 3 (i.e, n = 4 elements). For instance, if parity = 11, it represents 1011 (2) (i.e ) and following “`pattern`

” equals to [true, false, true, true].

Note : In the original source code, it’s checking all possible values from 0 to (1 << n) – 1 , but here we pick single value using `Random`

class.)

Initialize values on C# (.NET runtime) and start quantum simulator

```
const int n = 4;
var rand = new Random(0);
var parity = rand.Next(1 << n);
// run quantum simulator and pass "parity" to Q# program...
...
```

Runs on Quantum Simulator

```
open Microsoft.Quantum.Primitive;
open Microsoft.Quantum.Canon;
let pattern = BoolArrFromPositiveInt(parity, n);
```

From here, it all runs on quantum simulator.

Next we initialize = |+〉 (i = 0, …, n-1) and = |-〉. (See above procedure 1 in Bernstein-Vazirani algorithm.)

In this code, qubits[i] where i=0 … n-1 (which has n elements) is , and last qubits[n] is .

```
// all n+1 qubits are initialized as |0〉
qubits = Qubit[n + 1];
// set last qubits[n] as |1〉
X(qubits[n]);
// set qubits[i] = |+〉 (i=0 ... n-1) and qubits[n] = |-〉
ApplyToEach(H, qubits);
```

Next we define unitary transformation as follows. (See above procedure 2 in Bernstein-Vazirani algorithm.)

Note that previous “`qubits`

” (in which, qubits[i] (i=0 … n-1) represents and qubits[n] represents ) is passed into the following input’s argument “`qs`

“.

When you apply `Controlled X(a, b)`

(Controlled-X or CNOT), “a” is used as control bit and `X`

(= NOT gate) is applied to target “b”. As you can see, this operation is equivalent with classical XOR and this entire logic represents . (Note that quantum state doesn’t have the logical bitwise operation. For simulating classical logic gate in quantum computing, see “Lecture 2: From Classical to Quantum Model of Computation“.)

By the beauty of Q# abstraction, this for-loop iterations (also `ApplyToEach()`

) is equivalent to the multi-qubit operations (where U is some single operation with controlled and adjoint).

As a result, this operation creates a circuit for : |x〉|y〉 -> |x〉|〉. (For classical manners, it’s just like building a circuit for ….. Suppose we have blackbox access to this oracle.)

Note : “Unit” means “no result” in Q#. (It’s like “void” in C#.)

```
operation ParityOperationImpl (pattern : Bool[], qs : Qubit[]) : Unit {
let n = Length(pattern);
for (idx in 0 .. n - 1) {
if (pattern[idx]) {
Controlled X([qs[idx]], qs[n]);
}
}
}
function ParityOperation (pattern : Bool[]) : (Qubit[] => Unit) {
return ParityOperationImpl(pattern, _);
}
```

Now we apply this unitary transformation for above “`qubits`

” ( and ).

```
let Uf = ParityOperation(pattern);
...
Uf(qubits);
```

Finally we apply Hadamard again (see above procedure 3 in Bernstein-Vazirani algorithm) for (i.e, qubits[i] i=0 … n-1) and measure these qubits for getting result.

```
mutable resultArray = new Result[n];
...
ApplyToEach(H, qubits[0 .. n - 1]);
for (idx in 0 .. n - 1) {
set resultArray[idx] = MResetZ(qubits[idx]);
}
let resultBool = BoolArrFromResultArr(resultArray);
let resultInt = PositiveIntFromBoolArr(resultBool);
```

When you compare the result with previous “`parity`

” (i.e, where i=0 … n-1), you will find these are exactly same values.

Please see below for complete example code.

This also includes the implementation for Deutsch-Jozsa algorithm which is also based on the same phase kickback ideas.

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

I’ll explain more advanced problems using Q# in the future post.

- Programming Quantum Search (Grover’s Algorithm) (posted on March 2019)

Categories: Uncategorized

## 2 replies »