論文の概要: 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-10-01 21:58:05.448607
- 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:
- 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}^*$ の別の例を示す。
関連論文リスト
- Promise Clique Homology on weighted graphs is $\text{QMA}_1$-hard and
contained in $\text{QMA}$ [0.0]
計算トポロジにおける古典問題の複雑性, ホモロジー問題について検討する。
複雑性は量子複雑性クラスによって特徴づけられる。
この結果は、ホモロジーと超対称量子力学の結びつきの側面と見なすことができる。
論文 参考訳(メタデータ) (2023-11-28T21:15:30Z) - Universality of graph homomorphism games and the quantum coloring
problem [0.0]
量子グラフパラメータは、任意の同期非局所ゲームに対する勝利戦略をエンコードすることを示す。
同期ゲームにおける勝利戦略は、関連するグラフカラーゲームに対する勝利戦略に変換することができる。
論文 参考訳(メタデータ) (2023-05-29T14:28:28Z) - Enriched string-net models and their excitations [0.0]
ウォーカー・ワングモデルの境界線は通勤プロジェクターモデルの構築に使われてきた。
本稿ではこの2次元境界モデルの厳密な扱いについて述べる。
また,TQFT法を用いて,ウォーカー・ワンバルクの3次元バルク点励起をM "uger center" で示す。
論文 参考訳(メタデータ) (2023-05-23T13:45:33Z) - Revisiting Weighted Strategy for Non-stationary Parametric Bandits [82.1942459195896]
本稿では,非定常パラメトリックバンディットの重み付け戦略を再考する。
より単純な重みに基づくアルゴリズムを生成する改良された分析フレームワークを提案する。
我々の新しいフレームワークは、他のパラメトリックバンディットの後悔の限界を改善するのに使える。
論文 参考訳(メタデータ) (2023-03-05T15:11:14Z) - The quantum commuting model (Ia): The CHSH game and other examples:
Uniqueness of optimal states [91.3755431537592]
2つのプレイヤーゲームに対する普遍代数上の状態空間として、量子交換相関の普遍的記述を用いる。
この共通代数にCHSHゲームが一つの最適状態を残していることが分かる。
論文 参考訳(メタデータ) (2022-10-07T17:38:31Z) - Connes implies Tsirelson: a simple proof [91.3755431537592]
コンヌ埋め込み問題は同期的ツィレルソン予想を意味することを示す。
また、コンネスの代数 $mathcalRomega$ の異なる構成もコンネス埋め込み問題に現れる。
論文 参考訳(メタデータ) (2022-09-16T13:59:42Z) - 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) - Solving correlation clustering with QAOA and a Rydberg qudit system: a
full-stack approach [94.37521840642141]
量子近似最適化アルゴリズム(QAOA)とクォーディットを用いた相関クラスタリング問題について検討する。
具体的には、中性原子量子コンピュータを検討し、相関クラスタリングのためのフルスタックアプローチを提案する。
ゲート数によって定量化されるように、quditの実装はqubitエンコーディングよりも優れていることを示す。
論文 参考訳(メタデータ) (2021-06-22T11:07:38Z) - Near-Optimal Reinforcement Learning with Self-Play [50.29853537456737]
我々は,直接の監督なしに自己対決で最適な政策を学習するセルフプレイアルゴリズムに焦点をあてる。
本稿では,サンプル複雑性を$tildemathcalO(SAB)$,サンプル複雑性を$tildemathcalO(S(A+B)$とする新しいemphNash Vラーニングアルゴリズムを提案する。
論文 参考訳(メタデータ) (2020-06-22T05:00:13Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。