patternMinor
How many inputs does the Hadamard gate have?
Viewed 0 times
inputsthehowhadamarddoesmanygatehave
Problem
Look at the diagram in the middle of page 6-3 here,
http://stellar.mit.edu/S/course/6/fa14/6.845/courseMaterial/topics/topic3/lectureNotes/qctlec6/qctlec6.pdf
I am confused as to how should one think of the Hadamard gate.
As per the mathematics shown below it seems that the Hadamard gate, $H$ acts on tensor products of states as follows,
$$H( \otimes ^n | 0 \rangle) = \otimes ^n ( H | 0 \rangle ) = \otimes ^n ( \frac { |0\rangle + |1\rangle }{\sqrt{2} } ) = \frac{1}{\sqrt{2^n} } \sum_{x \in \{ 0,1\}^n} |x\rangle $$
But then the above interpretation and the diagram and the text have a few apparent discrepancies between them,
-
In the diagram there is no step which looks like $\otimes ^n ( H | 0 \rangle ) $. It seem that all the wires carrying $H|0\rangle$ are straight away sent to the $f$ oracle without this tensoring between them.
-
In terms of circuit complexity is this to be thought of as a "single" Hadamard gate or as $n$ Hadamard gates?
-
Lastly how does the gate $H$ know about the state $|1\rangle$ ? It only sees the $|0\rangle$ states.
-
And the last step is totally unclear: on which state is the $i$th Hadamard gate acting to get $ |s_i\rangle$? It doesn't seem to be there in the equations below.
Can someone help clarify this?
http://stellar.mit.edu/S/course/6/fa14/6.845/courseMaterial/topics/topic3/lectureNotes/qctlec6/qctlec6.pdf
I am confused as to how should one think of the Hadamard gate.
As per the mathematics shown below it seems that the Hadamard gate, $H$ acts on tensor products of states as follows,
$$H( \otimes ^n | 0 \rangle) = \otimes ^n ( H | 0 \rangle ) = \otimes ^n ( \frac { |0\rangle + |1\rangle }{\sqrt{2} } ) = \frac{1}{\sqrt{2^n} } \sum_{x \in \{ 0,1\}^n} |x\rangle $$
But then the above interpretation and the diagram and the text have a few apparent discrepancies between them,
-
In the diagram there is no step which looks like $\otimes ^n ( H | 0 \rangle ) $. It seem that all the wires carrying $H|0\rangle$ are straight away sent to the $f$ oracle without this tensoring between them.
-
In terms of circuit complexity is this to be thought of as a "single" Hadamard gate or as $n$ Hadamard gates?
-
Lastly how does the gate $H$ know about the state $|1\rangle$ ? It only sees the $|0\rangle$ states.
-
And the last step is totally unclear: on which state is the $i$th Hadamard gate acting to get $ |s_i\rangle$? It doesn't seem to be there in the equations below.
Can someone help clarify this?
Solution
The $n$-ary Hadamard gate acts on $n$ qubits. The state of the $n$ qubits is a unit norm vector of dimension $2^n$. You can take as basis the vectors $|x\rangle$ for $x \in \{0,1\}^n$.
As it happens, the $n$-ary Hadamard gate can be simulated by $n$ unary Hadamard gates acting on the individual qubits, which is what you see on page 6-3. The reason is that the $n$-dimensional Hadamard transform is the tensor product of $n$ one-dimensional Hadamard transforms.
The usual convention in circuit complexity is that gates have bounded fan-in. Otherwise you can compute any function using a large gate!
Consider the case $n=1$:
$$
\begin{bmatrix}
\frac{1}{\sqrt{2}} & \frac{1}{\sqrt{2}} \\
\frac{1}{\sqrt{2}} & -\frac{1}{\sqrt{2}}
\end{bmatrix}
\begin{bmatrix} 1 \\ 0 \end{bmatrix} =
\begin{bmatrix} \frac{1}{\sqrt{2}} \\ \frac{1}{\sqrt{2}} \end{bmatrix} \, .
$$
This is where $|1\rangle$ comes from.
The entire circuit involves initializing $n$ qubits at the state $|0\rangle$, applying $n$ unary Hadamard gates on the $n$ qubits, applying the black box function $f$, and then applying the Hadamard gates again on the $n$ qubits. The final state of the $i$th qubit turns out to be $|s_i\rangle$.
As it happens, the $n$-ary Hadamard gate can be simulated by $n$ unary Hadamard gates acting on the individual qubits, which is what you see on page 6-3. The reason is that the $n$-dimensional Hadamard transform is the tensor product of $n$ one-dimensional Hadamard transforms.
The usual convention in circuit complexity is that gates have bounded fan-in. Otherwise you can compute any function using a large gate!
Consider the case $n=1$:
$$
\begin{bmatrix}
\frac{1}{\sqrt{2}} & \frac{1}{\sqrt{2}} \\
\frac{1}{\sqrt{2}} & -\frac{1}{\sqrt{2}}
\end{bmatrix}
\begin{bmatrix} 1 \\ 0 \end{bmatrix} =
\begin{bmatrix} \frac{1}{\sqrt{2}} \\ \frac{1}{\sqrt{2}} \end{bmatrix} \, .
$$
This is where $|1\rangle$ comes from.
The entire circuit involves initializing $n$ qubits at the state $|0\rangle$, applying $n$ unary Hadamard gates on the $n$ qubits, applying the black box function $f$, and then applying the Hadamard gates again on the $n$ qubits. The final state of the $i$th qubit turns out to be $|s_i\rangle$.
Context
StackExchange Computer Science Q#44317, answer score: 3
Revisions (0)
No revisions yet.