2
$\begingroup$

I am currently learning from Nielsen and Chuang and I am currently learning about Deutsch-Jozsa algorithm. However, I am stumped with the mathematics of the algorithm at the following section: The section

I understand intuitively that it works very similarly with Deutsch algorithm where we could measure a global state of the function with only 1 measurement, but I couldn't do it mathematically. Why is the amplitude simply so without including the $x \cdot z$ factor? I am also having a hard time on the summation over $x$ on the amplitudes. Why is the resulting amplitude for the constant case is $\pm 1$ and 0 for the balanced case?

$\endgroup$
1
$\begingroup$

Why is the amplitude simply so without including the $x \dot z$ factor?

When you calculate the amplitude of the $|0\rangle^{\otimes n}$ state, you have $z = 0$ (the integer representation of the state you're looking at), so $x \dot z = 0$ for any $x$.

Why is the resulting amplitude for the constant case is ±1 and 0 for the balanced case?

For the constant case, if $f(x) = 0$, each of the terms $(-1)^{f(x)}/2^n = 1/2^n$, and there are $2^n$ of them, so they add up to 1. If $f(x) = 1$, each of the terms is $-1/2^n$, and they add up to -1, with the phase difference habitually discarded.

For the balanced cases, exactly half of the terms evaluate to $1/2^n$, and the other half to $-1/2^n$, so they cancel each other out, and the resulting sum is 0.

$\endgroup$
2
  • $\begingroup$ Thank you for the reply. I would like to clarify some things. Is z only 0 because initially it was $|0⟩^{⊗n}$? So if let's just say I use $|1⟩^{⊗n}$ The factor in question should persist right? $\endgroup$ May 30 at 4:25
  • $\begingroup$ z is 0 because we're looking at the amplitude of the basis state |z⟩ = |0...0⟩ in the resulting state $|\psi_3\rangle$. If we look at the amplitude of any other component, xz will remain, yes $\endgroup$ May 30 at 5:15

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.