論文の概要: A quantum algorithm for the solution of the 0-1 Knapsack problem
- arxiv url: http://arxiv.org/abs/2310.06623v1
- Date: Tue, 10 Oct 2023 13:40:30 GMT
- ステータス: 処理完了
- システム内更新日: 2023-10-11 15:15:45.505606
- Title: A quantum algorithm for the solution of the 0-1 Knapsack problem
- Title（参考訳）: 0-1 Knapsack問題の解に対する量子アルゴリズム
- Authors: S\"oren Wilkening, Andreea-Iulia Lefterovici, Lennart Binkowski,
Michael Perk, S\'andor Fekete, and Tobias J. Osborne
- Abstract要約: 与えられたインスタンスの可能なすべてのソリューションを重ね合わせて生成するアプローチである'Quantum Tree Generator'を導入する。
また,COMBOからのログデータを活用する高レベルなシミュレーション戦略も導入する。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Here we present two novel contributions for achieving quantum advantage in
solving difficult optimisation problems, both in theory and foreseeable
practice. (1) We introduce the ''Quantum Tree Generator'', an approach to
generate in superposition all feasible solutions of a given instance, yielding
together with amplitude amplification the optimal solutions for
$0$-$1$-Knapsack problems. The QTG offers exponential memory savings and
enables competitive runtimes compared to the state-of-the-art Knapsack solver
COMBO for instances involving as few as 600 variables. (2) By introducing a
high-level simulation strategy that exploits logging data from COMBO, we can
predict the runtime of our method way beyond the range of existing quantum
platforms and simulators, for various benchmark instances with up to 1600
variables. Combining both of these innovations, we demonstrate the QTG's
potential advantage for large-scale problems, indicating an effective approach
for combinatorial optimisation problems.
- Abstract（参考訳）: ここでは, 理論上と予測可能な双方において, 難解な最適化問題を解く上で, 量子優位を達成するための2つの新しい貢献を示す。
1) 与えられたインスタンスのすべての実現可能な解を重畳して生成する手法である'Quantum Tree Generator'を導入し、0$-$1-Knapsack問題に対して最適な解を振幅増幅する。
QTGは指数的メモリセーブを提供し、600変数のインスタンスに対して最先端のKnapsackソルバCOMBOと比較して競合ランタイムを可能にする。
2)コンボからのロギングデータを活用するハイレベルなシミュレーション戦略を導入することで,1600変数までの様々なベンチマークインスタンスに対して,既存の量子プラットフォームやシミュレータの範囲を超えて,提案手法のランタイムを予測できる。
これら2つのイノベーションを組み合わせることで,大規模問題に対するqtgの潜在的優位性を実証し,組合せ最適化問題に対する効果的なアプローチを示す。
関連論文リスト
- Quantum evolutionary algorithm for TSP combinatorial optimisation problem [0.0]
本稿では、量子遺伝的アルゴリズム(QGA)を用いて、旅行セールスマン問題(TSP)と呼ばれる新しい問題を解決する方法を実装する。
我々は、この新しいアプローチがいかにうまく機能するかを、古典的遺伝的アルゴリズム(CGA)として知られる従来の手法と比較した。
論文 参考訳（メタデータ） (2024-09-20T08:27:42Z) - 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) - Solving non-native combinatorial optimization problems using hybrid
quantum-classical algorithms [0.0]
組合せ最適化は、物流から金融まで幅広い分野に適用可能な、困難な問題である。
量子コンピューティングは、様々なアルゴリズムを用いてこれらの問題を解決するために使われてきた。
この研究は、量子と古典のリソースをハイブリッドなアプローチで統合することで、これらの課題を克服する枠組みを提示している。
論文 参考訳（メタデータ） (2024-03-05T17:46:04Z) - Quantum Approximate Optimisation for Not-All-Equal SAT [9.427635404752936]
変動量子アルゴリズムのQAOAを、満足度問題(SAT: Not-All-Equal SAT)の変種に適用する。
両ソルバのランタイムは問題サイズとともに指数関数的にスケールするが,QAOAのスケーリングは回路深さが十分に大きい場合に小さくなることを示す。
論文 参考訳（メタデータ） (2024-01-05T15:11:24Z) - 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) - Comparative Benchmark of a Quantum Algorithm for the Bin Packing Problem [0.8434687648198277]
Bin Packing Problem (BPP) は、ロジスティクスにおけるパラダイム最適化問題として際立っている。
我々は最近,一次元BPPに対するハイブリッドアプローチを提案している。
他の古典的手法と比較する。
論文 参考訳（メタデータ） (2022-07-15T13:09:12Z) - 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) - 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) - Hybrid Quantum-Classical Heuristic for the Bin Packing Problem [0.8434687648198277]
1次元Bin Packing Problem (1dBPP) を扱うためのハイブリッド古典量子法を提案する。
古典的な計算サブルーチンは、量子サブルーチンによって与えられる部分集合から問題に対する完全な解を構築する。
ハイブリッドな解法として、我々はH-BPPと呼ぶ。
論文 参考訳（メタデータ） (2022-04-12T09:05:27Z) - Cross Entropy Hyperparameter Optimization for Constrained Problem
Hamiltonians Applied to QAOA [68.11912614360878]
QAOA(Quantum Approximate Optimization Algorithm)のようなハイブリッド量子古典アルゴリズムは、短期量子コンピュータを実用的に活用するための最も奨励的なアプローチの1つである。
このようなアルゴリズムは通常変分形式で実装され、古典的な最適化法と量子機械を組み合わせて最適化問題の優れた解を求める。
本研究では,クロスエントロピー法を用いてランドスケープを形作り,古典的パラメータがより容易により良いパラメータを発見でき,その結果,性能が向上することを示す。
論文 参考訳（メタデータ） (2020-03-11T13:52:41Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。