patternMinor
Trying to understand how the first Hadamard gate in Deutsch–Jozsa algorithm works
Viewed 0 times
deutschjozsathetryingalgorithmunderstandfirsthadamardworkshow
Problem
I'm still a beginner in the quantum aspect of computer science (self-studying). So please bear with me if this may sound like a stupid question.
I know Hadamard gate transforms qubit into a superposition state with $\frac{1}{2}$ chance that the outcome would be 0 or 1 when the wave function collapses:
$$\frac{\left|0\right\rangle + \left|1\right\rangle}{\sqrt2} \text{ for }\left|0\right\rangle \\
\frac{\left|0\right\rangle - \left|1\right\rangle}{\sqrt2} \text{ for }\left|1\right\rangle$$
For already-in-a-superposition qubit, it would be just some linear transformation.
$$\alpha\left|0\right\rangle + \beta\left|1\right\rangle \rightarrow \alpha \frac{\left|0\right\rangle + \left|1\right\rangle}{\sqrt2} + \beta \frac{\left|0\right\rangle - \left|1\right\rangle}{\sqrt2} = \frac{\alpha+\beta}{\sqrt2}\left|0\right\rangle + \frac{\alpha-\beta}{\sqrt2}\left|1\right\rangle $$
But I got really confused when I see the $\Sigma \left|x\right\rangle$ in the equation on the Wikipedia article about Deutsch–Jozsa algorithm.
A Hadamard transformation is applied to each bit to obtain the state
Why is it doing a summation with a ever-increasing value of $x$? My understanding of a qubit is that it can only be in either $\left|0\right\rangle$, $\left|1\right\rangle$ or a superposition state.
What the equation is doing above appears to indicate that if $n$ is 2, we would get
$$\frac{1}{\sqrt{2^{3}}} \left|0\right\rangle (\left|0\right\rangle - \left|1\right\rangle) + \frac{1}{\sqrt{2^{3}}}\left|1\right\rangle (\left|0\right\rangle - \left|1\right\rangle) + \\\frac{1}{\sqrt{2^{3}}} \left|2\right\rangle (\left|0\right\rangle - \left|1\right\rangle) + \frac{1}{\sqrt{2^{3}}} \left|3\right\rangle (\left|0\right\rangle - \left|1\right\rangle)$$
How do I make sense of the $\left|2\right\rangle$ and $\left|3\right\rangle$?
[Update]
As I was writing the question, I remembered that qubits in the state of $\left|1\right\rangle$$\left|0\right\rangle$ are often expressed as $\
I know Hadamard gate transforms qubit into a superposition state with $\frac{1}{2}$ chance that the outcome would be 0 or 1 when the wave function collapses:
$$\frac{\left|0\right\rangle + \left|1\right\rangle}{\sqrt2} \text{ for }\left|0\right\rangle \\
\frac{\left|0\right\rangle - \left|1\right\rangle}{\sqrt2} \text{ for }\left|1\right\rangle$$
For already-in-a-superposition qubit, it would be just some linear transformation.
$$\alpha\left|0\right\rangle + \beta\left|1\right\rangle \rightarrow \alpha \frac{\left|0\right\rangle + \left|1\right\rangle}{\sqrt2} + \beta \frac{\left|0\right\rangle - \left|1\right\rangle}{\sqrt2} = \frac{\alpha+\beta}{\sqrt2}\left|0\right\rangle + \frac{\alpha-\beta}{\sqrt2}\left|1\right\rangle $$
But I got really confused when I see the $\Sigma \left|x\right\rangle$ in the equation on the Wikipedia article about Deutsch–Jozsa algorithm.
A Hadamard transformation is applied to each bit to obtain the state
Why is it doing a summation with a ever-increasing value of $x$? My understanding of a qubit is that it can only be in either $\left|0\right\rangle$, $\left|1\right\rangle$ or a superposition state.
What the equation is doing above appears to indicate that if $n$ is 2, we would get
$$\frac{1}{\sqrt{2^{3}}} \left|0\right\rangle (\left|0\right\rangle - \left|1\right\rangle) + \frac{1}{\sqrt{2^{3}}}\left|1\right\rangle (\left|0\right\rangle - \left|1\right\rangle) + \\\frac{1}{\sqrt{2^{3}}} \left|2\right\rangle (\left|0\right\rangle - \left|1\right\rangle) + \frac{1}{\sqrt{2^{3}}} \left|3\right\rangle (\left|0\right\rangle - \left|1\right\rangle)$$
How do I make sense of the $\left|2\right\rangle$ and $\left|3\right\rangle$?
[Update]
As I was writing the question, I remembered that qubits in the state of $\left|1\right\rangle$$\left|0\right\rangle$ are often expressed as $\
Solution
After studying the maths behind it, I realized that a linear algebraic expression for a quantum state may not appear to be intuitive at first sight (or prehaps it is only to the not mathematically gifted ones like myself).
Apparently, this is how the expression in the Wikipedia page is derived:
$$\begin{align} &\frac{\left|0...0\right\rangle + \left|0...1\right\rangle + \left|1...1\right\rangle}{\sqrt2 ... \sqrt2} \cdot \frac{1}{\sqrt{2}} (\left|0\right\rangle - \left|1\right\rangle)\\ =&\sum^{n}_{x=0}\frac{1}{\sqrt{2^n}} \left|x\right\rangle \cdot \frac{1}{\sqrt{2}} (\left|0\right\rangle - \left|1\right\rangle) \\=&\sum^{n}_{x=0}\frac{1}{\sqrt{2^{n+1}}} \left|x\right\rangle \cdot (\left|0\right\rangle - \left|1\right\rangle) \\ =&\frac{1}{\sqrt{2^{n+1}}} \sum^{n}_{x=0} \left|x\right\rangle (\left|0\right\rangle - \left|1\right\rangle) \end{align}$$
Now this explains why it is alright to have the four $\frac{1}{\sqrt{2^{3}}}$ probability amplitudes above, which is indeed just the product of $\frac{1}{\sqrt{2^{2}}}$ and $\frac{1}{\sqrt{2}}$.
$\frac{\left|0...0\right\rangle + \left|0...1\right\rangle + \left|1...1\right\rangle}{\sqrt2 ... \sqrt2} \cdot \frac{1}{\sqrt{2}} (\left|0\right\rangle - \left|1\right\rangle)$ sure feels like we are having a superposition state within a superposition state (I'm not sure if that is the correct way to interpret it). And this is probably what makes an entangled system so magical when it comes to computation.
Apparently, this is how the expression in the Wikipedia page is derived:
$$\begin{align} &\frac{\left|0...0\right\rangle + \left|0...1\right\rangle + \left|1...1\right\rangle}{\sqrt2 ... \sqrt2} \cdot \frac{1}{\sqrt{2}} (\left|0\right\rangle - \left|1\right\rangle)\\ =&\sum^{n}_{x=0}\frac{1}{\sqrt{2^n}} \left|x\right\rangle \cdot \frac{1}{\sqrt{2}} (\left|0\right\rangle - \left|1\right\rangle) \\=&\sum^{n}_{x=0}\frac{1}{\sqrt{2^{n+1}}} \left|x\right\rangle \cdot (\left|0\right\rangle - \left|1\right\rangle) \\ =&\frac{1}{\sqrt{2^{n+1}}} \sum^{n}_{x=0} \left|x\right\rangle (\left|0\right\rangle - \left|1\right\rangle) \end{align}$$
Now this explains why it is alright to have the four $\frac{1}{\sqrt{2^{3}}}$ probability amplitudes above, which is indeed just the product of $\frac{1}{\sqrt{2^{2}}}$ and $\frac{1}{\sqrt{2}}$.
$\frac{\left|0...0\right\rangle + \left|0...1\right\rangle + \left|1...1\right\rangle}{\sqrt2 ... \sqrt2} \cdot \frac{1}{\sqrt{2}} (\left|0\right\rangle - \left|1\right\rangle)$ sure feels like we are having a superposition state within a superposition state (I'm not sure if that is the correct way to interpret it). And this is probably what makes an entangled system so magical when it comes to computation.
Context
StackExchange Computer Science Q#37080, answer score: 4
Revisions (0)
No revisions yet.