論文の概要: Solving quadratic binary optimization problems using quantum SDP methods: Non-asymptotic running time analysis

• arxiv url: http://arxiv.org/abs/2502.15426v1
• Date: Fri, 21 Feb 2025 12:54:05 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-02-24 16:09:41.694409
• Title: Solving quadratic binary optimization problems using quantum SDP methods: Non-asymptotic running time analysis
• Title（参考訳）: 量子SDP法による二次二項最適化問題の解法:非漸近実行時間解析
• Authors: Fabian Henze, Viet Tran, Birte Ostermann, Richard Kueng, Timo de Wolff, David Gross,
• Abstract要約: 量子コンピュータは、最先端の古典的手法よりも優れたスケールのリソースを用いて、半定値プログラム(SDP)を解くことができる。 本稿では,量子SDPソルバの非漸近的リソース要求の解析を行う。
• 参考スコア（独自算出の注目度）: 1.9081120388919084
• License:
• Abstract: Quantum computers can solve semidefinite programs (SDPs) using resources that scale better than state-of-the-art classical methods as a function of the problem dimension. At the same time, the known quantum algorithms scale very unfavorably in the precision, which makes it non-trivial to find applications for which the quantum methods are well-suited. Arguably, precision is less crucial for SDP relaxations of combinatorial optimization problems (such as the Goemans-Williamson algorithm), because these include a final rounding step that maps SDP solutions to binary variables. With this in mind, Brand\~ao, Fran\c{c}a, and Kueng have proposed to use quantum SDP solvers in order to achieve an end-to-end speed-up for obtaining approximate solutions to combinatorial optimization problems. They did indeed succeed in identifying an algorithm that realizes a polynomial quantum advantage in terms of its asymptotic running time. However, asymptotic results say little about the problem sizes for which advantages manifest. Here, we present an analysis of the non-asymptotic resource requirements of this algorithm. The work consists of two parts. First, we optimize the original algorithm with a particular emphasis on performance for realistic problem instances. In particular, we formulate a version with adaptive step-sizes, an improved detection criterion for infeasible instances, and a more efficient rounding procedure. In a second step, we benchmark both the classical and the quantum version of the algorithm. The benchmarks did not identify a regime where even the optimized quantum algorithm would beat standard classical approaches for input sizes that can be realistically solved at all. In the absence of further significant improvements, these algorithms therefore fall into a category sometimes called galactic: Unbeaten in their asymptotic scaling behavior, but not practical for realistic problems.
• Abstract（参考訳）: 量子コンピュータは、問題次元の関数として最先端の古典的手法よりも優れたスケールのリソースを用いて、半定値プログラム(SDP)を解くことができる。 同時に、既知の量子アルゴリズムは精度において非常に好ましくないスケールをしており、量子法が適しているアプリケーションを見つけることは簡単ではない。 おそらく、SDP解をバイナリ変数にマッピングする最終的なラウンドングステップを含むため、組合せ最適化問題(ゲーマン・ウィリアムソンアルゴリズムなど)のSDP緩和には精度が重要でない。 これを考慮して、Brand\~ao、Fran\c{c}a、Kuengは、組合せ最適化問題の近似解を得るためのエンドツーエンドのスピードアップを達成するために量子SDPソルバを使うことを提案した。 彼らは、その漸近的な実行時間の観点から多項式量子優位性を実現するアルゴリズムの同定に成功した。 しかし、漸近的な結果は、利点が現れる問題のサイズについてはほとんど言及していない。 本稿では,このアルゴリズムの非漸近的資源要求の解析を行う。 作品は2つの部分で構成されている。 まず、現実的な問題インスタンスのパフォーマンスに特に重点を置いて、元のアルゴリズムを最適化する。 特に,適応的なステップサイズ,非実現不可能なインスタンスに対する検出基準の改善,より効率的なラウンドリング手順を備えたバージョンを定式化する。 2番目のステップでは、アルゴリズムの古典バージョンと量子バージョンの両方をベンチマークする。 ベンチマークでは、最適化された量子アルゴリズムでさえ、現実的に解決可能な入力サイズに対する標準的な古典的アプローチに勝る仕組みを特定できなかった。 さらなる大幅な改良がなければ、これらのアルゴリズムは時折銀河と呼ばれるカテゴリーに分類される: 漸近的なスケーリングの振る舞いを解き放つが、現実的な問題には実用的ではない。

関連論文リスト

• Quantum evolutionary algorithm for TSP combinatorial optimisation problem [0.0]
  本稿では、量子遺伝的アルゴリズム(QGA)を用いて、旅行セールスマン問題(TSP)と呼ばれる新しい問題を解決する方法を実装する。 我々は、この新しいアプローチがいかにうまく機能するかを、古典的遺伝的アルゴリズム(CGA)として知られる従来の手法と比較した。
  論文  参考訳（メタデータ） (2024-09-20T08:27:42Z)
• Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
  最近提案された量子アルゴリズムarXiv:2206.14999は半定値プログラミング(SDP)に基づいている SDPにインスパイアされた量子アルゴリズムを2乗和に一般化する。 この結果から,本アルゴリズムは大きな問題に適応し,最もよく知られた古典学に近似することが示唆された。
  論文  参考訳（メタデータ） (2024-08-14T19:04:13Z)
• Accelerating Cutting-Plane Algorithms via Reinforcement Learning Surrogates [49.84541884653309]
  凸離散最適化問題に対する現在の標準的なアプローチは、カットプレーンアルゴリズムを使うことである。 多くの汎用カット生成アルゴリズムが存在するにもかかわらず、大規模な離散最適化問題は、難易度に悩まされ続けている。 そこで本研究では,強化学習による切削平面アルゴリズムの高速化手法を提案する。
  論文  参考訳（メタデータ） (2023-07-17T20:11:56Z)
• An adaptive Bayesian quantum algorithm for phase estimation [0.0]
  平均絶対誤差と平均二乗誤差の最適2次スケーリングを実現するためのコヒーレンスに基づく位相推定アルゴリズムを提案する。 ノイズの存在下で、我々のアルゴリズムは理論的な下界に近づく誤差を生成する。
  論文  参考訳（メタデータ） (2023-03-02T19:00:01Z)
• Enhancing Quantum Algorithms for Quadratic Unconstrained Binary Optimization via Integer Programming [0.0]
  本研究では,最適化のための量子および古典的手法の可能性を統合する。 線形緩和により問題のサイズを小さくし、最小サイズの量子マシンで問題を処理できるようにした。 実量子ハードウェアの計算結果を多数提示する。
  論文  参考訳（メタデータ） (2023-02-10T20:12:53Z)
• Ising formulation of integer optimization problems for utilizing quantum annealing in iterative improvement strategy [1.14219428942199]
  繰り返し改善戦略において量子アニーリングを利用するために,整数最適化問題のイジング定式化を提案する。 基底状態と候補解との重なりがしきい値を超えた場合, 完全に連結されたフェロポッツモデルに対して一階相転移を回避できることを解析的に示す。
  論文  参考訳（メタデータ） (2022-11-08T02:12:49Z)
• Stochastic optimization algorithms for quantum applications [0.0]
  本稿では、一階法、二階法、量子自然勾配最適化法の使用法を概観し、複素数体で定義される新しいアルゴリズムを提案する。 全ての手法の性能は、変分量子固有解法、量子状態の量子制御、および量子状態推定に応用して評価される。
  論文  参考訳（メタデータ） (2022-03-11T16:17:05Z)
• Provably Faster Algorithms for Bilevel Optimization [54.83583213812667]
  バイレベル最適化は多くの重要な機械学習アプリケーションに広く適用されている。 両レベル最適化のための2つの新しいアルゴリズムを提案する。 両アルゴリズムが$mathcalO(epsilon-1.5)$の複雑さを達成し,既存のアルゴリズムを桁違いに上回っていることを示す。
  論文  参考訳（メタデータ） (2021-06-08T21:05:30Z)
• Lower Bounds and Optimal Algorithms for Smooth and Strongly Convex Decentralized Optimization Over Time-Varying Networks [79.16773494166644]
  通信ネットワークのノード間を分散的に保存するスムーズで強い凸関数の和を最小化するタスクについて検討する。 我々は、これらの下位境界を達成するための2つの最適アルゴリズムを設計する。 我々は,既存の最先端手法と実験的な比較を行うことにより,これらのアルゴリズムの理論的効率を裏付ける。
  論文  参考訳（メタデータ） (2021-06-08T15:54:44Z)
• Space-efficient binary optimization for variational computing [68.8204255655161]
  本研究では,トラベリングセールスマン問題に必要なキュービット数を大幅に削減できることを示す。 また、量子ビット効率と回路深さ効率のモデルを円滑に補間する符号化方式を提案する。
  論文  参考訳（メタデータ） (2020-09-15T18:17:27Z)
• Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth Nonlinear TD Learning [145.54544979467872]
  本稿では,各ステップごとに1つのデータポイントしか必要としない2つの単一スケールシングルループアルゴリズムを提案する。 本研究の結果は, 同時一次および二重側収束の形で表される。
  論文  参考訳（メタデータ） (2020-08-23T20:36:49Z)

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

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