{"metadata":{"_oai":{"id":"oai:ipsj.ixsq.nii.ac.jp:00218779","sets":["1164:10193:10905:10966"]},"path":["10966"],"owner":"44499","recid":"218779","title":["分散量子対話型証明"],"pubdate":{"attribute_name":"公開日","attribute_value":"2022-06-30"},"_buckets":{"deposit":"4ff317ac-8145-4ada-b743-5a8330b0545e"},"_deposit":{"id":"218779","pid":{"type":"depid","value":"218779","revision_id":0},"owners":[44499],"status":"published","created_by":44499},"item_title":"分散量子対話型証明","author_link":["569677","569675","569676"],"item_titles":{"attribute_name":"タイトル","attribute_value_mlt":[{"subitem_title":"分散量子対話型証明"},{"subitem_title":"Distributed Quantum Interactive Proofs","subitem_title_language":"en"}]},"item_type_id":"4","publish_date":"2022-06-30","item_4_text_3":{"attribute_name":"著者所属","attribute_value_mlt":[{"subitem_text_value":"名古屋大学"},{"subitem_text_value":"名古屋大学"},{"subitem_text_value":"名古屋大学"}]},"item_4_text_4":{"attribute_name":"著者所属(英)","attribute_value_mlt":[{"subitem_text_value":"Nagoya University","subitem_text_language":"en"},{"subitem_text_value":"Nagoya University","subitem_text_language":"en"},{"subitem_text_value":"Nagoya University","subitem_text_language":"en"}]},"item_language":{"attribute_name":"言語","attribute_value_mlt":[{"subitem_language":"jpn"}]},"item_publisher":{"attribute_name":"出版者","attribute_value_mlt":[{"subitem_publisher":"情報処理学会","subitem_publisher_language":"ja"}]},"publish_status":"0","weko_shared_id":-1,"item_file_price":{"attribute_name":"Billing file","attribute_type":"file","attribute_value_mlt":[{"url":{"url":"https://ipsj.ixsq.nii.ac.jp/record/218779/files/IPSJ-QS22006020.pdf","label":"IPSJ-QS22006020.pdf"},"date":[{"dateType":"Available","dateValue":"2024-06-30"}],"format":"application/pdf","billing":["billing_file"],"filename":"IPSJ-QS22006020.pdf","filesize":[{"value":"600.3 kB"}],"mimetype":"application/pdf","priceinfo":[{"tax":["include_tax"],"price":"0","billingrole":"5"},{"tax":["include_tax"],"price":"0","billingrole":"6"},{"tax":["include_tax"],"price":"0","billingrole":"53"},{"tax":["include_tax"],"price":"0","billingrole":"44"}],"accessrole":"open_date","version_id":"91deb05e-1de6-4fdf-b23f-37f33787f1f0","displaytype":"detail","licensetype":"license_note","license_note":"Copyright (c) 2022 by the Information Processing Society of Japan"}]},"item_4_creator_5":{"attribute_name":"著者名","attribute_type":"creator","attribute_value_mlt":[{"creatorNames":[{"creatorName":"ルガル, フランソワ"}],"nameIdentifiers":[{}]},{"creatorNames":[{"creatorName":"宮本, 昌幸"}],"nameIdentifiers":[{}]},{"creatorNames":[{"creatorName":"西村, 治道"}],"nameIdentifiers":[{}]}]},"item_4_source_id_9":{"attribute_name":"書誌レコードID","attribute_value_mlt":[{"subitem_source_identifier":"AA12894105","subitem_source_identifier_type":"NCID"}]},"item_4_textarea_12":{"attribute_name":"Notice","attribute_value_mlt":[{"subitem_textarea_value":"SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc."}]},"item_resource_type":{"attribute_name":"資源タイプ","attribute_value_mlt":[{"resourceuri":"http://purl.org/coar/resource_type/c_18gh","resourcetype":"technical report"}]},"item_4_source_id_11":{"attribute_name":"ISSN","attribute_value_mlt":[{"subitem_source_identifier":"2435-6492","subitem_source_identifier_type":"ISSN"}]},"item_4_description_7":{"attribute_name":"論文抄録","attribute_value_mlt":[{"subitem_description":"分散対話型証明は分散検証の枠組みの拡張として Kol，Oshman，Saxena によって 2018 年に定義され注目を集めている分野である．分散対話型証明において，n 頂点グラフ G の各頂点は証明者から短い証明を受け取り，それを用いて入力がある性質を満たすかどうかを判定する．非対話型である分散検証と比較して，分散対話型証明の場合は証明のサイズを劇的に小さくすることができるような問題が複数存在することが知られている．本研究では分散対話型証明の量子版，つまりグラフの頂点は証明者から量子状態を受け取り，量子計算を行うことができるようなモデルを導入する．本研究の主結果は，任意の定数 k に対して，k ターンの分散対話型証明で各ターンに f(n) ビットの証明を受け取るようなプロトコルは 5 ターンの分散量子対話型証明で各ターンに O(f(n)) 量子ビットの証明を受け取るようなプロトコルに変換できるということである．さらに，shared randomness を許せば 3 ターンにすることができることも示す．これらの主結果の系として，分散対話型証明の先行研究において研究されているいくつかの問題に対する 5 ターン及び 3 ターンの分散量子対話型証明のプロトコルを与えることができる．","subitem_description_type":"Other"}]},"item_4_description_8":{"attribute_name":"論文抄録(英)","attribute_value_mlt":[{"subitem_description":"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].","subitem_description_type":"Other"}]},"item_4_biblio_info_10":{"attribute_name":"書誌情報","attribute_value_mlt":[{"bibliographicPageEnd":"1","bibliographic_titles":[{"bibliographic_title":"量子ソフトウェア（QS）"}],"bibliographicPageStart":"1","bibliographicIssueDates":{"bibliographicIssueDate":"2022-06-30","bibliographicIssueDateType":"Issued"},"bibliographicIssueNumber":"20","bibliographicVolumeNumber":"2022-QS-6"}]},"relation_version_is_last":true,"weko_creator_id":"44499"},"id":218779,"updated":"2025-01-19T15:02:15.896147+00:00","links":{},"created":"2025-01-19T01:19:07.608617+00:00"}