# Understanding the working of oracle in Deutsch - Jozsa Algorithm

Reading through the official Qiskit textbook, I fell onto the problem of Deutsch - Jozsa Algorithm, which seemed little mystical to me at first but as I tried out the example of its working, I was unable to work out the last part of it, the example is copy-pasted below:

Let's go through a specific example for a two-bit balanced function with hidden bitstring a=3.

1. The first register of two qubits is initialized to |0⟩ and the second register qubit to |1⟩:

$$|ψ_0⟩=|00⟩_1|1⟩_2$$

1. Apply Hadamard on all qubits: $$|ψ_1⟩=\frac{1}{2}(|00⟩_1+|01⟩_1+|10⟩_1+|11⟩_1)\frac{1}{\sqrt{2}}(|0⟩_2−|1⟩_2)$$

2. For a=3, (11 in binary) the oracle function can be implemented as $$Q_f=CX_{1a}CX_{2a}$$,

$$|ψ_2⟩=\frac{1}{2\sqrt{2}}[|00⟩_1(|0⊕0⊕0⟩_2−|1⊕0⊕0⟩_2)+|01⟩_1(|0⊕0⊕1⟩_2−|1⊕0⊕1⟩_2)+|10⟩_1(|0⊕1⊕0⟩_2−|1⊕1⊕0⟩_2)+|11⟩_1(|0⊕1⊕1⟩_2−|1⊕1⊕1⟩_2)]$$

4.Thus:

$$|ψ_2⟩=\frac{1}{2\sqrt{2}}[|00⟩_1(|0⟩_2−|1⟩_2)−|01⟩_1(|0⟩_2−|1⟩_2)−|10⟩_1(|0⟩_2−|1⟩_2)+|11⟩_1(|0⟩_2−|1⟩_2)] =\frac{1}{2}(|00⟩_1−|01⟩_1−|10⟩_1+|11⟩_1)\frac{1}{\sqrt{2}}(|0⟩_2−|1⟩_2)$$ $$=\frac{1}{\sqrt{2}}(|0⟩_{10}−|1⟩_{10})\frac{1}{\sqrt{2}}(|0⟩_{11}−|1⟩_{11})\frac{1}{\sqrt{2}}(|0⟩_2−|1⟩_2)$$

1. Apply Hadamard on the first register:

$$|ψ_3⟩=|1⟩_{10}|1⟩_{11}(|0⟩_2−|1⟩_2)$$

2. Measuring the first two qubits will give the non-zero 11, indicating a balanced function.

The main problem in understanding was in the final step, going from :

$$|ψ_2⟩=\frac{1}{2}(|00⟩_1−|01⟩_1−|10⟩_1+|11⟩_1)\frac{1}{\sqrt{2}}(|0⟩_2−|1⟩_2)$$

to:

$$|ψ_2⟩=\frac{1}{\sqrt{2}}(|0⟩_{10}−|1⟩_{10})\frac{1}{\sqrt{2}}(|0⟩_{11}−|1⟩_{11})\frac{1}{\sqrt{2}}(|0⟩_{2}−|1⟩_{2})$$

It seems to be some sort of a factorization step, how does that work?

• I'm not sure what part you're stuck at given that you realise it is a factorization, however - $|00\rangle$ is shorthand for $|0\rangle \otimes |0\rangle$ where $\otimes$ is the tensor product and it distributes over addition just like regular multiplication. Mar 22 '20 at 9:20
• I didn't quite understood the way the subscripts are written in the last part, but I do understand that it's a factorization. But how did they wrote the subscripts? Mar 22 '20 at 9:34
• Looks like the first two qubits counts as system $1$ and the third qubit is system $2$ (By your very first point.) Later, when they factorized, within system 1, they labelled the fist qubit as $0$ and second qubit as $1$, therefore the full subscript for the first qubit is $10$ and second qubit is $11$. Mar 22 '20 at 9:37

Here the subscripts are of the form $$1i$$, where $$i$$ is the label of the subsystem (recall that you are using two qubits for this $$\left|\psi\right>_0=\left|00\right>_{1}$$). So any product of subscripts can be written as $$\left|q_0\right>_{10}\left|q_1\right>_{11}=\left|q_0q_1\right>_{1}$$ with $$q_0,q_1\in\{0,1\}$$ in this convention, which makes sense because $$q_0$$ occupies the position $$0$$ and $$q_1$$ occupies the position $$1$$ from left to right.
Also you are right, there is a factorization and you can check this fact expanding the first two terms related to the system $$1$$ in $$\left|\psi_2\right>$$ using the convention explained previously:
$$\left|\psi_2\right>=\frac{1}{\sqrt{2}}(\left|0\right>_{10}-\left|1\right>_{10})\frac{1}{\sqrt{2}}(\left|0\right>_{11}-\left|1\right>_{11})\frac{1}{\sqrt{2}}(\left|0\right>_{2}-\left|1\right>_{2})=\frac{1}{2}(\left|0\right>_{10}\left|0\right>_{11}-\left|0\right>_{10}\left|1\right>_{11}-\left|1\right>_{10}\left|0\right>_{11}+\left|1\right>_{10}\left|1\right>_{11})\frac{1}{\sqrt{2}}(\left|0\right>_{2}-\left|1\right>_{2})\\ =\frac{1}{2}(\left|00\right>_{1}-\left|01\right>_{1}-\left|10\right>_{1}+\left|11\right>_{1})\frac{1}{\sqrt{2}}(\left|0\right>_{2}-\left|1\right>_{2})$$.