論文の概要: Two prover perfect zero knowledge for MIP*
- arxiv url: http://arxiv.org/abs/2404.00926v1
- Date: Mon, 1 Apr 2024 05:07:22 GMT
- ステータス: 処理完了
- システム内更新日: 2024-04-03 23:16:25.668852
- Title: Two prover perfect zero knowledge for MIP*
- Title(参考訳): MIPにおける2つの証明者完全ゼロ知識*
- Authors: Kieran Mastel, William Slofstra,
- Abstract要約: MIP*のすべての言語は、PZK-MIP*プロトコルを2つのプロプライエタリに持つことを示す。
また、通信演算子BCSプロトコルを持つ全ての言語は、2つの証明子PZK通信演算子プロトコルを持つことを示した。
- 参考スコア(独自算出の注目度): 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The recent MIP*=RE theorem of Ji, Natarajan, Vidick, Wright, and Yuen shows that the complexity class MIP* of multiprover proof systems with entangled provers contains all recursively enumerable languages. Prior work of Grilo, Slofstra, and Yuen [FOCS '19] further shows (via a technique called simulatable codes) that every language in MIP* has a perfect zero knowledge (PZK) MIP* protocol. The MIP*=RE theorem uses two-prover one-round proof systems, and hence such systems are complete for MIP*. However, the construction in Grilo, Slofstra, and Yuen uses six provers, and there is no obvious way to get perfect zero knowledge with two provers via simulatable codes. This leads to a natural question: are there two-prover PZK-MIP* protocols for all of MIP*? In this paper, we show that every language in MIP* has a two-prover one-round PZK-MIP* protocol, answering the question in the affirmative. For the proof, we use a new method based on a key consequence of the MIP*=RE theorem, which is that every MIP* protocol can be turned into a family of boolean constraint system (BCS) nonlocal games. This makes it possible to work with MIP* protocols as boolean constraint systems, and in particular allows us to use a variant of a construction due to Dwork, Feige, Kilian, Naor, and Safra [Crypto '92] which gives a classical MIP protocol for 3SAT with perfect zero knowledge. To show quantum soundness of this classical construction, we develop a toolkit for analyzing quantum soundness of reductions between BCS games, which we expect to be useful more broadly. This toolkit also applies to commuting operator strategies, and our argument shows that every language with a commuting operator BCS protocol has a two prover PZK commuting operator protocol.
- Abstract(参考訳): Ji, Natarajan, Vidick, Wright, and Yuen の最近の MIP*=RE 定理は、絡み合った証明系における複雑性クラス MIP* がすべての帰納的可算言語を含んでいることを示している。
Grilo, Slofstra, Yuen [FOCS '19] の以前の研究は、MIP* のすべての言語が完全なゼロ知識 (PZK) MIP* プロトコルを持っていることを(シミュラタブルコードと呼ばれる技術を介して)示していた。
MIP*=RE定理は、2プロの1ラウンドの証明系を使い、したがって、そのような系は MIP* に対して完備である。
しかし、Grilo, Slofstra, and Yuen における構成は6つのプローバーを用いており、シミュラブル符号を通じて2つのプローバーで完全なゼロ知識を得る明確な方法はない。
2つのプロプライエタリなPZK-MIP*プロトコルは、すべてのMIP*に対して存在するか?
本稿では,MIP*のすべての言語が2ラウンドのPZK-MIP*プロトコルを持ち,肯定的な疑問に答えることを示す。
この証明には、MIP*=RE定理の鍵となる結果に基づく新しい手法を用いる。すなわち、全てのMIP*プロトコルをブール制約系(BCS)非局所ゲーム群に変換することができる。
これにより、MIP*プロトコルをブール制約システムとして扱うことができ、特にDwork, Feige, Kilian, Naor, Safra [Crypto '92] による構成の変種を使用できます。
この古典的な構成の量子音響性を示すために、BCSゲーム間の縮小の量子音響性を分析するツールキットを開発した。
このツールキットは演算子戦略にも適用され、演算子BCSプロトコルを持つ全ての言語が2つの証明子PZK演算子プロトコルを持つことを示す。
関連論文リスト
- Perfect Zero-Knowledge PCPs for #P [5.278573457491116]
完全ゼロ知識確率的証明(PZK-PCP)を#Pのすべての言語に対して構築する。
これは、BPP以外の言語向けのPZK-PCPの最初の構成である。
論文 参考訳(メタデータ) (2024-03-18T16:36:09Z) - The Computational Advantage of MIP* Vanishes in the Presence of Noise [4.2441960155849285]
本稿では,量子多目的対話型証明システムの計算能力に及ぼす雑音の影響を特徴付ける。
プローバが任意に多くのEPR状態を共有することができ、各EPR状態が任意に小さなノイズ量の影響を受けている場合、その複雑性クラスはNEXP = MIPに含まれる。
また、このパワーの崩壊はO(1)応答サイズではなくノイズによるものであることが示され、ノイズのないEPR状態がRE = MIP*[poly, poly]のフルパワーをクラスに与えることが示される。
論文 参考訳(メタデータ) (2023-12-07T15:28:40Z) - Communication complexity of entanglement assisted multi-party
computation [11.820804392113294]
プレーヤが2ドル、ドットが2ドル、n$が1に適切な情報を伝達する必要がある場合、プレーヤが$n$のマルチパーティ計算問題を考える。
量子プロトコル(複雑性$(n-1)log n$ bits)と古典的プロトコル(複雑性$(n-1)2(log n2$)ビット)を示す。
これは、我々の量子プロトコルが古典的プロトコルよりも厳密に優れていることを示している。
論文 参考訳(メタデータ) (2023-05-08T03:10:08Z) - Side Adapter Network for Open-Vocabulary Semantic Segmentation [69.18441687386733]
本稿では,Side Adapter Network (SAN) という,事前学習された視覚言語モデルを用いたオープン語彙セマンティックセマンティックセマンティックセマンティクスのための新しいフレームワークを提案する。
サイドネットワークは凍結したCLIPモデルにアタッチされ、ひとつはマスクの提案を予測し、もうひとつは注意バイアスを予測する。
トレーニング可能なパラメータは最大で18倍,推論速度は19倍に向上した。
論文 参考訳(メタデータ) (2023-02-23T18:58:28Z) - Quantum free games [2.298932494750101]
我々は、$n$変数上の3SATのベルQMA(2)プロトコルを示し、通信総量は$tildeO(sqrtn)である。
論文 参考訳(メタデータ) (2023-02-08T20:32:24Z) - A Secure Multiparty Quantum Least Common Multiple Computation Protocol [1.4049484216292827]
ShorのQPA(quantum period-finding algorithm)に基づく最小多元計算(LCM)のためのセキュア多元計算プロトコルを提案する。
また,QPAは確率的アルゴリズムであるため,既存のセキュアなマルチパーティ量子和プロトコルに基づく一票制投票プロトコルを提案する。
論文 参考訳(メタデータ) (2022-10-15T02:27:18Z) - Quantum Depth in the Random Oracle Model [57.663890114335736]
浅量子回路の計算能力と古典計算の組合せを包括的に評価する。
いくつかの問題に対して、1つの浅い量子回路で適応的な測定を行う能力は、適応的な測定をせずに多くの浅い量子回路を実行する能力よりも有用である。
論文 参考訳(メタデータ) (2022-10-12T17:54:02Z) - Towards Semantic Communication Protocols: A Probabilistic Logic
Perspective [69.68769942563812]
我々は,NPMを確率論理型言語ProbLogで記述された解釈可能なシンボルグラフに変換することによって構築された意味プロトコルモデル(SPM)を提案する。
その解釈性とメモリ効率を利用して、衝突回避のためのSPM再構成などのいくつかの応用を実演する。
論文 参考訳(メタデータ) (2022-07-08T14:19:36Z) - Resource Optimisation of Coherently Controlled Quantum Computations with
the PBS-calculus [55.2480439325792]
量子計算のコヒーレント制御は、いくつかの量子プロトコルやアルゴリズムを改善するために使用できる。
我々は、量子光学にインスパイアされたコヒーレント制御のためのグラフィカル言語PBS計算を洗練する。
論文 参考訳(メタデータ) (2022-02-10T18:59:52Z) - Computation-aided classical-quantum multiple access to boost network
communication speeds [61.12008553173672]
我々は,2次元のcq-MACに対する計算特性を持つ符号の達成可能な量子通信速度を定量化する。
従来の設計では実現不可能な通信速度(シングルユーザ容量)を最大化できることを示す。
論文 参考訳(メタデータ) (2021-05-30T11:19:47Z) - PBS-Calculus: A Graphical Language for Coherent Control of Quantum
Computations [77.34726150561087]
本稿では,量子演算のコヒーレント制御を含む量子計算を表現・推論するためにPBS計算を導入する。
我々はこの言語に方程式理論を加え、それが健全で完備であることが証明された。
我々は、制御された置換の実装やループのアンロールのようなアプリケーションを考える。
論文 参考訳(メタデータ) (2020-02-21T16:15:58Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。