論文の概要: Depth scaling of unstructured search via quantum approximate optimization
- arxiv url: http://arxiv.org/abs/2403.15540v2
- Date: Mon, 15 Jul 2024 11:12:58 GMT
- ステータス: 処理完了
- システム内更新日: 2024-07-17 01:25:37.956594
- Title: Depth scaling of unstructured search via quantum approximate optimization
- Title（参考訳）: 量子近似最適化による非構造探索の深さスケーリング
- Authors: Ernesto Campos, Daniil Rabinovich, Alexey Uvarov,
- Abstract要約: 変分量子アルゴリズムは、現在の量子計算のデファクトモデルとなっている。
そのような問題の1つは、ある文字列の特定のビットを見つけることで構成される非構造化探索である。
我々は、CTQWを用いてQAOA配列を復元し、最近のトロッター公式の理論の進歩を利用して、クエリの複雑さを束縛する。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Variational quantum algorithms have become the de facto model for current quantum computations. A prominent example of such algorithms -- the quantum approximate optimization algorithm (QAOA) -- was originally designed for combinatorial optimization tasks, but has been shown to be successful for a variety of other problems. However, for most of these problems the optimal circuit depth remains unknown. One such problem is unstructured search which consists on finding a particular bit string, or equivalently, preparing a state of high overlap with a target state. To bound the optimal QAOA depth for such problem we build on its known solution in a continuous time quantum walk (CTQW). We trotterize a CTQW to recover a QAOA sequence, and employ recent advances on the theory of Trotter formulas to bound the query complexity (circuit depth) needed to prepare a state of almost perfect overlap with the target state. The obtained complexity exceeds the Grover's algorithm complexity $O\left(N^\frac{1}{2}\right)$, but remains smaller than $O \left(N^{\frac{1}{2}+c}\right)$ for any $c>0$, which shows quantum advantage of QAOA over classical solutions. We verify our analytical predictions by numerical simulations of up to 68 qubits, which demonstrate that our result overestimates the number of QAOA layers resulting from a trotterized CTQW by at most a polynomial factor.
- Abstract（参考訳）: 変分量子アルゴリズムは、現在の量子計算のデファクトモデルとなっている。
このようなアルゴリズムの顕著な例である量子近似最適化アルゴリズム(QAOA)は、もともと組合せ最適化タスクのために設計されたものであるが、他の様々な問題に対して成功したことが示されている。
しかし、これらの問題の多くは最適回路深さが不明である。
そのような問題の1つは、特定のビット文字列を見つけること、または同等に、ターゲット状態と高い重なり合う状態を作成することで構成される非構造化探索である。
このような問題に対して最適なQAOA深さをバウンドするには、その既知の解を連続時間量子ウォーク(CTQW)で構築する。
我々はCTQWを用いてQAOAシークエンスを復元し、ターゲット状態とほぼ完全に重なる状態を作成するのに必要なクエリ複雑性(回路深さ)を束縛するために、最近のトロッター公式理論の進歩を利用する。
得られた複雑性はグロバーのアルゴリズムの複雑さ$O\left(N^\frac{1}{2}\right)$を超えるが、古典解よりもQAOAの量子的優位性を示す任意の$c>0$に対して$O \left(N^{\frac{1}{2}+c}\right)$よりも小さい。
我々は,最大68量子ビットの数値シミュレーションにより解析的予測を検証し,この結果から,少なくとも多項式係数による散乱CTQWから得られたQAOA層数を過大評価することを示した。
関連論文リスト
- Quantum conjugate gradient method using the positive-side quantum eigenvalue transformation [0.35794129023851595]
量子固有値変換(QET)を用いた量子共役勾配(QCG)法を提案する。
数値的な結果から,本アルゴリズムは回路深度を大幅に改善し,QETに基づく別のアルゴリズムよりも3～4桁の精度で性能を向上する。
論文 参考訳（メタデータ） (2024-04-03T13:13:55Z) - Quantum Subroutine for Variance Estimation: Algorithmic Design and Applications [80.04533958880862]
量子コンピューティングは、アルゴリズムを設計する新しい方法の基礎となる。
どの場の量子スピードアップが達成できるかという新たな課題が生じる。
量子サブルーチンの設計は、従来のサブルーチンよりも効率的で、新しい強力な量子アルゴリズムに固い柱を向ける。
論文 参考訳（メタデータ） (2024-02-26T09:32:07Z) - Variational Quantum Algorithms for the Allocation of Resources in a Cloud/Edge Architecture [1.072460284847973]
変分量子アルゴリズムは, 近い将来, 古典的アルゴリズムの代替となる可能性が示唆された。
特に、2つのアルゴリズム、すなわち量子近似最適化アルゴリズム(QAOA)と変分量子固有解器(VQE)の性能を比較した。
シミュレーション実験は、クラウドと2つのエッジノードを含む %CM230124 の単純な問題に対して実施され、VQE アルゴリズムは、検索空間を制限できる適切な回路テクスタイタンサッチを備えている場合に、より良い性能を保証することを示す。
論文 参考訳（メタデータ） (2024-01-25T17:37:40Z) - Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。
量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
論文 参考訳（メタデータ） (2022-12-06T22:01:49Z) - Optimizing the depth of variational quantum algorithms is strongly
QCMA-hard to approximate [0.6445605125467572]
変分量子アルゴリズム (VQA) は、量子ハードウェアへの短期的応用に向けて激しい研究が行われている。
VQA の重要なパラメータは変分アンザッツ' のエンプデプス' である。
与えられたVQAアンザッツの最適深さを近似することは困難であることを示す。
論文 参考訳（メタデータ） (2022-11-22T19:00:01Z) - Complexity-Theoretic Limitations on Quantum Algorithms for Topological
Data Analysis [59.545114016224254]
トポロジカルデータ解析のための量子アルゴリズムは、古典的手法よりも指数関数的に有利である。
我々は、量子コンピュータにおいても、TDA(ベッチ数の推定)の中心的なタスクが難解であることを示します。
我々は、入力データが単純さの仕様として与えられると、指数的量子優位性を取り戻すことができると論じる。
論文 参考訳（メタデータ） (2022-09-28T17:53:25Z) - An entanglement perspective on the quantum approximate optimization
algorithm [0.0]
ランダム化および最適化されたQAOA回路による絡み合いの増大と広がりについて検討する。
また、ランダム行列理論に関連する絡み合いスペクトルについても検討する。
論文 参考訳（メタデータ） (2022-06-14T17:37:44Z) - Adiabatic Quantum Computing for Multi Object Tracking [170.8716555363907]
マルチオブジェクト追跡(MOT)は、オブジェクト検出が時間を通して関連付けられているトラッキング・バイ・検出のパラダイムにおいて、最もよくアプローチされる。
これらの最適化問題はNPハードであるため、現在のハードウェア上の小さなインスタンスに対してのみ正確に解決できる。
本手法は,既成整数計画法を用いても,最先端の最適化手法と競合することを示す。
論文 参考訳（メタデータ） (2022-02-17T18:59:20Z) - Q-Match: Iterative Shape Matching via Quantum Annealing [64.74942589569596]
形状対応を見つけることは、NP-hard quadratic assignment problem (QAP)として定式化できる。
本稿では,アルファ拡大アルゴリズムに触発されたQAPの反復量子法Q-Matchを提案する。
Q-Match は、実世界の問題にスケールできるような長文対応のサブセットにおいて、反復的に形状マッチング問題に適用できる。
論文 参考訳（メタデータ） (2021-05-06T17:59:38Z) - An optimal quantum sampling regression algorithm for variational
eigensolving in the low qubit number regime [0.0]
量子サンプリング回帰(QSR)は、代替の量子古典的アルゴリズムである。
低量子ビット数構造における時間的複雑さに基づいて,その利用事例を分析した。
ベンチマーク問題に対するアルゴリズムの有効性を示す。
論文 参考訳（メタデータ） (2020-12-04T00:01:15Z) - Space-efficient binary optimization for variational computing [68.8204255655161]
本研究では,トラベリングセールスマン問題に必要なキュービット数を大幅に削減できることを示す。
また、量子ビット効率と回路深さ効率のモデルを円滑に補間する符号化方式を提案する。
論文 参考訳（メタデータ） (2020-09-15T18:17:27Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。