Abstract

After Shor's factoring algorithm on a quantum computer, quantum computation and quantum information theory got a lot attention. In these days, people are trying to answer any classical question in a quantum point of view. Fault tolerant quantum computation, quantum coding, quantum algorithms, quantum complexity and quantum information theory are examples of such theories that have been developed during these years. It seems that ''entanglement'' is the main resource of quantum mechanic that gives us more power in the theory of computation, than the classical case. In quantum information theory there are some methods to measure the entanglement. The most famous such measure is ''entanglement of formation''. However, additivity, one of the main properties of such measure is not known for entanglement of formation. We can also measure entanglement in complexity theory point of view. We can provide some fixed amount of entanglement for a quantum computer and ask him to solve hard problems. BQP, QMA, QCMA are some quantum complexity classes that are defined based on this idea. QMA is known as the quantum version of the complexity class NP. That is Merlin provides a quantum witness for Arthur, and Arthur tries to check the witness in polynomial time. Let us assume that there are k Merlins, rather than just one, and define QMA(k) similarly. It is obvious that in classical case more than one Merlin never helps Arthur to solve harder problems. However it is unknown in quantum case. In this talk, after basic definitions of quantum computation we introduce the quantum complexity classes QMA and QMA(k), and then show that QMA(k)=QMA(2), for k>2, if the additivity conjecture in quantum information theory holds. This talk is based on a join work with Shor, Aaronson, Fefferman and Drucker.



Information: