Deutsch-Jozsa Algorithm

The Deutsch-Jozsa algorithm, first introduced in Reference, was the first example of a quantum algorithm that performs better than the best classical algorithm. It showed that there can be advantages to using a quantum computer as a computational tool for a specific problem. We will first talk about the Deutsch Algorithm step by step and then go into the Deutsch-Jozsa algorithm.

1. Deutsch Algorithm

1.1 Problem Statement

Given a function $f(x),x\in 0,1$, how can we know whether f(x) is a balanced function or constant function?

We first dig into what is balanced function and constant function.

• Balanced Function means $f(0)\ne f(1)$, including two possibilites:

• $f(0)=0,f(1)=1$
  

• $f(0)=1,f(1)=0$
  

• Constant Function means $f(0)=f(1)$, including two possibilities:

• $f(0)=f(1)=0$
  

• $f(0)=f(1)=1$
  

1.2 Solution Circuit

We first present the solution circuit and try to find why it can help to find the solution. In the following picture, we assume $n=1$ in the upper register.

Circuit

The following figure shows how we deduce from the beginning to the end. (I will spend some time using markdown to compile it in the future :).)

Note

Note

Note

1.3 Example Circuit

We use the balanced function as an example to see what happened.

• Balanced Function One

Balanced Function Circuit

The process goes like this:

Balanced Function Circuit

The process goes like this:

We can find that the results of the first register in two circuits are $|1⟩$. Similarly, if we use constant function as an example, the result will be $|0⟩$. That's what Deutsch can do to solve this problem.

By only one measurement, we can know whether a function is balanced or constant, while in the classical computing world, we need twice to know the result.

2. Deutsch-Jozsa Algorithm

Deutsch-Jozsa Algorithm extends Deutsch algorithm into $2^n$ dimensions.

The algorithm goes with the following procedures:

1. State Preparation$|{\psi }_0⟩=|0{⟩}^{\otimes n}|1⟩$
   

2. Superposition by using Hardmard Gate$|{\psi }_1⟩={\sum }_{x\in {0,1}^n}\frac{|x⟩}{\sqrt{2^n}}\left[\frac{|0⟩-|1⟩}{\sqrt{2}}\right]$
   

3. Use the targeted function in the circuit$|{\psi }_2⟩={\sum }_x\frac{(-1{)}^{f(x)}|x⟩}{\sqrt{2^n}}\left[\frac{|0⟩-|1⟩}{\sqrt{2}}\right]$
   

4. Another Hardmard Gate$H^{\otimes n}$to the first register.$|{\psi }_3⟩={\sum }_z{\sum }_x\frac{(-1{)}^{x\cdot z+f(x)}|z⟩}{2^n}\left[\frac{|0⟩-|1⟩}{\sqrt{2}}\right]$
   

5. Measurement. Note that the amplitude of the state$|0{⟩}^{\otimes n}$$is$${\sum }_x(-1{)}^{f(x)}/2^n$
   

Let's look at the two possible cases $f$ constant and $f$ balanced $-$ to discern what happens. In the case where $f$ is constant, the amplitude for $|0{⟩}^{\otimes n}$ is $+1$ or $-1$, depending on the constant value $f(x)$ takes. Because $|{\psi }_3⟩$ is of unit length it follows that all the other amplitudes must be zero, and observation will yield 0s for all qubits in the query register.

If $f$ is balanced then the positive and negative contributions to the amplitude for $|0{⟩}^{\otimes n}$ cancel, leaving an amplitude of zero, and measurement must yield a result other than 0 on at least one qubit in the query register.

Reference:

1. Nielsen, Michael A., and Isaac Chuang. "Quantum computation and quantum information." (2002): 558-559.

2. Asfaw, Abraham, et al. "Learn quantum computation using qiskit." Accessed: Oct 24 (2020): 2020.

3. Susskind, Leonard, and Art Friedman. Quantum mechanics: the theoretical minimum. Basic Books, 2014.