論文の概要: Certificate games
- arxiv url: http://arxiv.org/abs/2211.03396v2
- Date: Tue, 8 Nov 2022 11:39:44 GMT
- ステータス: 翻訳完了
- システム内更新日: 2023-01-20 02:02:13.503467
- Title: Certificate games
- Title（参考訳）: 証明ゲーム
- Authors: Sourav Chakraborty, Anna G\'al, Sophie Laplante, Rajat Mittal, Anupa
Sunny
- Abstract要約: 本稿では,ゲームに勝つ確率に基づいた複雑性尺度であるCertificate Game complexityについて検討する。
公開コインモデルの複雑さはランダム化クエリと証明書の複雑さによって上限づけられていることを示す。
我々は証明書ゲームのシングルビット版を考える(この2人のプレイヤーのインプットはハミング距離が1ドル)。
共有ランダム性を持つシングルビット版の証明書ゲーム複雑性は、一定要素までの感度に等しいことを証明した。
- 参考スコア（独自算出の注目度）: 2.817395666721831
- 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 $i$ such that $x_i\neq
y_i$ (zero-communication setting).
We give upper and lower bounds for private coin, public coin, shared
entanglement and non-signaling strategies, and give some separations. We show
that complexity in the public coin model is upper bounded by Randomized query
and Certificate complexity. On the other hand, it is lower bounded by
fractional and randomized certificate complexity, making it a good candidate to
prove strong lower bounds on randomized query complexity. Complexity in the
private coin model is bounded from below by zero-error randomized query
complexity.
The quantum measure highlights an interesting and surprising difference
between classical and quantum query models. Whereas the public coin certificate
game complexity is bounded from above by randomized query complexity, 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 or fractional block sensitivity.
We consider the single-bit version of certificate games (inputs of the two
players have Hamming distance $1$). We prove that the single-bit version of
certificate game complexity with shared randomness is equal to sensitivity up
to constant factors, giving a new characterization of sensitivity. The
single-bit version with private randomness is equal to $\lambda^2$, where
$\lambda$ is the spectral sensitivity.
- Abstract（参考訳）: 本稿では,2人のプレーヤーに異なる関数値の入力が与えられ,x_i\neq y_i$(ゼロコミュニケーション設定)のような$i$の出力が要求されるゲームに勝つ確率に基づく複雑性の尺度であるCertificate Game complexityを紹介し,研究する。
我々は、プライベートコイン、パブリックコイン、共有絡み合いとノンシグナリング戦略の上限を上下に設定し、いくつかの分離を与える。
公開コインモデルの複雑さはランダム化クエリと証明書の複雑さによって上限づけられていることを示す。
一方、分数的およびランダム化証明書の複雑さにより境界が低くなり、ランダム化クエリの複雑さに対して強い下位境界を証明するのがよい候補となる。
プライベートコインモデルの複雑さは、ゼロエラーランダム化クエリの複雑さによって下から制限される。
この量子測度は、古典的および量子的クエリーモデルの間の興味深い、驚くべき違いを浮き彫りにする。
公開コイン証明書ゲーム複雑性はランダム化されたクエリ複雑性によって上から区切られているのに対し、量子証明書ゲーム複雑性は量子クエリ複雑性よりも2倍大きい可能性がある。
量子情報の概念であるノンシグナリング(non-signaling)を使用して、$or$関数の量子証明書ゲーム複雑性(量子クエリの複雑性は$\theta(\sqrt{n})$)を低く設定し、その後、この ‘non-signaling bottleneck'' が高感度、ブロック感度、分数ブロック感度のすべての関数に適用されることを示す。
私たちは、証明書ゲームのシングルビットバージョンを考えています(2人のプレーヤーの入力は、距離が1ドル弱です)。
共有ランダム性を持つシングルビット版の証明書ゲーム複雑性は、一定要素までの感度に等しいことを証明し、新しい感度特性を与える。
プライベートなランダム性を持つシングルビットバージョンは$\lambda^2$に等しいが、$\lambda$はスペクトル感度である。
関連論文リスト
- 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。