論文の概要: Circuit Design of Two-Step Quantum Search Algorithm for Solving Traveling Salesman Problems
- arxiv url: http://arxiv.org/abs/2405.07129v2
- Date: Mon, 07 Oct 2024 12:35:27 GMT
- ステータス: 翻訳完了
- システム内更新日: 2024-10-08 13:11:58.255584
- 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要約: 2組の演算子を用いた2段階量子探索(TSQS)アルゴリズムを提案する。
最初のステップでは、すべての実現可能な解は、同じ重ね合わせ状態に増幅される。
2番目のステップでは、この重ね合わせ状態から最適解状態が増幅される。
- 参考スコア(独自算出の注目度): 1.4513830934124627
- License:
- Abstract: Quantum search algorithms, such as Grover's algorithm, are anticipated to efficiently solve constrained combinatorial optimization problems. However, applying these algorithms to the traveling salesman problem (TSP) on a quantum circuit presents a significant challenge. Existing quantum search algorithms for the TSP typically assume that an initial state -- an equal superposition of all feasible solutions satisfying the problem's constraints -- is pre-prepared. The query complexity of preparing this state using brute-force methods scales exponentially with the factorial growth of feasible solutions, creating a significant hurdle in designing quantum circuits for large-scale TSPs. To address this issue, we propose a two-step quantum search (TSQS) algorithm that employs two sets of operators. In the first step, all the feasible solutions are amplified into their equal superposition state. In the second step, the optimal solution state is amplified from this superposition state. The TSQS algorithm demonstrates greater efficiency compared to conventional search algorithms that employ a single oracle operator for finding a solution within the encoded space. Encoded in the higher-order unconstrained binary optimization (HOBO) representation, our approach significantly reduces the qubit requirements. This enables efficient initial state preparation through a unified circuit design, offering a quadratic speedup in solving the TSP without prior knowledge of feasible solutions.
- Abstract(参考訳): グロバーのアルゴリズムのような量子探索アルゴリズムは、制約付き組合せ最適化問題を効率的に解くことが期待されている。
しかし、これらのアルゴリズムを量子回路上のトラベルセールスマン問題(TSP)に適用することは大きな課題である。
TSPの既存の量子探索アルゴリズムは、通常、初期状態 -- 問題の制約を満たす全ての実現可能な解の等しい重ね合わせ -- が準備されていると仮定する。
ブルートフォース法を用いてこの状態を作成する際のクエリの複雑さは、実現可能な解の因子的成長と指数関数的にスケールし、大規模TSPのための量子回路を設計する上で大きなハードルとなる。
この問題に対処するために,2組の演算子を用いた2段階量子探索(TSQS)アルゴリズムを提案する。
最初のステップでは、すべての実現可能な解は、同じ重ね合わせ状態に増幅される。
2番目のステップでは、この重ね合わせ状態から最適解状態が増幅される。
TSQSアルゴリズムは、符号化された空間内の解を見つけるために単一のオラクル演算子を用いる従来の探索アルゴリズムと比較して、より効率がよいことを示す。
高次非制約バイナリ最適化(HOBO)表現に符号化され、本手法は量子ビット要求を大幅に低減する。
これにより、統一回路設計による効率的な初期状態生成が可能となり、実現可能な解の事前知識を必要とせずに、TSPを解く際の2次高速化が提供される。
関連論文リスト
- T-Count Optimizing Genetic Algorithm for Quantum State Preparation [0.05999777817331316]
本稿では,Clifford+Tゲートセットのゲートからなる状態準備回路に対して,遺伝的アルゴリズムを提案する。
我々のアルゴリズムは、最もエラーが多いコンポーネントの数が減少するフォールトトレラント実装可能なソリューションを自動的に生成する。
論文 参考訳(メタデータ) (2024-06-06T12:26:14Z) - A Quantum Approach to solve N-Queens Problem [0.7373617024876725]
我々はN-Queens問題を解くために、2つの革新的な量子アルゴリズムを導入した。
N-クイーン問題(N-Queens problem)とは、N倍のN$チェスボードにN$クイーンを配置し、同じ行、列、対角線で互いに攻撃を受けないようにすることである。
このアルゴリズムは、制御されたW状態と動的回路を用いて、NP-Complete計算問題に効率的に対処する。
論文 参考訳(メタデータ) (2023-12-26T19:42:05Z) - 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) - Ising formulation of integer optimization problems for utilizing quantum
annealing in iterative improvement strategy [1.14219428942199]
繰り返し改善戦略において量子アニーリングを利用するために,整数最適化問題のイジング定式化を提案する。
基底状態と候補解との重なりがしきい値を超えた場合, 完全に連結されたフェロポッツモデルに対して一階相転移を回避できることを解析的に示す。
論文 参考訳(メタデータ) (2022-11-08T02:12:49Z) - Quadratic Unconstrained Binary Optimisation via Quantum-Inspired
Annealing [58.720142291102135]
本稿では,2次非制約二項最適化の事例に対する近似解を求める古典的アルゴリズムを提案する。
我々は、チューニング可能な硬さと植え付けソリューションを備えた大規模問題インスタンスに対して、我々のアプローチをベンチマークする。
論文 参考訳(メタデータ) (2021-08-18T09:26:17Z) - Implementable Hybrid Quantum Ant Colony Optimization Algorithm [0.0]
NP-hard問題に対する近似解を生成するための新しいハイブリッド量子アルゴリズムを提案する。
我々は,近距離量子コンピュータで真に実装できる改良されたアルゴリズムを開発した。
ノイズレス量子回路をシミュレートしたベンチマークと、IBM量子コンピュータを用いた実験により、アルゴリズムの有効性が示された。
論文 参考訳(メタデータ) (2021-07-08T13:50:51Z) - Polynomial unconstrained binary optimisation inspired by optical
simulation [52.11703556419582]
制約のないバイナリ最適化の問題を解決するために,光コヒーレントIsingマシンにヒントを得たアルゴリズムを提案する。
提案アルゴリズムを既存のPUBOアルゴリズムに対してベンチマークし,その優れた性能を観察する。
タンパク質の折り畳み問題や量子化学問題へのアルゴリズムの適用は、PUBO問題による電子構造問題の近似の欠点に光を当てる。
論文 参考訳(メタデータ) (2021-06-24T16:39:31Z) - Lower Bounds and Optimal Algorithms for Smooth and Strongly Convex
Decentralized Optimization Over Time-Varying Networks [79.16773494166644]
通信ネットワークのノード間を分散的に保存するスムーズで強い凸関数の和を最小化するタスクについて検討する。
我々は、これらの下位境界を達成するための2つの最適アルゴリズムを設計する。
我々は,既存の最先端手法と実験的な比較を行うことにより,これらのアルゴリズムの理論的効率を裏付ける。
論文 参考訳(メタデータ) (2021-06-08T15:54:44Z) - Quantum Permutation Synchronization [88.4588059792167]
本稿では,コンピュータビジョンの文脈における量子ビジョン問題を解決する量子アルゴリズムQuantumSyncを提案する。
本稿では、QUBO 問題に置換制約を挿入し、アバスティック量子 DWave コンピュータの電流生成に関する制約付き QUBO 問題を解決する方法を示す。
論文 参考訳(メタデータ) (2021-01-19T17:51:02Z) - Space-efficient binary optimization for variational computing [68.8204255655161]
本研究では,トラベリングセールスマン問題に必要なキュービット数を大幅に削減できることを示す。
また、量子ビット効率と回路深さ効率のモデルを円滑に補間する符号化方式を提案する。
論文 参考訳(メタデータ) (2020-09-15T18:17:27Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。