Deutsch-Jozsa Algorithm (to be zero or not)

The problem to which this algorithm suggests solution is that there is an input set of all possible values of n bits, there is a function whose global property is to be constant or balanced which means it takes either all the inputs to a constant value or half of the inputs to a value and other half of the inputs to another value. \(f: \{0,1\}^n\rightarrow \{0,1\}\). Element number of input set is \(2^n\). Element number of output set is either 1 or 2. And global propert of \(f\) will be determined. A classical computer solves this problem with \(\frac{2^n}{2}+1\) number of queries. What about a quantum computer uses D-J Alg.? It solves this problem in which number of queries?

Input state's space is \(2^{n+1}\) dimensional.

After \(\ket{\psi_0}\), we apply Hadamard gate to \(n+1\) qubits. We combine \(n\) qubits with Kronecker product. Now we have the superposition of all the basis of \(2^n\) dimensional space and the last qubit:

Now, we are in the stage of applying the unitary transformation \(U_f\). n bunch of qubits gidiği gibi çıkıyor, the function \(f(x)\) is applied onto the last qubit only. \(f(x)\) is either constant or balanced, in all the situations the last qubit will change according to \(\ket{0\oplus f(x)}-\ket{1\oplus f(x)}\). Let's say \(f(x)\) is constant and is equal to \(0\). Then, the last qubit remains as it is, n bunch of qubits too. Let's say \(f(x)\) is constant and is equal to \(1\). Then, the last qubit becomes \(\frac{-\ket{0}+\ket{1}}{\sqrt{2}}=-\frac{\ket{0}-\ket{1}}{\sqrt{2}}\). n bunch of qubits expression doesn't change. Only, we see either \(+\) or \(-\) caused by the last qubit. So general expression in case of constant function:

If \(f(x)=0\) for all the inputs, \(\ket{\psi_2}\) has \(+\) sign. If \(f(x)=1\) for all the inputs, \(\ket{\psi_2}\) has \(-\) sign.

\(\ket{\psi_3}=\ket{0}^{\otimes n} (-1)^{f(x)}\frac{\ket{0}-\ket{1}}{\sqrt{2}}\)

First n-qubit is called as registers, last qubit is called as target qubit. Registers constitute the input set in the problem. Last qubit is just like an ancillary qubit.

Let's assume \(n=2\). If \(f(x)\) is balanced and:

    case III:
  • \(f(00)=0\)
  • \(f(01)=0\)
  • \(f(10)=1\)
  • \(f(11)=1\)

It means that if 1.qubit is 0, do nothing to 3.qubit. If 1.qubit is 1, flip 3.qubit. (2.kübit etkisiz eleman.)

\(\ket{\psi_1}=\frac{1}{\sqrt{4}}(\ket{00}+\ket{01}+\ket{10}+\ket{11})\frac{\ket{0}-\ket{1}}{\sqrt{2}}\)

In \(\ket{\psi_3}\), last qubit will change according to first qubit. So group qubits according to first qubit:

\(\ket{\psi_2}=\frac{1}{\sqrt{4}}\big((\ket{00}+\ket{01})\frac{\ket{0}-\ket{1}}{\sqrt{2}}+(\ket{10}+\ket{11})\frac{\ket{0}-\ket{1}}{\sqrt{2}}\big)\)

If first qubit is 1, flip third qubit:

\(\ket{\psi_2}=\frac{1}{\sqrt{4}}\big((\ket{00}+\ket{01})\frac{\ket{0}-\ket{1}}{\sqrt{2}}+(\ket{10}+\ket{11})\frac{\ket{1}-\ket{0}}{\sqrt{2}}\big)\)

Take \(-\) sign from last qubit and use it in first and second qubit:

\(\ket{\psi_2}=\frac{1}{\sqrt{4}}\big((\ket{00}+\ket{01})\frac{\ket{0}-\ket{1}}{\sqrt{2}}+(-\ket{10}-\ket{11})\frac{\ket{0}-\ket{1}}{\sqrt{2}}\big)\)

\(\ket{\psi_2}=\frac{\ket{0}-\ket{1}}{\sqrt{2}} \frac{\ket{0}+\ket{1}}{\sqrt{2}} \frac{\ket{0}-\ket{1}}{\sqrt{2}}\)

\(\ket{\psi_3}=\ket{10}\frac{\ket{0}-\ket{1}}{\sqrt{2}}\)

    case IV:
  • \(f(00)=1\)
  • \(f(01)=1\)
  • \(f(10)=0\)
  • \(f(11)=0\)

It means that if 1.qubit is 0, flip 3.qubit. If 1.qubit is 1, do nothing to 3.qubit.

\(\ket{\psi_3}=-\ket{10}\frac{\ket{0}-\ket{1}}{\sqrt{2}}\)

    case V:
  • \(f(00)=0\)
  • \(f(01)=1\)
  • \(f(10)=0\)
  • \(f(11)=1\)

It means that if 2.qubit is 0, do nothing to 3.qubit. If 2.qubit is 1, flip 3.qubit.

\(\ket{\psi_3}=\ket{01}\frac{\ket{0}-\ket{1}}{\sqrt{2}}\)

    case VI:
  • \(f(00)=1\)
  • \(f(01)=0\)
  • \(f(10)=1\)
  • \(f(11)=0\)

It means that if 2.qubit is 0, flip 3.qubit. If 2.qubit is 1, do nothing to 3.qubit.

\(\ket{\psi_3}=-\ket{01}\frac{\ket{0}-\ket{1}}{\sqrt{2}}\)

As a result, after the measurement of registers if \(\ket{00}\) is obtained, we understand that \(f(x)\) is a constant function. If other results than \(\ket{00}\) is obtained, we understand that \(f(x)\) is a balanced function. In the generalization, \(\ket{00}\) becomes \(\ket{0}^{\otimes n}\) and while a classical computer solves this problem with \(\frac{2^n}{2}+1\) queries, a quantum computer solves this problem with \(n\) queries.