論文の概要: A Realizable GAS-based Quantum Algorithm for Traveling Salesman Problem

• arxiv url: http://arxiv.org/abs/2212.02735v1
• Date: Tue, 6 Dec 2022 03:54:07 GMT
• ステータス: 処理完了
• システム内更新日: 2023-01-09 17:38:35.993627
• Title: A Realizable GAS-based Quantum Algorithm for Traveling Salesman Problem
• Title（参考訳）: 走行セールスマン問題に対するガスベース量子アルゴリズムの実現
• Authors: Jieao Zhu, Yihuai Gao, Hansen Wang, Tiefu Li, and Hao Wu
• Abstract要約: 本稿では,Grover Adaptive Search(GAS)に基づく旅行セールスマン問題(TSP)の量子アルゴリズムを提案する。 この戦略は量子コンピューティングの可逆性要件を完全に考慮し、使用した量子ビットが単に上書きやリリースできないという難しさを克服する。 7ノードのTSPでは31量子ビットしか必要とせず、最適解を得る成功率は86.71%である。
• 参考スコア（独自算出の注目度）: 2.208581695286558
• License: http://creativecommons.org/publicdomain/zero/1.0/
• Abstract: The paper proposes a quantum algorithm for the traveling salesman problem (TSP) based on the Grover Adaptive Search (GAS), which can be successfully executed on IBM's Qiskit library. Under the GAS framework, there are at least two fundamental difficulties that limit the application of quantum algorithms for combinatorial optimization problems. One difficulty is that the solutions given by the quantum algorithms may not be feasible. The other difficulty is that the number of qubits of current quantum computers is still very limited, and it cannot meet the minimum requirements for the number of qubits required by the algorithm. In response to the above difficulties, we designed and improved the Hamiltonian Cycle Detection (HCD) oracle based on mathematical theorems. It can automatically eliminate infeasible solutions during the execution of the algorithm. On the other hand, we design an anchor register strategy to save the usage of qubits. The strategy fully considers the reversibility requirement of quantum computing, overcoming the difficulty that the used qubits cannot be simply overwritten or released. As a result, we successfully implemented the numerical solution to TSP on IBM's Qiskit. For the seven-node TSP, we only need 31 qubits, and the success rate in obtaining the optimal solution is 86.71%.
• Abstract（参考訳）: 本稿では,IBMのQiskitライブラリ上で実行可能なGrover Adaptive Search(GAS)に基づく,旅行セールスマン問題(TSP)の量子アルゴリズムを提案する。 GASフレームワークでは、組合せ最適化問題に対する量子アルゴリズムの適用を制限する、少なくとも2つの基本的な困難がある。 1つの困難は、量子アルゴリズムによって与えられる解は実現不可能であるかもしれないことである。 もう1つの難点は、現在の量子コンピュータの量子ビット数はまだ非常に限られており、アルゴリズムが要求する量子ビット数の最小要件を満たせないことである。 上記の困難に対応するため,我々は数理定理に基づくハミルトニアンサイクル検出(hcd)オラクルを設計し,改良した。 アルゴリズムの実行中に無効なソリューションを自動的に排除することができる。 一方,我々は,qubitsの使用を節約するためのアンカーレジスタ戦略を設計した。 この戦略は量子コンピューティングの可逆性要件を完全に考慮し、使用する量子ビットが単に上書きや解放できないという難しさを克服する。 その結果,IBMのQiskit上でTSPの数値解を実現した。 7ノードのTSPでは31量子ビットしか必要とせず、最適解を得る成功率は86.71%である。

関連論文リスト

• Solving The Travelling Salesman Problem Using A Single Qubit [0.0]
  トラベルセールスマン問題(TSP)はNP-ハード組合せ最適化問題として人気がある。 本稿では,量子並列性(quantum parallelism)の原理を導出し,単一量子ビットを用いて任意のTSPを解くアルゴリズムを提案する。 我々のアルゴリズムの基盤となるフレームワークは、古典的ブラキストクロンのアプローチの量子バージョンである。
  論文  参考訳（メタデータ） (2024-07-24T12:06:37Z)
• A Framework to Formulate Pathfinding Problems for Quantum Computing [2.9723999564214267]
  パスフィンディング問題に対するQUBOの定式化を自動的に生成するフレームワークを提案する。 手作業による修正作業を必要とせずに簡単に比較できる3つの異なる符号化スキームをサポートしている。 結果として得られるQUBOの定式化は堅牢で効率的であり、それまでの面倒でエラーを起こしやすい改定プロセスを減らす。
  論文  参考訳（メタデータ） (2024-04-16T18:00:06Z)
• Solving various NP-Hard problems using exponentially fewer qubits on a Quantum Computer [0.0]
  NPハード問題は、一般時間アルゴリズムで正確に解けるとは考えられていない。 本稿では,問題のサイズに応じて対数的にスケールする独自手法を構築した。 これらのアルゴリズムは、100以上のノードのグラフサイズを持つ量子シミュレータと、256のグラフサイズまでの実際の量子コンピュータでテストされる。
  論文  参考訳（メタデータ） (2023-01-17T16:03:33Z)
• Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
  量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。 量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
  論文  参考訳（メタデータ） (2022-12-06T22:01:49Z)
• Complexity-Theoretic Limitations on Quantum Algorithms for Topological Data Analysis [59.545114016224254]
  トポロジカルデータ解析のための量子アルゴリズムは、古典的手法よりも指数関数的に有利である。 我々は、量子コンピュータにおいても、TDA(ベッチ数の推定)の中心的なタスクが難解であることを示します。 我々は、入力データが単純さの仕様として与えられると、指数的量子優位性を取り戻すことができると論じる。
  論文  参考訳（メタデータ） (2022-09-28T17:53:25Z)
• Iterative Qubits Management for Quantum Index Searching in a Hybrid System [56.39703478198019]
  IQuCSは、量子古典ハイブリッドシステムにおけるインデックス検索とカウントを目的としている。 我々はQiskitでIQuCSを実装し、集中的な実験を行う。 その結果、量子ビットの消費を最大66.2%削減できることが示されている。
  論文  参考訳（メタデータ） (2022-09-22T21:54:28Z)
• 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)
• Adiabatic Quantum Graph Matching with Permutation Matrix Constraints [75.88678895180189]
  3次元形状と画像のマッチング問題は、NPハードな置換行列制約を持つ二次代入問題(QAP)としてしばしば定式化される。 本稿では,量子ハードウェア上での効率的な実行に適した制約のない問題として,いくつかのQAPの再構成を提案する。 提案アルゴリズムは、将来の量子コンピューティングアーキテクチャにおいて、より高次元にスケールする可能性がある。
  論文  参考訳（メタデータ） (2021-07-08T17:59:55Z)
• Space-efficient binary optimization for variational computing [68.8204255655161]
  本研究では,トラベリングセールスマン問題に必要なキュービット数を大幅に削減できることを示す。 また、量子ビット効率と回路深さ効率のモデルを円滑に補間する符号化方式を提案する。
  論文  参考訳（メタデータ） (2020-09-15T18:17:27Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。