Kobayashi, Hirotada ;
Le Gall, Francois ;
Nishimura, Harumichi
Generalized Quantum ArthurMerlin Games
Abstract
This paper investigates the role of interaction and coins in quantum ArthurMerlin games (also called publiccoin 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 ArthurMerlin 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 twoturn quantum ArthurMerlin games where both of the two messages are quantum, denoted qqQAM in this paper, does not change by adding a constant number of turns of classical interaction prior to the communications of qqQAM 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 qqQAM: 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, qqQAM may provide a good measure in computational complexity theory. It is further proved that the class qqQAM_1, the perfectcompleteness variant of qqQAM, gives new bounds for standard wellstudied classes of twoturn quantum interactive proof systems. Finally, the collapse theorem above is extended to comprehensively classify the role of classical and quantum interactions in quantum ArthurMerlin games: it is proved that, for any constant m >= 2, the class of problems having $m$turn quantum ArthurMerlin proof systems is either equal to PSPACE or equal to the class of problems having twoturn quantum ArthurMerlin 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 ArthurMerlin Games}},
booktitle = {30th Conference on Computational Complexity (CCC 2015)},
pages = {488511},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783939897811},
ISSN = {18688969},
year = {2015},
volume = {33},
editor = {David Zuckerman},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2015/5069},
URN = {urn:nbn:de:0030drops50697},
doi = {10.4230/LIPIcs.CCC.2015.488},
annote = {Keywords: interactive proof systems, ArthurMerlin games, quantum computing, complete problems, entanglement}
}
2015
Keywords: 

interactive proof systems, ArthurMerlin games, quantum computing, complete problems, entanglement 
Seminar: 

30th Conference on Computational Complexity (CCC 2015)

Issue date: 

2015 
Date of publication: 

2015 