論文の概要: Tight Limits on Nonlocality from Nontrivial Communication Complexity;
a.k.a. Reliable Computation with Asymmetric Gate Noise
- arxiv url: http://arxiv.org/abs/1809.09748v5
- Date: Mon, 1 May 2023 18:12:06 GMT
- ステータス: 処理完了
- システム内更新日: 2023-05-03 18:49:09.099310
- Title: Tight Limits on Nonlocality from Nontrivial Communication Complexity;
a.k.a. Reliable Computation with Asymmetric Gate Noise
- Title（参考訳）: 非自明な通信複雑性からの非局所性の厳密な限界 : 非対称ゲートノイズを用いた信頼性計算
- Authors: Noah Shutty, Mary Wootters, Patrick Hayden
- Abstract要約: ある種の超量子非局所相関の存在が通信複雑性の崩壊を引き起こすことは、長い間知られている。
最大勝利確率が量子値を超える任意の物理理論において、通信複雑性が崩壊することを示す。
我々は、0.91の結果が証明戦略の大規模なクラスで可能な限り最良のものであることを示す。
- 参考スコア（独自算出の注目度）: 19.970633213740363
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: It has long been known that the existence of certain superquantum nonlocal
correlations would cause communication complexity to collapse. The absurdity of
a world in which any nonlocal binary function could be evaluated with a
constant amount of communication in turn provides a tantalizing way to
distinguish quantum mechanics from incorrect theories of physics; the statement
"communication complexity is nontrivial" has even been conjectured to be a
concise information-theoretic axiom for characterizing quantum mechanics. We
directly address the viability of that perspective with two results. First, we
exhibit a nonlocal game such that communication complexity collapses in any
physical theory whose maximal winning probability exceeds the quantum value.
Second, we consider the venerable CHSH game that initiated this line of
inquiry. In that case, the quantum value is about 0.85 but it is known that a
winning probability of approximately 0.91 would collapse communication
complexity. We provide evidence that the 0.91 result is the best possible using
a large class of proof strategies, suggesting that the communication complexity
axiom is insufficient for characterizing CHSH correlations. Both results build
on new insights about reliable classical computation. The first exploits our
formalization of an equivalence between amplification and reliable computation,
while the second follows from an upper bound on the threshold for reliable
computation with formulas of noisy XOR and AND gates.
- Abstract（参考訳）: ある種の超量子非局所相関の存在が通信複雑性の崩壊を引き起こすことは、長い間知られている。
任意の非局所二元関数が一定の量の通信量で評価できる世界の愚かさは、量子力学と不正確な物理理論を区別するためのタンタライズな方法を与える。
我々は2つの結果によって、その視点の存続可能性に直接対処する。
まず, 最大当選確率が量子値を超える物理理論において, 通信複雑性が崩壊するような非局所ゲームを示す。
第2に,この一連の調査を開始したCHSHゲームについて考察する。
この場合、量子値はおよそ0.85であるが、約0.91の勝利確率が通信複雑性を崩壊させることが知られている。
以上の結果から,CHSH相関を特徴づけるには通信複雑性公理が不十分であることが示唆された。
どちらの結果も、信頼性の高い古典計算に関する新たな洞察に基づいている。
第一は増幅と信頼度計算の等価性の形式化を,第二は雑音xorとゲートの式を用いた信頼度計算のしきい値の上界から導出する。
関連論文リスト
- Taming Quantum Time Complexity [50.10645865330582]
時間複雑性の設定において、正確さと遠心性の両方を達成する方法を示します。
我々は、トランスデューサと呼ばれるものに基づく量子アルゴリズムの設計に新しいアプローチを採用する。
論文 参考訳（メタデータ） (2023-11-27T14:45:19Z) - Communication Complexity of Common Randomness Generation with Isotropic
States [5.312109949216557]
本稿は、一方通行古典通信と一方通行量子通信の2つの通信モデルについて考察する。
古典的通信の場合、量子等方性状態はノイズのある古典的相関に勝らないことを示す。
量子通信の場合、量子等方性状態の超高密度符号化を用いることで、共通乱数率を増大させることができることを示す。
論文 参考訳（メタデータ） (2023-11-08T14:48:15Z) - Unbounded Quantum Advantage in One-Way Strong Communication Complexity
of a Distributed Clique Labelling Relation [0.19090202146054183]
分散クリフラベル問題により誘導される関係のクラスに対する一方向ゼロエラー古典的および量子的通信複雑性について検討する。
ここでは、プレイヤーがリソースを共有しない場合に考慮された特定の関係のクラスについて、任意のグラフに対してCCRタスクに量子的優位性はないことを示す。
我々は、このタスクの半デバイス非依存のディメンション目撃への応用と、ミューチュアルアンバイアスベースの検出について強調する。
論文 参考訳（メタデータ） (2023-05-17T16:58:05Z) - Improved Quantum Algorithms for Fidelity Estimation [77.34726150561087]
証明可能な性能保証を伴う忠実度推定のための新しい,効率的な量子アルゴリズムを開発した。
我々のアルゴリズムは量子特異値変換のような高度な量子線型代数技術を用いる。
任意の非自明な定数加算精度に対する忠実度推定は一般に困難であることを示す。
論文 参考訳（メタデータ） (2022-03-30T02:02:16Z) - Resource theory of quantum uncomplexity [0.5872014229110214]
ブラウンとススキンドの予想を証明し、非複素性の資源理論を定義できると証明する。
この研究は、量子情報理論から資源理論ツールキットの多体複雑性を解き放つ。
論文 参考訳（メタデータ） (2021-10-21T18:00:01Z) - Depth-efficient proofs of quantumness [77.34726150561087]
量子性の証明は、古典的検証器が信頼できない証明器の量子的利点を効率的に証明できる挑戦応答プロトコルの一種である。
本稿では、証明者が量子回路を一定深度でしか実行できない量子性構成の証明を2つ与える。
論文 参考訳（メタデータ） (2021-07-05T17:45:41Z) - Quantum communication complexity beyond Bell nonlocality [87.70068711362255]
効率的な分散コンピューティングは、リソース要求タスクを解決するためのスケーラブルな戦略を提供する。
量子リソースはこのタスクに適しており、古典的手法よりも優れた明確な戦略を提供する。
我々は,ベルのような不等式に,新たなコミュニケーション複雑性タスクのクラスを関連付けることができることを証明した。
論文 参考訳（メタデータ） (2021-06-11T18:00:09Z) - The Second Law of Quantum Complexity and the Entanglement Wormhole [0.0]
量子複雑性は、2つの量子状態の間のフビニ計量の代替尺度として生じる。
これは、1つの状態からもう1つの状態へ変換できる最小の単項演算子として定義される。
論文 参考訳（メタデータ） (2021-04-11T15:23:47Z) - On Query-to-Communication Lifting for Adversary Bounds [14.567067583556714]
古典的対向境界は,一定サイズのガジェットを用いて,ランダム化通信の複雑性を低く抑えることを示す。
また、正重量子対角線が近似次数の2乗よりも大きいことも示している。
論文 参考訳（メタデータ） (2020-12-07T02:10:37Z) - Secure Two-Party Quantum Computation Over Classical Channels [63.97763079214294]
古典的アリス(Alice)と量子的ボブ(Quantum Bob)が古典的なチャネルを通してのみ通信できるような設定を考える。
悪質な量子逆数の場合,ブラックボックスシミュレーションを用いた2次元量子関数を実現することは,一般に不可能であることを示す。
我々は、QMA関係Rの古典的量子知識(PoQK)プロトコルを入力として、古典的当事者によって検証可能なRのゼロ知識PoQKを出力するコンパイラを提供する。
論文 参考訳（メタデータ） (2020-10-15T17:55:31Z) - Fault-tolerant Coding for Quantum Communication [71.206200318454]
ノイズチャネルの多くの用途でメッセージを確実に送信するために、回路をエンコードしてデコードする。
すべての量子チャネル$T$とすべての$eps>0$に対して、以下に示すゲートエラー確率のしきい値$p(epsilon,T)$が存在し、$C-epsilon$より大きいレートはフォールトトレラント的に達成可能である。
我々の結果は、遠方の量子コンピュータが高レベルのノイズの下で通信する必要があるような、大きな距離での通信やオンチップでの通信に関係している。
論文 参考訳（メタデータ） (2020-09-15T15:10:50Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。