I understand that in general quantum black box algorithms (such as the ones which play a part in Simon's & Deutsch's algorithm) implement a quantum circuit to compute some function $f\left(x\right)$ in such a way that the input is fed with trailing zero qubits, and the result is the input followed by the output, e.g:

$$\Ket{x}\Ket{0} \rightarrow \Ket{x}\Ket{f(x)}\,.$$

My question is, since basically one can write the above more explicitly as:$$ \Ket{x}\otimes\Ket{0} \rightarrow \Ket{x}\otimes\Ket{f(x)} \,,$$whether it is possible, in case $\Ket{x}$ is not a pure state but a superposition, to get an output which "mixes" inputs with the wrong outputs.

To clarify what I mean I'll give an example: Suppose our input is the one qubit superposition:

$$\Ket{x} = \frac{\Ket{0}+\Ket{1}}{\sqrt{2}}$$

Will the result of the black-box circuit be the following tensor product:

$$ \left\lbrack\frac{\Ket{0}+\Ket{1}}{\sqrt{2}}\right\rbrack \otimes \left\lbrack\frac{\Ket{f(0)}+\Ket{f(1)}}{\sqrt{2}}\right\rbrack $$

(Which I find confusing and unlikely) Or, the other option which seems to be more natural:


(Or perhaps both are wrong? :))


2 Answers 2


$$\newcommand{\Bra}[1]{\left<#1\right|}\newcommand{\Ket}[1]{\left|#1\right>}\newcommand{\bk}[2]{\left<#1\middle|#2\right>}\newcommand{\bke}[3]{\left<#1\middle|#2\middle|#3\right>}$$ It is always good to start from considering an example. Suppose you have CNOT gate; then \begin{align} \Ket{0}\Ket{0} \rightarrow \Ket{0}\Ket{0}\\ \Ket{1}\Ket{0} \rightarrow \Ket{1}\Ket{1} \end{align} By linearity \begin{align} \frac{1}{\sqrt{2}}(\Ket{0}\Ket{0} + \Ket{1}\Ket{0}) \rightarrow \frac{1}{\sqrt{2}}(\Ket{0}\Ket{0}+ \Ket{1}\Ket{1}) \end{align} or \begin{align} \frac{1}{\sqrt{2}}(\Ket{0} + \Ket{1})\Ket{0} \rightarrow \frac{1}{\sqrt{2}}(\Ket{0}\Ket{0}+ \Ket{1}\Ket{1}) \end{align} So your first guess is wrong, but the second guess seems to be true, and it is not hard to convince yourself that it is indeed true.

  • $\begingroup$ Thanks! Indeed, I should have thought about taking CNOT as the simplest example for f(x). Thanks again. $\endgroup$
    – Amit
    Commented May 20, 2018 at 18:35

Nice question. Your second example is correct. I will show this by using Equation 2 from here:

$(A + B)\otimes C = A\otimes C + B\otimes C$.

For your example:

$\left(\frac{|0\rangle+|1\rangle}{\sqrt{2}}\right)\otimes|f(x)\rangle = \frac{|0\rangle\otimes|f(x)\rangle}{\sqrt{2}}+\frac{|1\rangle\otimes|f(x)\rangle}{\sqrt{2}} = \frac{|0\rangle\otimes|f(0)\rangle}{\sqrt{2}}+\frac{|1\rangle\otimes|f(1)\rangle}{\sqrt{2}}$

You can see this being done, for example, in the first line of Page 6 in these lecture notes of Prof. John Watrous.


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.