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.

On line 2.1, a qbit variables x and y are declared.
On line 2.2, a new qubit is allocated and x is assigned this qubit, similarly for the variable y on line 2.3.
On lines 2.5 and 2.6, the qubits x and y are initialized to the states |0> and |1>, respectively.
On lines 2.6 and 2.7, a Hadamard transformation is applied onto the qubits x and y, respectively.
On lines 2.8-2.11, the unitary transformation corresponding to the chosen function f is applied onto the qubits x and y.
On line 2.12, a Hadamard transformation is applied onto the qubit x.
On lines 2.13-2.17, the qubit x is measured in the standard basis. Depending on the measurement result, the function f is determined to be constant or balanced, and this result is printed to the output.

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	}
	}

LanQ – a quantum imperative programming language

Examples

Implementation of the Deutsch-Jozsa algorithm

Brief description of the program

Detailed description of the program

The program

Download source code