論文の概要: Fast digital methods for adiabatic state preparation
- arxiv url: http://arxiv.org/abs/2004.04164v2
- Date: Wed, 2 Mar 2022 20:36:14 GMT
- ステータス: 処理完了
- システム内更新日: 2023-05-25 11:34:01.910791
- Title: Fast digital methods for adiabatic state preparation
- Title(参考訳): adiabatic state preparedのための高速ディジタル手法
- Authors: Kianna Wan and Isaac H. Kim
- Abstract要約: ゲート型量子コンピュータにおいて,逆誤差の複雑多元対数を伴う断熱状態生成のための量子アルゴリズムを提案する。
- 参考スコア(独自算出の注目度): 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We present a quantum algorithm for adiabatic state preparation on a
gate-based quantum computer, with complexity polylogarithmic in the inverse
error. Our algorithm digitally simulates the adiabatic evolution between two
self-adjoint operators $H_0$ and $H_1$, exponentially suppressing the diabatic
error by harnessing the theoretical concept of quasi-adiabatic continuation as
an algorithmic tool. Given an upper bound $\alpha$ on $\|H_0\|$ and $\|H_1\|$
along with the promise that the $k$th eigenstate $|\psi_k(s)\rangle$ of $H(s)
\equiv (1-s)H_0 + sH_1$ is separated from the rest of the spectrum by a gap of
at least $\gamma > 0$ for all $s \in [0,1]$, this algorithm implements an
operator $\widetilde{U}$ such that $\||\psi_k(1)\rangle -
\widetilde{U}|\psi_k(s)\rangle\| \leq \epsilon$ using
$O(\alpha^2/\gamma^2)\text{polylog}(\alpha/\gamma\epsilon)$ queries to
block-encodings of $H_0$ and $H_1$. In addition, we develop an algorithm that
is applicable only to ground states and requires multiple queries to an oracle
that prepares $|\psi_0(0)\rangle$, but has slightly better scaling in all
parameters. We also show that the costs of both algorithms can be further
reduced under certain reasonable conditions, such as when $\|H_1 - H_0\|$ is
small compared to $\alpha$, or when more information about the gap of $H(s)$ is
available. For certain problems, the scaling can even be improved to linear in
$\|H_1 - H_0\|/\gamma$ up to polylogarithmic factors.
- Abstract(参考訳): ゲート型量子コンピュータにおいて,逆誤差の複雑多元対数を伴う断熱状態生成のための量子アルゴリズムを提案する。
本アルゴリズムは,自己随伴演算子である$h_0$ と $h_1$ の間の断熱的進化を数値的にシミュレートし,準断熱継続の理論概念をアルゴリズムツールとして利用する。
Given an upper bound $\alpha$ on $\|H_0\|$ and $\|H_1\|$ along with the promise that the $k$th eigenstate $|\psi_k(s)\rangle$ of $H(s) \equiv (1-s)H_0 + sH_1$ is separated from the rest of the spectrum by a gap of at least $\gamma > 0$ for all $s \in [0,1]$, this algorithm implements an operator $\widetilde{U}$ such that $\||\psi_k(1)\rangle\widetilde{U}|\psi_k(s)\rangle\| \leq \epsilon$ using $O(\alpha^2/\gamma^2)\text{polylog}(\alpha/\gamma\epsilon)$ queries to block-encodings of $H_0$ and $H_1$.
さらに、基底状態のみに適用可能なアルゴリズムを開発し、$|\psi_0(0)\rangle$を準備するオラクルに複数のクエリを要求するが、すべてのパラメータのスケーリングがわずかに改善されている。
また、$\|h_1 - h_0\|$ が$\alpha$ よりも小さい場合や$h(s)$ の差に関するさらなる情報が得られる場合など、ある合理的な条件下では両方のアルゴリズムのコストをさらに削減できることを示した。
ある種の問題に対して、スケーリングは$\|H_1 - H_0\|/\gamma$からポリ対数因子まで線形に改善することができる。
関連論文リスト
- Basic quantum subroutines: finding multiple marked elements and summing
numbers [1.1265248232450553]
量子クエリーの最適数$O(sqrtN k)$を用いて、サイズ$N$のリスト内のすべての$k$マーク要素を見つける方法を示す。
論文 参考訳(メタデータ) (2023-02-20T19:11:44Z) - Optimal SQ Lower Bounds for Learning Halfspaces with Massart Noise [9.378684220920562]
マスアートノイズの存在下でハーフスペースを学習するための、最も厳密な統計クエリ(SQ)の下界。
任意の $eta in [0,1/2]$ に対して、$eta$ よりも誤り分類誤差の少ない全ての SQ アルゴリズムは、スーパーポリノミカルな精度のクエリを必要とすることを示す。
論文 参考訳(メタデータ) (2022-01-24T17:33:19Z) - Logarithmic Regret from Sublinear Hints [76.87432703516942]
自然クエリモデルにより,アルゴリズムが$O(log T)$ regretsを$O(sqrtT)$ hintsで得ることを示す。
また、$o(sqrtT)$ hintsは$Omega(sqrtT)$ regretより保証できないことも示しています。
論文 参考訳(メタデータ) (2021-11-09T16:50:18Z) - Threshold Phenomena in Learning Halfspaces with Massart Noise [56.01192577666607]
ガウス境界の下でのマスアートノイズ付きmathbbRd$におけるPAC学習ハーフスペースの問題について検討する。
この結果は,Massartモデルにおける学習ハーフスペースの複雑さを定性的に特徴づけるものである。
論文 参考訳(メタデータ) (2021-08-19T16:16:48Z) - Quantum speedups for dynamic programming on $n$-dimensional lattice
graphs [0.11470070927586015]
複雑性を$widetilde O(T_Dn)$で表すと、$T_D D+1$となる。
最もよく知られている古典的アルゴリズムは $textpoly(m,n)log n T_Dn$ であるが、量子アルゴリズムの時間複雑性は $textpoly(m,n)log n T_Dn$ である。
論文 参考訳(メタデータ) (2021-04-29T14:50:03Z) - Improved quantum data analysis [2.1756081703276]
我々は、$O(log2 m)/epsilon2)$$$d$次元状態のサンプルのみを必要とする量子"Threshold Search"アルゴリズムを提供する。
また, $tildeO((log3 m)/epsilon2)$サンプルを用いた仮説選択法も提案する。
論文 参考訳(メタデータ) (2020-11-22T01:22:37Z) - An Optimal Separation of Randomized and Quantum Query Complexity [67.19751155411075]
すべての決定木に対して、与えられた順序 $ellsqrtbinomdell (1+log n)ell-1,$ sum to at least $cellsqrtbinomdell (1+log n)ell-1,$ where $n$ is the number of variables, $d$ is the tree depth, $c>0$ is a absolute constant。
論文 参考訳(メタデータ) (2020-08-24T06:50:57Z) - Model-Free Reinforcement Learning: from Clipped Pseudo-Regret to Sample
Complexity [59.34067736545355]
S$状態、$A$アクション、割引係数$gamma in (0,1)$、近似しきい値$epsilon > 0$の MDP が与えられた場合、$epsilon$-Optimal Policy を学ぶためのモデルなしアルゴリズムを提供する。
十分小さな$epsilon$の場合、サンプルの複雑さで改良されたアルゴリズムを示す。
論文 参考訳(メタデータ) (2020-06-06T13:34:41Z) - Tight Quantum Lower Bound for Approximate Counting with Quantum States [78.33558762484924]
アーロンソン等が考える数え上げ問題の次の変種について、厳密な下界を証明する。
問題は、入力セット$xsubseteq [n]$が$k$か$k'= (1+epsilon)k$であるかどうかを区別することである。
論文 参考訳(メタデータ) (2020-02-17T10:53:50Z) - On the Complexity of Minimizing Convex Finite Sums Without Using the
Indices of the Individual Functions [62.01594253618911]
有限和の有限ノイズ構造を利用して、大域オラクルモデルの下での一致する$O(n2)$-upper境界を導出する。
同様のアプローチを踏襲したSVRGの新規な適応法を提案し、これはオラクルと互換性があり、$tildeO(n2+nsqrtL/mu)log (1/epsilon)$と$O(nsqrtL/epsilon)$, for $mu>0$と$mu=0$の複雑さ境界を実現する。
論文 参考訳(メタデータ) (2020-02-09T03:39:46Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。