論文の概要: Low Depth Phase Oracle Using a Parallel Piecewise Circuit
- arxiv url: http://arxiv.org/abs/2409.04587v2
- Date: Tue, 08 Oct 2024 17:53:38 GMT
- ステータス: 翻訳完了
- システム内更新日: 2024-10-10 16:16:19.779561
- Title: Low Depth Phase Oracle Using a Parallel Piecewise Circuit
- Title(参考訳): 並列回路を用いた低深さOracle
- Authors: Zhu Sun, Gregory Boyd, Zhenyu Cai, Hamza Jnane, Balint Koczor, Richard Meister, Romy Minko, Benjamin Pring, Simon C. Benjamin, Nikitas Stamatopoulos,
- Abstract要約: 位相 $exp(i f(x))$ を計算基底状態 $left| x right>$ に適用する重要なタスクについて検討する。
また、ターゲット qubit を$f(x)$ に依存する角度で回転させる密接な関連するタスクについても検討する。
- 参考スコア(独自算出の注目度): 3.629687485125086
- License:
- Abstract: We explore the important task of applying a phase $exp(i f(x))$ to a computational basis state $\left| x \right>$. The closely related task of rotating a target qubit by an angle depending on $f(x)$ is also studied. Such operations are key in many quantum subroutines, and often the function $f$ can be well-approximated by a piecewise linear composition. Examples range from the application of diagonal Hamiltonian terms (such as the Coulomb interaction) in grid-based many-body simulation, to derivative pricing algorithms. Here we exploit a parallelisation of the piecewise approach so that all constituent elementary rotations are performed simultaneously, that is, we achieve a total rotation depth of one. Moreover, we explore the use of recursive catalyst 'towers' to implement these elementary rotations efficiently. Depending on the choice of implementation strategy, we find a depth as low as $O(log n + log S)$ for a register of $n$ qubits and a piecewise approximation of $S$ sections. In the limit of multiple repetitions of the oracle, we find that catalyst tower approaches have an $O(S \cdot n)$ T-count, whereas linear interpolation with QROM has an $O(n^{log_2(3)})$ T-count.
- Abstract(参考訳): 位相 $exp(i f(x))$ を計算基底状態 $\left| x \right>$ に適用する重要なタスクについて検討する。
また、ターゲット qubit を$f(x)$ に依存する角度で回転させる密接な関連するタスクについても検討する。
このような演算は多くの量子サブルーチンにおいて鍵であり、しばしば関数 $f$ は断片的な線形合成によってうまく近似することができる。
例えば、グリッドベースの多体シミュレーションにおける対角的ハミルトン項(クーロン相互作用など)の応用から、微分価格アルゴリズムまで様々である。
ここでは,すべての基本回転を同時に行うために,片方向アプローチの並列化を利用して,全回転深度を1とする。
さらに, これらの基本回転を効率的に実装するために, 再帰触媒「塔」の使用について検討する。
実装戦略の選択により、$O(log n + log S)$のレジスタと$S$セクションの断片的な近似に対して、深さが$O(log n + log S)$と低いことが分かる。
オラクルの繰り返しの極限において、触媒塔のアプローチは$O(S \cdot n)$ T-countを持つのに対し、QROMとの線形補間は$O(n^{log_2(3)})$ T-countを持つ。
関連論文リスト
- Single-qubit rotation algorithm with logarithmic Toffoli count and gate depth [0.0]
我々のアルゴリズムは、繰り返し固定回転を適用するのではなく、直ちに$R_thetaast$を適用する。
厳密に1/2$以上の確率で成功し、予想されるトフォリ数対数$tfrac1epsilon$、期待されるゲート深さ$tfrac1epsilon$で対数を持つ。
論文 参考訳(メタデータ) (2024-04-08T15:46:56Z) - Fast parallel sampling under isoperimetry [10.619901778151336]
ログソボレフの不等式を満たすディストリビューション$pi$ over $mathbb Rd$から並列にサンプリングする方法を示す。
提案アルゴリズムは分布$hatpi$からKullback-Leibler分散の$pi$に近いサンプルを出力する。
論文 参考訳(メタデータ) (2024-01-17T07:24:18Z) - Efficiently Learning One-Hidden-Layer ReLU Networks via Schur
Polynomials [50.90125395570797]
正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。
本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
論文 参考訳(メタデータ) (2023-07-24T14:37:22Z) - Quantum Simulation of the First-Quantized Pauli-Fierz Hamiltonian [0.5097809301149342]
我々は、我々の分割と形式主義の征服を通じて、大きな$Lambda$の量子化よりも優れたスケーリングと量子化を得られることを示す。
また,マルチコントロールされたXゲート群を実装する新しい方法を含む,ゲート最適化のための新しいアルゴリズムおよび回路レベル技術も提供する。
論文 参考訳(メタデータ) (2023-06-19T23:20:30Z) - Spacetime-Efficient Low-Depth Quantum State Preparation with
Applications [93.56766264306764]
任意の量子状態を作成するための新しい決定論的手法は、以前の方法よりも少ない量子資源を必要とすることを示す。
我々は、量子機械学習、ハミルトンシミュレーション、方程式の線形系を解くことなど、この能力が役立ついくつかのアプリケーションを強調した。
論文 参考訳(メタデータ) (2023-03-03T18:23:20Z) - DADAO: Decoupled Accelerated Decentralized Asynchronous Optimization [0.0]
DADAOは、L$-smooth と $mu$-strongly convex 関数の和を最小化する最初の分散化、高速化、非同期化、プライマリ化、一階述語アルゴリズムである。
我々のアルゴリズムは、$mathcalO(nsqrtchisqrtfracLmulog(frac1epsilon)$ localと$mathcalO(nsqrtchisqrtfracLmulog()のみを必要とすることを示す。
論文 参考訳(メタデータ) (2022-07-26T08:47:54Z) - Quantum Resources Required to Block-Encode a Matrix of Classical Data [56.508135743727934]
回路レベルの実装とリソース推定を行い、古典データの高密度な$Ntimes N$行列をブロックエンコードして$epsilon$を精度良くすることができる。
異なるアプローチ間のリソーストレードオフを調査し、量子ランダムアクセスメモリ(QRAM)の2つの異なるモデルの実装を検討する。
我々の結果は、単純なクエリの複雑さを超えて、大量の古典的データが量子アルゴリズムにアクセスできると仮定された場合のリソースコストの明確な図を提供する。
論文 参考訳(メタデータ) (2022-06-07T18:00:01Z) - Complexity of zigzag sampling algorithm for strongly log-concave
distributions [6.336005544376984]
強いログ凹分布に対するジグザグサンプリングアルゴリズムの計算複雑性について検討する。
ジグザグサンプリングアルゴリズムは, 計算コストが$obiglに匹敵するchi-squareの発散において, $varepsilon$ 誤差を達成することを証明した。
論文 参考訳(メタデータ) (2020-12-21T03:10:21Z) - Streaming Complexity of SVMs [110.63976030971106]
本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。
両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
論文 参考訳(メタデータ) (2020-07-07T17:10:00Z) - $Q$-learning with Logarithmic Regret [60.24952657636464]
楽観的な$Q$は$mathcalOleft(fracSAcdot mathrmpolyleft(Hright)Delta_minlogleft(SATright)right)$ cumulative regret bound, where $S$ is the number of state, $A$ is the number of action, $H$ is the planning horizon, $T$ is the total number of steps, $Delta_min$ is the least sub-Optitimality gap。
論文 参考訳(メタデータ) (2020-06-16T13:01:33Z) - Backward Feature Correction: How Deep Learning Performs Deep
(Hierarchical) Learning [66.05472746340142]
本稿では,SGD による階層的学習 _efficiently_ と _automatically_ を学習目標として,多層ニューラルネットワークがどのように行うかを分析する。
我々は、下位機能のエラーを上位層と共にトレーニングする際に自動的に修正できる"後方特徴補正"と呼ばれる新しい原則を確立する。
論文 参考訳(メタデータ) (2020-01-13T17:28:29Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。