分散量子対話型証明

• Item type: SIG Technical Reports(1)
• 公開日: 2022-06-30
• タイトル: 分散量子対話型証明
• タイトル / 言語: en
• タイトル: Distributed Quantum Interactive Proofs
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 名古屋大学
• 著者所属: 名古屋大学
• 著者所属: 名古屋大学
• 著者所属(英): en
• 著者所属(英): Nagoya University
• 著者所属(英): en
• 著者所属(英): Nagoya University
• 著者所属(英): en
• 著者所属(英): Nagoya University
• 著者名: ルガル, フランソワ; 宮本, 昌幸; 西村, 治道
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 分散対話型証明は分散検証の枠組みの拡張として Kol，Oshman，Saxena によって 2018 年に定義され注目を集めている分野である．分散対話型証明において，n 頂点グラフ G の各頂点は証明者から短い証明を受け取り，それを用いて入力がある性質を満たすかどうかを判定する．非対話型である分散検証と比較して，分散対話型証明の場合は証明のサイズを劇的に小さくすることができるような問題が複数存在することが知られている．本研究では分散対話型証明の量子版，つまりグラフの頂点は証明者から量子状態を受け取り，量子計算を行うことができるようなモデルを導入する．本研究の主結果は，任意の定数 k に対して，k ターンの分散対話型証明で各ターンに f(n) ビットの証明を受け取るようなプロトコルは 5 ターンの分散量子対話型証明で各ターンに O(f(n)) 量子ビットの証明を受け取るようなプロトコルに変換できるということである．さらに，shared randomness を許せば 3 ターンにすることができることも示す．これらの主結果の系として，分散対話型証明の先行研究において研究されているいくつかの問題に対する 5 ターン及び 3 ターンの分散量子対話型証明のプロトコルを与えることができる．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: The study of distributed interactive proofs was initiated by Kol, Oshman, and Saxena [PODC 2018] as a generalization of distributed decision mechanisms (proof-labeling schemes, etc.), and has received a lot of attention in recent years. In distributed interactive proofs, the nodes of an n-node network G can exchange short messages (called certificates) with a powerful prover. The goal is to decide if the input (including G itself) belongs to some language, with as few turns of interaction and as few bits exchanged between nodes and the prover as possible. There are several results showing that the size of certificates can be reduced drastically with a constant number of interactions compared to non-interactive distributed proofs. In this paper, we introduce the quantum counterpart of distributed interactive proofs: certificates can now be quantum bits, and the nodes of the network can perform quantum computation. The main result of this paper shows that by using quantum distributed interactive proofs, the number of interactions can be significantly reduced. More precisely, our main result shows that for any constant k, the class of languages that can be decided by a k-turn classical (i.e., non-quantum) distributed interactive protocol with f(n)-bit certificate size is contained in the class of languages that can be decided by a 5-turn distributed quantum interactive protocol with O(f(n))-bit certificate size. We also show that if we allow to use shared randomness, the number of turns can be reduced to 3-turn. Since no similar turn-reduction classical technique is currently known, our result gives evidence of the power of quantum computation in the setting of distributed interactive proofs as well. As a corollary of our results, we show that there exist 5-turn/3-turn distributed quantum interactive protocols with small certificate size for problems that have been considered in prior works on distributed interactive proofs [Kol, Oshman, and Saxena, PODC 2018][Naor, Parter, and Yogev, SODA 2020].
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AA12894105
• 書誌情報: 量子ソフトウェア（QS）; 巻 2022-QS-6, 号 20, p. 1-1, 発行日 2022-06-30
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 2435-6492
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会