論文の概要: Modified Iterative Quantum Amplitude Estimation is Asymptotically
Optimal
- arxiv url: http://arxiv.org/abs/2208.14612v2
- Date: Mon, 14 Nov 2022 19:46:37 GMT
- ステータス: 処理完了
- システム内更新日: 2023-01-28 09:21:27.140733
- Title: Modified Iterative Quantum Amplitude Estimation is Asymptotically
Optimal
- Title(参考訳): 修正反復量子振幅推定は漸近的に最適である
- Authors: Shion Fukuzawa, Christopher Ho, Sandy Irani, Jasen Zion
- Abstract要約: 量子振幅推定(QAE)のための最初のQFTフリーアルゴリズムを提供する。
QAEアルゴリズムは量子コンピュータの多くの応用においてサブルーチンとして現れる。
- 参考スコア(独自算出の注目度): 0.37798600249187286
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In this work, we provide the first QFT-free algorithm for Quantum Amplitude
Estimation (QAE) that is asymptotically optimal while maintaining the leading
numerical performance. QAE algorithms appear as a subroutine in many
applications for quantum computers. The optimal query complexity achievable by
a quantum algorithm for QAE is $O\left(\frac{1}{\epsilon}\log
\frac{1}{\alpha}\right)$ queries, providing a speedup of a factor of
$1/\epsilon$ over any other classical algorithm for the same problem. The
original algorithm for QAE utilizes the quantum Fourier transform (QFT) which
is expected to be a challenge for near-term quantum hardware. To solve this
problem, there has been interest in designing a QAE algorithm that avoids using
QFT. Recently, the iterative QAE algorithm (IQAE) was introduced by Grinko et
al. with a near-optimal $O\left(\frac{1}{\epsilon}\log \left(\frac{1}{\alpha}
\log \frac{1}{\epsilon}\right)\right)$ query complexity and small constant
factors. In this work, we combine ideas from the preceding line of work to
introduce a QFT-free QAE algorithm that maintains the asymptotically optimal
$O\left(\frac{1}{\epsilon}\log \frac{1}{\alpha}\right)$ query complexity while
retaining small constant factors. We supplement our analysis with numerical
experiments comparing our performance with IQAE where we find that our
modifications retain the high performance, and in some cases even improve the
numerical results.
- Abstract(参考訳): 本研究は,量子振幅推定(QAE)のためのQFTフリーアルゴリズムとして,先行する数値性能を維持しつつ,漸近的に最適である。
QAEアルゴリズムは量子コンピュータの多くの応用においてサブルーチンとして現れる。
QAEの量子アルゴリズムで達成可能な最適なクエリ複雑性は$O\left(\frac{1}{\epsilon}\log \frac{1}{\alpha}\right)$クエリであり、同じ問題に対して他の古典的アルゴリズムよりも1/\epsilon$の高速化を提供する。
QAEのアルゴリズムは量子フーリエ変換(QFT)を用いており、これは短期量子ハードウェアの課題であると考えられている。
この問題を解決するために、QFTの使用を避けるQAEアルゴリズムの設計に興味がある。
近年、Grinkoらにより反復QAEアルゴリズム (IQAE) が導入され、クエリの複雑さと小さな定数要素がほぼ最適である$O\left(\frac{1}{\epsilon}\log \left(\frac{1}{\alpha} \log \frac{1}{\epsilon}\right)\right)が導入された。
本研究では、先行研究のアイデアを組み合わせて、QFTフリーQAEアルゴリズムを導入し、漸近的に最適な$O\left(\frac{1}{\epsilon}\log \frac{1}{\alpha}\right)$クエリ複雑性を維持しながら、小さな定数要素を保持する。
IQAEと比較した数値実験により解析結果を補足し, 改良によって高い性能が維持され, 場合によっては数値結果も改善されている。
関連論文リスト
- Quantum Circuit Optimization with AlphaTensor [47.9303833600197]
我々は,所定の回路を実装するために必要なTゲート数を最小化する手法であるAlphaTensor-Quantumを開発した。
Tカウント最適化の既存の方法とは異なり、AlphaTensor-Quantumは量子計算に関するドメイン固有の知識を取り入れ、ガジェットを活用することができる。
注目すべきは、有限体における乗法であるカラツバの手法に似た効率的なアルゴリズムを発見することである。
論文 参考訳(メタデータ) (2024-02-22T09:20:54Z) - Quantum Variational Algorithms for the Allocation of Resources in a
Cloud/Edge Architecture [1.1715858161748576]
クラウド/エッジアーキテクチャは、異種コンピューティングノードの複数のレイヤを編成する必要がある。
異なるノード上での計算の最適割り当てとスケジューリングは非常に難しい問題であり、NP困難である。
近い将来,変分量子アルゴリズムが古典的アルゴリズムの代替となる可能性が示唆された。
論文 参考訳(メタデータ) (2024-01-25T17:37:40Z) - Generalized Quantum Signal Processing [0.6768558752130311]
本稿では、一般的なSU(2)回転を信号処理演算子として用いた一般化量子信号処理手法を提案する。
我々のアプローチは、達成可能な変換の族に対するすべての実用的な制限を持ち上げ、残りの唯一の条件は、$|P|leq 1$である。
P$しか知られていない場合、我々は1分以内で識別できる効率的なGPU最適化を提供し、それに対応する$Q$は107$である。
論文 参考訳(メタデータ) (2023-08-03T01:51:52Z) - Quantum Phase Estimation by Compressed Sensing [0.0]
圧縮センシングに基づく初期量子コンピュータのための新しいハイゼンベルク制限量子位相推定アルゴリズムを提案する。
我々のアルゴリズムは、合計ランタイム$mathcalO(epsilon-1textpolylog(epsilon-1))$で周波数を復元することができる。
また、より一般的な量子固有値推定問題(QEEP)を考察し、オフグリッド圧縮センシングがQEEPの解決の有力な候補であることを示す。
論文 参考訳(メタデータ) (2023-06-12T10:21:59Z) - Efficient quantum linear solver algorithm with detailed running costs [0.0]
量子信号処理に基づくフィルタリング手法を用いて,アイデアダイアバティックな量子コンピューティングを組み合わせた量子線形解法アルゴリズムを提案する。
我々のプロトコルは、初期実装において、最先端技術に対する量子線形解決器のコストを桁違いに削減する。
論文 参考訳(メタデータ) (2023-05-19T00:07:32Z) - On the Global Convergence of Fitted Q-Iteration with Two-layer Neural
Network Parametrization [33.12181620473604]
本稿では,2層型ReLUニューラルネットワークを用いたQ-Iterationについて検討し,アルゴリズムの複雑さの保証を求める。
このアプローチは,オーダー最適化である $tildemathcalO (1/epsilon2)$ のサンプル複雑性を実現する。
論文 参考訳(メタデータ) (2022-11-14T19:00:24Z) - Study of Adaptative Derivative-Assemble Pseudo-Trotter Ansatzes in VQE
through qiskit API [0.0]
変分量子アルゴリズム(VQA)は、量子位相推定アルゴリズムの問題を解決するために設計された。
ADAPT-VQEは最小数のパラメータを持つ準最適アンサッツを決定する。
パラメータ数、精度、H2およびLiH分子で使用されるCNOTゲートの数など、これらのアルゴリズムをすべて異なる基準で比較する。
論文 参考訳(メタデータ) (2022-10-25T16:53:14Z) - Finite-Time Error Bounds for Greedy-GQ [25.655180037837766]
We show that Greedy-GQ algorithm converges under $1/s。
我々の分析は、実際の収束を早めるためのステップサイズの選択を提供し、貿易の複雑さと得られた政策の質を示唆する。
論文 参考訳(メタデータ) (2022-09-06T15:04:57Z) - Best of Both Worlds: Practical and Theoretically Optimal Submodular
Maximization in Parallel [32.5364938726281]
主アルゴリズムは、独立した関心を持つ可能性のある2つのコンポーネントから組み立てられる。
LINEARSEQの変種は、文献のどのアルゴリズムよりも小さい$O(log(n))$の適応複雑性を持つ。
論文 参考訳(メタデータ) (2021-11-15T17:10:40Z) - Finite-Time Analysis for Double Q-learning [50.50058000948908]
二重Q-ラーニングのための非漸近的有限時間解析を初めて提供する。
同期と非同期の二重Q-ラーニングの両方が,グローバル最適化の$epsilon$-accurate近辺に収束することが保証されていることを示す。
論文 参考訳(メタデータ) (2020-09-29T18:48:21Z) - Momentum Q-learning with Finite-Sample Convergence Guarantee [49.38471009162477]
本稿では,有限サンプル保証を用いたモーメントに基づくQ-ラーニングアルゴリズムのクラスを解析する。
線形関数近似とマルコフサンプリングによるMomentumQの収束保証を確立する。
提案したMomentumQが他のモーメントベースのQ-ラーニングアルゴリズムより優れていることを示す。
論文 参考訳(メタデータ) (2020-07-30T12:27:03Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。