論文の概要: A Quantum Constraint Generation Framework for Binary Linear Programs
- arxiv url: http://arxiv.org/abs/2503.21222v1
- Date: Thu, 27 Mar 2025 07:24:33 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-03-28 12:51:16.170949
- Title: A Quantum Constraint Generation Framework for Binary Linear Programs
- Title（参考訳）: バイナリ線形プログラムのための量子制約生成フレームワーク
- Authors: András Czégel, Boglárka G. -Tóth,
- Abstract要約: 量子コンピュータを用いたバイナリ線形プログラミング(BLP)のための新しい手法を提案する。
量子最適化アルゴリズム(ハイブリッドまたは量子専用)は現在、ICPのためのスタンドアロンの解法である。
本研究では,任意の量子最適化アルゴリズムを量子情報古典制約生成フレームワークにラップする。
- 参考スコア（独自算出の注目度）: 0.0
- License:
- Abstract: We propose a new approach to utilize quantum computers for binary linear programming (BLP), which can be extended to general integer linear programs (ILP). Quantum optimization algorithms, hybrid or quantum-only, are currently general purpose, standalone solvers for ILP. However, to consider them practically useful, we expect them to overperform the current state of the art classical solvers. That expectation is unfair to quantum algorithms: in classical ILP solvers, after many decades of evolution, many different algorithms work together as a robust machine to get the best result. This is the approach we would like to follow now with our quantum 'solver' solutions. In this study we wrap any suitable quantum optimization algorithm into a quantum informed classical constraint generation framework. First we relax our problem by dropping all constraints and encode it into an Ising Hamiltonian for the quantum optimization subroutine. Then, by sampling from the solution state of the subroutine, we obtain information about constraint violations in the initial problem, from which we decide which coupling terms we need to introduce to the Hamiltonian. The coupling terms correspond to the constraints of the initial binary linear program. Then we optimize over the new Hamiltonian again, until we reach a feasible solution, or other stopping conditions hold. Since one can decide how many constraints they add to the Hamiltonian in a single step, our algorithm is at least as efficient as the (hybrid) quantum optimization algorithm it wraps. We support our claim with results on small scale minimum cost exact cover problem instances.
- Abstract（参考訳）: 本稿では,汎用整数線形プログラム (ILP) に拡張可能な2進線形プログラム (BLP) に量子コンピュータを利用する新しい手法を提案する。
量子最適化アルゴリズム(ハイブリッドまたは量子専用)は現在、ICPのためのスタンドアロンの解法である。
しかし、これらが実用上有用であると考えるためには、現在の最先端の古典的解法よりも優れていると期待する。
古典的なILPソルバでは、何十年にもわたって進化してきた後、多くの異なるアルゴリズムが、最高の結果を得るために堅牢なマシンとして機能する。
これは、我々の量子「解決」ソリューションで現在フォローしたいアプローチです。
本研究では,任意の量子最適化アルゴリズムを量子情報古典制約生成フレームワークにラップする。
まず、全ての制約を解き、量子最適化サブルーチンのイジング・ハミルトンにエンコードすることで問題を緩和する。
そして、サブルーチンの解状態からサンプリングすることにより、初期問題における制約違反に関する情報を得る。
結合項は初期バイナリ線形プログラムの制約に対応する。
そして、新しいハミルトニアンを再び最適化し、実現可能な解や他の停止条件が保たれるまで計算する。
1つのステップでハミルトニアンにどれだけの制約を加えるかを決定することができるので、我々のアルゴリズムは、包む(ハイブリッド)量子最適化アルゴリズムと同じくらい効率的である。
我々は,小規模で最小限のコストでカバー問題に対処できるという主張を支持している。
関連論文リスト
- Quantum Subroutines in Branch-Price-and-Cut for Vehicle Routing [0.0]
この研究で、限られた資源を持つ量子がNPハード問題に対する大規模な正確な最適化アルゴリズムにどのように統合できるかを実証する。
我々のアルゴリズムの重要な特徴は、量子によって返される最良の解からではなく、あるコスト閾値以下の全ての解から得られることである。
論文 参考訳（メタデータ） (2024-12-20T08:27:23Z) - 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) - A quantum annealing approach to the minimum distance problem of quantum codes [0.0]
本稿では,量子安定化器符号の最小距離を準拘束的二項最適化問題として再定式化することで計算する手法を提案する。
D-Wave Advantage 4.1quantum annealerと比較することにより,本手法の実用性を示す。
論文 参考訳（メタデータ） (2024-04-26T21:29:42Z) - Q-CHOP: Quantum constrained Hamiltonian optimization [2.7022651232296946]
量子制約ハミルトン最適化(Q-CHOP)と呼ばれる制約付き最適化のための新しい量子アルゴリズムを提案する。
基本的な考え方は、常にハミルトンの制約を強制し、実現可能な状態の部分空間への進化を制限することである。
ペナルティ項を用いた制約付き一般用アダバティックアルゴリズムに対して,Q-CHOPをベンチマークした。
論文 参考訳（メタデータ） (2024-03-08T20:03:59Z) - Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。
量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
論文 参考訳（メタデータ） (2022-12-06T22:01:49Z) - Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
Bernstein-Vaziraniアルゴリズムは、オラクルに符号化されたビット文字列を決定できる。
我々はベルンシュタイン・ヴァジラニアルゴリズムの量子資源を詳細に分析する。
絡み合いがない場合、初期状態における量子コヒーレンス量とアルゴリズムの性能が直接関係していることが示される。
論文 参考訳（メタデータ） (2022-05-26T20:32:36Z) - 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) - Adiabatic Quantum Graph Matching with Permutation Matrix Constraints [75.88678895180189]
3次元形状と画像のマッチング問題は、NPハードな置換行列制約を持つ二次代入問題(QAP)としてしばしば定式化される。
本稿では,量子ハードウェア上での効率的な実行に適した制約のない問題として,いくつかのQAPの再構成を提案する。
提案アルゴリズムは、将来の量子コンピューティングアーキテクチャにおいて、より高次元にスケールする可能性がある。
論文 参考訳（メタデータ） (2021-07-08T17:59:55Z) - Solving Quadratic Unconstrained Binary Optimization with
divide-and-conquer and quantum algorithms [0.0]
分割・対数手法を用いて、元の問題を小さな問題の集合に還元する。
この手法は任意のQUBOインスタンスに適用でき、全古典的またはハイブリッドな量子古典的アプローチにつながる。
論文 参考訳（メタデータ） (2021-01-19T19:00:40Z) - Quantum Assisted Eigensolver [0.0]
本研究では,ハミルトニアンの基底状態と基底状態エネルギーを近似するハイブリッド量子古典アルゴリズムを提案する。
アルゴリズムの量子部分からの出力を古典コンピュータの入力として利用する。
論文 参考訳（メタデータ） (2020-09-23T08:33:18Z) - Quantum Gram-Schmidt Processes and Their Application to Efficient State
Read-out for Quantum Algorithms [87.04438831673063]
本稿では、生成した状態の古典的ベクトル形式を生成する効率的な読み出しプロトコルを提案する。
我々のプロトコルは、出力状態が入力行列の行空間にある場合に適合する。
我々の技術ツールの1つは、Gram-Schmidt正則手順を実行するための効率的な量子アルゴリズムである。
論文 参考訳（メタデータ） (2020-04-14T11:05:26Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。