In Nielsen and Chuang, for the following circuit that demonstrates quantum parallelism, I have the following question:

enter image description here

since the output state of the circuit is $$\frac1{\sqrt2}(|0,f(0)\rangle+|1,f(1)\rangle).$$

How would we isolate the state of f(0) and f(1) from the state of 0 and 1 to get information that we want (state of f(0) and f(1))?

  • 2
    $\begingroup$ Hi! Each post should be focused on one question. Ideally, it would also have a good title, which is easier when it asks one question :-) $\endgroup$ Aug 20, 2021 at 2:22

1 Answer 1


The idea is after only one application of $U_f$, the superposition state now contains both function values of $f(x)$ entangled to their corresponding input value $x$. This effect is called quantum parallelism.

This can be extend to more general cases, where the data register (the register at the top) has more than 1 qubit. Suppose the data register has $n$ qubits, then by first applying Hadamard gate to each of the qubit (so that each of the qubit starts in the state $\dfrac{|0\rangle + |1\rangle}{\sqrt{2}}$ then we have:

$$ U_f: \dfrac{1}{\sqrt{2^n}} \sum_{x =0}^{2^n -1} |x\rangle |0\rangle \rightarrow \dfrac{1}{\sqrt{2^n}} \sum_{x =0}^{2^n -1} |x\rangle |f(x)\rangle $$

Note if you let $n = 1$ then you get back the form in your question: $$ U_f: \dfrac{1}{\sqrt{2}}\big(|0\rangle + |1\rangle \big)|0\rangle = \dfrac{1}{\sqrt{2}}\big(|0\rangle|0\rangle + |1\rangle |0\rangle \big) \rightarrow \dfrac{1}{\sqrt{2}}\big(|0\rangle|f(0) \rangle + |1\rangle |f(1)\rangle \big) $$

So the idea is that with just one application of $U_f$, which uses only $n$ qubits, you created a state that contains all of the $2^n$ function values $f(x)$ that are entangled with their corresponding input value $x$.

However, you are right that extracting out each value of $f(x)$ can be a problem. This is because we can only gain limited information from this superposition because of the Holevo bound theorem. That is, upon measurement in the computational basis, we will project the final state onto a single input/output pair $|x\rangle |f(x) \rangle$ randomly. So even though $2^n$ values of $f(x)$ appear in the superposition state, we still really need $2^n$ computations of $U_f$ to extract them all. This is why quantum parallelism is actually less powerful than we think. And in general, quantum parallelism and quantum computation don't just provide an exponential speed-up over classical computation. We must carefully designing the algorithm to take advantage of this parallelism.


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.