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?


1 Answer 1


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$.

  • $\begingroup$ This seems a bit weird for this reason : After the $f$ oracle has acted on the superposition state, $\frac{1}{\sqrt{2^n }} \sum_{x \in \{0,1 \}^n} |x> $ what one is left with is a quantum system in the state $\frac{1}{\sqrt{2^n }} \sum_{x \in \{0,1\}^n} (-1)^{x.s} |x> $. Now how does the $i^{th}$ Hadamard gate in the second layer pick out which is the $i^{th}$ qubit? I would have thought that what comes out of the $f$ oracle is this superposition state, $\frac{1}{\sqrt{2^n }} \sum_{x \in \{0,1\}^n} (-1)^{x.s} |x> $ $\endgroup$
    – user6818
    Commented Jul 10, 2015 at 22:34
  • $\begingroup$ The qubits are physical objects which can be operated upon individually. The state of the entire system is some superposition involving the states of the individual qubits in some (possibly) dependent fashion. $\endgroup$ Commented Jul 10, 2015 at 22:36
  • $\begingroup$ So do you know the quantum state of the $i^{th}$ qubit's quantum state after the $f$ oracle has given its output? $\endgroup$
    – user6818
    Commented Jul 10, 2015 at 22:37
  • $\begingroup$ It doesn't have a state per se. If you measure the $i$th qubit then the state of the entire system collapses to a tensor product of a deterministic state of the $i$th qubit and some superposition of the remaining qubits. $\endgroup$ Commented Jul 10, 2015 at 22:38
  • $\begingroup$ True. That I understand. But then what is the input state to the $i^{th}$ Hadamard gate in the second layer? On what state is it acting on? $\endgroup$
    – user6818
    Commented Jul 10, 2015 at 22:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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