Copying quantum computer makes NP-complete problems tractable.
Mika Hirvensalo · 1998
Under the assumption that a quantum computer can exactly copy quantum superpositions, we show that NP-complete problems can be solved probabilistically in polynomial time. We also propose two methods that could potentially allow to avoid the use of a quantum copymachine. Supported by the Academy of Finland under grant 14047. To be presented at MCU'98, March 1998, Metz, France. TUCS Research Group Theory Group: Mathematical Methods in Computer Science 1 Introduction It was conjectured by R. Feynman [5] in 1982 that it may be impossible to simulate quantum physical phenomena by an ordinary computer without an exponential slowdown in the efficiency of the simulation. In his work, Feynman also suggested that the slowdown could be avoided by allowing the computer run according to rules of quantum mechanics, thus introducing the idea of quantum computer. However, quantum computation remained quite a marginal phenomenon in the theory of computing until 1994, when Peter W. Shor discovered ...