LanQ – a quantum imperative programming language


Implementation of the Deutsch-Jozsa algorithm

The Deutsch-Jozsa algorithm described by Deutsch and Jozsa can be implemented in LanQ as shown below.

Brief description of the program

The program determines whether a given function f: {0,1} -> {0,1} is a balanced or a constant function in just one step. The function f is given in the form of a unitary operator U that maps a vector |x y> to |x (y xor f(x))>.

First, two qubits are prepared in the overall state |01>. Then Hadamard transformation is applied to both of them, the unitary operator U is then applied and finally a Hadamard transformation is performed on the first qubit. The subsequent measurement returns 0 if the function is constant, if the function is balanced, it returns 1.

Detailed description of the program

The Deutsch-Jozsa algorithm implementation consists of only one method from which the program is run. We now describe the program line by line.

On line 1.1, we include a library which defines a Hermitian operators ProjTo0 and ProjTo1. These operators, given a qubit in a maximally mixed state, simulate projection to |0> and |1> basis vector, respectively. (We use this operator instead of measurement as this would create two probabilistic branches, one in |0> and the other in |1> basis state, what would double the number of required resources on the simulating computer.) On line 1.2, we include a library which defines the unitary matrices representing the function f.

The program

 /** * Implementation of the Deutsch-Jozsa algorithm. */
1.1#library "library.libq"
1.2#library "deutsch.libq"
 void main() {
2.1 qbit x,y;
2.2 x = new qbit();
2.3 y = new qbit();
2.4 ProjTo0(x);
2.5 ProjTo1(y);
2.6 Had(x);
2.7 Had(y);
 /* * Uncomment one of the following four lines to choose the function f. * See the library deutsch.libq for the definition of the operators. */
2.8 U_balanced_x(x,y);
2.9// U_balanced__not_x(x,y);
2.10// U_const_0(x,y);
2.11// U_const_1(x,y);
2.12 Had(x);
2.13 if (measure(StdBasis,x) == 0) {
2.14 print("U is a constant function\n");
2.15 } else {
2.16 print("U is a balanced function\n");
2.17 }

Download source code