論文の概要: Distributed Quantum Interactive Proofs
- arxiv url: http://arxiv.org/abs/2210.01390v1
- Date: Tue, 4 Oct 2022 05:38:31 GMT
- ステータス: 処理完了
- システム内更新日: 2023-01-23 22:12:23.375432
- Title: Distributed Quantum Interactive Proofs
- Title（参考訳）: 分散量子インタラクティブな証明
- Authors: Fran\c{c}ois Le Gall, Masayuki Miyamoto, Harumichi Nishimura
- Abstract要約: 分散対話型証明では、$n$ノードネットワーク$G$のノードは、短いメッセージ(証明書と呼ばれる)を強力な証明器で交換することができる。
目標は、入力($G$自身を含む)が何らかの言語に属しているかどうかを判断し、対話のターンがほとんどなく、ノードと証明者の間でできる限りビットを交換することである。
証明は量子ビットとなり、ネットワークのノードは量子計算を行うことができる。
- 参考スコア（独自算出の注目度）: 0.5156484100374058
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: 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
first result of this paper shows that by using quantum distributed interactive
proofs, the number of interactions can be significantly reduced. More
precisely, our 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 \emph{classical} technique is currently known, our
result gives evidence of the power of quantum computation in the setting of
distributed interactive proofs as well.
- Abstract（参考訳）: 分散対話型証明の研究は、kol, oshman, saxena [podc 2018] によって、分散決定機構(証明ラベル方式など)の一般化として開始され、近年多くの注目を集めている。
分散インタラクティブな証明では、$n$ノードネットワークのノード$g$は、強力な証明者と短いメッセージ(証明書と呼ばれる)を交換できる。
目標は、入力($G$自身を含む)が何らかの言語に属しているかどうかを判断し、対話のターンがほとんどなく、ノードと証明者の間でできる限りビットを交換することである。
非インタラクティブな分散証明と比較して, 一定数の相互作用で証明書のサイズを劇的に削減できることを示す結果がいくつかある。
本稿では,分散対話型証明の量子対について紹介する:証明書は量子ビットとなり,ネットワークのノードは量子計算を行うことができる。
本研究の最初の結果は,量子分散対話型証明を用いることで,対話の回数を大幅に削減できることを示す。
より正確には、任意の定数~$k$に対して、$k$ターン古典(すなわち、$f(n)$-bit証明書サイズを持つ分散対話プロトコルによって決定できる言語のクラスは、$O(f(n)$-bit証明書サイズを持つ5$ターン分散量子対話プロトコルによって決定できる言語のクラスに含まれることを示す。
また,共有ランダム性の利用を許せば,ターン数を3ターンに減らすことができることを示した。
この結果から, 分散対話型証明の設定において, 量子計算のパワーを証明できる可能性が示唆された。
関連論文リスト
- Single-Round Proofs of Quantumness from Knowledge Assumptions [41.94295877935867]
量子性の証明は、効率的な量子コンピュータが通過できる、効率よく検証可能な対話型テストである。
既存のシングルラウンドプロトコルは大きな量子回路を必要とするが、マルチラウンドプロトコルはより小さな回路を使用するが、実験的な中間回路測定を必要とする。
我々は、既存の知識仮定に基づいて、量子性の効率的なシングルラウンド証明を構築した。
論文 参考訳（メタデータ） (2024-05-24T17:33:10Z) - The Power of Unentangled Quantum Proofs with Non-negative Amplitudes [55.90795112399611]
非負の振幅を持つ非絡み合った量子証明のパワー、つまり $textQMA+(2)$ を表すクラスについて研究する。
特に,小集合拡張,ユニークなゲーム,PCP検証のためのグローバルプロトコルを設計する。
QMA(2) が $textQMA+(2)$ に等しいことを示す。
論文 参考訳（メタデータ） (2024-02-29T01:35:46Z) - One Clean Qubit Suffices for Quantum Communication Advantage [3.729242965449096]
1つの量子ビットが純粋な状態にあり、他の全ての量子ビットが最大混合される量子通信の1つのクリーン量子ビットモデルについて検討する。
我々の証明は、Ellis, Kindler, Lifshitz, Minzerが最近導入した超収縮性不等式に基づいている。
論文 参考訳（メタデータ） (2023-10-03T19:58:08Z) - Scalable Determination of Multipartite Entanglement in Quantum Networks [1.248349449820389]
絡み合った終端ノードからなる量子ネットワークは、非並列な量子インターネットアプリケーションに対する古典的相関よりも強く機能する。
我々は、信頼できない恒星ネットワークにおける量子ネットワークの忠実度と真の$N$-nodeの絡み合いを決定するには、たったの$N+1$の設定が必要であることを示した。
論文 参考訳（メタデータ） (2023-03-31T02:22:42Z) - Simple Tests of Quantumness Also Certify Qubits [69.96668065491183]
量子性の検定は、古典的検証者が証明者が古典的でないことを(のみ)証明できるプロトコルである。
我々は、あるテンプレートに従う量子性のテストを行い、(Kalai et al., 2022)のような最近の提案を捉えた。
すなわち、同じプロトコルは、証明可能なランダム性や古典的な量子計算のデリゲートといったアプリケーションの中心にあるビルディングブロックであるqubitの認定に使用できる。
論文 参考訳（メタデータ） (2023-03-02T14:18:17Z) - Quantum Depth in the Random Oracle Model [57.663890114335736]
浅量子回路の計算能力と古典計算の組合せを包括的に評価する。
いくつかの問題に対して、1つの浅い量子回路で適応的な測定を行う能力は、適応的な測定をせずに多くの浅い量子回路を実行する能力よりも有用である。
論文 参考訳（メタデータ） (2022-10-12T17:54:02Z) - Efficient Bipartite Entanglement Detection Scheme with a Quantum
Adversarial Solver [89.80359585967642]
パラメータ化量子回路で完了した2プレーヤゼロサムゲームとして,両部絡み検出を再構成する。
このプロトコルを線形光ネットワーク上で実験的に実装し、5量子量子純状態と2量子量子混合状態の両部絡み検出に有効であることを示す。
論文 参考訳（メタデータ） (2022-03-15T09:46:45Z) - A direct product theorem for quantum communication complexity with
applications to device-independent cryptography [6.891238879512672]
我々は、$l$プレーヤの入力集合にまたがる分布である$p$に対して、任意の絡み合い支援量子通信プロトコルの成功確率は、$n$で指数関数的に低下することを示した。
また、デバイスが情報を漏らさないという仮定なしに、デバイス非依存(DI)量子暗号が可能であることも示している。
論文 参考訳（メタデータ） (2021-06-08T12:52:10Z) - Quantum Communication Complexity of Distribution Testing [114.31181206328276]
2人のプレーヤーが1つのディストリビューションから$t$のサンプルを受け取ります。
目標は、2つの分布が等しいか、または$epsilon$-far であるかどうかを決定することである。
この問題の量子通信複雑性が$tildeO$(tepsilon2)$ qubitsであることを示す。
論文 参考訳（メタデータ） (2020-06-26T09:05:58Z) - Semidefinite tests for quantum network topologies [0.9176056742068814]
量子ネットワークは、長距離通信、量子暗号、クロック同期、分散量子コンピューティングにおいて重要な役割を果たしている。
与えられた量子ネットワークがどの相関を生じさせるのかという問題は、いまだに未解決のままである。
従来は古典的ケースで導かれていた観測可能共分散の制約が量子ネットワークにも適用可能であることを示す。
論文 参考訳（メタデータ） (2020-02-13T22:36:46Z) - Genuine Network Multipartite Entanglement [62.997667081978825]
両部エンタングルメントを分散できるソースは、それ自体、$k$の本当の$k$-partiteエンタングルドステートを、任意の$k$に対して生成できる、と我々は主張する。
我々は、真のネットワーク絡みの解析的および数値的な証人を提供し、過去の多くの量子実験を、この機能の実証として再解釈する。
論文 参考訳（メタデータ） (2020-02-07T13:26:00Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。