論文の概要: Amplitude-Ensemble Quantum-Inspired Tabu Search Algorithm for Solving 0/1 Knapsack Problems
- arxiv url: http://arxiv.org/abs/2311.12867v2
- Date: Sun, 17 Mar 2024 14:05:24 GMT
- ステータス: 処理完了
- システム内更新日: 2024-03-20 03:02:46.012770
- Title: Amplitude-Ensemble Quantum-Inspired Tabu Search Algorithm for Solving 0/1 Knapsack Problems
- Title（参考訳）: 0/1クナップサック問題の解法における振幅エンサンブル量子インスパイアされたタブ探索アルゴリズム
- Authors: Kuo-Chun Tseng, Wei-Chieh Lai, I-Chia Chen, Yun-Hsiang Hsiao, Jr-Yu Chiue, Wei-Chun Huang,
- Abstract要約: QTS(Quantum-inspired Tabu Search)の改良版が提案され、AE-QTS(Amplitude-ensemble)と呼ばれる人口情報の利用が促進された。
これにより、AE-QTSは、アルゴリズムの単純さを維持しつつ、抽象的な概念で実際の量子検索アルゴリズムであるGrover Search Algorithmによく似ている。
AE-QTSはQTSを含む他のアルゴリズムよりも高い性能を示し、QTSは全てのケースで平均20%、場合によっては30%以上の性能を示した。
- 参考スコア（独自算出の注目度）: 0.41232474244672235
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In this paper, an improved version of QTS (Quantum-inspired Tabu Search) has been proposed, which enhances the utilization of population information, called "amplitude-ensemble" QTS (AE-QTS). This makes AE-QTS more similar to the real quantum search algorithm, Grover Search Algorithm, in abstract concept, while keeping the simplicity of the algorithm. Later, we demonstrate the AE-QTS on the classical combinatorial optimization 0/1 knapsack problem. Experimental results show that the AE-QTS outperforms other algorithms, including the QTS, by at least an average of 20% in all cases and even by 30% in some cases. Even as the problem complexity increases, the quality of the solutions found by our method remains superior to that of the QTS. These results prove that our method has better search performance.
- Abstract（参考訳）: 本稿では,QTS(Quantum-inspired Tabu Search)の改良版を提案する。
これにより、AE-QTSは、アルゴリズムの単純さを維持しつつ、抽象的な概念で実際の量子検索アルゴリズムであるGrover Search Algorithmによく似ている。
その後、AE-QTSを古典的組合せ最適化0/1knapsack問題で実証する。
実験の結果,AE-QTSはQTSを含む他のアルゴリズムよりも高い性能を示した。
問題複雑性が増大しても,本手法の解の質はQTSよりも優れている。
これらの結果から,本手法は検索性能が向上することが示された。
関連論文リスト
- 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) - Depth scaling of unstructured search via quantum approximate optimization [0.0]
変分量子アルゴリズムは、現在の量子計算のデファクトモデルとなっている。
そのような問題の1つは、ある文字列の特定のビットを見つけることで構成される非構造化探索である。
我々は、CTQWを用いてQAOA配列を復元し、最近のトロッター公式の理論の進歩を利用して、クエリの複雑さを束縛する。
論文 参考訳（メタデータ） (2024-03-22T18:00:03Z) - Quantum Subroutine for Variance Estimation: Algorithmic Design and Applications [80.04533958880862]
量子コンピューティングは、アルゴリズムを設計する新しい方法の基礎となる。
どの場の量子スピードアップが達成できるかという新たな課題が生じる。
量子サブルーチンの設計は、従来のサブルーチンよりも効率的で、新しい強力な量子アルゴリズムに固い柱を向ける。
論文 参考訳（メタデータ） (2024-02-26T09:32:07Z) - Quantum Approximate Optimisation for Not-All-Equal SAT [9.427635404752936]
変動量子アルゴリズムのQAOAを、満足度問題(SAT: Not-All-Equal SAT)の変種に適用する。
両ソルバのランタイムは問題サイズとともに指数関数的にスケールするが,QAOAのスケーリングは回路深さが十分に大きい場合に小さくなることを示す。
論文 参考訳（メタデータ） (2024-01-05T15:11:24Z) - Probabilistic Sampling of Balanced K-Means using Adiabatic Quantum Computing [93.83016310295804]
AQCは研究関心の問題を実装でき、コンピュータビジョンタスクのための量子表現の開発に拍車をかけた。
本研究では,この情報を確率的バランスの取れたk平均クラスタリングに活用する可能性について検討する。
最適でない解を捨てる代わりに, 計算コストを少なくして, 校正後部確率を計算することを提案する。
これにより、合成タスクと実際の視覚データについて、D-Wave AQCで示すような曖昧な解とデータポイントを識別することができる。
論文 参考訳（メタデータ） (2023-10-18T17:59:45Z) - Quantum Annealing for Single Image Super-Resolution [86.69338893753886]
単一画像超解像(SISR)問題を解くために,量子コンピューティングに基づくアルゴリズムを提案する。
提案したAQCアルゴリズムは、SISRの精度を維持しつつ、古典的なアナログよりも向上したスピードアップを実現する。
論文 参考訳（メタデータ） (2023-04-18T11:57:15Z) - Amplitude amplification-inspired QAOA: Improving the success probability
for solving 3SAT [55.78588835407174]
振幅増幅アルゴリズムは、可変代入を満たすために非構造化探索に適用することができる。
Quantum Approximate Optimization Algorithm (QAOA)は、ノイズのある中間量子デバイスのための3SATを解くための有望な候補である。
振幅増幅によるQAOAの変種を導入し、3SATの成功確率を改善する。
論文 参考訳（メタデータ） (2023-03-02T11:52:39Z) - Modified Iterative Quantum Amplitude Estimation is Asymptotically
Optimal [0.37798600249187286]
量子振幅推定(QAE)のための最初のQFTフリーアルゴリズムを提供する。
QAEアルゴリズムは量子コンピュータの多くの応用においてサブルーチンとして現れる。
論文 参考訳（メタデータ） (2022-08-31T03:20:10Z) - 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) - Focusing on the Hybrid Quantum Computing -- Tabu Search Algorithm: new
results on the Asymmetric Salesman Problem [1.672938048065882]
本稿では,分割問題に対するハイブリッド量子コンピューティング - Tabu Search Algorithm の結果と結果を拡張する。
さらなる貢献として、この研究は量子コンピューティングを用いた非対称トラベリングセールスマン問題の最初の解法であると仮定する。
論文 参考訳（メタデータ） (2021-02-11T10:08:44Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。