Uncategorized

Programming Primitive Quantum Algorithm

In order to solve the realistic problem with quantum computing, it’s also important to take advantage of a variety of quantum algorithms.
In this post I show you primitive programming sample with Bernstein-Vazirani algorithm to solve some specific problem for your very beginning and introduction. (Later I show you other famous algorithms and as well as programming examples. This first example will be helpful for your start.)

Here we use Q# for programming language and sample code in this post is one of Q# examples in official 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 (Explanation for 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 computation (of 3 steps) by Bernstein-Vazirani quantum algorithm as follows.

Bernstein-Vazirani algorithm

  1. Suppose we initialize n qubits |〉 = |+〉, |〉 = |+〉, … |〉 = |+〉 (i.e, initialize |0〉 and apply Hadamard), and initialize 1 qubit y = |-〉 (i.e, initialize |1〉 and apply Hadamard)
  2. 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.
  3. 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 lecture “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 for beginners that Hadamard gate is not just for creating superposition, but this gate is a special transformation and most used for various algorithms, because this can generate the uniform states for all qubits such that :

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 .) That is, |+〉 and |-〉 have the same observation 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 .)

Next 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

let pattern = IntAsBoolArray(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〉
using (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];
...

// apply Hadamard again except last qubit
ApplyToEach(H, qubits[0 .. n - 1]);

// measure and reset qubit
for (idx in 0 .. n - 1) {
  set resultArray[idx] w/= idx <- MResetZ(qubits[idx]);
}
let resultBool = ResultArrayAsBoolArray(resultArray);
let resultInt = BoolArrayAsInt(resultBool);

When you compare the result with previous “parity” (i.e, where i=0 … n-1), you will find these are exactly same values.

 

Our completed sample is here :

C# (.cs)

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

...

static void Main(string[] args)
{
  var sim = new QuantumSimulator(throwOnReleasingQubitsNotInZeroState: true);

  const int n = 4;
  var rand = new Random(0);
  var parity = rand.Next(1 << n);
  var measuredParity = BernsteinVaziraniTestCase.Run(sim, n, parity).Result;

  System.Console.WriteLine($"Actual Parity is {parity}");
  System.Console.WriteLine($"Measured Parity is {measuredParity}");
  System.Console.ReadLine();
}
...

Q# (.qs)

open Microsoft.Quantum.Intrinsic;
open Microsoft.Quantum.Canon;
open Microsoft.Quantum.Measurement;
open Microsoft.Quantum.Arrays;
open Microsoft.Quantum.Convert;

operation BernsteinVaziraniTestCase (n : Int, patternInt : Int) : Int {
  mutable resultArray = new Result[n];

  let pattern = IntAsBoolArray(patternInt, n);

  using (qubits = Qubit[n + 1]) { // all n+1 qubits are initialized as |0〉

    // set last qubits[n] as |1〉
    X(qubits[n]);

    // set qubits[i] = |+〉 (i=0 ... n-1) and qubits[n] = |-〉
    ApplyToEach(H, qubits);

    // apply unitary transformation for qubits
    let Uf = ParityOperation(pattern);
    Uf(qubits);

    // apply Hadamard again
    ApplyToEach(H, qubits[0 .. n - 1]);

    // measure and reset qubit
    for (idx in 0 .. n - 1) {
      set resultArray w/= idx <- MResetZ(qubits[idx]);
    }
    let resultBool = ResultArrayAsBoolArray(resultArray);
    let resultInt = BoolArrayAsInt(resultBool);

    // reset last qubit
    Reset(qubits[n]);

    return resultInt;
  }
}

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, _);
}

Please see below for original 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 algorithms (well-known algorithms) using Q# in the future post.

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