論文の概要: A quantum search method for quadratic and multidimensional knapsack problems
- arxiv url: http://arxiv.org/abs/2503.22325v1
- Date: Fri, 28 Mar 2025 10:58:26 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-03-31 15:28:59.801928
- Title: A quantum search method for quadratic and multidimensional knapsack problems
- Title（参考訳）: 二次および多次元クナップサック問題の量子探索法
- Authors: Sören Wilkening, Andreea-Iulia Lefterovici, Lennart Binkowski, Marlene Funck, Michael Perk, Robert Karimov, Sándor Fekete, Tobias J. Osborne,
- Abstract要約: 量子ツリージェネレータ(QTG)を0-1クナップサック問題、0-1クナップサック問題(QKP)、多次元クナップサック問題(MDKP)に拡張する。
QTGは与えられたインスタンスに対するすべての実現可能な解の重ね合わせを構築するので、有望な状態準備ルーチンとして利用することができる。
古典的解法であるグロビに対して,QKPとMDKPにおけるアルゴリズムの性能を評価する。
- 参考スコア（独自算出の注目度）: 0.0
- License:
- Abstract: Solving combinatorial optimization problems is a promising application area for quantum algorithms in real-world scenarios. In this work, we extend the "Quantum Tree Generator" (QTG), previously proposed for the 0-1 Knapsack Problem, to the 0-1 Quadratic Knapsack Problem (QKP) and the Multidimensional Knapsack Problem (MDKP). The QTG constructs a superposition of all feasible solutions for a given instance and can therefore be utilized as a promising state preparation routine within amplitude amplification to produce high-quality solutions. Previously, QTG-based search was tested on the 0-1 Knapsack Problem, where it demonstrated the potential for practical quantum advantage, once quantum computers with a few hundred logical and fully connected qubits are available. Here, we evaluate the algorithm's performance on QKP and MDKP against the classical solver Gurobi. To facilitate large-scale evaluations, we employ an advanced benchmarking technique that enables runtime predictions for instances with up to 2000 variables for QKP and up to 1500 variables and 100 constraints for MDKP. Our results indicate that QTG-based search can produce high-quality solutions with competitive runtimes for QKP. However, its performance declines for MDKP, highlighting the challenges quantum algorithms face when tackling highly constrained optimization problems.
- Abstract（参考訳）: 組合せ最適化問題を解くことは、現実のシナリオにおける量子アルゴリズムの有望な応用分野である。
本研究では,従来の0-1クナップサック問題に対して提案されていた「量子ツリージェネレータ」(QTG)を,0-1クナップサック問題(QKP)と多次元クナップサック問題(MDKP)に拡張する。
QTGは、与えられたインスタンスに対する全ての実現可能な解の重ね合わせを構築するので、振幅増幅における有望な状態準備ルーチンとして利用でき、高品質な解を生成することができる。
以前は、QTGベースの探索は0-1 Knapsack Problemでテストされ、数百の論理量子ビットと完全に接続された量子ビットを持つ量子コンピュータが利用可能となると、実用的な量子優位性の可能性を示した。
本稿では,古典的解法であるGurobiに対して,QKPとMDKPにおけるアルゴリズムの性能を評価する。
大規模評価を容易にするため,QKPが最大2000変数,MDKPが最大1500変数,MDKPが100制約のインスタンスに対して,実行時の予測を可能にする高度なベンチマーク手法を採用した。
以上の結果から,QTGに基づく検索により,QKPの競合するランタイムを備えた高品質なソリューションが実現可能であることが示唆された。
しかし、MDKPの性能低下は、高度に制約された最適化問題に取り組む際に量子アルゴリズムが直面する課題を浮き彫りにした。
関連論文リスト
- 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) - Depth scaling of unstructured search via quantum approximate optimization [0.0]
変分量子アルゴリズムは、現在の量子計算のデファクトモデルとなっている。
そのような問題の1つは、ある文字列の特定のビットを見つけることで構成される非構造化探索である。
我々は、CTQWを用いてQAOA配列を復元し、最近のトロッター公式の理論の進歩を利用して、クエリの複雑さを束縛する。
論文 参考訳（メタデータ） (2024-03-22T18:00:03Z) - A quantum algorithm for solving 0-1 Knapsack problems [0.0]
与えられたインスタンスのすべての実現可能なソリューションを重ね合わせに生成するアプローチである"Quantum Tree Generator"を導入する。
新しい実行時計算手法を導入することで、既存のプラットフォームやシミュレータの範囲を超えて、メソッドのランタイムを予測できます。
論文 参考訳（メタデータ） (2023-10-10T13:40:30Z) - Post-processing variationally scheduled quantum algorithm for constrained combinatorial optimization problems [6.407238428292173]
本稿では,制約付き最適化問題(COP)の解法として,変分計画量子アルゴリズム(pVSQA)を提案する。
pVSQAは変分法と後処理技術を組み合わせたものである。
我々は,量子アニールとゲート型量子デバイスにpVSQAを実装した。
論文 参考訳（メタデータ） (2023-09-15T03:09:16Z) - Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。
量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
論文 参考訳（メタデータ） (2022-12-06T22:01:49Z) - End-to-end resource analysis for quantum interior point methods and portfolio optimization [63.4863637315163]
問題入力から問題出力までの完全な量子回路レベルのアルゴリズム記述を提供する。
アルゴリズムの実行に必要な論理量子ビットの数と非クリフォードTゲートの量/深さを報告する。
論文 参考訳（メタデータ） (2022-11-22T18:54:48Z) - Hybrid Quantum-Classical Heuristic for the Bin Packing Problem [0.8434687648198277]
1次元Bin Packing Problem (1dBPP) を扱うためのハイブリッド古典量子法を提案する。
古典的な計算サブルーチンは、量子サブルーチンによって与えられる部分集合から問題に対する完全な解を構築する。
ハイブリッドな解法として、我々はH-BPPと呼ぶ。
論文 参考訳（メタデータ） (2022-04-12T09:05:27Z) - Adiabatic Quantum Graph Matching with Permutation Matrix Constraints [75.88678895180189]
3次元形状と画像のマッチング問題は、NPハードな置換行列制約を持つ二次代入問題(QAP)としてしばしば定式化される。
本稿では,量子ハードウェア上での効率的な実行に適した制約のない問題として,いくつかのQAPの再構成を提案する。
提案アルゴリズムは、将来の量子コンピューティングアーキテクチャにおいて、より高次元にスケールする可能性がある。
論文 参考訳（メタデータ） (2021-07-08T17:59:55Z) - 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) - Adiabatic Quantum Optimization Fails to Solve the Knapsack Problem [0.0]
D-Wave 2000Q adiabatic quantum computer to solve the integer-weight knapsack problem。
断熱的量子最適化では、knapsackの最適充填に対応する解が得られない。
論文 参考訳（メタデータ） (2020-08-17T16:29:34Z) - Cross Entropy Hyperparameter Optimization for Constrained Problem
Hamiltonians Applied to QAOA [68.11912614360878]
QAOA(Quantum Approximate Optimization Algorithm)のようなハイブリッド量子古典アルゴリズムは、短期量子コンピュータを実用的に活用するための最も奨励的なアプローチの1つである。
このようなアルゴリズムは通常変分形式で実装され、古典的な最適化法と量子機械を組み合わせて最適化問題の優れた解を求める。
本研究では,クロスエントロピー法を用いてランドスケープを形作り,古典的パラメータがより容易により良いパラメータを発見でき,その結果,性能が向上することを示す。
論文 参考訳（メタデータ） (2020-03-11T13:52:41Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。