論文の概要: A quantum speedup algorithm for TSP based on quantum dynamic programming with very few qubits
- arxiv url: http://arxiv.org/abs/2502.08853v3
- Date: Fri, 28 Feb 2025 05:56:03 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-03-03 13:37:57.234310
- Title: A quantum speedup algorithm for TSP based on quantum dynamic programming with very few qubits
- Title（参考訳）: ごく少数の量子ビットをもつ量子動的計画法に基づくTSPの量子スピードアップアルゴリズム
- Authors: Bai Xujun, Shang Yun,
- Abstract要約: ゲート複雑性における初期状態として,N長ハミルトニアンサイクルの均一な重ね合わせ状態を生成する量子アルゴリズムを提案する。
理論的にはクエリの複雑さが低いが、実用的な実装ソリューションが欠如しているアルゴリズムと比較すると、本アルゴリズムは回路実装が可能である。
- 参考スコア（独自算出の注目度）: 0.0
- License:
- Abstract: The Traveling Salesman Problem (TSP) is a classical NP-hard problem that plays a crucial role in combinatorial optimization. In this paper, we are interested in the quantum search framework for the TSP because it has robust theoretical guarantees. However, we need to first search for all Hamiltonian cycles from a very large solution space, which greatly weakens the advantage of quantum search algorithms. To address this issue, one can first prepare a superposition state of all feasible solutions, and then amplify the amplitude of the optimal solution from it. We propose a quantum algorithm to generate the uniform superposition state of all N-length Hamiltonian cycles as an initial state within polynomial gate complexity based on pure quantum dynamic programming with very few ancillary qubits, which achieves exponential acceleration compared to the previous initial state preparation algorithm. As a result, we realized the theoretical minimum query complexity of quantum search algorithms for a general TSP. Compared to some algorithms that theoretically have lower query complexities but lack practical implementation solutions, our algorithm has feasible circuit implementation. Our work provides a meaningful research case on how to fully utilize the structures of specific problems to unleash the acceleration capability of the quantum search algorithms.
- Abstract（参考訳）: トラベリングセールスマン問題(TSP)は、組合せ最適化において重要な役割を果たす古典的なNPハード問題である。
本稿では,理論的確証が堅固であるため,TSPの量子探索フレームワークに関心がある。
しかし、我々は、量子探索アルゴリズムの利点を著しく弱める非常に大きな解空間から、まずすべてのハミルトンサイクルを探索する必要がある。
この問題に対処するために、まずすべての実現可能な解の重ね合わせ状態を作成し、それから最適解の振幅を増幅することができる。
そこで本研究では,全てのN長ハミルトニアンサイクルの一様重畳状態を生成する量子アルゴリズムを提案する。
その結果、一般的なTSPに対する量子探索アルゴリズムの理論的最小クエリの複雑さを実現した。
理論的にはクエリの複雑さが低いが、実用的な実装ソリューションが欠如しているアルゴリズムと比較すると、本アルゴリズムは回路実装が可能である。
我々の研究は、量子探索アルゴリズムの加速能力を解き放つために、特定の問題の構造を完全に活用する方法に関する有意義な研究ケースを提供する。
関連論文リスト
- 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) - Circuit Design of Two-Step Quantum Search Algorithm for Solving Traveling Salesman Problems [1.4513830934124627]
2組の演算子を用いた2段階量子探索(TSQS)アルゴリズムを提案する。
最初のステップでは、すべての実現可能な解は、同じ重ね合わせ状態に増幅される。
2番目のステップでは、この重ね合わせ状態から最適解状態が増幅される。
論文 参考訳（メタデータ） (2024-05-12T01:44:19Z) - Depth scaling of unstructured search via quantum approximate optimization [0.0]
変分量子アルゴリズムは、現在の量子計算のデファクトモデルとなっている。
そのような問題の1つは、ある文字列の特定のビットを見つけることで構成される非構造化探索である。
我々は、CTQWを用いてQAOA配列を復元し、最近のトロッター公式の理論の進歩を利用して、クエリの複雑さを束縛する。
論文 参考訳（メタデータ） (2024-03-22T18:00:03Z) - Iterative Quantum Algorithms for Maximum Independent Set: A Tale of
Low-Depth Quantum Algorithms [0.0]
我々は、反復最大量子アルゴリズム(Iterative Maximum Quantum Algorithms)と呼ばれる、量子最適化のための新しいハイブリッドアプローチのクラスについて研究する。
深度$p=1$のQAOAの場合、このアルゴリズムはMISの古典的欲求アルゴリズムと全く同じ操作と選択を行う。
論文 参考訳（メタデータ） (2023-09-22T18:00:03Z) - Quantum Annealing for Single Image Super-Resolution [86.69338893753886]
単一画像超解像(SISR)問題を解くために,量子コンピューティングに基づくアルゴリズムを提案する。
提案したAQCアルゴリズムは、SISRの精度を維持しつつ、古典的なアナログよりも向上したスピードアップを実現する。
論文 参考訳（メタデータ） (2023-04-18T11:57:15Z) - Quantum Clustering with k-Means: a Hybrid Approach [117.4705494502186]
我々は3つのハイブリッド量子k-Meansアルゴリズムを設計、実装、評価する。
我々は距離の計算を高速化するために量子現象を利用する。
我々は、我々のハイブリッド量子k-平均アルゴリズムが古典的バージョンよりも効率的であることを示す。
論文 参考訳（メタデータ） (2022-12-13T16:04:16Z) - Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。
量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
論文 参考訳（メタデータ） (2022-12-06T22:01:49Z) - Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
Bernstein-Vaziraniアルゴリズムは、オラクルに符号化されたビット文字列を決定できる。
我々はベルンシュタイン・ヴァジラニアルゴリズムの量子資源を詳細に分析する。
絡み合いがない場合、初期状態における量子コヒーレンス量とアルゴリズムの性能が直接関係していることが示される。
論文 参考訳（メタデータ） (2022-05-26T20:32:36Z) - Polynomial T-depth Quantum Solvability of Noisy Binary Linear Problem:
From Quantum-Sample Preparation to Main Computation [0.0]
雑音二元線形問題(NBLP)の量子可解性について完全解析する。
NBLPの解くコストは、指数関数的に増大する論理量子ビットを犠牲にして、問題の規模で解決できることが示される。
論文 参考訳（メタデータ） (2021-09-23T07:46:20Z) - Space-efficient binary optimization for variational computing [68.8204255655161]
本研究では,トラベリングセールスマン問題に必要なキュービット数を大幅に削減できることを示す。
また、量子ビット効率と回路深さ効率のモデルを円滑に補間する符号化方式を提案する。
論文 参考訳（メタデータ） (2020-09-15T18:17:27Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。