論文の概要: A Hybrid Quantum-Classical Heuristic to solve large-scale Integer Linear
Programs
- arxiv url: http://arxiv.org/abs/2103.15433v2
- Date: Mon, 12 Jul 2021 06:11:59 GMT
- ステータス: 処理完了
- システム内更新日: 2023-04-06 06:19:07.011411
- Title: A Hybrid Quantum-Classical Heuristic to solve large-scale Integer Linear
Programs
- Title（参考訳）: 大規模整数線形プログラムを解くハイブリッド量子古典的ヒューリスティック
- Authors: Marika Svensson, Martin Andersson, Mattias Gr\"onkvist, Pontus
Vikst{\aa}l, Devdatt Dubhashi, Giulia Ferrini, and G\"oran Johansson
- Abstract要約: 本稿では、整数線形プログラムの解を見つけることができる任意の量子アルゴリズムをブランチ・アンド・プライス・アルゴリズムに統合する手法を提案する。
量子アルゴリズムの役割は、ブランチ・アンド・プライスに現れるサブプロブレムに対する整数解を見つけることである。
- 参考スコア（独自算出の注目度）: 0.4925222726301578
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We present a method that integrates any quantum algorithm capable of finding
solutions to integer linear programs into the Branch-and-Price algorithm, which
is regularly used to solve large-scale integer linear programs with a specific
structure. The role of the quantum algorithm is to find integer solutions to
subproblems appearing in Branch-and-Price. Obtaining optimal or near-optimal
integer solutions to these subproblems can increase the quality of solutions
and reduce the depth and branching factor of the Branch-and-Price algorithm and
hence reduce the overall running time. We investigate the viability of the
approach by considering the Tail Assignment problem and the Quantum Approximate
Optimization Algorithm (QAOA). Here, the master problem is the optimization
problem Set Partitioning or its decision version Exact Cover and can be
expressed as finding the ground state of an Ising spin glass Hamiltonian. For
Exact Cover, our numerical results indicate that the required algorithm depth
decreases with the number of feasible solutions for a given success probability
of finding a feasible solution. For Set Partitioning, on the other hand, we
find that for a given success probability of finding the optimal solution, the
required algorithm depth can increase with the number of feasible solutions if
the Hamiltonian is balanced poorly, which in the worst case is exponential in
the problem size. We therefore address the importance of properly balancing the
objective and constraint parts of the Hamiltonian. We empirically find that the
approach is viable with QAOA if polynomial algorithm depth can be realized on
quantum devices.
- Abstract（参考訳）: 本稿では、整数線形プログラムの解を見つけることのできる任意の量子アルゴリズムを、特定の構造を持つ大規模整数線形プログラムの解法としてよく用いられるブランチ・アンド・プライスアルゴリズムに統合する手法を提案する。
量子アルゴリズムの役割は、分枝価格で現れる部分問題に対する整数解を見つけることである。
これらの部分問題に対して最適あるいは最適に近い整数解を得ると、解の質が向上し、分岐価格アルゴリズムの深さと分岐係数が減少し、その結果、全体の実行時間を短縮できる。
本稿では,Tail Assignment 問題とQuantum Approximate Optimization Algorithm (QAOA) を考慮したアプローチの有効性を検討する。
ここで、主問題は最適化問題 Set Partitioning あるいは Exact Cover であり、Ising spin glass Hamiltonian の基底状態として表すことができる。
厳密なカバーについては, アルゴリズムの深さは, 実現可能な解を求める成功確率に対して, 実現可能な解の数によって減少することを示す。
一方、集合分割の場合、最適解を見つけるための与えられた成功確率に対して、ハミルトン方程式が不均衡であれば、必要となるアルゴリズム深さは実現可能な解の数によって増大し、最悪の場合、問題のサイズは指数関数的である。
したがって、ハミルトニアンの目的と制約部分の適切にバランスをとることが重要である。
量子デバイス上で多項式アルゴリズムの深さが実現できれば,この手法はQAOAで実現可能である。
関連論文リスト
- The Differentiable Feasibility Pump [49.55771920271201]
本稿では,従来の実現可能性ポンプとその追随点の多くを,特定のパラメータを持つ勾配差アルゴリズムとみなすことができることを示す。
この再解釈の中心的な側面は、伝統的なアルゴリズムがそのコストに関して線形緩和の解を区別することを観察することである。
論文 参考訳（メタデータ） (2024-11-05T22:26:51Z) - An Analysis of Quantum Annealing Algorithms for Solving the Maximum Clique Problem [49.1574468325115]
我々は、QUBO問題として表されるグラフ上の最大傾きを見つける量子D波アンナーの能力を解析する。
本稿では, 相補的な最大独立集合問題に対する分解アルゴリズムと, ノード数, 傾き数, 密度, 接続率, 解サイズの他のノード数に対する比を制御するグラフ生成アルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-06-11T04:40:05Z) - A Review on Quantum Approximate Optimization Algorithm and its Variants [47.89542334125886]
量子近似最適化アルゴリズム(Quantum Approximate Optimization Algorithm、QAOA)は、難解な最適化問題を解くことを目的とした、非常に有望な変分量子アルゴリズムである。
この総合的なレビューは、様々なシナリオにおけるパフォーマンス分析を含む、QAOAの現状の概要を提供する。
我々は,提案アルゴリズムの今後の展望と方向性を探りながら,選択したQAOA拡張と変種の比較研究を行う。
論文 参考訳（メタデータ） (2023-06-15T15:28:12Z) - Ising formulation of integer optimization problems for utilizing quantum
annealing in iterative improvement strategy [1.14219428942199]
繰り返し改善戦略において量子アニーリングを利用するために,整数最適化問題のイジング定式化を提案する。
基底状態と候補解との重なりがしきい値を超えた場合, 完全に連結されたフェロポッツモデルに対して一階相転移を回避できることを解析的に示す。
論文 参考訳（メタデータ） (2022-11-08T02:12:49Z) - Problem-Size Independent Angles for a Grover-Driven Quantum Approximate
Optimization Algorithm [0.0]
本稿では,Grover-driven,QAOA-prepared状態下でのハミルトニアンの期待値の計算をシステムサイズとは無関係に行うことができることを示す。
このような計算は、大きな問題の大きさの限界において、QAOAにおける角度のパフォーマンスと予測可能性に関する洞察を与えるのに役立つ。
論文 参考訳（メタデータ） (2022-08-22T17:18:25Z) - Quantum Goemans-Williamson Algorithm with the Hadamard Test and
Approximate Amplitude Constraints [62.72309460291971]
本稿では,n+1$ qubitsしか使用しないGoemans-Williamsonアルゴリズムの変分量子アルゴリズムを提案する。
補助量子ビット上で適切にパラメータ化されたユニタリ条件として目的行列を符号化することにより、効率的な最適化を実現する。
各種NPハード問題に対して,Goemans-Williamsonアルゴリズムの量子的効率的な実装を考案し,提案プロトコルの有効性を実証する。
論文 参考訳（メタデータ） (2022-06-30T03:15:23Z) - A quantum-inspired tensor network method for constrained combinatorial
optimization problems [5.904219009974901]
本稿では,一般に局所的に制約された最適化問題に対する量子インスパイアされたテンソルネットワークに基づくアルゴリズムを提案する。
我々のアルゴリズムは、興味のある問題に対してハミルトニアンを構築し、量子問題に効果的にマッピングする。
本研究は,本手法の有効性と応用の可能性を示すものである。
論文 参考訳（メタデータ） (2022-03-29T05:44:07Z) - Quantum constraint learning for quantum approximate optimization
algorithm [0.0]
本稿では,探索部分空間を厳しく制約するミキサーハミルトンを学習するための量子機械学習手法を提案する。
学習したユニタリを直接適応可能なアンサッツを使用してQAOAフレームワークにプラグインすることができる。
また,Wasserstein距離を用いた近似最適化アルゴリズムの性能を,制約なしで評価する直感的計量法を開発した。
論文 参考訳（メタデータ） (2021-05-14T11:31:14Z) - Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。
問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。
本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-01-07T08:00:02Z) - Space-efficient binary optimization for variational computing [68.8204255655161]
本研究では,トラベリングセールスマン問題に必要なキュービット数を大幅に削減できることを示す。
また、量子ビット効率と回路深さ効率のモデルを円滑に補間する符号化方式を提案する。
論文 参考訳（メタデータ） (2020-09-15T18:17:27Z) - Lower Bounds on Circuit Depth of the Quantum Approximate Optimization
Algorithm [0.3058685580689604]
回路深度に対する下位境界の同定に問題インスタンスの構造を用いる方法を示す。
我々は、MaxCut、MaxIndSet、およびVertex CoveringおよびBoolean satisifiabilityのいくつかのケースがQAOAアプローチに適していると主張している。
論文 参考訳（メタデータ） (2020-08-04T20:52:34Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。