論文の概要: Super-Quadratic Quantum Speedups for Combinatorial Optimization via Tilted Walks

• arxiv url: http://arxiv.org/abs/2609.40088v1
• Date: Wed, 30 Sep 2026 16:31:21 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-01 18:57:28.069462
• Title: Super-Quadratic Quantum Speedups for Combinatorial Optimization via Tilted Walks
• Title（参考訳）: Tilted Walksによる組合せ最適化のための超量子量子スピードアップ
• Abstract要約: 正確な最適化問題を解くための量子フレームワークである量子傾斜歩行を導入する。 我々は、基本マルコフ連鎖(ミキサー)の判別を客観的関数でバイアスする傾きハミルトニアンのパワーの平均を適用する。
• 参考スコア（独自算出の注目度）: 2.4493299476776778
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We introduce quantum tilted walks, a quantum algorithmic framework for solving exact combinatorial optimization problems. The framework applies an average of powers of a tilted Hamiltonian that biases the discriminant matrix of a base Markov chain (mixer) with the objective function. Our starting point is quantum short-path algorithms, which prepare the ground state of such a Hamiltonian and obtain super-quadratic speedups over exhaustive search for certain combinatorial optimization problems. Recently, Le Gall and Tamaki~(arXiv:2604.12131) developed a classical conditioning-and-search algorithm for weighted MAX-E$k$-LIN2 and weighted MAX-$k$-CSP. Under the same assumptions, their algorithm is only sub-quadratically slower than quantum short-path algorithms. Consequently, existing short-path algorithms do not establish a super-quadratic speedup over this stronger classical baseline. For maximization problems, we give conditions under which tilted walks increase the amplitude on the target state with high objective value when initialized from a starting state with lower objective value. This framework captures conditioning-and-search and yields super-quadratic speedups over it for the same problems. While our framework recovers quantum short-path algorithms as a special case, it neither requires ground-state preparation nor initialization in the ground state of the base mixer. We demonstrate these advantages on a synthetic optimization problem for which tilted walks achieve a super-quadratic speedup whereas the short-path algorithms do not.
• Abstract（参考訳）: 正確な組合せ最適化問題を解くための量子アルゴリズムフレームワークである量子傾斜歩行を導入する。 このフレームワークは、基本マルコフ連鎖(ミキサー)の判別行列と目的関数を偏見する傾いたハミルトンの力の平均を適用している。 我々の出発点である量子ショートパスアルゴリズムは、ハミルトニアンの基底状態を作成し、ある種の組合せ最適化問題に対する徹底的な探索よりも超四進法的なスピードアップを得る。 最近、Le Gall と Tamaki (arXiv:2604.12131) は MAX-E$k$-LIN2 と MAX-E$k$-CSP の古典的条件探索アルゴリズムを開発した。 同じ仮定の下では、それらのアルゴリズムは量子ショートパスアルゴリズムよりも4分の1遅いだけである。 したがって、既存のショートパスアルゴリズムは、この強い古典的ベースラインに対する超四進法的なスピードアップを確立しない。 最大化問題として、傾いた歩行が目標状態の振幅を高い目標値で増加させる条件を、目標値が低いスタート状態から初期化する場合に与える。 このフレームワークは条件付けと探索をキャプチャし、同じ問題に対して超クアッドレートのスピードアップをもたらす。 我々のフレームワークは量子ショートパスアルゴリズムを特別な場合として回収するが、基底ミキサーの基底状態における基底状態の準備や初期化は必要としない。 これらの利点は、傾いた歩行が超二乗スピードアップを達成する合成最適化問題において示されるが、ショートパスアルゴリズムは実現しない。

関連論文リスト

• Quartic quantum speedups for community detection [84.14713515477784]
  我々は,準量子スピードアップを実現するハイパーグラフコミュニティ検出のための量子アルゴリズムを開発した。 提案アルゴリズムは,従来検討されていた PCA や $p$XORSAT といった問題を超えて拡張した Kikuchi 法に基づいている。
  論文  参考訳（メタデータ） (2025-10-09T17:35:17Z)
• Learning Feasible Quantum States for Quadratic Constrained Binary Optimization Problems [41.23247424467223]
  我々はQCBOの制約を満たす量子状態の同値重ね合わせを生成する変動的アプローチを開発する。 結果として生じる同値な重ね合わせは、QUBO/QCBOを解く量子アルゴリズムの初期状態として使用できる。
  論文  参考訳（メタデータ） (2025-08-04T16:44:53Z)
• Branch-and-bound digitized counterdiabatic quantum optimization [39.58317527488534]
  分岐とバウンドのアルゴリズムは、厳密な下界を得るために目的関数の緩和に依存する凸最適化問題を効果的に解く。 本稿では,緩和困難に対処する分枝・分枝・分枝・分枝・分枝対応量子最適化法 (BB-DCQO) を提案する。
  論文  参考訳（メタデータ） (2025-04-21T18:19:19Z)
• Classical optimization with imaginary time block encoding on quantum computers: The MaxCut problem [1.354560757162539]
  ITE-BEと呼ばれる新しい手法を開発した。 我々は,本手法が他の量子アルゴリズムとうまく結合できることを実証した。
  論文  参考訳（メタデータ） (2024-11-16T08:17:36Z)
• Optimization by Decoded Quantum Interferometry [38.063836468778895]
  Decoded Quantum Interferometry (DQI) は、量子フーリエ変換を用いて、復号化問題に対する最適化問題を削減する量子アルゴリズムである。 有限体上の最適適合を近似するために、DQIは既知の古典的アルゴリズムよりも超多項式的なスピードアップを達成する。
  論文  参考訳（メタデータ） (2024-08-15T17:47:42Z)
• Quantum speedup of leverage score sampling and its application [0.0]
  本稿では,レバレッジスコアの計算を高速化する量子アルゴリズムを提案する。 応用として,ベクトル解出力を用いた剛性回帰問題に対する新しい量子アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-01-15T14:40:18Z)
• Solving the semidefinite relaxation of QUBOs in matrix multiplication time, and faster with a quantum computer [0.157286095422595]
  いくつかの量子SDOソルバは、低精度な状態において高速化を提供する。 この事実を利用してアルゴリズムの精度への依存を指数関数的に改善する。 我々のアルゴリズムの量子実装は、$mathcalO left(ns + n1.5 cdot textpolylog left(n, | C |_F, frac1epsilon right)$の最悪の実行時間を示す。
  論文  参考訳（メタデータ） (2023-01-10T23:12:05Z)
• QAOA-in-QAOA: solving large-scale MaxCut problems on small quantum machines [81.4597482536073]
  量子近似最適化アルゴリズム(QAOAs)は、量子マシンのパワーを利用し、断熱進化の精神を継承する。 量子マシンを用いて任意の大規模MaxCut問題を解くためにQAOA-in-QAOA(textQAOA2$)を提案する。 提案手法は,大規模最適化問題におけるQAOAsの能力を高めるために,他の高度な戦略にシームレスに組み込むことができる。
  論文  参考訳（メタデータ） (2022-05-24T03:49:10Z)

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

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