Study of Unentanglement in Quantum Computers
Rayan Chikhi · 2008
This report explains the research work done during a February-June 2008 internship at MIT under the supervision of Scott Aaronson and Seth Lloyd. It exposes some necessary background knowledge in quantum mechanics, quantum computing and quantum complexity theory, and then focuses on the work conducted during this internship. The subject of this internship is to study two important classes of quantum problems, QMA and QMA(2), which consist of all languages that can be verified using respectively one and two unentangled quantum proofs. Whether these classes are equal or distinct is an open problem of great interest in quantum computing. To prove that they are the same, one can possibly simulate QMA(2) problems in QMA using a quantum operation called a disentangler. However, it has been conjectured that polynomial disentanglers do not exist, and therefore this approach fails. In this report, we investigate this conjecture and give two results: in a specific situation, when exponential precision is required, this conjecture holds as long as P 6 = NP. Moreover, in the same situation, we show that the conjecture could be proven unconditionally using a stronger hypothesis.