論文の概要: Optimal query complexity for fractional quantum evolution

• arxiv url: http://arxiv.org/abs/2610.01940v1
• Date: Thu, 01 Oct 2026 16:08:16 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-03 01:19:24.254238
• Title: Optimal query complexity for fractional quantum evolution
• Title（参考訳）: 分数量子進化のための最適クエリ複雑性
• Abstract要約: 分数クエリ問題に対する最適なクエリ複雑性は、$_!left(frac1logfrac1varepsilonright)$である。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by-sa/4.0/
• Abstract: Given oracle access to an unknown unitary $U=e^{iH}$ , the fractional query problem asks how many queries are required to implement a noninteger power $U^t=e^{itH}$, $0<t<1$, when the spectrum is separated from the branch cut by a gap $δ$. Quantum singular value transformation gives an upper bound of $O\!\left(\frac{1}δ\log\frac{1}{\varepsilon}\right)$ queries for approximation error $\varepsilon$. We prove a matching lower bound for arbitrary query algorithms. Our argument reduces any $N$-query circuit to the approximation of $e^{itθ}$ by a trigonometric polynomial with degree bounded by $O(N)$, together with Remez inequality. This allows us to establish the lower bound of $Ω_τ\!\left(\frac{1}δ\log\frac{1}{\varepsilon}\right)$. Consequently, the optimal query complexity for fractional query problem is $Θ_τ\!\left(\frac{1}δ\log\frac{1}{\varepsilon}\right)$, showing that the known QSVT construction is asymptotically optimal. We also give an alternative lower bound proof based on constructing a linear functional that annihilates the approximant space, yielding a $Ω_τ\!\left(\log\frac{1}{\varepsilon}\right)$ bound uniform to $δ$.
• Abstract（参考訳）: 未知のユニタリな$U=e^{iH}$へのオラクルアクセスが与えられたとき、分数クエリ問題は、ギャップ$δ$で切断されたブランチからスペクトルが分離されたときに、非整数パワー$U^t=e^{itH}$, $0<t<1$ を実装するために要求されるクエリ数を問う。 量子特異値変換は、上限の$O\! for approximation error $\varepsilon$.\left(\frac{1}δ\log\frac{1}{\varepsilon}\right)$ query for approximation error $\varepsilon。 任意のクエリアルゴリズムに対して,一致した下界を証明した。 我々の議論は、任意の$N$-クエリ回路を$e^{itθ}$の近似に$O(N)$で有界な三角多項式とRemezの不等式との近似に還元する。 これにより、$Ω_τ\! \left(\frac{1}δ\log\frac{1}{\varepsilon}\right)$ したがって、分数クエリ問題に対する最適クエリの複雑さは、$\_τ\! \left(\frac{1}δ\log\frac{1}{\varepsilon}\right)$ は、既知の QSVT の構成が漸近的に最適であることを示す。 また、近似空間を消滅させる線型汎函数の構成に基づく別の下界証明を与え、$Ω_τ\! \left(\log\frac{1}{\varepsilon}\right)${δ$.\left(\log\frac{1}{\varepsilon}\right)$ bound uniform to $δ$.

関連論文リスト

• Sparse Hamiltonian simulation with optimal dependence on the maximum column Euclidean norm [5.374239522015395]
  我々は、$d$sparse Hermitian Hamiltonian $H$をシミュレートするための量子アルゴリズムを与える。 $d>1$と$tgelog (2/)$の場合、バウンダリは最悪のケースの低いバウンダリと一致する。 また、行と列ごとに最大$d$のノンゼロエントリを持つブラックボックスユニタリのゲート効率の実装も提供します。
  論文  参考訳（メタデータ） (2026-10-01T16:47:55Z)
• Faster quantum linear system solver beyond the condition number [50.84794327094274]
  線形系の正規化解 $|xrangle$ を生成する2つの量子アルゴリズムを、条件数$=lVert A-1rVert$ に依存しない複雑性を持つ精度 $Ax=| b rangle$ に提示する。 フィルタベースのソルバは非常にシンプルで、実行時プレファクタが適しています。
  論文  参考訳（メタデータ） (2026-07-08T17:49:40Z)
• Beyond Averaging in John Ellipsoid Approximation: High-Accuracy Algorithms in the Leverage-Score Model [37.35522173770848]
  対称ポリトープ$P=mathbfxinmathbbRd:|mathbfAmathbfx|_inftyle1$, $mathbfAinmathbbRntimes d$のジョン・エリプシドは、長いレバレッジスコアアルゴリズムによって計算される。
  論文  参考訳（メタデータ） (2026-06-18T11:00:03Z)
• Min-Max Optimization Requires Exponentially Many Queries [71.85811744604827]
  非min-nonconcave 関数 $f$ $[0,1] のクエリ複雑性。 f$ へのクエリとその勾配点が 1 ord$ で指数関数的な点を成さなければならないことを示す。
  論文  参考訳（メタデータ） (2026-05-13T17:34:24Z)
• Actively Learning Halfspaces without Synthetic Data [34.777547976926456]
  我々は、点合成なしでハーフスペースを学習するための効率的なアルゴリズムを設計する。 コーナリーとして、軸整合半空間に対して最適な$O(d + log n)$クエリ決定論的学習器を得る。 我々のアルゴリズムはブール関数を$f$ over $n$要素で学習するより一般的な問題を解く。
  論文  参考訳（メタデータ） (2025-09-25T07:39:25Z)
• Low-degree learning and the metric entropy of polynomials [44.99833362998488]
  少なくとも$Omega(sqrtvarepsilon)2dlog n leq log mathsfM(mathscrF_n,d,|cdot|_L,varepsilon)は2辺の推定値$c(1-varepsilon)2dlogを満たす。
  論文  参考訳（メタデータ） (2022-03-17T23:52:08Z)
• 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)
• Agnostic Q-learning with Function Approximation in Deterministic Systems: Tight Bounds on Approximation Error and Sample Complexity [94.37110094442136]
  本稿では,決定論的システムにおける関数近似を用いたQ$学習の問題について検討する。 もし$delta = Oleft(rho/sqrtdim_Eright)$なら、$Oleft(dim_Eright)$を使って最適なポリシーを見つけることができる。
  論文  参考訳（メタデータ） (2020-02-17T18:41:49Z)
• 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)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。