論文の概要: Tight Bounds for Quantum Phase Estimation and Related Problems
- arxiv url: http://arxiv.org/abs/2305.04908v1
- Date: Mon, 8 May 2023 17:46:01 GMT
- ステータス: 処理完了
- システム内更新日: 2023-05-09 13:22:18.467500
- Title: Tight Bounds for Quantum Phase Estimation and Related Problems
- Title（参考訳）: 量子位相推定の厳密な境界と関連する問題
- Authors: Nikhil S. Mande, Ronald de Wolf
- Abstract要約: 精度$delta$と誤差確率$epsilon$は$Omegaleft(frac1deltalog1epsilonright)$であることを示す。
また、多くのアドバイス(アドバイス準備ユニタリの応用)を持つことは、コストを大幅に削減することはなく、また、$U$の固有値に関する知識も少なくないことも示している。
- 参考スコア（独自算出の注目度）: 0.90238471756546
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Phase estimation, due to Kitaev [arXiv'95], is one of the most fundamental
subroutines in quantum computing. In the basic scenario, one is given black-box
access to a unitary $U$, and an eigenstate $\lvert \psi \rangle$ of $U$ with
unknown eigenvalue $e^{i\theta}$, and the task is to estimate the eigenphase
$\theta$ within $\pm\delta$, with high probability. The cost of an algorithm
for us will be the number of applications of $U$ and $U^{-1}$.
We tightly characterize the cost of several variants of phase estimation
where we are no longer given an arbitrary eigenstate, but are required to
estimate the maximum eigenphase of $U$, aided by advice in the form of states
(or a unitary preparing those states) which are promised to have at least a
certain overlap $\gamma$ with the top eigenspace.
We give algorithms and matching lower bounds (up to logarithmic factors) for
all ranges of parameters.
We show that a small number of copies of the advice state (or of an
advice-preparing unitary) are not significantly better than having no advice at
all. We also show that having lots of advice (applications of the
advice-preparing unitary) does not significantly reduce cost, and neither does
knowledge of the eigenbasis of $U$. As an immediate consequence we obtain a
lower bound on the complexity of the Unitary recurrence time problem, matching
an upper bound of She and Yuen~[ITCS'23] and resolving one of their open
questions.
Lastly, we show that a phase-estimation algorithm with precision $\delta$ and
error probability $\epsilon$ has cost
$\Omega\left(\frac{1}{\delta}\log\frac{1}{\epsilon}\right)$, matching an easy
upper bound. This contrasts with some other scenarios in quantum computing
(e.g., search) where error-reduction costs only a factor
$O(\sqrt{\log(1/\epsilon)})$. Our lower bound technique uses a variant of the
polynomial method with trigonometric polynomials.
- Abstract（参考訳）: Kitaev [arXiv'95] による位相推定は、量子コンピューティングにおける最も基本的なサブルーチンの1つである。
基本的なシナリオでは、単位の$U$と未知の固有値$e^{i\theta}$を持つ固有状態$\lvert \psi \rangle$ of$U$へのブラックボックスアクセスが与えられ、そのタスクは、高い確率で$\pm\delta$内の固有位相$\theta$を推定する。
アルゴリズムのコストは、$U$と$U^{-1}$のアプリケーションの数になります。
我々は、任意の固有状態が与えられなくなった場合の位相推定のいくつかのバリエーションのコストを厳密に特徴付けるが、最大固有位相を u$ と見積もることが必要であり、少なくともトップ固有空間との重複を約束する状態(またはそれらの状態を作成するユニタリ)の形でのアドバイスによって支援される。
パラメータのすべての範囲に対してアルゴリズムと(対数係数まで)下限のマッチングを与える。
アドバイスステート(またはアドバイス準備ユニタリ)の少数のコピーは、アドバイスが全くないよりは、はるかに良いものではないことを示す。
また、多くのアドバイス(アドバイス準備ユニタリの応用)を持つことは、コストを大幅に削減するものではなく、u$の固有ベイシスに関する知識もないことも示しています。
結果として、ユニタリ再帰時間問題(unitary repeat time problem)の複雑さの限界が低くなり、 she と yuen~[itcs'23] の上限を満たし、解き明かされた質問の1つを解き明かすことができる。
最後に、精度$\delta$と誤差確率$\epsilon$を持つ位相推定アルゴリズムは、簡単な上限値と一致する$\omega\left(\frac{1}{\delta}\log\frac{1}{\epsilon}\right)$であることを示す。
これは、量子コンピューティング(例えば、検索)における他のいくつかのシナリオとは対照的であり、エラーの引き込みは$O(\sqrt{\log(1/\epsilon)})$のみである。
我々の下界法は三角多項式を持つ多項式法の変種を用いる。
関連論文リスト
- The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
この問題は通信複雑性のランダム化を$Omega(frac1kcdot n2log|mathbbF|)$とする。
アプリケーションとして、$k$パスを持つ任意のストリーミングアルゴリズムに対して、$Omega(frac1kcdot n2log|mathbbF|)$スペースローバウンドを得る。
論文 参考訳（メタデータ） (2024-10-26T06:21:42Z) - A Quantum Approximation Scheme for k-Means [0.16317061277457]
QRAMモデルにおける古典的な$k$-meansクラスタリング問題に対する量子近似スキームを提案する。
我々の量子アルゴリズムは、時間$tildeO left(2tildeO(frackvarepsilon) eta2 dright)$で実行される。
教師なし学習の以前の研究とは異なり、我々の量子アルゴリズムは量子線型代数のサブルーチンを必要としない。
論文 参考訳（メタデータ） (2023-08-16T06:46:37Z) - Efficient Quantum State Synthesis with One Query [0.0]
本稿では,古典的オラクルへの単一クエリ(重ね合わせ)を実現する時間類似量子アルゴリズムを提案する。
我々は、すべての$n$-qubit状態が、適切な有限ゲート集合上の$On/n)$-size回路によって0.01エラー内に構築可能であることを証明した。
論文 参考訳（メタデータ） (2023-06-02T17:49:35Z) - How to simulate quantum measurement without computing marginals [3.222802562733787]
量子状態$psi$を標準で計算するためのアルゴリズムを,古典的に記述し,解析する。
我々のアルゴリズムはサンプリングタスクを$n$-qubit状態のポリ(n)$振幅の計算に還元する。
論文 参考訳（メタデータ） (2021-12-15T21:44:05Z) - Quantum Algorithms for Ground-State Preparation and Green's Function
Calculation [5.28670135448572]
周波数領域における多体グリーン関数の基底状態準備と計算のための射影量子アルゴリズムを提案する。
アルゴリズムはユニタリ演算(LCU)の線形結合に基づいており、基本的には量子資源のみを使用する。
論文 参考訳（メタデータ） (2021-12-10T18:39:55Z) - Minimal Expected Regret in Linear Quadratic Control [79.81807680370677]
オンライン学習アルゴリズムを考案し、その期待された後悔を保証します。
当時のこの後悔は、$A$と$B$が未知の場合、$widetildeO((d_u+d_x)sqrtd_xT)$によって上界(i)となる。
論文 参考訳（メタデータ） (2021-09-29T14:07:21Z) - No quantum speedup over gradient descent for non-smooth convex
optimization [22.16973542453584]
ブラックボックスアクセスは(必ずしも滑らかではない)関数 $f:mathbbRn から mathbbR$ とその (サブ) 階数へのアクセスである。
私たちのゴールは、$epsilon$-approximate minimum of $f$ を、真極小から少なくとも$R$ の距離から始めることにある。
下界で使われる関数族はランダム化アルゴリズムでは難しいが、$O(GR/epsilon)$量子クエリで解くことができる。
論文 参考訳（メタデータ） (2020-10-05T06:32:47Z) - 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) - Streaming Complexity of SVMs [110.63976030971106]
本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。
両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
論文 参考訳（メタデータ） (2020-07-07T17:10:00Z) - Maximizing Determinants under Matroid Constraints [69.25768526213689]
我々は、$det(sum_i in Sv_i v_i v_itop)$が最大になるような基底を$S$$$$M$とする問題を研究する。
この問題は、実験的なデザイン、商品の公平な割り当て、ネットワーク設計、機械学習など、さまざまな分野に現れている。
論文 参考訳（メタデータ） (2020-04-16T19:16:38Z) - Locally Private Hypothesis Selection [96.06118559817057]
我々は、$mathcalQ$から$p$までの総変動距離が最良の分布に匹敵する分布を出力する。
局所的な差分プライバシーの制約は、コストの急激な増加を引き起こすことを示す。
提案アルゴリズムは,従来手法のラウンド複雑性を指数関数的に改善する。
論文 参考訳（メタデータ） (2020-02-21T18:30:48Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。