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?
-
$\begingroup$ Could you separate the different parts of that Question, please? Isn't whether quantum cloning is possible quite different from whether any classical function can be implemented as a quantum circuit? Implementing any classical function as a quantum circuit might help, but how could that make anything else impossible? $\endgroup$– Robbie GoodwinJul 19, 2022 at 18:05
3 Answers
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.
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$.
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.