論文の概要: Mutually unbiased bases as a commuting polynomial optimisation problem

• arxiv url: http://arxiv.org/abs/2308.01879v1
• Date: Thu, 3 Aug 2023 17:14:22 GMT
• ステータス: 処理完了
• システム内更新日: 2023-08-04 13:20:00.009151
• Title: Mutually unbiased bases as a commuting polynomial optimisation problem
• Title（参考訳）: 可換多項式最適化問題としての無バイアス基底
• Authors: Luke Mortimer
• Abstract要約: 我々は、実数に対する最適化問題として、相互に偏りのない基底の問題を考察する。 最適化手法を多数組み合わせた2つの手法を用いる。 このようなアルゴリズムが最終的に有限メモリで次元6に関するオープンな問題を解くことを実証する。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We consider the problem of mutually unbiased bases as a polynomial optimization problem over the reals. We heavily reduce it using known symmetries before exploring it using two methods, combining a number of optimization techniques. The first of these is a search for bases using Lagrange-multipliers that converges rapidly in case of MUB existence, whilst the second combines a hierarchy of semidefinite programs with branch-and-bound techniques to perform a global search. We demonstrate that such an algorithm would eventually solve the open question regarding dimension 6 with finite memory, although it still remains intractable. We explore the idea that to show the inexistence of bases, it suffices to search for orthonormal vector sets of certain smaller sizes, rather than full bases. We use our two methods to conjecture the minimum set sizes required to show infeasibility, proving it for dimensions 3. The fact that such sub-problems seem to also be infeasible heavily reduces the number of variables, by 66\% in the case of the open problem, potentially providing an large speedup for other algorithms and bringing them into the realm of tractability.
• Abstract（参考訳）: 実数上の多項式最適化問題として相互に偏りのない基底の問題を考える。 2つの手法を用いて探索する前に、既知の対称性を用いて大幅に削減し、多くの最適化手法を組み合わせた。 1つ目は、mubが存在する場合に急速に収束するラグランジュ乗算器を用いたベース探索であり、もう1つは半定値プログラムの階層と分岐境界法を組み合わせて大域探索を行う。 このようなアルゴリズムが最終的に有限記憶で次元6に関するオープン問題を解くことを実証するが、まだ難解なままである。 我々は、基底の不存在を示すために、あるより小さなサイズの正則ベクトル集合を探すのに十分であるという考えを探求する。 我々はこの2つの方法を用いて実現不可能性を示すのに必要な最小集合サイズを推測し、次元 3 に対して証明する。 このようなサブプロブレムが実現不可能であるという事実は、オープンな問題の場合、変数の数を66\%減らし、他のアルゴリズムに対して大きなスピードアップを提供し、トラクタビリティの領域に持ち込む可能性がある。

関連論文リスト

• Towards exact algorithmic proofs of maximal mutually unbiased bases sets in arbitrary integer dimension [0.0]
  離散量子系におけるMUB(Mutually Unbiased Bases)の概念について検討する。 素数の和である次元$d$に対して、MUB集合を形成する最大$d+1$基底の集合が存在することが知られている。 しかし、素数の和ではない次元における MUB の最大数は分かっていない。
  論文  参考訳（メタデータ） (2023-09-21T18:00:42Z)
• An Oblivious Stochastic Composite Optimization Algorithm for Eigenvalue Optimization Problems [76.2042837251496]
  相補的な合成条件に基づく2つの難解なミラー降下アルゴリズムを導入する。 注目すべきは、どちらのアルゴリズムも、目的関数のリプシッツ定数や滑らかさに関する事前の知識なしで機能する。 本稿では,大規模半確定プログラム上での手法の効率性とロバスト性を示す。
  論文  参考訳（メタデータ） (2023-06-30T08:34:29Z)
• Pseudonorm Approachability and Applications to Regret Minimization [73.54127663296906]
  我々は、高次元 $ell_infty$-approachability 問題を、低次元の擬ノルムアプローチ可能性問題に変換する。 我々は、$ell$や他のノルムに対するアプローチ可能性に関する以前の研究に類似した疑似ノルムアプローチ可能性のアルゴリズム理論を開発する。
  論文  参考訳（メタデータ） (2023-02-03T03:19:14Z)
• Explicit Second-Order Min-Max Optimization Methods with Optimal Convergence Guarantee [86.05440220344755]
  我々は,非制約のmin-max最適化問題のグローバルなサドル点を求めるために,不正確な正規化ニュートン型手法を提案し,解析する。 提案手法は有界集合内に留まるイテレートを生成し、その反復は制限関数の項で$O(epsilon-2/3)$内の$epsilon$-saddle点に収束することを示す。
  論文  参考訳（メタデータ） (2022-10-23T21:24:37Z)
• On the Second-order Convergence Properties of Random Search Methods [7.788439526606651]
  本研究では,2次情報に依存しない標準的なランダム検索手法が2次定常点に収束することを証明する。 本稿では,関数評価のみに依存する負曲率の新しい変種を提案する。
  論文  参考訳（メタデータ） (2021-10-25T20:59:31Z)
• Optimal Gradient-based Algorithms for Non-concave Bandit Optimization [76.57464214864756]
  この研究は、未知の報酬関数が非可逆であるようなバンドイット問題の大群を考察する。 我々のアルゴリズムは、非常に一般化されたゼロ階最適化のパラダイムに基づいている。 標準的な楽観的アルゴリズムは次元因子によって準最適であることを示す。
  論文  参考訳（メタデータ） (2021-07-09T16:04:24Z)
• Revisiting the Complexity Analysis of Conflict-Based Search: New Computational Techniques and Improved Bounds [5.158632635415881]
  最適解に対する最先端のアプローチは Conflict-Based Search (CBS) である CBSの複雑性分析を再検討し、最悪の場合のアルゴリズムの実行時間に厳密な制限を与える。
  論文  参考訳（メタデータ） (2021-04-18T07:46:28Z)
• A Regularized Limited Memory BFGS method for Large-Scale Unconstrained Optimization and its Efficient Implementations [0.0]
  そこで本研究では,特定の正規化手法を用いた新しい制限メモリBFGS (L-BFGS) 法を提案する。 通常の仮定の下では、そのグローバルな収束を示す。 また、ノンモノトーン法やウルフ線探索の同時利用など、いくつかの手法で拡張する。
  論文  参考訳（メタデータ） (2021-01-12T11:24:37Z)
• Learning to Accelerate Heuristic Searching for Large-Scale Maximum Weighted b-Matching Problems in Online Advertising [51.97494906131859]
  バイパルタイトbマッチングはアルゴリズム設計の基本であり、経済市場や労働市場などに広く適用されている。 既存の正確で近似的なアルゴリズムは、通常そのような設定で失敗する。 我々は、以前の事例から学んだ知識を活用して、新しい問題インスタンスを解決するtextttNeuSearcherを提案する。
  論文  参考訳（メタデータ） (2020-05-09T02:48:23Z)
• Lagrangian Decomposition for Neural Network Verification [148.0448557991349]
  ニューラルネットワーク検証の基本的なコンポーネントは、出力が取ることのできる値のバウンダリの計算である。 ラグランジアン分解に基づく新しい手法を提案する。 ランニングタイムのごく一部で、既成の解法に匹敵するバウンダリが得られることを示す。
  論文  参考訳（メタデータ） (2020-02-24T17:55:10Z)

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

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