Using Cloning to Solve NP Complete Problems

Abstract

Assuming a cloning oracle, satisfiability, which is an NP complete problem, is shown to belong to $BP{P}^C$ and $BQ{P}^C$ (depending on the ability of the oracle C to clone either a binary random variable or a qubit). The same result is extended in the case of an approximate cloning oracle, thus establishing that $NP\subseteq BP{P}^C\subseteq BQ{P}^C$ and $NP\subseteq BP{P}^{AC}\subseteq BQ{P}^{AC}$, where C and AC are the exact and approximate cloning oracles, respectively. Although exact cloning is impossible in quantum systems, approximate cloning remains a possibility. However, the best known methods for approximate cloning (based on unitary evolution) do not currently achieve the desired precision levels. And it remains an open question whether they could be improved when non-linear (or non-unitary) operators are used. Finally, a straightforward attempt to dispense with cloning, replacing it by unitary evolution, is proved to be impossible.