論文の概要: Optimal Scaling Quantum Interior Point Method for Linear Optimization

• arxiv url: http://arxiv.org/abs/2512.04510v1
• Date: Thu, 04 Dec 2025 06:44:22 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-12-05 21:11:46.027427
• Title: Optimal Scaling Quantum Interior Point Method for Linear Optimization
• Title（参考訳）: 線形最適化のための最適スケーリング量子内点法
• Authors: Mohammadhossein Mohammadisiahroudi, Zeguan Wu, Pouya Sampourmahani, Jun-Kai You, Tamás Terlaky,
• Abstract要約: 本稿では,量子コンピュータ上でシステムを構築し,解決する新しい量子IPMを提案する。 このフレームワークは、完全に高密度なLO問題に対して$mathcalO(n2)$の最適な最悪のスケーリングを実現する。 我々のアルゴリズムは量子複雑性が$mathcalO(n1.5 _A log1)$QRAMへのクエリと$mathcalO(n2 log(frac1)$古典演算である。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The emergence of huge-scale, data-intensive linear optimization (LO) problems in applications such as machine learning has driven the need for more computationally efficient interior point methods (IPMs). While conventional IPMs are polynomial-time algorithms with rapid convergence, their per-iteration cost can be prohibitively high for dense large-scale LO problems. Quantum linear system solvers have shown potential in accelerating the solution of linear systems arising in IPMs. In this work, we introduce a novel almost-exact quantum IPM, where the Newton system is constructed and solved on a quantum computer, while solution updates occur on a classical machine. Additionally, all matrix-vector products are performed on the quantum hardware. This hybrid quantum-classical framework achieves an optimal worst-case scaling of $\mathcal{O}(n^2)$ for fully dense LO problems. To ensure high precision, despite the limited accuracy of quantum operations, we incorporate iterative refinement techniques both within and outside the proposed IPM iterations. The proposed algorithm has a quantum complexity of $\mathcal{O}(n^{1.5} κ_A \log(\frac{1}ε))$ queries to QRAM and $\mathcal{O}(n^2 \log(\frac{1}ε))$ classical arithmetic operations. Our method outperforms the worst-case complexity of prior classical and quantum IPMs, offering a significant improvement in scalability and computational efficiency.
• Abstract（参考訳）: 機械学習のようなアプリケーションにおける大規模でデータ集約的な線形最適化(LO)問題の出現により、より計算効率の良いインテリアポイント法(IPM)の必要性が高まった。 従来のIMMは、高速収束の多項式時間アルゴリズムであるが、大規模なLO問題に対して、解当コストは禁断的に高い。 量子線形系解法は、IPMで生じる線形系の解を加速する可能性を示している。 本研究では,ニュートン系を量子コンピュータ上で構築・解き,解の更新を古典的マシン上で行う新しい量子IPMを提案する。 さらに、全ての行列ベクトル積が量子ハードウェア上で実行される。 このハイブリッド量子古典的フレームワークは、完全密度LO問題に対して$\mathcal{O}(n^2)$の最適な最悪のスケーリングを実現する。 量子演算の精度が限られているにもかかわらず、高い精度を確保するため、提案したIMMイテレーションの内外の両方で反復的精細化手法を取り入れる。 提案アルゴリズムは量子複雑性が$\mathcal{O}(n^{1.5} κ_A \log(\frac{1}ε))$QRAMへのクエリと$\mathcal{O}(n^2 \log(\frac{1}ε))$古典演算である。 提案手法は,従来の古典的および量子的IPMの最悪の複雑性よりも優れており,スケーラビリティと計算効率が大幅に向上している。

関連論文リスト

• 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)
• 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)
• Enhancing Quantum Algorithms for Quadratic Unconstrained Binary Optimization via Integer Programming [0.0]
  本研究では,最適化のための量子および古典的手法の可能性を統合する。 線形緩和により問題のサイズを小さくし、最小サイズの量子マシンで問題を処理できるようにした。 実量子ハードウェアの計算結果を多数提示する。
  論文  参考訳（メタデータ） (2023-02-10T20:12:53Z)
• An Inexact Feasible Quantum Interior Point Method for Linearly Constrained Quadratic Optimization [0.0]
  量子線形システムアルゴリズム(QLSA)は、線形システムの解法に依存するアルゴリズムを高速化する可能性がある。 本研究では, 線形制約付き2次最適化問題の解法において, 実効性のないQIPM(Inexact-Feasible QIPM)を提案する。
  論文  参考訳（メタデータ） (2023-01-13T01:36:13Z)
• Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
  量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。 量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
  論文  参考訳（メタデータ） (2022-12-06T22:01:49Z)
• Automatic and effective discovery of quantum kernels [41.61572387137452]
  量子コンピューティングは、カーネルマシンが量子カーネルを利用してデータ間の類似度を表現できるようにすることで、機械学習モデルを強化することができる。 本稿では,ニューラルアーキテクチャ検索やAutoMLと同じような最適化手法を用いて,この問題に対するアプローチを提案する。 その結果、高エネルギー物理問題に対する我々のアプローチを検証した結果、最良のシナリオでは、手動設計のアプローチに関して、テストの精度を一致または改善できることが示された。
  論文  参考訳（メタデータ） (2022-09-22T16:42:14Z)
• Efficient Use of Quantum Linear System Algorithms in Interior Point Methods for Linear Optimization [0.0]
  線形最適化問題を解くために、非現実的な量子内点法を開発した。 また、量子ソルバの過度な時間なしで、反復リファインメントによって正確な解を得る方法についても論じる。
  論文  参考訳（メタデータ） (2022-05-02T21:30:56Z)
• Adiabatic Quantum Computing for Multi Object Tracking [170.8716555363907]
  マルチオブジェクト追跡(MOT)は、オブジェクト検出が時間を通して関連付けられているトラッキング・バイ・検出のパラダイムにおいて、最もよくアプローチされる。 これらの最適化問題はNPハードであるため、現在のハードウェア上の小さなインスタンスに対してのみ正確に解決できる。 本手法は,既成整数計画法を用いても,最先端の最適化手法と競合することを示す。
  論文  参考訳（メタデータ） (2022-02-17T18:59:20Z)
• Space-efficient binary optimization for variational computing [68.8204255655161]
  本研究では,トラベリングセールスマン問題に必要なキュービット数を大幅に削減できることを示す。 また、量子ビット効率と回路深さ効率のモデルを円滑に補間する符号化方式を提案する。
  論文  参考訳（メタデータ） (2020-09-15T18:17:27Z)

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

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