論文の概要: 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 19:09:59.663247
- 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: http://creativecommons.org/licenses/by/4.0/
- 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の性能低下は、高度に制約された最適化問題に取り組む際に量子アルゴリズムが直面する課題を浮き彫りにした。
関連論文リスト
- Solving Constrained Combinatorial Optimization Problems with Variational Quantum Imaginary Time Evolution [4.266376725904727]
本稿では,VarQITEが従来の手法に比べて平均最適性ギャップを著しく小さくすることを示す。
ハミルトニアンのスケーリングにより、最適化コストをさらに削減し、収束を加速できることを実証する。
論文 参考訳（メタデータ） (2025-04-17T03:09:37Z) - 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) - Qubit efficient quantum algorithms for the vehicle routing problem on
NISQ processors [48.68474702382697]
時間窓付き車両ルーティング問題(VRPTW)は、ロジスティクス業界で直面する一般的な最適化問題である。
そこで本研究では,以前に導入した量子ビット符号化方式を用いて,バイナリ変数の数を削減した。
論文 参考訳（メタデータ） (2023-06-14T13:44:35Z) - Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。
量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
論文 参考訳（メタデータ） (2022-12-06T22:01:49Z) - Unbalanced penalization: A new approach to encode inequality constraints of combinatorial problems for quantum optimization algorithms [42.29248343585333]
余分なスラック変数を必要としない代替手法を提案する。
我々は,旅行セールスマン問題,ビン包装問題,ナプサック問題に対するアプローチを評価した。
この新しいアプローチは、リソースの少ない不等式制約の問題を解決するために使用できる。
論文 参考訳（メタデータ） (2022-11-25T06:05:18Z) - Hybrid Quantum-Classical Heuristic for the Bin Packing Problem [0.8434687648198277]
1次元Bin Packing Problem (1dBPP) を扱うためのハイブリッド古典量子法を提案する。
古典的な計算サブルーチンは、量子サブルーチンによって与えられる部分集合から問題に対する完全な解を構築する。
ハイブリッドな解法として、我々はH-BPPと呼ぶ。
論文 参考訳（メタデータ） (2022-04-12T09:05:27Z) - Q-FW: A Hybrid Classical-Quantum Frank-Wolfe for Quadratic Binary
Optimization [44.96576908957141]
本稿では,量子コンピュータ上での2次線形反復問題を解くために,フランク・ウルフアルゴリズム(Q-FW)に基づく古典量子ハイブリッドフレームワークを提案する。
論文 参考訳（メタデータ） (2022-03-23T18:00:03Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。