論文の概要: Comparative study of variations in quantum approximate optimization
algorithms for the Traveling Salesman Problem
- arxiv url: http://arxiv.org/abs/2307.07243v1
- Date: Fri, 14 Jul 2023 09:35:58 GMT
- ステータス: 処理完了
- システム内更新日: 2023-07-17 14:33:25.112552
- Title: Comparative study of variations in quantum approximate optimization
algorithms for the Traveling Salesman Problem
- Title（参考訳）: 巡回セールスマン問題の量子近似最適化アルゴリズムにおける変動の比較研究
- Authors: Wenyang Qian, Robert A. M. Basili, Mary Eshaghian-Wilner, Ashfaq
Khokhar, Glenn Luecke, James P. Vary
- Abstract要約: 本稿では,量子近似最適化アルゴリズム (QAOA) を用いたトラベリングセールスマン問題 (TSP) に取り組む。
ゲート型ディジタル量子シミュレータから得られた数値結果について述べる。
十分にバランスのとれたQAOAミキサーの設計は、長期的にはゲートベースのシミュレータと現実的な量子デバイスにとってより有望な可能性を示す。
- 参考スコア（独自算出の注目度）: 0.06524460254566902
- License: http://creativecommons.org/licenses/by-nc-nd/4.0/
- Abstract: The Traveling Salesman Problem (TSP) is one of the most often-used NP-Hard
problems in computer science to study the effectiveness of computing models and
hardware platforms. In this regard, it is also heavily used as a vehicle to
study the feasibility of the quantum computing paradigm for this class of
problems. In this paper, we tackle the TSP using the quantum approximate
optimization algorithm (QAOA) approach by formulating it as an optimization
problem. By adopting an improved qubit encoding strategy and a layerwise
learning optimization protocol, we present numerical results obtained from the
gate-based digital quantum simulator, specifically targeting TSP instances with
3, 4, and 5 cities. We focus on the evaluations of three distinctive QAOA mixer
designs, considering their performances in terms of numerical accuracy and
optimization cost. Notably, we find a well-balanced QAOA mixer design exhibits
more promising potential for gate-based simulators and realistic quantum
devices in the long run, an observation further supported by our noise model
simulations. Furthermore, we investigate the sensitivity of the simulations to
the TSP graph. Overall, our simulation results show the digital quantum
simulation of problem-inspired ansatz is a successful candidate for finding
optimal TSP solutions.
- Abstract（参考訳）: トラベリングセールスマン問題(TSP)は、コンピュータ科学においてコンピュータモデルとハードウェアプラットフォームの有効性を研究するために最もよく用いられるNP-Hard問題の一つである。
この点に関しては、この種の問題に対する量子コンピューティングパラダイムの実現可能性を研究する手段としても多用されている。
本稿では、量子近似最適化アルゴリズム(QAOA)を用いて、TSPを最適化問題として定式化する。
改良された量子ビット符号化戦略と階層学習最適化プロトコルを用いることで,3,4,5都市のtspインスタンスを対象とするゲート型ディジタル量子シミュレータから得られた数値結果を示す。
本稿では,3種類のQAOAミキサーの設計について,数値的精度と最適化コストの観点から評価する。
特に、バランスの取れたqaoaミキサーの設計は、長期にわたってゲートベースのシミュレータと現実的な量子デバイスに有望な可能性を示しており、ノイズモデルシミュレーションによりさらに支持されている。
さらに,シミュレーションのTSPグラフに対する感度について検討した。
シミュレーションの結果,問題にインスパイアされたアンサッツのディジタル量子シミュレーションが最適解の候補となることが示された。
関連論文リスト
- Performance Benchmarking of Quantum Algorithms for Hard Combinatorial Optimization Problems: A Comparative Study of non-FTQC Approaches [0.0]
本研究は、4つの異なる最適化問題にまたがっていくつかの非フォールト耐性量子コンピューティングアルゴリズムを体系的にベンチマークする。
我々のベンチマークには、変分量子固有解法など、ノイズの多い中間スケール量子(NISQ)アルゴリズムが含まれている。
以上の結果から,FTQC以外のアルゴリズムは全ての問題に対して最適に動作しないことが明らかとなり,アルゴリズム戦略の調整の必要性が浮き彫りになった。
論文 参考訳（メタデータ） (2024-10-30T08:41:29Z) - Quantum evolutionary algorithm for TSP combinatorial optimisation problem [0.0]
本稿では、量子遺伝的アルゴリズム(QGA)を用いて、旅行セールスマン問題(TSP)と呼ばれる新しい問題を解決する方法を実装する。
我々は、この新しいアプローチがいかにうまく機能するかを、古典的遺伝的アルゴリズム(CGA)として知られる従来の手法と比較した。
論文 参考訳（メタデータ） (2024-09-20T08:27:42Z) - Bayesian Parameterized Quantum Circuit Optimization (BPQCO): A task and hardware-dependent approach [49.89480853499917]
変分量子アルゴリズム(VQA)は、最適化と機械学習問題を解決するための有望な量子代替手段として登場した。
本稿では,回路設計が2つの分類問題に対して得られる性能に与える影響を実験的に示す。
また、実量子コンピュータのシミュレーションにおいて、ノイズの存在下で得られた回路の劣化について検討する。
論文 参考訳（メタデータ） (2024-04-17T11:00:12Z) - Towards Optimizations of Quantum Circuit Simulation for Solving Max-Cut
Problems with QAOA [1.5047640669285467]
量子近似最適化アルゴリズム(QAOA)は、近似を用いて最適化問題を解くために用いられる一般的な量子アルゴリズムの1つである。
しかし、仮想量子コンピュータ上でのQAOAの実行は、最適化問題を解くのに遅いシミュレーション速度に悩まされている。
本稿では,QAOAの量子演算を数学的に最適化し,QCSを高速化する手法を提案する。
論文 参考訳（メタデータ） (2023-12-05T06:08:57Z) - Qubit efficient quantum algorithms for the vehicle routing problem on
NISQ processors [48.68474702382697]
時間窓付き車両ルーティング問題(VRPTW)は、ロジスティクス業界で直面する一般的な最適化問題である。
そこで本研究では,以前に導入した量子ビット符号化方式を用いて,バイナリ変数の数を削減した。
論文 参考訳（メタデータ） (2023-06-14T13:44:35Z) - Performance comparison of optimization methods on variational quantum
algorithms [2.690135599539986]
変分量子アルゴリズム(VQA)は、学術・工業研究への応用に短期的な量子ハードウェアを使用するための有望な道を提供する。
SLSQP, COBYLA, CMA-ES, SPSAの4つの最適化手法の性能について検討した。
論文 参考訳（メタデータ） (2021-11-26T12:13:20Z) - Variational Quantum Optimization with Multi-Basis Encodings [62.72309460291971]
マルチバスグラフ複雑性と非線形活性化関数の2つの革新の恩恵を受ける新しい変分量子アルゴリズムを導入する。
その結果,最適化性能が向上し,有効景観が2つ向上し,測定の進歩が減少した。
論文 参考訳（メタデータ） (2021-06-24T20:16:02Z) - Fixed Depth Hamiltonian Simulation via Cartan Decomposition [59.20417091220753]
時間に依存しない深さの量子回路を生成するための構成的アルゴリズムを提案する。
一次元横フィールドXYモデルにおけるアンダーソン局在化を含む、モデルの特殊クラスに対するアルゴリズムを強調する。
幅広いスピンモデルとフェルミオンモデルに対して正確な回路を提供するのに加えて、我々のアルゴリズムは最適なハミルトニアンシミュレーションに関する幅広い解析的および数値的な洞察を提供する。
論文 参考訳（メタデータ） (2021-04-01T19:06:00Z) - Adaptive pruning-based optimization of parameterized quantum circuits [62.997667081978825]
Variisyハイブリッド量子古典アルゴリズムは、ノイズ中間量子デバイスの使用を最大化する強力なツールである。
我々は、変分量子アルゴリズムで使用されるそのようなアンサーゼを「効率的な回路訓練」(PECT)と呼ぶ戦略を提案する。
すべてのアンサッツパラメータを一度に最適化する代わりに、PECTは一連の変分アルゴリズムを起動する。
論文 参考訳（メタデータ） (2020-10-01T18:14:11Z) - Space-efficient binary optimization for variational computing [68.8204255655161]
本研究では,トラベリングセールスマン問題に必要なキュービット数を大幅に削減できることを示す。
また、量子ビット効率と回路深さ効率のモデルを円滑に補間する符号化方式を提案する。
論文 参考訳（メタデータ） (2020-09-15T18:17:27Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。