論文の概要: Practical lower bounds for hybrid quantum interior point methods in linear programming
- arxiv url: http://arxiv.org/abs/2604.24362v1
- Date: Mon, 27 Apr 2026 11:54:23 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-04-28 17:12:07.966275
- Title: Practical lower bounds for hybrid quantum interior point methods in linear programming
- Title（参考訳）: 線形計画法におけるハイブリッド量子内点法のための実践的下界
- Authors: Lennart Binkowski,
- Abstract要約: 量子インテリアポイント法(QIPMs)は、線形プログラミングの古典的解法よりも高速化を約束する。
従来のオープンソースHiGHSと比較して,QIPMパイプラインの実用的利点をすでに排除できるかどうかを評価する。
私はQIPMに最も優れた機能的解法QLSAを装備し、2つのニュートン系の定式化を評価する。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Quantum interior point methods (QIPMs) promise polynomial speed-ups over classical solvers for linear programming by outsourcing the solution of Newton linear systems to quantum linear solvers (QLSAs). However, asymptotic speed-ups do not necessarily translate to practical advantages on realistic problem instances. In this work, I evaluate whether practical advantage of a standard hybrid QIPM pipeline can already be excluded relative to the classical open-source solver HiGHS on a broad and diverse collection of LP instances spanning eight problem families, including public benchmark libraries, such as MIPlib, and relaxations of combinatorial optimisation problems. Following the hybrid benchmarking paradigm initiated by Cade et al., I derive rigorous lower bounds on the quantum runtime under a series of highly benevolent assumptions and compare them against classical runtimes. I equip the QIPMs with the best-performing functional QLSA, the Chebyshev-based method, as identified by Lefterovici et al., and evaluate two Newton system formulations proposed by Mohammadisiahroudi et al.: the modified normal equation system and the orthogonal subspace system. The exclusion analysis yields a consistent negative picture: across all instances and for any realistic quantum cycle duration, the quantum runtime lower bounds already exceed the classical runtimes, establishing that these hybrid QIPMs will offer no practical advantage over good classical solvers for realistic linear programming instances.
- Abstract（参考訳）: 量子内点法(QIPM)は、ニュートン線形系の解を量子線形解法(QLSA)にアウトソーシングすることで、古典的な線形計画法よりも多項式の高速化を約束する。
しかし、漸近的なスピードアップは、現実的な問題の場合において実用上の利点に必ずしも変換されない。
本研究では,MIPlibなどの公開ベンチマークライブラリや組合せ最適化問題の緩和など,8つの問題ファミリにまたがるLPインスタンスの広範かつ多種多様なコレクションにおいて,従来のオープンソース解決器であるHiGHSと比較して,標準ハイブリッドQIPMパイプラインの実用的メリットをすでに排除できるかどうかを評価する。
Cade らによって始められたハイブリッドベンチマークのパラダイムに従えば、量子ランタイムの厳密な下限を、一連の高利害な仮定の下で導き出し、それらを古典的なランタイムと比較する。
I set the QIPMs with the best-performing functional QLSA, the Chebyshev-based method as identified by Lefterovici et al , and evaluate two Newton system formulations proposed by Mohammadisiahroudi et al : the modified normal equation system and the orthogonal subspace system。
すべてのインスタンスと任意の現実的な量子サイクルの期間において、量子ランタイムの下位境界はすでに古典的なランタイムを超えており、これらのハイブリッドQIPMは、現実的な線形プログラミングインスタンスに対する優れた古典的解法よりも実践的な優位性を得られない。
関連論文リスト
- Iterative Optimization with Partial Convergence Guarantees on Neutral Atom Quantum Computers [0.0]
Lp-Qutsは、NAQCサンプルラーを古典的な切断平面アルゴリズムに統合するハイブリッド量子古典的フレームワークである。
我々は、Lp-Qutsを古典最適化フレームワークに効果的に組み込んで、量子資源を減らした準最適解を提供する方法を示す。
論文 参考訳（メタデータ） (2026-03-30T19:12:21Z) - Global Optimization for Parametrized Quantum Circuits [3.558201566667322]
トレーニング可能なパラメータを一定数有する量子回路の実践的なクラスのトレーニングについて検討する。
我々の主な成果は、完全にランダム化された近似スキーム (FPRAS) である。
変分アルゴリズムにおける標準的なハイブリッド量子古典的トレーニングとは異なり、我々の手法は計算を2つの異なる段階に分けている。
論文 参考訳（メタデータ） (2026-03-23T09:49:40Z) - Quantum Random Feature Method for Solving Partial Differential Equations [36.58357595906332]
量子コンピューティングは、古典的な手法よりも指数的なスピードアップの可能性を秘めているため、科学計算の可能性を秘めている。
本研究では,数値解析とニューラル解析の両方の利点を利用する量子ランダム法(QRFM)を提案する。
論文 参考訳（メタデータ） (2025-10-09T08:42:09Z) - Quantum Annealing for Machine Learning: Applications in Feature Selection, Instance Selection, and Clustering [41.94295877935867]
量子解法と古典解法をともに実装し,その有効性を比較する。
特徴選択のために,特徴量と冗長性のバランスをとるいくつかのQUBO構成を提案する。
事例選択では,既存手法を拡張した事例レベルの重要度尺度を提案する。
クラスタリングには古典的クラスタリングとQUBOベースのメドイドリファインメントを併用した古典的量子パイプラインを組み込む。
論文 参考訳（メタデータ） (2025-07-20T17:59:14Z) - Practical Application of the Quantum Carleman Lattice Boltzmann Method in Industrial CFD Simulations [44.99833362998488]
この研究は、格子ボルツマン法(LBM)に基づくCFDへのハイブリッド量子古典的アプローチの実用的な数値評価を提示する。
本手法は, 異なる境界条件, 周期性, バウンスバック, 移動壁を有する3つのベンチマークケースで評価した。
提案手法の有効性を検証し,10～3ドル程度の誤差忠実度と,実際の量子状態サンプリングに十分な確率を達成できた。
論文 参考訳（メタデータ） (2025-04-17T15:41:48Z) - Quantum Annealing for Combinatorial Optimization: A Benchmarking Study [39.125366249242646]
現状の量子解法は,従来の解法よりも精度が0.013%高く,解法時間も6,561xであることを示す。
この結果から,特にハイブリッド構成において,従来のQAよりもQAを活用できるという利点が浮かび上がっている。
論文 参考訳（メタデータ） (2025-04-08T16:43:24Z) - Integrating Quantum Algorithms Into Classical Frameworks: A Predictor-corrector Approach Using HHL [0.562479170374811]
我々は、Harrow, Hassidim and Lloyd (HHL) によって提案された方程式の線形系に対するよく知られたアルゴリズムを、直接解法ではなく予測子-相関子に適応させることにより適用する。
この戦略は、多くの古典的アルゴリズムでよく見られる計算コストの高いステップのインテリジェントな省略を可能にし、同時に量子状態の抽出に関連する悪名高い読み出し問題を緩和する。
このアプローチの汎用性は、滑らかな粒子流体力学、プラズマシミュレーション、反応性流れ構成など、様々な分野の応用を通して説明される。
論文 参考訳（メタデータ） (2024-06-28T15:31:10Z) - A Hybrid Quantum-Classical Approach to the Electric Mobility Problem [0.8796261172196743]
NP-hard Electric Vehicle Fleet Charging and Allocation Problemのためのハイブリッド量子古典ルーチンを提案する。
分解法の性能を古典的・量子的メタヒューリスティックスで評価する。
提案手法の主な利点は、多くの不等式制約のある現実的な問題に対して量子ベースの方法を可能にすることである。
論文 参考訳（メタデータ） (2023-10-04T12:14:56Z) - Q-FW: A Hybrid Classical-Quantum Frank-Wolfe for Quadratic Binary
Optimization [44.96576908957141]
本稿では,量子コンピュータ上での2次線形反復問題を解くために,フランク・ウルフアルゴリズム(Q-FW)に基づく古典量子ハイブリッドフレームワークを提案する。
論文 参考訳（メタデータ） (2022-03-23T18:00:03Z) - Near Term Algorithms for Linear Systems of Equations [0.0]
本稿では,進化的AnsatzのVQLS(EAVQLS)への最初の応用,論理的Ansatz VQLS(LAVQLS)の最初の実装,実量子ハードウェア上でのCQS法の原理実証の第一弾などについて述べる。
論文 参考訳（メタデータ） (2021-08-25T17:35:52Z) - Q-Match: Iterative Shape Matching via Quantum Annealing [64.74942589569596]
形状対応を見つけることは、NP-hard quadratic assignment problem (QAP)として定式化できる。
本稿では,アルファ拡大アルゴリズムに触発されたQAPの反復量子法Q-Matchを提案する。
Q-Match は、実世界の問題にスケールできるような長文対応のサブセットにおいて、反復的に形状マッチング問題に適用できる。
論文 参考訳（メタデータ） (2021-05-06T17:59:38Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。