論文の概要: Topics in Algebra of Synchronous Games, Algebraic Graph Identities and Quantum NP-hardness Reductions
- arxiv url: http://arxiv.org/abs/2408.10114v2
- Date: Tue, 20 Aug 2024 03:29:26 GMT
- ステータス: 処理完了
- システム内更新日: 2024-08-21 12:23:48.862426
- Title: Topics in Algebra of Synchronous Games, Algebraic Graph Identities and Quantum NP-hardness Reductions
- Title（参考訳）: 同期ゲーム, 代数グラフ Identities, 量子NP硬度低減の話題
- Authors: Entong He,
- Abstract要約: 同期ゲームとその関連ゲーム代数の対応性について検討する。
我々は、特定のモデルによる完璧な戦略の存在を確認するための計算ツールを構築している。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We review the correspondence between a synchronous game and its associated game algebra. We slightly develop the work of Helton et al.[HMPS17] by proposing results on algebraic and locally commuting graph identities. Based on the theoretical works on noncommutative Nullstellens\"atze [BWHK23], we build computational tools involving Gr\"obner basis method and semidefinite programming to check the existence of perfect strategies with specific models. We prove the equivalence between the hereditary and $C^*$ models proposed in [HMPS17]. We also extend Ji's reduction $\texttt{3-Coloring}^* \leq_p \texttt{3-SAT}^*$ [Ji13] and exhibit another instance of quantum-version NP-hardness reduction $\texttt{Clique}^* \leq_p \texttt{3-SAT}^*$.
- Abstract（参考訳）: 同期ゲームとその関連ゲーム代数の対応性について検討する。
我々は代数的および局所的な可換グラフの恒等性に関する結果を提案することで、Helton et al [HMPS17] の研究を少し発展させる。
非可換Nullstellens\"atze [BWHK23]に関する理論的研究に基づいて、Gr\"obner basis methodと半定値プログラミングを含む計算ツールを構築し、特定のモデルによる完璧な戦略の存在を確認する。
我々は[HMPS17]で提案された遺伝モデルと$C^*$モデルの等価性を証明した。
また、Ji の還元 $\texttt{3-Coloring}^* \leq_p \texttt{3-SAT}^*$ [Ji13] を拡張し、量子変換 NP-ハードネス還元 $\texttt{Clique}^* \leq_p \texttt{3-SAT}^*$ の別の例を示す。
関連論文リスト
- Parity vs. AC0 with simple quantum preprocessing [0.0]
我々は、$mathsfAC0$が$mathsfQNC0$回路の測定結果に作用するハイブリッド回路モデルについて検討する。
私たちは、$mathsfQNC0$が、タスクの検索とサンプリングに驚くほど強力なのに対して、その出力のグローバルな相関において、そのパワーは"ロックアウト"されていることに気付きました。
論文 参考訳（メタデータ） (2023-11-22T20:27:05Z) - Universality of graph homomorphism games and the quantum coloring
problem [0.0]
量子グラフパラメータは、任意の同期非局所ゲームに対する勝利戦略をエンコードすることを示す。
同期ゲームにおける勝利戦略は、関連するグラフカラーゲームに対する勝利戦略に変換することができる。
論文 参考訳（メタデータ） (2023-05-29T14:28:28Z) - Connes implies Tsirelson: a simple proof [91.3755431537592]
コンヌ埋め込み問題は同期的ツィレルソン予想を意味することを示す。
また、コンネスの代数 $mathcalRomega$ の異なる構成もコンネス埋め込み問題に現れる。
論文 参考訳（メタデータ） (2022-09-16T13:59:42Z) - Near-Optimal Learning of Extensive-Form Games with Imperfect Information [54.55092907312749]
本稿では,2プレイヤーゼロサムゲームにおいて,$widetildemathcalO((XA+YB)/varepsilon2)$プレイのエピソードのみを必要とするアルゴリズムの最初の行を,$varepsilon$-approximate Nash平衡を求める。
これにより$widetildemathcalO((X2A+Y2B)/varepsilon2)$が$widetildemathcalO(maxX,
論文 参考訳（メタデータ） (2022-02-03T18:18:28Z) - Uncertainties in Quantum Measurements: A Quantum Tomography [52.77024349608834]
量子系 $S$ に関連する可観測物は非可換代数 $mathcal A_S$ を形成する。
密度行列 $rho$ は可観測物の期待値から決定できると仮定される。
アーベル代数は内部自己同型を持たないので、測定装置は可観測物の平均値を決定することができる。
論文 参考訳（メタデータ） (2021-12-14T16:29:53Z) - Nonlocal Games, Compression Theorems, and the Arithmetical Hierarchy [0.12891210250935145]
非局所ゲームと算術的階層の関係について検討する。
量子値を正確に計算することは、それを近似するよりも厳密に、また通勤演算子値を計算するより厳密に難しいことを示す。
論文 参考訳（メタデータ） (2021-10-09T21:53:02Z) - Synchronous games with $*$-isomorphic game algebras [0.0]
我々は、$nk$入力および$k$出力上の任意の同期ゲームのゲーム代数が、$nk$入力および$nk$出力上の関連する双同期ゲームのゲーム代数に同型であることを示す。
また、$n$の質問と$k>3$の回答を持つ任意の同期ゲーム代数と$n(k-2)の質問と$3$の回答を持つ同期ゲーム代数との間に$*$同型を示す。
論文 参考訳（メタデータ） (2021-09-10T13:19:14Z) - Quantum double aspects of surface code models [77.34726150561087]
基礎となる量子double $D(G)$対称性を持つ正方格子上でのフォールトトレラント量子コンピューティングの北エフモデルを再検討する。
有限次元ホップ代数$H$に基づいて、我々の構成がどのように$D(H)$モデルに一般化するかを示す。
論文 参考訳（メタデータ） (2021-06-25T17:03:38Z) - Near-Optimal Reinforcement Learning with Self-Play [50.29853537456737]
我々は,直接の監督なしに自己対決で最適な政策を学習するセルフプレイアルゴリズムに焦点をあてる。
本稿では,サンプル複雑性を$tildemathcalO(SAB)$,サンプル複雑性を$tildemathcalO(S(A+B)$とする新しいemphNash Vラーニングアルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-06-22T05:00:13Z) - Tight Quantum Lower Bound for Approximate Counting with Quantum States [49.6558487240078]
Aaronson, Kothari, Kretschmer, Thaler (2020) が考える数え上げ問題の次の変種に対する厳密な下界を証明する。
このタスクは、入力セット$xsubseteq [n]$が$k$か$k'=(1+varepsilon)k$であるかどうかを識別する。
論文 参考訳（メタデータ） (2020-02-17T10:53:50Z) - MIP*=RE [9.42581332803306]
言語のクラス MIP* は、複数の量子プロバーサを共有する絡み合いと相互作用する古典的検証器によって決定できることを示す。
我々は、フォン・ノイマン代数のコンヌの理論の難解性を提供する。
論文 参考訳（メタデータ） (2020-01-13T16:32:40Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。