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)] $$


$$|ψ_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) $$


$$ |ψ_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?

  • $\begingroup$ 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. $\endgroup$ Mar 22 '20 at 9:20
  • $\begingroup$ 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? $\endgroup$ Mar 22 '20 at 9:34
  • $\begingroup$ 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$. $\endgroup$ 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})$.

I hope this can help you to clarify your problem.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.