論文の概要: Quantum Interior Point Methods for Semidefinite Optimization

• arxiv url: http://arxiv.org/abs/2112.06025v3
• Date: Thu, 7 Sep 2023 21:15:31 GMT
• ステータス: 処理完了
• システム内更新日: 2023-09-11 19:02:37.310203
• Title: Quantum Interior Point Methods for Semidefinite Optimization
• Title（参考訳）: 半定値最適化のための量子内部点法
• Authors: Brandon Augustino, Giacomo Nannicini, Tam\'as Terlaky and Luis F. Zuluaga
• Abstract要約: 半定値最適化問題に対する2つの量子内点法を提案する。 第1のスキームは、不正確な探索方向を計算し、実現可能な点のみを探索することが保証されない。 第二のスキームはニュートン線形系のヌルスペース表現を用いて、不正確な探索方向であっても実現可能であることを保証する。
• 参考スコア（独自算出の注目度）: 0.16874375111244327
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We present two quantum interior point methods for semidefinite optimization problems, building on recent advances in quantum linear system algorithms. The first scheme, more similar to a classical solution algorithm, computes an inexact search direction and is not guaranteed to explore only feasible points; the second scheme uses a nullspace representation of the Newton linear system to ensure feasibility even with inexact search directions. The second is a novel scheme that might seem impractical in the classical world, but it is well-suited for a hybrid quantum-classical setting. We show that both schemes converge to an optimal solution of the semidefinite optimization problem under standard assumptions. By comparing the theoretical performance of classical and quantum interior point methods with respect to various input parameters, we show that our second scheme obtains a speedup over classical algorithms in terms of the dimension of the problem $n$, but has worse dependence on other numerical parameters.
• Abstract（参考訳）: 量子線形系アルゴリズムの最近の進歩に基づいて,半定値最適化問題に対する2つの量子内点法を提案する。 第1のスキームは、より古典的な解法アルゴリズムと似ており、不適合な探索方向を計算し、実現可能な点のみを探索することは保証されていない。 2つ目は古典世界では実用的でないと思われる新しいスキームであるが、ハイブリッド量子古典的設定に適している。 両スキームが標準仮定の下で半定値最適化問題の最適解に収束することを示す。 様々な入力パラメータに対する古典的内部点法と量子的内部点法の理論的性能を比較することにより,第2のスキームは,問題 $n$ の次元で古典的アルゴリズムを高速化するが,他の数値的パラメータに依存しないことを示す。

関連論文リスト

• Fast Computation of Optimal Transport via Entropy-Regularized Extragradient Methods [75.34939761152587]
  2つの分布間の最適な輸送距離の効率的な計算は、様々な応用を促進するアルゴリズムとして機能する。 本稿では,$varepsilon$加法精度で最適な輸送を計算できるスケーラブルな一階最適化法を提案する。
  論文  参考訳（メタデータ） (2023-01-30T15:46:39Z)
• Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
  量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。 量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
  論文  参考訳（メタデータ） (2022-12-06T22:01:49Z)
• Variational quantum algorithm for unconstrained black box binary optimization: Application to feature selection [1.9182522142368683]
  制約のないブラックボックス二項問題の解法として,変分量子アルゴリズムを提案する。 これは最適化のための量子アルゴリズムの典型的な設定とは対照的である。 提案手法は,従来の特徴選択手法よりも競争力があり,性能も向上していることを示す。
  論文  参考訳（メタデータ） (2022-05-06T07:02:15Z)
• Quantum Optimization Heuristics with an Application to Knapsack Problems [5.866941279460248]
  本稿では,量子近似最適化アルゴリズム(QAOA)を制約付き最適化問題に適合させる2つの手法を提案する。 最初のテクニックでは、初期の量子状態と混合操作を定義し、量子最適化アルゴリズムを調整して、この初期欲求解に関する可能な解を探索する方法が述べられている。 第2の手法は、グリーディ溶液の周りの局所的なミニマを避けるために、量子探索に使用される。
  論文  参考訳（メタデータ） (2021-08-19T17:22:44Z)
• Quadratic Unconstrained Binary Optimisation via Quantum-Inspired Annealing [58.720142291102135]
  本稿では,2次非制約二項最適化の事例に対する近似解を求める古典的アルゴリズムを提案する。 我々は、チューニング可能な硬さと植え付けソリューションを備えた大規模問題インスタンスに対して、我々のアプローチをベンチマークする。
  論文  参考訳（メタデータ） (2021-08-18T09:26:17Z)
• Implementable Hybrid Quantum Ant Colony Optimization Algorithm [0.0]
  NP-hard問題に対する近似解を生成するための新しいハイブリッド量子アルゴリズムを提案する。 我々は,近距離量子コンピュータで真に実装できる改良されたアルゴリズムを開発した。 ノイズレス量子回路をシミュレートしたベンチマークと、IBM量子コンピュータを用いた実験により、アルゴリズムの有効性が示された。
  論文  参考訳（メタデータ） (2021-07-08T13:50:51Z)
• Training variational quantum algorithms is NP-hard [0.7614628596146599]
  古典最適化の問題はNPハードであることが示される。 対数的に多くの量子ビットや自由フェルミオンからなる古典的トラクタブルシステムであっても、最適化はNPハードであることが示される。
  論文  参考訳（メタデータ） (2021-01-18T19:00:01Z)
• Recent Theoretical Advances in Non-Convex Optimization [56.88981258425256]
  近年、深層ネットワークにおける非最適化アルゴリズムの解析やデータ問題への関心が高まっており、非最適化のための理論的最適化アルゴリズムの最近の結果の概要を概説する。
  論文  参考訳（メタデータ） (2020-12-11T08:28:51Z)
• Quantum Assisted Eigensolver [0.0]
  本研究では,ハミルトニアンの基底状態と基底状態エネルギーを近似するハイブリッド量子古典アルゴリズムを提案する。 アルゴリズムの量子部分からの出力を古典コンピュータの入力として利用する。
  論文  参考訳（メタデータ） (2020-09-23T08:33:18Z)
• Convergence of adaptive algorithms for weakly convex constrained optimization [59.36386973876765]
  モローエンベロープの勾配のノルムに対して$mathcaltilde O(t-1/4)$収束率を証明する。 我々の分析では、最小バッチサイズが1ドル、定数が1位と2位のモーメントパラメータが1ドル、そしておそらくスムーズな最適化ドメインで機能する。
  論文  参考訳（メタデータ） (2020-06-11T17:43:19Z)
• Cross Entropy Hyperparameter Optimization for Constrained Problem Hamiltonians Applied to QAOA [68.11912614360878]
  QAOA(Quantum Approximate Optimization Algorithm)のようなハイブリッド量子古典アルゴリズムは、短期量子コンピュータを実用的に活用するための最も奨励的なアプローチの1つである。 このようなアルゴリズムは通常変分形式で実装され、古典的な最適化法と量子機械を組み合わせて最適化問題の優れた解を求める。 本研究では,クロスエントロピー法を用いてランドスケープを形作り,古典的パラメータがより容易により良いパラメータを発見でき,その結果,性能が向上することを示す。
  論文  参考訳（メタデータ） (2020-03-11T13:52:41Z)

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

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