論文の概要: Quantum Optimization in Loc(Q)ation Science: QUBO Formulations, Benchmark Problems, and a Computational Study
- arxiv url: http://arxiv.org/abs/2602.10951v1
- Date: Wed, 11 Feb 2026 15:39:26 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-02-12 21:44:02.054812
- Title: Quantum Optimization in Loc(Q)ation Science: QUBO Formulations, Benchmark Problems, and a Computational Study
- Title（参考訳）: Loc(Q)ation Scienceにおける量子最適化:QUBOの定式化、ベンチマーク問題、計算学的研究
- Authors: Felix P. Broesamle, Stefan Nickel,
- Abstract要約: Quadratic Unconstrained Binary Optimizationは、$mathbfNP$-hardの幅広いクラスのための統一モデリングフレームワークを提供する。
我々は、位置科学、ネットワーク設計、ロジスティクスにおけるいくつかの基本的な問題に対するQUBOの定式化を開発する。
これらのQUBOの定式化は、量子アルゴリズムと量子ハードウェアを評価するための代表的なベンチマーク問題として機能する。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Recent advances in quantum computing and the increasing availability of quantum hardware have substantially enhanced the practical relevance of quantum approaches to discrete optimization. Among these, the Quadratic Unconstrained Binary Optimization (QUBO) formulation provides a unifying modeling framework for a broad class of $\mathbf{NP}$-hard problems and is naturally suited to quantum computing and quantum-inspired algorithms. Location science, network design, and logistics represent core application domains of discrete optimization, combining high practical impact with substantial computational challenges. In this work, we develop QUBO formulations for several fundamental problems in these domains, including a nonlinear integer formulation of the Discrete Ordered Median Problem (DOMP). Beyond their modeling relevance, these QUBO formulations serve as representative benchmark problems for assessing quantum algorithms and quantum hardware. We further derive a tight bound for the penalty parameter ensuring equivalence between the QUBO formulation and its underlying integer program. Finally, we conduct a comprehensive computational study using QAOA, WS-QAOA, and classical heuristics for QUBO instances of the $p$-Median Problem and the Fixed-Charge Facility Location Problem (FCFLP), and introduce two effective warm-start strategies for WS-QAOA based on its linear programming relaxation.
- Abstract（参考訳）: 量子コンピューティングの最近の進歩と量子ハードウェアの可用性の向上により、離散最適化への量子アプローチの実践的妥当性が大幅に向上した。
これらのうち、Quadratic Unconstrained Binary Optimization (QUBO) の定式化は、$\mathbf{NP}$-hardの幅広いクラスに対する統一モデリングフレームワークを提供し、量子コンピューティングや量子インスパイアされたアルゴリズムに自然に適している。
ロケーションサイエンス、ネットワークデザイン、ロジスティクスは、離散最適化のコアアプリケーションドメインであり、実用的な影響と重大な計算上の課題を組み合わせたものである。
本研究では,これらの領域において,離散順序メディア問題(DOMP)の非線形整数定式化を含むいくつかの基本問題に対するQUBO定式化を開発する。
モデリングの関連性以外にも、これらのQUBOの定式化は量子アルゴリズムと量子ハードウェアを評価するための代表的なベンチマーク問題として機能する。
さらに、QUBOの定式化とそれに基づく整数プログラムの等価性を確保するために、ペナルティパラメータの厳密な境界を導出する。
最後に,QAOA,WS-QAOA,および$p$-Median ProblemおよびFCFLPのQUBOインスタンスに対する古典的ヒューリスティックスを用いた総合計算を行い,その線形プログラミング緩和に基づいて,WS-QAOAに対する2つの効果的なウォームスタート戦略を導入する。
関連論文リスト
- Quantum Annealing for Combinatorial Optimization: Foundations, Architectures, Benchmarks, and Emerging Directions [0.0]
科学、工学、産業における重要な意思決定問題は最適化に基づいている。
我々は, 断熱量子力学, Ising と QUBO モデル, 確率的および非確率的ハミルトニアン, 現代のフラックス・キュービット・アニールへのダイアバティック・トランジションに関する統一的な枠組みを開発する。
埋め込みとエンコーディングのオーバーヘッドがスケーラビリティとパフォーマンスの最大の部分であることに気付きました。
論文 参考訳（メタデータ） (2026-02-03T04:51:26Z) - Quantum optimisation applied to the Quadratic Assignment Problem [4.483208369550461]
本稿では,量子ウォークに基づく最適化アルゴリズム (NV-QWOA) を用いて,2次アサインメント問題 (QAP) の小型解法の性能について検討する。
目的関数評価の回数と、5から10の施設を持つQAPインスタンス全体にわたる最適あるいはほぼ最適のソリューションに一貫して到達するのに必要となるアルゴリズムの反復数という2つの指標を用いて性能を評価する。
我々の研究は、複雑な量子問題に対する量子ウォークの実用性を強調し、将来の量子最適化アルゴリズムの基礎を確立した。
論文 参考訳（メタデータ） (2026-01-03T07:50:03Z) - An Introduction to the Quantum Approximate Optimization Algorithm [51.56484100374058]
チュートリアルは変分量子回路とQUBO問題の概要から始まる。
次に、ハミルトンの定式化、ゲート分解、サンプル応用など、QAOAの詳細を探索する。
このチュートリアルはこれらの概念を高階ハミルトニアンに拡張し、関連する対称性と回路構成について議論する。
論文 参考訳（メタデータ） (2025-11-23T09:54:20Z) - Branch-and-bound digitized counterdiabatic quantum optimization [39.58317527488534]
分岐とバウンドのアルゴリズムは、厳密な下界を得るために目的関数の緩和に依存する凸最適化問題を効果的に解く。
本稿では,緩和困難に対処する分枝・分枝・分枝・分枝・分枝対応量子最適化法 (BB-DCQO) を提案する。
論文 参考訳（メタデータ） (2025-04-21T18:19:19Z) - A Comparative Study of Quantum Optimization Techniques for Solving Combinatorial Optimization Benchmark Problems [4.266376725904727]
本稿では,NP-hard問題に対する量子最適化手法の評価を目的とした,包括的なベンチマークフレームワークを提案する。
本フレームワークは,多次元クナップサック問題(MDKP),最大独立集合(MIS),二次割当問題(QAP),市場シェア問題(MSP)など,主要な課題に重点を置いている。
論文 参考訳（メタデータ） (2025-03-15T13:02:22Z) - Benchmarking of quantum and classical SDP relaxations for QUBO formulations of real-world logistics problems [0.4636927061010061]
擬似的非制約二項最適化問題の半定値プログラミング緩和に関する膨大な実験的検討を行った。
オープンな)車両ルーティング問題と(親和性に基づく)スロットリング問題に関する業界ベースの事例のQUBO再構成を検証した。
論文 参考訳（メタデータ） (2025-03-13T18:51:45Z) - Bias-field digitized counterdiabatic quantum optimization [39.58317527488534]
我々はこのプロトコルをバイアス場デジタルダイアバティック量子最適化(BF-DCQO)と呼ぶ。
私たちの純粋に量子的なアプローチは、古典的な変分量子アルゴリズムへの依存を排除します。
基底状態の成功確率のスケーリング改善を実現し、最大2桁まで増大する。
論文 参考訳（メタデータ） (2024-05-22T18:11:42Z) - Quantum Annealing for Single Image Super-Resolution [86.69338893753886]
単一画像超解像(SISR)問題を解くために,量子コンピューティングに基づくアルゴリズムを提案する。
提案したAQCアルゴリズムは、SISRの精度を維持しつつ、古典的なアナログよりも向上したスピードアップを実現する。
論文 参考訳（メタデータ） (2023-04-18T11:57:15Z) - Adiabatic Quantum Computing for Multi Object Tracking [170.8716555363907]
マルチオブジェクト追跡(MOT)は、オブジェクト検出が時間を通して関連付けられているトラッキング・バイ・検出のパラダイムにおいて、最もよくアプローチされる。
これらの最適化問題はNPハードであるため、現在のハードウェア上の小さなインスタンスに対してのみ正確に解決できる。
本手法は,既成整数計画法を用いても,最先端の最適化手法と競合することを示す。
論文 参考訳（メタデータ） (2022-02-17T18:59:20Z) - Polynomial unconstrained binary optimisation inspired by optical
simulation [52.11703556419582]
制約のないバイナリ最適化の問題を解決するために,光コヒーレントIsingマシンにヒントを得たアルゴリズムを提案する。
提案アルゴリズムを既存のPUBOアルゴリズムに対してベンチマークし,その優れた性能を観察する。
タンパク質の折り畳み問題や量子化学問題へのアルゴリズムの適用は、PUBO問題による電子構造問題の近似の欠点に光を当てる。
論文 参考訳（メタデータ） (2021-06-24T16:39:31Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。