論文の概要: 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と比較した数値実験により解析結果を補足し, 改良によって高い性能が維持され, 場合によっては数値結果も改善されている。
関連論文リスト
- Optimization by Decoded Quantum Interferometry [43.55132675053983]
本稿では,古典的復号化問題に対する古典的最適化問題を減じるための量子アルゴリズムを提案する。
DQIは、既知の量子時間古典アルゴリズムよりも近似比が良いことを示す。
論文 参考訳（メタデータ） (2024-08-15T17:47:42Z) - 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) - High-precision and low-depth eigenstate property estimation: theory and resource estimation [2.6811507121199325]
量子多体系の固有状態特性を推定することは、古典的および量子コンピューティングの双方にとって、長年にわたる、挑戦的な問題である。
本稿では,固有状態に対する固有値と観測可能な期待値を推定するランダムサンプリングアルゴリズムのフルスタック設計を提案する。
論文 参考訳（メタデータ） (2024-06-06T17:54:26Z) - Calculating response functions of coupled oscillators using quantum phase estimation [40.31060267062305]
量子コンピュータを用いた結合型古典的高調波発振器系の周波数応答関数の推定問題について検討する。
提案する量子アルゴリズムは,標準的な$sスパース,オーラクルベースのクエリアクセスモデルで動作する。
そこで,本アルゴリズムの簡単な適応により,時間内に無作為な結束木問題を解くことを示す。
論文 参考訳（メタデータ） (2024-05-14T15:28:37Z) - Quantum algorithms for Hopcroft's problem [45.45456673484445]
計算幾何学の基本的な問題であるホップクロフト問題に対する量子アルゴリズムについて検討する。
この問題の古典的な複雑さはよく研究されており、最もよく知られているアルゴリズムは$O(n4/3)の時間で動作する。
我々の結果は、時間複雑性が$widetilde O(n5/6)$の2つの異なる量子アルゴリズムである。
論文 参考訳（メタデータ） (2024-05-02T10:29:06Z) - Depth scaling of unstructured search via quantum approximate optimization [0.0]
変分量子アルゴリズムは、現在の量子計算のデファクトモデルとなっている。
そのような問題の1つは、ある文字列の特定のビットを見つけることで構成される非構造化探索である。
我々は、CTQWを用いてQAOA配列を復元し、最近のトロッター公式の理論の進歩を利用して、クエリの複雑さを束縛する。
論文 参考訳（メタデータ） (2024-03-22T18:00:03Z) - 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 Analysis for Double Q-learning [50.50058000948908]
二重Q-ラーニングのための非漸近的有限時間解析を初めて提供する。
同期と非同期の二重Q-ラーニングの両方が,グローバル最適化の$epsilon$-accurate近辺に収束することが保証されていることを示す。
論文 参考訳（メタデータ） (2020-09-29T18:48:21Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。