Is effective quantum cloning possible, given that any classical function can be implemented as a quantum circuit?

Question

As in Compiling a classical function to a quantum circuit in practice, as far as my understanding goes, it is known that any classical function can be implemented as a quantum circuit. So given $f(x)=x$, there should be some quantum circuit $Q_f$ such that, up to garbage bits and normalization, $$ \sum_{x}|x,0^k\rangle \xrightarrow{\mathit{Q_f}} \sum_{x}|x,x\rangle. $$ However, the no-cloning theorem suggests this is not possible, which leaves me confused. What is going on?

Answer 1

No-cloning theorem suggests no such thing. A closer look at the theorem's proof reveals a loophole for orthonormal states. The theorem says that there is no unitary $U$ such that

$$ U|\psi\rangle|0\rangle=|\psi\rangle|\psi\rangle\tag1 $$

for all states $|\psi\rangle$. The proof goes through by showing that if $(1)$ is satisfied for states $|\psi_1\rangle$ and $|\psi_2\rangle$ then $x=\langle\psi_1|\psi_2\rangle\in\{0,1\}$. This is a consequence of the following simple calculation

$$ \begin{align} x &= \langle\psi_1|\psi_2\rangle\tag2\\ &= \langle\psi_1|\psi_2\rangle\langle 0|0\rangle\tag3\\ &= \langle\psi_1|\langle 0|U^\dagger U|\psi_2\rangle|0\rangle\tag4\\ &= \langle\psi_1|\psi_2\rangle\langle\psi_1|\psi_2\rangle\tag5\\ &= x^2.\tag6 \end{align} $$

Now, the only complex number $x$ such that $x=x^2$ is zero or one. Therefore, for any unitary $U$, the set of copiable states (i.e. states for which $(1)$ is satisfied) is orthonormal. Since the set of all states is not othonormal, no unitary can copy all states. However, any orthonormal basis, such as the computational basis $|b\rangle$ for $b\in\{0,1\}^n$, is copiable.

In particular, the unitary that copies the single-qubit computational basis states is the well-known CNOT gate. To see this, note that $(1)$ is satisfied by the substitutions $U=\text{CNOT}$ and $|\psi\rangle=|0\rangle, |1\rangle$. This is a special case of $Q_f$ for the case of a single qubit.

Answer 2

Just to complement the other answer, the operation $Q_f$ does certainly exist and is sometimes called a transversal CNOT: Given an arbitrary $n$-qubit state expressed in the computational basis as $$ |\psi\rangle = \sum_{\mathbf{x} \in \{0,1\}^n} c_\mathbf{x} |\mathbf{x}\rangle \tag{1} $$

then we can prepare the $2n$-qubit state \begin{equation} |\phi\rangle = \sum_{\mathbf{x} \in \{0,1\}^n} c_\mathbf{x} |\mathbf{x}\rangle |\mathbf{x}\rangle \tag{2} \end{equation}

by executing the following circuit:

                                                                     

The existence of both this operation and the no-cloning theorem implies that the no-cloning theorem cannot imply that this operation does not exist.

We have not really cloned $|\psi\rangle$ in a rigorous sense, since the new state contains $2n$-qubits with quite a bit of entanglement. One might wonder whether we could somehow un-entangle the two registers of $|\phi\rangle$ to get out multiple copies of $|\psi\rangle$. But here the no cloning theorem does imply such an operation would be impossible: there can be no way to extract two copies of $|\psi\rangle$ from $|\phi\rangle$.

Answer 3

Classical cloning circuit is called fanout. If we implement fanout as a quantum circuit (for example, by CNOT gate), we will see that it does not clone arbitrary qubit, as no-cloning theorem requires, only pair of "classical" qubits, $\{0,1\}$. There is no contradiction here. A quantum circuit implementing classical circuit should only do the same with the "classical" qubits, there are no limitations on other qubits.