License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CCC.2015.488
URN: urn:nbn:de:0030-drops-50697
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2015/5069/
Kobayashi, Hirotada ;
Le Gall, Francois ;
Nishimura, Harumichi
Generalized Quantum Arthur-Merlin Games
Abstract
This paper investigates the role of interaction and coins in quantum Arthur-Merlin games (also called public-coin quantum interactive proof systems). While the existing model restricts the messages from the verifier to be classical even in the quantum setting, the present work introduces a generalized version of quantum Arthur-Merlin games where the messages from the verifier can be quantum as well: the verifier can send not only random bits, but also halves of EPR pairs. This generalization turns out to provide several novel characterizations of quantum interactive proof systems with a constant number of turns. First, it is proved that the complexity class corresponding to two-turn quantum Arthur-Merlin games where both of the two messages are quantum, denoted qq-QAM in this paper, does not change by adding a constant number of turns of classical interaction prior to the communications of qq-QAM proof systems. This can be viewed as a quantum analogue of the celebrated collapse theorem for AM due to Babai. To prove this collapse theorem, this paper presents a natural complete problem for qq-QAM: deciding whether the output of a given quantum circuit is close to a totally mixed state. This complete problem is on the very line of the previous studies investigating the hardness of checking properties related to quantum circuits, and thus, qq-QAM may provide a good measure in computational complexity theory. It is further proved that the class qq-QAM_1, the perfect-completeness variant of qq-QAM, gives new bounds for standard well-studied classes of two-turn quantum interactive proof systems. Finally, the collapse theorem above is extended to comprehensively classify the role of classical and quantum interactions in quantum Arthur-Merlin games: it is proved that, for any constant m >= 2, the class of problems having $m$-turn quantum Arthur-Merlin proof systems is either equal to PSPACE or equal to the class of problems having two-turn quantum Arthur-Merlin proof systems of a specific type, which provides a complete set of quantum analogues of Babai's collapse theorem.
BibTeX - Entry
@InProceedings{kobayashi_et_al:LIPIcs:2015:5069,
author = {Hirotada Kobayashi and Francois Le Gall and Harumichi Nishimura},
title = {{Generalized Quantum Arthur-Merlin Games}},
booktitle = {30th Conference on Computational Complexity (CCC 2015)},
pages = {488--511},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-939897-81-1},
ISSN = {1868-8969},
year = {2015},
volume = {33},
editor = {David Zuckerman},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2015/5069},
URN = {urn:nbn:de:0030-drops-50697},
doi = {10.4230/LIPIcs.CCC.2015.488},
annote = {Keywords: interactive proof systems, Arthur-Merlin games, quantum computing, complete problems, entanglement}
}
|
Keywords: |
|
interactive proof systems, Arthur-Merlin games, quantum computing, complete problems, entanglement |
|
Collection: |
|
30th Conference on Computational Complexity (CCC 2015) |
|
Issue Date: |
|
2015 |
|
Date of publication: |
|
06.06.2015 |
