論文の概要: 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の潜在的優位性を実証し,組合せ最適化問題に対する効果的なアプローチを示す。
関連論文リスト
- Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
我々は、$m=mathcalO(nk)$バイナリ変数を$n$ qubitsだけを使って最適化するために、$k>1$で可変量子ソルバを導入する。
我々は,特定の量子ビット効率の符号化が,バレン高原の超ポリノミウム緩和を内蔵特徴としてもたらすことを解析的に証明した。
論文 参考訳(メタデータ) (2024-01-17T18:59:38Z) - Variational Amplitude Amplification for Solving QUBO Problems [0.0]
本研究は、キュービット重畳状態に適したQUBO問題に焦点をあてる。
我々は、QUBOをコストオラクルの演算として符号化する回路設計を、標準Grover拡散演算子$U_textrms$と組み合わせると、最適および近似最適解に対応する状態の測定確率が高くなることを示す。
論文 参考訳(メタデータ) (2023-01-31T14:33:40Z) - 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 [58.720142291102135]
余分なスラック変数を必要としない代替手法を提案する。
我々は,旅行セールスマン問題,ビン包装問題,ナプサック問題に対するアプローチを評価した。
この新しいアプローチは、リソースの少ない不等式制約の問題を解決するために使用できる。
論文 参考訳(メタデータ) (2022-11-25T06:05:18Z) - 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) - A Gauss-Newton based Quantum Algorithm for Combinatorial Optimization [0.0]
最適化問題に対するガウス・ニュートン型量子アルゴリズム(GNQA)を提案するが、最適条件下では、局所的なミニマやプラトーに閉じ込められることなく、最適解の1つに迅速に収束する。
我々のアプローチは、最適解を正確に表すテンソル積状態と、二項変数のすべての組み合わせを含むハミルトニアンに対して適切な関数を用いることによってそれらを緩和する。
そこで,本研究では,GNQAが収束特性と精度の両方において,他の最適化手法よりも優れていることを示す。
論文 参考訳(メタデータ) (2022-03-25T23:49:31Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。