論文の概要: Better bounds on Grothendieck constants of finite orders

• arxiv url: http://arxiv.org/abs/2409.03739v1
• Date: Thu, 5 Sep 2024 17:53:52 GMT
• ステータス: 処理完了
• システム内更新日: 2024-09-06 19:33:34.837740
• Title: Better bounds on Grothendieck constants of finite orders
• Title（参考訳）: 有限位数のグロタンディーク定数のより良い境界
• Authors: Sébastien Designolle, Tamás Vértesi, Sebastian Pokutta,
• Abstract要約: 我々は最近のフランク・ウルフのアプローチを利用して、いくつかのグロタンディーク定数を下限とするよい候補を提供する。 完全証明は難解な二項最適化問題を解くことに依存する。
• 参考スコア（独自算出の注目度）: 20.068273625719943
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Grothendieck constants $K_G(d)$ bound the advantage of $d$-dimensional strategies over $1$-dimensional ones in a specific optimisation task. They have applications ranging from approximation algorithms to quantum nonlocality. However, apart from $d=2$, their values are unknown. Here, we exploit a recent Frank-Wolfe approach to provide good candidates for lower bounding some of these constants. The complete proof relies on solving difficult binary quadratic optimisation problems. For $d\in\{3,4,5\}$, we construct specific rectangular instances that we can solve to certify better bounds than those previously known; by monotonicity, our lower bounds improve on the state of the art for $d\leqslant9$. For $d\in\{4,7,8\}$, we exploit elegant structures to build highly symmetric instances achieving even greater bounds; however, we can only solve them heuristically. We also recall the standard relation with violations of Bell inequalities and elaborate on it to interpret generalised Grothendieck constants $K_G(d\mapsto2)$ as the advantage of complex quantum mechanics over real quantum mechanics. Motivated by this connection, we also improve the bounds on $K_G(d\mapsto2)$.
• Abstract（参考訳）: Grothendieck constants $K_G(d)$ bound the advantage of $d$-dimensional strategy over $1$-dimensional ones in a specific optimization task。 近似アルゴリズムから量子非局所性まで、様々な応用がある。 しかし、$d=2$以外は、値は不明である。 ここでは、これらの定数のいくつかを下げるためのよい候補を提供するために、最近のフランク・ウルフのアプローチを利用する。 完全証明は難解な二項最適化問題を解くことに依存する。 d\in\{3,4,5\}$の場合、従来よりも優れた境界を証明できる特定の長方形のインスタンスを構築します。 d\in\{4,7,8\}$の場合、高対称性のインスタンスを構築するためにエレガントな構造を利用する。 またベルの不等式に反する標準的な関係を思い出し、それについて精巧に説明し、一般化されたグロタンディーク定数$K_G(d\mapsto2)$を実量子力学よりも複雑な量子力学の利点として解釈する。 この接続により、$K_G(d\mapsto2)$のバウンダリも改善される。

関連論文リスト

• Efficient Quantum State Synthesis with One Query [0.0]
  本稿では,古典的オラクルへの単一クエリ(重ね合わせ)を実現する時間類似量子アルゴリズムを提案する。 我々は、すべての$n$-qubit状態が、適切な有限ゲート集合上の$On/n)$-size回路によって0.01エラー内に構築可能であることを証明した。
  論文  参考訳（メタデータ） (2023-06-02T17:49:35Z)
• Pseudonorm Approachability and Applications to Regret Minimization [73.54127663296906]
  我々は、高次元 $ell_infty$-approachability 問題を、低次元の擬ノルムアプローチ可能性問題に変換する。 我々は、$ell$や他のノルムに対するアプローチ可能性に関する以前の研究に類似した疑似ノルムアプローチ可能性のアルゴリズム理論を開発する。
  論文  参考訳（メタデータ） (2023-02-03T03:19:14Z)
• A Newton-CG based barrier-augmented Lagrangian method for general nonconvex conic optimization [53.044526424637866]
  本稿では、2つの異なる対象の一般円錐最適化を最小化する近似二階定常点(SOSP)について検討する。 特に、近似SOSPを見つけるためのNewton-CGベースの拡張共役法を提案する。
  論文  参考訳（メタデータ） (2023-01-10T20:43:29Z)
• Grothendieck bound in a single quantum system [0.0]
  グロタンディークの境界は単一の量子系の文脈で用いられる。 グロタンディークの定理は任意の行列の観点からここで再定式化される。
  論文  参考訳（メタデータ） (2022-12-22T13:06:31Z)
• Exponential Separation between Quantum and Classical Ordered Binary Decision Diagrams, Reordering Method and Hierarchies [68.93512627479197]
  量子順序付き二項決定図($OBDD$)モデルについて検討する。 入力変数の任意の順序で、OBDDの下位境界と上位境界を証明します。 read$k$-times Ordered Binary Decision Diagrams (k$-OBDD$)の幅の階層を拡張します。
  論文  参考訳（メタデータ） (2022-04-22T12:37:56Z)
• Improved upper bounds on the stabilizer rank of magic states [0.0]
  改良は、マジック状態 $|Trangle=sqrt2-1(|0rangle+eipi/4|1rangle)$ の安定化ランクに $m$ の上限で新しい上限を設定することで得られる。 Clifford ゲートと$m$のインスタンスからなる回路に対して,実行時 $textpoly(n,m) 2m/2$ のシングルキュービット $Z$-rotation ゲートの強いシミュレーションアルゴリズムを得る。
  論文  参考訳（メタデータ） (2021-06-14T20:20:51Z)
• Private Stochastic Convex Optimization: Optimal Rates in $\ell_1$ Geometry [69.24618367447101]
  対数要因まで $(varepsilon,delta)$-differently private の最適過剰人口損失は $sqrtlog(d)/n + sqrtd/varepsilon n.$ です。 損失関数がさらなる滑らかさの仮定を満たすとき、余剰損失は$sqrtlog(d)/n + (log(d)/varepsilon n)2/3で上界(対数因子まで)であることが示される。
  論文  参考訳（メタデータ） (2021-03-02T06:53:44Z)
• Lower Bounds and Accelerated Algorithms for Bilevel Optimization [62.192297758346484]
  バイレベル最適化は、最近の機械学習問題に広く応用されているため、近年、関心が高まりつつある。 結果がminimaxアプリケーションよりも難しいことを示します。
  論文  参考訳（メタデータ） (2021-02-07T21:46:29Z)
• Epsilon-nets, unitary designs and random quantum circuits [0.11719282046304676]
  エプシロンネット(Epsilon-nets)は、量子情報や量子コンピューティングにおける多くの応用に関連するユニタリ演算の概念である。 固定された$d$に対して、$delta$-approx $t$-expanders を構成するユニタリが $epsilon$-nets for $tsimeqfracd5/2epsilon$ および $delta=left(fracepsilon3/2dright)d2$ となることを証明している。 近似tdesign が生成可能であることを示す。
  論文  参考訳（メタデータ） (2020-07-21T15:16:28Z)
• Second-Order Information in Non-Convex Stochastic Optimization: Power and Limitations [54.42518331209581]
  私たちは発見するアルゴリズムを見つけます。 epsilon$-approximate stationary point ($|nabla F(x)|le epsilon$) using $(epsilon,gamma)$surimateランダムランダムポイント。 ここでの私たちの下限は、ノイズのないケースでも新規です。
  論文  参考訳（メタデータ） (2020-06-24T04:41:43Z)
• Quasi-polynomial time algorithms for free quantum games in bounded dimension [11.56707165033]
  2プレイヤフリーゲームの値に対する加法$epsilon$-approximationsを計算するために、$exp(mathcalObig(T12(log2(AT)+log(Q)log(AT))/epsilon2big))という半定値プログラムを与える。 量子分離性問題と接続し、線形制約を伴う改良された多部量子デ・フィネッティ定理を用いる。
  論文  参考訳（メタデータ） (2020-05-18T16:55:08Z)

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

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