2001/12/21 by John A. Drakopoulos, Drakopoulos, John A., Theodore N. Tomaras +2
Computer Science · Physics and Astronomy · #Computability, Logic, AI Algorithms #FOS: Physical sciences #Quantum Computing Algorithms and Architecture #Quantum Physics (quant-ph) #Teaching and Learning Programming #quant-ph
paper · pdf · doi:10.48550/arxiv.quant-ph/0112133
arxiv created 2001/12/21 · openalex publication_date 2001/12/21 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Assuming a cloning oracle, satisfiability, which is an NP complete problem, is shown to belong to BPPC and BQPC (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 ⊆ BPPC ⊆ BQPC and NP ⊆ BPPAC ⊆ BQPAC, 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.