Quantum Algo: Deutsch-Jozsa Algorithm

Is quantum parallelism be possible for n-qubits?

9 min readJun 30, 2021

--

In the previous article Deutsch Algorithm, We understood Deutsch’s Algorithm is simple, but important, as it shows that a quantum algorithm can find a property of an unknown function with a smaller number of queries than any possible classical algorithm.

In this article, we discuss about the Deutsch–Jozsa algorithm which solves a problem that is a straight forward generalization of the problem solved by the Deutsch algorithm.

The setup:

Let us generalize the Deutsch algorithm to other functions. Rather than talking about functions f : {0, 1} → {0, 1}, let us talk about functions with a larger domain. Consider functions as shown below fig 1

fig 1: Accepts string of n 0’s and 1’s and outputs a 0 or 1

The question is the following:

We are given a reversible circuit implementing an unknown function f, but this time f is a function from n-bit strings to a single bit. That is, as shown in above fig 1.

Given Promise or Data:

f is constant i.e: f(x) is the same for all x.
f is balanced i.e: f(x) = 0 for exactly half of the input strings x, and f(x) = 1 for the other half of the input strings x.

With the above promise the problem here is to determine whether f is a constant, or a balanced function with the minimum number of function evaluations.

what a classical algorithm would do?

fig 2: classical illustration of Deutsch-Jozsa Algorithm

The classical algorithm in this case is to simply try inputs and compare the outputs. If any two different inputs give different outputs then we can immediately deduce that the function is balanced, but if all the outputs are the same it seems likely that the function is constant. In this latter case we cannot be sure the function is constant until N/2+1 different inputs have been tried, by which time a balanced function is certain to have revealed itself. Thus solving the Deutsch–Jozsa problem classically will require between 2 (best case) and N/2 + 1 (worst case) queries.

For the Deutsch problem N = 2 and these two limits are the same. Remarkably, a quantum computer implementing the Deutsch–Jozsa algorithm can always answer the question in a single query.

Deutsch-Jozsa algorithm:

We replace the unary Hadamard gates of Deutsch’s circuit with nth order Hadamard gates to accommodate the wider data register lines, but otherwise, the circuit layout is organized the same.

The circuit reveals that we will be applying quantum parallelism by allowing the upper Hadamard to produce a perfectly mixed input state, into Uf ’s data register(top register), and using the phase kick-back trick by putting |-⟩ into Uf ’s target register(bottom register).

As we did for the Deutsch algorithm in the previous article, we follow the state through the circuit. Initially the state is

Consider the action of an n-qubit Hadamard transformation on the n-qubit input state as shown in fig 5. i.e:( H|0⟩ = |+⟩ = (|0⟩ + |1⟩)/√2).

fig 5: n-qubit Hadamard transformation on n-qubit |0⟩ state

By expanding out the tensor product, this can be rewritten as as shown in fig 6

The above way of writing the state is a very common and useful. The n-qubit Hadamard gate acting on the n-qubit state of all zeros gives a superposition of all n-qubit basis states called an ‘equally weighted superposition’.

The state immediately after the first n-qubit Hadamard in the Deutsch– Jozsa algorithm is as shown in below fig 7.

fig 7: after the first n-qubit Hadamard as shown in fig 3

Now consider the state immediately after the Uf gate or Oracle. The state is as shown in below fig 8 and fig 9

fig 8: applying Unitary gate *Uf to* |ψ2⟩

from the previous article Deutsch Algorithm, we can write the wave function after applying unitary gate Uf as shown below fig 9

To facilitate our analysis of the state after the interference is completed by the second Hadamard gate as shown in the fig 3, consider the action of the n-qubit Hadamard gate on an n-qubit basis state |x⟩

It is easy to verify that the effect of the 1-qubit Hadamard gate on a 1-qubit basis state |x⟩, which can be written as shown in the below fig 10

fig 10: H gate in |x⟩

Rearrange the above result as shown in below fig 11 which is resembles to Deutsch Algorithm.

Then we can see that the action of the Hadamard transformation on an n-qubit basis state |x⟩ =|x1⟩|x2⟩… |xn⟩ is given by

Apply the fig 11 result to the n-qubit case, which gives the below fig 13

fig 13: after applying fig 10 result to fig 12

After rearrange the fig 13 similar to fig 11, which is shown in below fig 14

Finally, apply the above condition to the state |ψ3⟩ where n-qubit Hadamard shall be applied to n-qubit string as shown in fig 3. After applying n-qubit Hadamard to the state |ψ2⟩ results |ψ3⟩ as shown in below fig 15.

fig 15: After applying n-qubit Hadamard to the state |ψ2⟩

Now the top qubits of state |ψ3⟩ are measured. Rather than figuring out what we will get after measuring the top qubit, lets think differently

What is the probability that the top qubits of |ψ3⟩ will collapse to the state|0⟩?

We can answer this by setting z = 0 in the above fig 15 and realizing that z, x.z = 0 for all x. In this case, we have can reduce |ψ3⟩ to as shown in fig 16

fig 16: after reducing the |ψ3⟩ with condition z = 0

So, the probability of collapsing to |0⟩ is totally dependent on f(x):

If f(x) is constant at 1, the top qubits become -1|0⟩ as shown in below fig 17

If f(x) is constant at 0, the top qubits become +1|0⟩ as shown in below fig 18

And finally, if f is balanced, the positive and negative contributions of the amplitudes cancel, and the overall amplitude is 0 which means half of the x’s will cancel the other half and the top qubits will become 0|0⟩ as shown in below fig 18

fig 18: |ψ3⟩ to 0|0⟩ for f being balanced

When measuring the top qubits of |ψ3⟩,

we will only get |0⟩ if the function is constant.
If anything else is found after being measured, then the function is balanced.

conclusion: we have solved the Deutsch-Jozsa problem in one function evaluation as opposed to the N/2 + 1 function evaluations needed in classical computations. That is an exponential speedup!

Implementation of Deutsch-Jozsa Algorithm:

Let us consider a problem where f(x) = x1 ⊕ x2 . x3, determine whether f is a constant, or a balanced function.

Preparation:

x2 . x3(. represents AND operation) can be achieved using Toffoli gate. ⊕ operation can be achieved using CNOT gate

implement using IBMQ circuit composer:

composer 1: creating circuit for the mentioned problem

composer 2: the result for the mentioned problem is 0101

the measurement result for the mentioned problem is |010⟩ which concludes the given function f(x) is balanced.

implement using IBMQ qiskit module:

for the given function creating AND gate using Toffoli or MCT(Multi control Toffoli) as shown in below qiskit1.

for the given function creating XOR gate using CNOT or CX as shown in below qiskit2.

below function creates initial condition and the Hadamard gates before measurement with the parameter pos, where pos represents position if it is set to ‘initial’ will attach initial state as shown in fig 3 else if pos is set to ‘output’ will attach gates for measurement in X-bases as shown in fig 3

qiskit 3: generate initial and end conditions

The below function generates Deutsch-Jozsa circuit for the given function

qiskit 4: generates Deutsch Jozsa circuit

the below code block sets no of qubits required, initializes the registers and generates the DJ circuit

qiskit 5: no of qubits, registers and visualize the circuit

circuit generated for the given function as shown in below qiskit6

After the circuit running over simulator, below is the histogram for the obtained result

qiskit 7: the result for the mentioned problem is 001

the measurement result for the mentioned problem is |001⟩ which concludes the given function f(x) is balanced.

implement using Cirq module:

In the following code blocks we walk through over implementation of Oracle for the mentioned function( f(x) = x1 ⊕ x2 . x3) and Deutsch-Jozsa circuit using Cirq.