論文の概要: Certificate Games and Consequences for the Classical Adversary Bound

• arxiv url: http://arxiv.org/abs/2211.03396v3
• Date: Mon, 10 Mar 2025 20:14:40 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-03-12 22:35:51.086971
• Title: Certificate Games and Consequences for the Classical Adversary Bound
• Title（参考訳）: 古典的逆境の認定ゲームとコンシークエンス
• Authors: Sourav Chakraborty, Anna Gál, Mika Göös, Sophie Laplante, Rajat Mittal, Anupa Sunny,
• Abstract要約: 証明ゲームの4つのバージョン、すなわち、プライベートコイン、パブリックコイン、共有エンタングルメント、および非署名ゲームについて検討する。 量子測度は古典的クエリモデルと量子的クエリモデルの間に興味深い、そして驚くべき違いを明らかにしている。
• 参考スコア（独自算出の注目度）: 3.11717505289722
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We introduce and study Certificate Game complexity, a measure of complexity based on the probability of winning a game where two players are given inputs with different function values and are asked to output some index $i$ such that $x_i\neq y_i$, in a zero-communication setting. We study four versions of certificate games, namely private coin, public coin, shared entanglement and non-signaling games. The public-coin variant of certificate games gives a new characterization of the classical adversary bound, a lower bound on randomized query complexity which was introduced as a classical version of the quantum (non-negative) quantum adversary bound. We show that complexity in the public coin model (therefore also the classical adversary) is bounded above by certificate complexity, as well as by expectational certificate complexity and sabotage complexity. On the other hand, it is bounded below by fractional and randomized certificate complexity. The quantum measure reveals an interesting and surprising difference between classical and quantum query models: the quantum certificate game complexity can be quadratically larger than quantum query complexity. We use non-signaling, a notion from quantum information, to give a lower bound of $n$ on the quantum certificate game complexity of the OR function, whose quantum query complexity is $\Theta(\sqrt{n})$, then go on to show that this ``non-signaling bottleneck'' applies to all functions with high sensitivity, block sensitivity, fractional block sensitivity, as well as classical adversary. This implies the collapse of all models of certificate games, except private randomness, to the classical adversary bound. We consider the single-bit version of certificate games, where the inputs of the two players are restricted to having Hamming distance 1, and give a new characterization of sensitivity and spectral sensitivity.
• Abstract（参考訳）: 我々は,2人のプレーヤーに異なる関数値の入力が与えられ,x_i\neq y_i$ のような指数 $i$ をゼロコミュニケーション設定で出力するゲームに勝つ確率に基づく複雑性の尺度 Certificate Game complexity を紹介し,研究する。 証明ゲームの4つのバージョン、すなわち、プライベートコイン、パブリックコイン、共有エンタングルメント、および非署名ゲームについて検討する。 証明ゲームの公開コイン変種は、量子(非負)量子逆境界の古典的なバージョンとして導入されたランダム化クエリ複雑性の下位境界である古典的逆境界の新たな特徴を与える。 公的なコインモデルの複雑さ(前述した古典的逆境)は、証明書の複雑さと期待された証明書の複雑さと破壊の複雑さによって境界づけられていることが示される。 一方、以下は分数的およびランダム化証明書の複雑さによって制限される。 この量子測度は、古典的および量子的クエリモデルの間の興味深い、驚くべき違いを明らかにしている。 量子情報の概念である非符号化(non-signaling)を用いて、OR関数の量子証明ゲーム(quantum certificate game)の複雑さに$n$の低いバウンダリを与える。その量子的クエリ複雑性は$\Theta(\sqrt{n})$である。 これは、私的ランダム性を除いて、証明書ゲームの全モデルが古典的な逆境に崩壊することを意味する。 両プレイヤーの入力をハミング距離1に制限したシングルビット版証明書ゲームについて検討し、感度とスペクトル感度の新たな特徴を与える。

関連論文リスト

• Complexity Theory for Quantum Promise Problems [5.049812996253858]
  p/mBQP, p/mQ(C)MA, $textp/mQSZK_texthv$, p/mQIP, p/mBQP/qpoly, p/mBQP/poly, p/mPSPACEの構造結果を示す。 驚いたことに、我々の発見は、彼らの古典的な類推から分岐する関係を明らかにした。 応用においては、量子暗号、量子特性試験、およびユニタリ合成における興味深い問題に対処する。
  論文  参考訳（メタデータ） (2024-11-06T07:29:52Z)
• Quantum complexity and localization in random quantum circuits [0.0]
  ランダム量子回路の複雑性を計測・無測定で研究する。 測定なしの$N$ qubitsの場合、飽和値は$2N-1$、飽和時間は$2N$となる。 複雑性はアンダーソンの局所化と多体局在の新しいプローブとして機能する。
  論文  参考訳（メタデータ） (2024-09-05T16:10:54Z)
• A bound on the quantum value of all compiled nonlocal games [49.32403970784162]
  暗号コンパイラは、任意の非ローカルゲームを単一の計算バウンド証明器で対話的プロトコルに変換する。 我々は、コンパイルされた2人プレイヤの非ローカルゲームに対して量子音響結果を確立する。
  論文  参考訳（メタデータ） (2024-08-13T08:11:56Z)
• The Power of Unentangled Quantum Proofs with Non-negative Amplitudes [55.90795112399611]
  非負の振幅を持つ非絡み合った量子証明のパワー、つまり $textQMA+(2)$ を表すクラスについて研究する。 特に,小集合拡張,ユニークなゲーム,PCP検証のためのグローバルプロトコルを設計する。 QMA(2) が $textQMA+(2)$ に等しいことを示す。
  論文  参考訳（メタデータ） (2024-02-29T01:35:46Z)
• Taming Quantum Time Complexity [45.867051459785976]
  時間複雑性の設定において、正確さと遠心性の両方を達成する方法を示します。 我々は、トランスデューサと呼ばれるものに基づく量子アルゴリズムの設計に新しいアプローチを採用する。
  論文  参考訳（メタデータ） (2023-11-27T14:45:19Z)
• Photonic implementation of the quantum Morra game [69.65384453064829]
  本研究は,古典ゲームを特殊なケースとして含めることにより,従来の研究を基盤とした2プレーヤ量子モラゲームの忠実な翻訳について研究する。 本稿では、アリスが古典ゲームのバランスを崩し、勝利の優位性を持つ量子状態におけるゲームの自然な変形を提案する。 量子情報と通信の研究における量子モラゲームの可能性について論じる。
  論文  参考訳（メタデータ） (2023-11-14T19:41:50Z)
• Learning quantum states and unitaries of bounded gate complexity [2.034135396070497]
  我々は、G$2量子ビットゲートを持つ量子回路によって生成された状態を微量なトレース距離に学習するには、G$で線形にスケールするサンプル複雑性が必要であることを証明した。 また、$G$ゲートによって生成されるユニタリを、小さな平均ケースエラーに対して線形に$G$で学習するのに最適なクエリの複雑さが証明される。
  論文  参考訳（メタデータ） (2023-10-30T18:00:03Z)
• Information-Computation Tradeoffs for Learning Margin Halfspaces with Random Classification Noise [50.64137465792738]
  ランダム分類ノイズを用いたPAC$gamma$-marginハーフスペースの問題について検討する。 我々は、問題のサンプル複雑性と計算効率の良いアルゴリズムのサンプル複雑性との間に固有のギャップを示唆する情報計算トレードオフを確立する。
  論文  参考訳（メタデータ） (2023-06-28T16:33:39Z)
• Majorization-based benchmark of the complexity of quantum processors [105.54048699217668]
  我々は、様々な量子プロセッサの動作を数値的にシミュレートし、特徴付ける。 我々は,各デバイスの性能をベンチマークラインと比較することにより,量子複雑性を同定し,評価する。 我々は、回路の出力状態が平均して高い純度である限り、偏化ベースのベンチマークが成り立つことを発見した。
  論文  参考訳（メタデータ） (2023-04-10T23:01:10Z)
• Simple Tests of Quantumness Also Certify Qubits [69.96668065491183]
  量子性の検定は、古典的検証者が証明者が古典的でないことを(のみ)証明できるプロトコルである。 我々は、あるテンプレートに従う量子性のテストを行い、(Kalai et al., 2022)のような最近の提案を捉えた。 すなわち、同じプロトコルは、証明可能なランダム性や古典的な量子計算のデリゲートといったアプリケーションの中心にあるビルディングブロックであるqubitの認定に使用できる。
  論文  参考訳（メタデータ） (2023-03-02T14:18:17Z)
• The NISQ Complexity of Collision Finding [2.9405711598281536]
  現代の暗号における基本的なプリミティブである衝突耐性ハッシュは、同じハッシュ値を生成する入力を効率的に見つける方法がないことを保証している。 現在、量子敵はNISQのパワーを備えたフルスケールのコンピュータを必要とする。 本稿では, NISQアルゴリズムの3つの異なるモデルについて検討する。
  論文  参考訳（メタデータ） (2022-11-23T13:55:28Z)
• Verifiable Quantum Advantage without Structure [15.701707809084716]
  ランダムなオラクルをSHA2のような具体的な暗号ハッシュ関数に置き換える。 以上の結果の最小限のインスタンス化が可能である。
  論文  参考訳（メタデータ） (2022-04-05T08:58:24Z)
• On query complexity measures and their relations for symmetric functions [0.0]
  本稿では, ブール法と逆法を用いて, 量子クエリの複雑性を低く抑える方法について述べる。 また、部分対称関数Gap Majorityの量子クエリ複雑性についても考察する。 証明の複雑さとブロック感度が対称関数の感度と比較していかに大きいかを示す。
  論文  参考訳（メタデータ） (2021-10-25T02:55:39Z)
• Straddling-gates problem in multipartite quantum systems [20.428960719376164]
  量子回路の複雑性,結合複雑性の変種について検討する。 任意の$m$partite Schmidt decomposable状態が$m$のバインディング複雑性を持つことを示す。
  論文  参考訳（メタデータ） (2021-10-13T16:28:12Z)
• Depth-efficient proofs of quantumness [77.34726150561087]
  量子性の証明は、古典的検証器が信頼できない証明器の量子的利点を効率的に証明できる挑戦応答プロトコルの一種である。 本稿では、証明者が量子回路を一定深度でしか実行できない量子性構成の証明を2つ与える。
  論文  参考訳（メタデータ） (2021-07-05T17:45:41Z)
• Secure Two-Party Quantum Computation Over Classical Channels [63.97763079214294]
  古典的アリス(Alice)と量子的ボブ(Quantum Bob)が古典的なチャネルを通してのみ通信できるような設定を考える。 悪質な量子逆数の場合,ブラックボックスシミュレーションを用いた2次元量子関数を実現することは,一般に不可能であることを示す。 我々は、QMA関係Rの古典的量子知識(PoQK)プロトコルを入力として、古典的当事者によって検証可能なRのゼロ知識PoQKを出力するコンパイラを提供する。
  論文  参考訳（メタデータ） (2020-10-15T17:55:31Z)
• Quantum Go Machine [15.33065067850941]
  偏光度に絡み合った相関光子対を用いたGoの量子バージョンを実験的に実証した。 コヒーレンスや絡み合いのようないくつかの量子資源は、量子石の状態を表すために符号化することもできる。 この結果から,量子可能困難を伴う新たなゲーム開発パラダイムが確立された。
  論文  参考訳（メタデータ） (2020-07-23T18:00:01Z)
• Quantum Communication Complexity of Distribution Testing [114.31181206328276]
  2人のプレーヤーが1つのディストリビューションから$t$のサンプルを受け取ります。 目標は、2つの分布が等しいか、または$epsilon$-far であるかどうかを決定することである。 この問題の量子通信複雑性が$tildeO$(tepsilon2)$ qubitsであることを示す。
  論文  参考訳（メタデータ） (2020-06-26T09:05:58Z)
• Complexity limitations on one-turn quantum refereed games [0.6091702876917281]
  本論文は,量子参照ゲームの理論的側面を研究する。 抽象ゲームは、審判に量子状態を送信する2人のプレーヤーの間のものである。 審判は、2つの状態に対して効率よく実施可能な共同測定を行い、どのプレイヤーが勝つかを判定する。
  論文  参考訳（メタデータ） (2020-02-04T19:28:03Z)

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

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