論文の概要: Out of the Loop: Structural Approximation of Optimisation Landscapes and non-Iterative Quantum Optimisation
- arxiv url: http://arxiv.org/abs/2408.06493v1
- Date: Mon, 12 Aug 2024 21:02:58 GMT
- ステータス: 処理完了
- システム内更新日: 2024-08-14 19:17:34.789358
- Title: Out of the Loop: Structural Approximation of Optimisation Landscapes and non-Iterative Quantum Optimisation
- Title（参考訳）: ループの外:最適化ランドスケープの構造近似と非Iterative Quantumtimization
- Authors: Tom Krüger, Wolfgang Mauerer,
- Abstract要約: 量子近似最適化アルゴリズム (quantum Approximate optimization algorithm, Qaoa) は、最適化のための量子古典的反復法として広く研究されている。
インスタンスに依存しないが問題固有の非定型計算に基づく新しいアルゴリズム変種を導入する。
我々のアプローチは、カオの量子非依存構造に関する長年の予想を証明することに基づいている。
- 参考スコア（独自算出の注目度）: 3.9857517408503567
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: The Quantum Approximate Optimisation Algorithm (qaoa) is a widely studied quantum-classical iterative heuristic for combinatorial optimisation. While qaoa targets problems in complexity class NP, the classical optimisation procedure required in every iteration is itself known to be NP-hard. Still, advantage over classical approaches is suspected for certain scenarios, but nature and origin of its computational power are not yet satisfactorily understood. By introducing means of efficiently and accurately approximating the qaoa optimisation landscape from solution space structures, we derive a new algorithmic variant: Instead of performing an iterative quantum-classical computation for each input instance, our non-iterative method is based on a quantum circuit that is instance-independent, but problem-specific. It matches or outperforms unit-depth qaoa for key combinatorial problems, despite reduced computational effort. Our approach is based on proving a long-standing conjecture regarding instance-independent structures in qaoa. By ensuring generality, we link existing empirical observations on qaoa parameter clustering to established approaches in theoretical computer science, and provide a sound foundation for understanding the link between structural properties of solution spaces and quantum optimisation.
- Abstract（参考訳）: 量子近似最適化アルゴリズム (Quantum Approximate Optimisation Algorithm, Qaoa) は、組合せ最適化のための量子古典的反復ヒューリスティックである。
カオアは複雑性クラスNPの問題を対象としているが、全ての反復で求められる古典的な最適化手順はNPハードであることが知られている。
それでも、古典的アプローチに対する優位性は特定のシナリオでは疑わしいが、その計算力の性質と起源はまだ十分に理解されていない。
解空間構造からカオア最適化景観を効率よく正確に近似する手法を導入することで、新しいアルゴリズムの変種を導き出す: 入力インスタンスごとに反復的な量子古典計算を実行する代わりに、インスタンスに依存しないが問題固有の量子回路をベースとする。
これは計算の労力を減らしたにもかかわらず、重要な組合せ問題に対して単位深度カオアと一致または上回る。
我々のアプローチは、カオのインスタンス非依存構造に関する長年の予想を証明することに基づいている。
一般性を確保することによって、カオアパラメータクラスタリングに関する既存の経験的観測を理論計算機科学の確立されたアプローチにリンクし、解空間の構造的性質と量子最適化とのリンクを理解するための音基盤を提供する。
関連論文リスト
- 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) - 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) - Variational Quantum Approximate Spectral Clustering for Binary
Clustering Problems [0.7550566004119158]
本稿では,変分量子近似スペクトルクラスタリング(VQASC)アルゴリズムを提案する。
VQASCは、伝統的に古典的な問題で必要とされるシステムサイズ、Nよりも少ないパラメータの最適化を必要とする。
合成と実世界の両方のデータセットから得られた数値結果について述べる。
論文 参考訳（メタデータ） (2023-09-08T17:54:42Z) - Sample Complexity for Quadratic Bandits: Hessian Dependent Bounds and
Optimal Algorithms [64.10576998630981]
最適なヘッセン依存型サンプルの複雑さを, 初めて厳密に評価した。
ヘシアン非依存のアルゴリズムは、すべてのヘシアンインスタンスに対して最適なサンプル複雑さを普遍的に達成する。
本アルゴリズムにより得られたサンプルの最適複雑さは,重み付き雑音分布においても有効である。
論文 参考訳（メタデータ） (2023-06-21T17:03:22Z) - A Review on Quantum Approximate Optimization Algorithm and its Variants [47.89542334125886]
量子近似最適化アルゴリズム(Quantum Approximate Optimization Algorithm、QAOA)は、難解な最適化問題を解くことを目的とした、非常に有望な変分量子アルゴリズムである。
この総合的なレビューは、様々なシナリオにおけるパフォーマンス分析を含む、QAOAの現状の概要を提供する。
我々は,提案アルゴリズムの今後の展望と方向性を探りながら,選択したQAOA拡張と変種の比較研究を行う。
論文 参考訳（メタデータ） (2023-06-15T15:28:12Z) - Quantum Optimisation for Continuous Multivariable Functions by a
Structured Search [0.0]
量子変分アルゴリズムは量子重ね合わせと絡み合いを利用して指数関数的に大きな解空間を最適化する。
量子変分アルゴリズムは、離散化された連続解空間の一般的な構造特性を利用して、連続多変数関数を効率的に最適化できることを示す。
論文 参考訳（メタデータ） (2022-10-12T14:16:06Z) - Iteration Complexity of Variational Quantum Algorithms [5.203200173190989]
雑音は量子回路のバイアスによる目的関数の評価を行う。
我々は、欠落した保証を導き、収束率が影響を受けないことを見出す。
論文 参考訳（メタデータ） (2022-09-21T19:18:41Z) - A quantum-inspired tensor network method for constrained combinatorial
optimization problems [5.904219009974901]
本稿では,一般に局所的に制約された最適化問題に対する量子インスパイアされたテンソルネットワークに基づくアルゴリズムを提案する。
我々のアルゴリズムは、興味のある問題に対してハミルトニアンを構築し、量子問題に効果的にマッピングする。
本研究は,本手法の有効性と応用の可能性を示すものである。
論文 参考訳（メタデータ） (2022-03-29T05:44:07Z) - Polynomial unconstrained binary optimisation inspired by optical
simulation [52.11703556419582]
制約のないバイナリ最適化の問題を解決するために,光コヒーレントIsingマシンにヒントを得たアルゴリズムを提案する。
提案アルゴリズムを既存のPUBOアルゴリズムに対してベンチマークし,その優れた性能を観察する。
タンパク質の折り畳み問題や量子化学問題へのアルゴリズムの適用は、PUBO問題による電子構造問題の近似の欠点に光を当てる。
論文 参考訳（メタデータ） (2021-06-24T16:39:31Z) - Adaptive pruning-based optimization of parameterized quantum circuits [62.997667081978825]
Variisyハイブリッド量子古典アルゴリズムは、ノイズ中間量子デバイスの使用を最大化する強力なツールである。
我々は、変分量子アルゴリズムで使用されるそのようなアンサーゼを「効率的な回路訓練」(PECT)と呼ぶ戦略を提案する。
すべてのアンサッツパラメータを一度に最適化する代わりに、PECTは一連の変分アルゴリズムを起動する。
論文 参考訳（メタデータ） (2020-10-01T18:14:11Z) - Cross Entropy Hyperparameter Optimization for Constrained Problem
Hamiltonians Applied to QAOA [68.11912614360878]
QAOA(Quantum Approximate Optimization Algorithm)のようなハイブリッド量子古典アルゴリズムは、短期量子コンピュータを実用的に活用するための最も奨励的なアプローチの1つである。
このようなアルゴリズムは通常変分形式で実装され、古典的な最適化法と量子機械を組み合わせて最適化問題の優れた解を求める。
本研究では,クロスエントロピー法を用いてランドスケープを形作り,古典的パラメータがより容易により良いパラメータを発見でき,その結果,性能が向上することを示す。
論文 参考訳（メタデータ） (2020-03-11T13:52:41Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。