論文の概要: Solving The Travelling Salesman Problem Using A Single Qubit
- arxiv url: http://arxiv.org/abs/2407.17207v1
- Date: Wed, 24 Jul 2024 12:06:37 GMT
- ステータス: 処理完了
- システム内更新日: 2024-07-25 14:04:14.534910
- Title: Solving The Travelling Salesman Problem Using A Single Qubit
- Title（参考訳）: 単一ビットを用いたトラベリングセールスマン問題の解法
- Authors: Kapil Goswami, Gagan Anekonda Veereshi, Peter Schmelcher, Rick Mukherjee,
- Abstract要約: トラベルセールスマン問題(TSP)はNP-ハード組合せ最適化問題として人気がある。
本稿では,量子並列性(quantum parallelism)の原理を導出し,単一量子ビットを用いて任意のTSPを解くアルゴリズムを提案する。
我々のアルゴリズムの基盤となるフレームワークは、古典的ブラキストクロンのアプローチの量子バージョンである。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: The travelling salesman problem (TSP) is a popular NP-hard-combinatorial optimization problem that requires finding the optimal way for a salesman to travel through different cities once and return to the initial city. The existing methods of solving TSPs on quantum systems are either gate-based or binary variable-based encoding. Both approaches are resource-expensive in terms of the number of qubits while performing worse compared to existing classical algorithms even for small-size problems. We present an algorithm that solves an arbitrary TSP using a single qubit by invoking the principle of quantum parallelism. The cities are represented as quantum states on the Bloch sphere while the preparation of superposition states allows us to traverse multiple paths at once. The underlying framework of our algorithm is a quantum version of the classical Brachistochrone approach. Optimal control methods are employed to create a selective superposition of the quantum states to find the shortest route of a given TSP. The numerical simulations solve a sample of four to nine cities for which exact solutions are obtained. The algorithm can be implemented on any quantum platform capable of efficiently rotating a qubit and allowing state tomography measurements. For the TSP problem sizes considered in this work, our algorithm is more resource-efficient and accurate than existing quantum algorithms with the potential for scalability. A potential speed-up of polynomial time over classical algorithms is discussed.
- Abstract（参考訳）: トラベリングセールスマン問題(TSP)は、セールスマンが一度異なる都市を旅して初期都市に戻るのに最適な方法を見つける必要がある、NP-ハード組合せ最適化問題である。
量子システム上でのTSPを解く既存の方法は、ゲートベースまたはバイナリ変数ベースエンコーディングである。
どちらの手法も、量子ビットの個数という点では資源に精通するが、従来のアルゴリズムに比べて小さな問題であっても性能は劣る。
本稿では,量子並列性(quantum parallelism)の原理を導出し,単一量子ビットを用いて任意のTSPを解くアルゴリズムを提案する。
都市はブロッホ球上の量子状態として表され、重畳状態の準備により複数の経路を同時に通過することができる。
我々のアルゴリズムの基盤となるフレームワークは、古典的ブラキストクロンのアプローチの量子バージョンである。
最適制御法は、与えられたTSPの最も短い経路を見つけるために、量子状態の選択的な重ね合わせを作成するために用いられる。
数値シミュレーションは、正確な解が得られる4から9の都市のサンプルを解く。
このアルゴリズムは、量子ビットを効率的に回転させ、状態トモグラフィー測定を可能にするあらゆる量子プラットフォームに実装することができる。
この研究で考慮されたTSP問題のサイズについて、我々のアルゴリズムは既存の量子アルゴリズムよりもリソース効率が高く正確であり、スケーラビリティの可能性がある。
古典的アルゴリズムによる多項式時間の潜在的な高速化について論じる。
関連論文リスト
- A quantum speedup algorithm for TSP based on quantum dynamic programming with very few qubits [0.0]
ゲート複雑性における初期状態として,N長ハミルトニアンサイクルの均一な重ね合わせ状態を生成する量子アルゴリズムを提案する。
理論的にはクエリの複雑さが低いが、実用的な実装ソリューションが欠如しているアルゴリズムと比較すると、本アルゴリズムは回路実装が可能である。
論文 参考訳（メタデータ） (2025-02-12T23:58:25Z) - 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) - Quantum Circuit Optimization with AlphaTensor [47.9303833600197]
我々は,所定の回路を実装するために必要なTゲート数を最小化する手法であるAlphaTensor-Quantumを開発した。
Tカウント最適化の既存の方法とは異なり、AlphaTensor-Quantumは量子計算に関するドメイン固有の知識を取り入れ、ガジェットを活用することができる。
注目すべきは、有限体における乗法であるカラツバの手法に似た効率的なアルゴリズムを発見することである。
論文 参考訳（メタデータ） (2024-02-22T09:20:54Z) - Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。
量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
論文 参考訳（メタデータ） (2022-12-06T22:01:49Z) - A Realizable GAS-based Quantum Algorithm for Traveling Salesman Problem [2.208581695286558]
本稿では,Grover Adaptive Search(GAS)に基づく旅行セールスマン問題(TSP)の量子アルゴリズムを提案する。
この戦略は量子コンピューティングの可逆性要件を完全に考慮し、使用した量子ビットが単に上書きやリリースできないという難しさを克服する。
7ノードのTSPでは31量子ビットしか必要とせず、最適解を得る成功率は86.71%である。
論文 参考訳（メタデータ） (2022-12-06T03:54:07Z) - Approximate encoding of quantum states using shallow circuits [0.0]
量子シミュレーションとアルゴリズムの一般的な要件は、2量子ゲートのシーケンスを通して複雑な状態を作成することである。
ここでは、限られた数のゲートを用いて、ターゲット状態の近似符号化を作成することを目的とする。
我々の研究は、局所ゲートを用いて目標状態を作成する普遍的な方法を提供し、既知の戦略よりも大幅に改善されたことを示す。
論文 参考訳（メタデータ） (2022-06-30T18:00:04Z) - Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
Bernstein-Vaziraniアルゴリズムは、オラクルに符号化されたビット文字列を決定できる。
我々はベルンシュタイン・ヴァジラニアルゴリズムの量子資源を詳細に分析する。
絡み合いがない場合、初期状態における量子コヒーレンス量とアルゴリズムの性能が直接関係していることが示される。
論文 参考訳（メタデータ） (2022-05-26T20:32:36Z) - Efficiently Solve the Max-cut Problem via a Quantum Qubit Rotation
Algorithm [7.581898299650999]
我々はQQRA(Quantum Qubit Rotation Algorithm)という単純なアルゴリズムを導入する。
最大カット問題の近似解は 1 に近い確率で得られる。
我々は、よく知られた量子近似最適化アルゴリズムと古典的なゲーマン・ウィリアムソンアルゴリズムと比較する。
論文 参考訳（メタデータ） (2021-10-15T11:19:48Z) - On Applying the Lackadaisical Quantum Walk Algorithm to Search for
Multiple Solutions on Grids [63.75363908696257]
不足量子ウォーク(英: lackadaisical quantum walk)は、頂点が重量$l$の自己ループを持つグラフ構造を探索するために開発されたアルゴリズムである。
本稿では,グリッド上の複数解の探索に不連続な量子ウォークを適用した際の問題に対処する。
論文 参考訳（メタデータ） (2021-06-11T09:43:09Z) - Iterative Quantum Assisted Eigensolver [0.0]
我々は、ハミルトニアン基底状態を近似するハイブリッド量子古典アルゴリズムを提供する。
我々のアルゴリズムは、現在の量子コンピュータに適した方法で、強力なKrylov部分空間法に基づいている。
論文 参考訳（メタデータ） (2020-10-12T12:25:16Z) - Space-efficient binary optimization for variational computing [68.8204255655161]
本研究では,トラベリングセールスマン問題に必要なキュービット数を大幅に削減できることを示す。
また、量子ビット効率と回路深さ効率のモデルを円滑に補間する符号化方式を提案する。
論文 参考訳（メタデータ） (2020-09-15T18:17:27Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。