Using Cloning to Solve NP Complete Problems

Details Using Cloning to Solve NP Complete Problems Using Cloning to Solve NP Complete Problems

2001-12-21

arxiv.org/abs/quant-ph/0112133v1

Physics

Quantum Physics

Scientific paper

Assuming a cloning oracle, satisfiability, which is an NP complete problem, is shown to belong to $BPP^C$ and $BQP^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 BPP^C \subseteq BQP^C$ and $NP \subseteq BPP^{AC} \subseteq BQP^{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.

Affiliated with

Also associated with

No associations

Rating

Using Cloning to Solve NP Complete Problems does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Using Cloning to Solve NP Complete Problems, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Using Cloning to Solve NP Complete Problems will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-175987