Clarification needed regarding quantum "black-box" circuits

Question

$\newcommand{\Ket}[1]{\left|#1\right>}$

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:

$$\frac{\Ket{0}\Ket{f(0)}+\Ket{1}\Ket{f(1)}}{\sqrt{2}}$$

(Or perhaps both are wrong? :))

Answer 1

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.

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