論文の概要: Adiabatic Quantum Optimization Fails to Solve the Knapsack Problem
- arxiv url: http://arxiv.org/abs/2008.07456v1
- Date: Mon, 17 Aug 2020 16:29:34 GMT
- ステータス: 処理完了
- システム内更新日: 2022-10-28 04:09:42.959852
- Title: Adiabatic Quantum Optimization Fails to Solve the Knapsack Problem
- Title（参考訳）: 断熱量子最適化はクナプサック問題を解くことができない
- Authors: Lauren Pusey-Nazzaro, Prasanna Date
- Abstract要約: D-Wave 2000Q adiabatic quantum computer to solve the integer-weight knapsack problem。
断熱的量子最適化では、knapsackの最適充填に対応する解が得られない。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In this work, we attempt to solve the integer-weight knapsack problem using
the D-Wave 2000Q adiabatic quantum computer. The knapsack problem is a
well-known NP-complete problem in computer science, with applications in
economics, business, finance, etc. We attempt to solve a number of small
knapsack problems whose optimal solutions are known; we find that adiabatic
quantum optimization fails to produce solutions corresponding to optimal
filling of the knapsack in all problem instances. We compare results obtained
on the quantum hardware to the classical simulated annealing algorithm and two
solvers employing a hybrid branch-and-bound algorithm. The simulated annealing
algorithm also fails to produce the optimal filling of the knapsack, though
solutions obtained by simulated and quantum annealing are no more similar to
each other than to the correct solution. We discuss potential causes for this
observed failure of adiabatic quantum optimization.
- Abstract（参考訳）: 本研究では,D-Wave 2000Qアダイバティック量子コンピュータを用いて整数重み付きクナプサック問題を解く。
ナップサック問題(英: knapsack problem)は、経済学、ビジネス、金融など、コンピュータ科学においてよく知られたnp完全問題である。
我々は、最適解が知られている多くの小さなナップサック問題を解こうとする; 断熱量子最適化は、すべての問題において、ナップサックの最適充填に対応する解を作り出すことができない。
量子ハードウェア上で得られた結果と古典的アニーリングアルゴリズムとハイブリッド分岐結合アルゴリズムを用いた2つの解法との比較を行った。
シミュレートアニーリングアルゴリズムはまた、クナプサックの最適充填を生成するのに失敗するが、シミュレートアニーリングと量子アニーリングによって得られる解は、正しい解よりも互いに似ていない。
断熱的量子最適化の観測失敗の原因について考察する。
関連論文リスト
- 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) - Assessing Quantum Computing Performance for Energy Optimization in a
Prosumer Community [1.072460284847973]
消費者問題」とは、利用者のニーズ、電力価格、地域再生可能エネルギーの可利用性に基づいて家庭の負荷をスケジューリングする問題である。
量子コンピュータは、量子演算の本質的な並列性のおかげで、この問題を扱う上で大きなブレークスルーをもたらす可能性がある。
本報告では,シミュレータと実量子ハードウェアを用いた,様々な問題サイズに対する広範な実験について報告する。
論文 参考訳（メタデータ） (2023-11-17T15:48:51Z) - Hybrid classical-quantum branch-and-bound algorithm for solving integer
linear problems [0.0]
量子アニールは、QUBOの定式化で表されるいくつかのロジスティック最適化問題を解くのに適している。
量子異方体が提案する解法は一般に最適ではなく、熱ノイズやその他の乱雑な効果は計算に関わる量子ビットの数が大きすぎるときに生じる。
本稿では,従来の分枝分枝分枝法を用いて,より少ない量子ビット数で表されるサブプロブレムに分割する手法を提案する。
論文 参考訳（メタデータ） (2023-11-16T09:19:01Z) - A Universal Quantum Algorithm for Weighted Maximum Cut and Ising
Problems [0.0]
本稿では,二項問題の近似解を計算するためのハイブリッド量子古典アルゴリズムを提案する。
我々は、重み付き最大カットまたはイジング・ハミルトン演算子をブロック符号化するユニタリおよびエルミート演算子を実装するために浅深さ量子回路を用いる。
この作用素の変動量子状態への期待を測定すると、量子系の変動エネルギーが得られる。
論文 参考訳（メタデータ） (2023-06-10T23:28:13Z) - Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。
量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
論文 参考訳（メタデータ） (2022-12-06T22:01:49Z) - Efficient Use of Quantum Linear System Algorithms in Interior Point
Methods for Linear Optimization [0.0]
線形最適化問題を解くために、非現実的な量子内点法を開発した。
また、量子ソルバの過度な時間なしで、反復リファインメントによって正確な解を得る方法についても論じる。
論文 参考訳（メタデータ） (2022-05-02T21:30:56Z) - A Hybrid Quantum-Classical Algorithm for Robust Fitting [47.42391857319388]
本稿では,ロバストフィッティングのためのハイブリッド量子古典アルゴリズムを提案する。
私たちのコアコントリビューションは、整数プログラムの列を解く、新しい堅牢な適合式である。
実際の量子コンピュータを用いて得られた結果について述べる。
論文 参考訳（メタデータ） (2022-01-25T05:59:24Z) - Adiabatic Quantum Graph Matching with Permutation Matrix Constraints [75.88678895180189]
3次元形状と画像のマッチング問題は、NPハードな置換行列制約を持つ二次代入問題(QAP)としてしばしば定式化される。
本稿では,量子ハードウェア上での効率的な実行に適した制約のない問題として,いくつかのQAPの再構成を提案する。
提案アルゴリズムは、将来の量子コンピューティングアーキテクチャにおいて、より高次元にスケールする可能性がある。
論文 参考訳（メタデータ） (2021-07-08T17:59:55Z) - Quantum Permutation Synchronization [88.4588059792167]
本稿では,コンピュータビジョンの文脈における量子ビジョン問題を解決する量子アルゴリズムQuantumSyncを提案する。
本稿では、QUBO 問題に置換制約を挿入し、アバスティック量子 DWave コンピュータの電流生成に関する制約付き QUBO 問題を解決する方法を示す。
論文 参考訳（メタデータ） (2021-01-19T17:51:02Z) - Space-efficient binary optimization for variational computing [68.8204255655161]
本研究では,トラベリングセールスマン問題に必要なキュービット数を大幅に削減できることを示す。
また、量子ビット効率と回路深さ効率のモデルを円滑に補間する符号化方式を提案する。
論文 参考訳（メタデータ） (2020-09-15T18:17:27Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。