DocumentCode :
1632913
Title :
Arthur and Merlin in a quantum world
Author :
Watrous, John
Author_Institution :
Dept. of Comput. Sci., Calgary Univ., Alta., Canada
fYear :
2002
fDate :
6/24/1905 12:00:00 AM
Firstpage :
132
Lastpage :
132
Abstract :
Arthur does not have a lot of time to spend performing difficult computations. He´s recently obtained a quantum computer, but often it seems not to help - he only has a few quantum algorithms, and Merlin maintains that there aren´t any other interesting ones, so Merlin is forced to convince the untrusting Arthur of the truth of various facts. However, Arthur and Merlin have a new resource at their disposal: quantum information. Some relationships among complexity classes defined by quantum Arthur-Merlin games and other commonly studied complexity classes are known, but many open questions remain. In this paper, I discuss quantum Arthur-Merlin games in detail, with an emphasis on open problems
Keywords :
computational complexity; game theory; quantum computing; complexity class relationships; quantum Arthur-Merlin games; quantum algorithms; quantum computer; quantum information; Computational complexity; Computational modeling; Computer science; Information processing; Polynomials; Protocols; Quadrature amplitude modulation; Quantum computing; Quantum entanglement;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Computational Complexity, 2002. Proceedings. 17th IEEE Annual Conference on
Conference_Location :
Montreal, Que.
ISSN :
1093-0159
Print_ISBN :
0-7695-1468-5
Type :
conf
DOI :
10.1109/CCC.2002.1004351
Filename :
1004351
Link To Document :
بازگشت