Fugu-MT 論文翻訳(概要): Two prover perfect zero knowledge for MIP*

論文の概要: Two prover perfect zero knowledge for MIP*

arxiv url: http://arxiv.org/abs/2404.00926v2
Date: Mon, 29 Jul 2024 21:28:16 GMT
ステータス: 処理完了
システム内更新日: 2024-07-31 21:55:07.813900
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演算子プロトコルを持つことを示す。

関連論文リスト

SSIP: automated surgery with quantum LDPC codes [55.2480439325792]
クビットCSSコード間の手術を自動化するための,オープンソースの軽量PythonパッケージであるSSIP(Identifying Pushouts)による安全手術について述べる。ボンネットの下では、鎖複体の圏における普遍構成によって支配される$mathbbF$上の線型代数を実行する。高い符号距離を犠牲にすることなく,手術によって様々な論理的測定を安価に行うことができることを示す。
論文参考訳（メタデータ） (2024-07-12T16:50:01Z)
The Round Complexity of Proofs in the Bounded Quantum Storage Model [0.7366405857677227]
有界量子記憶モデル(BQSM)におけるプロトコルのラウンド圧縮に関する研究このモデルでは、悪意のあるパーティは有界量子メモリを持ち、プロトコルに送信される全てのキュービットを格納できない。標準手法では, NIZKはBQS相手に対する平易なモデルではありそうにないことを示す。
論文参考訳（メタデータ） (2024-05-28T15:24:48Z)
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.041530553470258]
エンタングルメント MIP* を持つ量子マルチプロペラ対話型証明システムは、古典的な MIP よりもはるかに強力である。 QinとYao '21と'23の最近の研究は、プローサの共有状態がノイズを含む場合、この利点は著しく減少することを示した。提案手法では,各EPR状態が任意に小さなノイズ量で影響を受ける場合,その複雑性クラスはNEXP = MIPと等価であることを示す。
論文参考訳（メタデータ） (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)
Quantum free games [2.298932494750101]
我々は、$n$変数上の3SATのベルQMA(2)プロトコルを示し、通信総量は$tildeO(sqrtn)である。
論文参考訳（メタデータ） (2023-02-08T20:32:24Z)
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)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。