論文の概要: Circuit Design of Two-Step Quantum Search Algorithm for Solving Traveling Salesman Problems
- arxiv url: http://arxiv.org/abs/2405.07129v1
- Date: Sun, 12 May 2024 01:44:19 GMT
- ステータス: 処理完了
- システム内更新日: 2024-05-14 18:18:14.077821
- Title: Circuit Design of Two-Step Quantum Search Algorithm for Solving Traveling Salesman Problems
- Title（参考訳）: トラベリングセールスマン問題の解法のための2ステップ量子探索アルゴリズムの回路設計
- Authors: Rei Sato, Gordon Cui, Kazuhiro Saito, Hideyuki Kawashima, Tetsuro Nikuni, Shohei Watabe,
- Abstract要約: 旅行セールスマン問題(TSP)を解決するための現在の量子探索アルゴリズムは、制約を満たす実現可能な解状態の同値な重ね合わせの初期状態が既に予め用意されていると仮定する。
初期状態の準備とTSPの解決のための2つの異なる演算子を持つ2段階量子探索アルゴリズムを提案する。
我々のアルゴリズムは、高次非制約バイナリ最適化(HOBO)表現に符号化されており、特に必要量子ビット数を減少させる。
- 参考スコア（独自算出の注目度）: 1.4513830934124627
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Quantum search algorithms, such as Grover's algorithm, are expected to efficiently solve constrained combinatorial optimization problems. However, implementing a quantum search algorithm for solving the traveling salesman problem (TSP) on a circuit poses a potential challenge because current quantum search algorithms for TSP assume that an initial state of equal superposition of feasible solution states satisfying the constraint is already prepared a priori. The time complexity of brute-force preparation of the initial state increases exponentially with the factorial growth of feasible solutions, posing a considerable obstacle in designing quantum circuits for large-scale TSP. To overcome this problem, we propose a two-step quantum search algorithm with two distinct operators for preparing the initial state and solving TSP. The algorithm first amplifies an equal superposition state of all feasible solutions of TSP and subsequently amplifies the optimal solution states among these feasible solution states. Our algorithm, encoded in the higher-order unconstrained binary optimization (HOBO) representation, notably reduces the required number of qubits, enabling efficient preparation of the initial state with a unified circuit design and solving TSP with a quadratic speedup in the absence of prior knowledge of feasible solutions.
- Abstract（参考訳）: グロバーのアルゴリズムのような量子探索アルゴリズムは、制約付き組合せ最適化問題を効率的に解くことが期待されている。
しかし、サーキット上での走行セールスマン問題(TSP)を解決するための量子探索アルゴリズムの実装は、現在のTSPの量子探索アルゴリズムが、制約を満たす実現可能な解状態の等重畳の初期状態が既に予め用意されていると仮定しているため、潜在的に困難である。
ブライト力による初期状態の生成の時間的複雑さは、実現可能な解の因子的成長とともに指数関数的に増加し、大規模TSPのための量子回路の設計においてかなりの障害となる。
この問題を解決するために,2つの異なる演算子を持つ2段階の量子探索アルゴリズムを提案し,初期状態を作成してTSPを解く。
このアルゴリズムはまず、TSPのすべての実現可能な解の等しい重ね合わせ状態を増幅し、その後、これらの実現可能な解状態の最適解状態を増幅する。
我々のアルゴリズムは、高次非制約バイナリ最適化(HOBO)表現に符号化されており、特に要求されるキュービット数を減らし、統一回路設計による初期状態の効率的な作成と、実現可能な解の事前知識がない2次高速化による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) - Solving The Travelling Salesman Problem Using A Single Qubit [0.0]
トラベルセールスマン問題(TSP)はNP-ハード組合せ最適化問題として人気がある。
本稿では,量子並列性(quantum parallelism)の原理を導出し,単一量子ビットを用いて任意のTSPを解くアルゴリズムを提案する。
我々のアルゴリズムの基盤となるフレームワークは、古典的ブラキストクロンのアプローチの量子バージョンである。
論文 参考訳（メタデータ） (2024-07-24T12:06:37Z) - Optimized General Uniform Quantum State Preparation [0.0]
我々は,任意のN状態の均一な重ね合わせを調製し,奥行きを最小化し,アシラリー量子ビットを使わずに最適化された回路の一般解法を開発した。
このアルゴリズムは、特に2つのワイヤゲートの使用において効率的であり、IonQ量子コンピュータ上で検証され、量子非構造探索アルゴリズムに応用されていることを示す。
論文 参考訳（メタデータ） (2023-11-30T22:40:33Z) - Evaluating the Practicality of Quantum Optimization Algorithms for
Prototypical Industrial Applications [44.88678858860675]
本稿では,量子近似最適化アルゴリズム (QAOA) と量子断熱アルゴリズム (QAA) の応用について検討する。
我々は,これらの2つのアルゴリズムの性能を,選択した評価指標を用いて,ソリューションの品質の観点から比較する。
論文 参考訳（メタデータ） (2023-11-20T09:09:55Z) - Quantum Annealing for Single Image Super-Resolution [86.69338893753886]
単一画像超解像(SISR)問題を解くために,量子コンピューティングに基づくアルゴリズムを提案する。
提案したAQCアルゴリズムは、SISRの精度を維持しつつ、古典的なアナログよりも向上したスピードアップを実現する。
論文 参考訳（メタデータ） (2023-04-18T11:57:15Z) - Quantum Dueling: an Efficient Solution for Combinatorial Optimization [3.7398607565670536]
量子デュエル(quantum dueling)と呼ぶ汎用最適化のための新しいアルゴリズムを提案する。
量子デュエルは、追加のqubitレジスタを統合することで革新的であり、2組のソリューションが競合するデュエルのシナリオを効果的に生成する。
我々の研究は、量子ビットの数を増やすことで、これまで考えられていなかったアルゴリズムの開発が可能になり、効率的な量子アルゴリズム設計の進歩の道を開くことを実証している。
論文 参考訳（メタデータ） (2023-02-20T18:33:55Z) - 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) - Provably Faster Algorithms for Bilevel Optimization [54.83583213812667]
バイレベル最適化は多くの重要な機械学習アプリケーションに広く適用されている。
両レベル最適化のための2つの新しいアルゴリズムを提案する。
両アルゴリズムが$mathcalO(epsilon-1.5)$の複雑さを達成し,既存のアルゴリズムを桁違いに上回っていることを示す。
論文 参考訳（メタデータ） (2021-06-08T21:05:30Z) - Efficient Algorithms for Causal Order Discovery in Quantum Networks [44.356294905844834]
入力および出力システムへのブラックボックスアクセスを前提として,最初の効率的な量子因果順序探索アルゴリズムを開発した。
我々は、量子コムを用いて因果順序をモデル化し、我々のアルゴリズムは、与えられたプロセスと互換性のある入力と出力の順序を出力する。
我々のアルゴリズムは、量子通信ネットワークで利用可能な伝送経路を効率的に検出し、最適化する方法を提供する。
論文 参考訳（メタデータ） (2020-12-03T07:12:08Z) - Space-efficient binary optimization for variational computing [68.8204255655161]
本研究では,トラベリングセールスマン問題に必要なキュービット数を大幅に削減できることを示す。
また、量子ビット効率と回路深さ効率のモデルを円滑に補間する符号化方式を提案する。
論文 参考訳（メタデータ） (2020-09-15T18:17:27Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。