論文の概要: Topics in Non-local Games: Synchronous Algebras, Algebraic Graph Identities, and Quantum NP-hardness Reductions
- arxiv url: http://arxiv.org/abs/2408.10114v5
- Date: Mon, 30 Sep 2024 08:55:30 GMT
- ステータス: 処理完了
- システム内更新日: 2024-11-08 06:44:48.884108
- Title: Topics in Non-local Games: Synchronous Algebras, Algebraic Graph Identities, and Quantum NP-hardness Reductions
- Title（参考訳）: 非局所ゲームにおけるトピック:同期代数、代数グラフ Identities、量子NP硬度低減
- Authors: Entong He,
- Abstract要約: 我々は遺伝モデルと$C*$モデルの等価性を証明している(Hlton et al., New York J. Math)。
また、量子変換NP硬度低減$texttt3-SAT* leq_p textttClique*$ も拡張し、この還元の別の例を示す。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We review the correspondence between synchronous games and their associated $*$-algebra. Building upon the work of (Helton et al., New York J. Math. 2017), we propose results on algebraic and locally commuting graph identities. Based on the noncommutative Nullstellens\"atze (Watts, Helton and Klep, Annales Henri Poincar\'e 2023), we build computational tools that check the non-existence of perfect $C^*$ and algebraic strategies of synchronous games using Gr\"obner basis methods and semidefinite programming. We prove the equivalence between the hereditary and $C^*$ models questioned in (Helton et al., New York J. Math. 2017). We also extend the quantum-version NP-hardness reduction $\texttt{3-SAT}^* \leq_p \texttt{3-Coloring}^*$ due to (Ji, arXiv 2013) by exhibiting another instance of such reduction $\texttt{3-SAT}^* \leq_p \texttt{Clique}^*$.
- Abstract（参考訳）: 同期ゲームとそれに関連する$*$-algebraの対応をレビューする。
The work on the work of (Helton et al , New York J. Math. 2017), we propose results on algebraic and local commuting graph identities。
非可換なNullstellens\"atze (Watts, Helton and Klep, Annales Henri Poincar\'e 2023)に基づいて、Gr\"obner基底法と半定値プログラミングを用いて、完全$C^*$と同期ゲームの代数的戦略の非存在をチェックする計算ツールを構築する。
遺伝モデルと$C^*$モデルの等価性を証明した(Helton et al , New York J. Math. 2017)。
また、(Ji, arXiv 2013) による量子変換 NP-ハードネス還元$\texttt{3-SAT}^* \leq_p \texttt{3-Coloring}^*$ も拡張し、そのような還元$\texttt{3-SAT}^* \leq_p \texttt{Clique}^*$ の別の例を示す。
関連論文リスト
- 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。