論文の概要: Tight Quantum Lower Bound for Approximate Counting with Quantum States
- arxiv url: http://arxiv.org/abs/2002.06879v1
- Date: Mon, 17 Feb 2020 10:53:50 GMT
- ステータス: 処理完了
- システム内更新日: 2023-06-03 11:16:22.172769
- Title: Tight Quantum Lower Bound for Approximate Counting with Quantum States
- Title（参考訳）: 量子状態を持つ近似カウントのためのタイト量子下限
- Authors: Aleksandrs Belovs and Ansis Rosmanis
- Abstract要約: アーロンソン等が考える数え上げ問題の次の変種について、厳密な下界を証明する。
問題は、入力セット$xsubseteq [n]$が$k$か$k'= (1+epsilon)k$であるかどうかを区別することである。
- 参考スコア（独自算出の注目度）: 78.33558762484924
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We prove tight lower bounds for the following variant of the counting problem
considered by Aaronson et al. The task is to distinguish whether an input set
$x\subseteq [n]$ has size either $k$ or $k'=(1+\epsilon)k$. We assume the
algorithm has access to
* the membership oracle, which, for each $i\in [n]$, can answer whether $i\in
x$, or not; and
* the uniform superposition $|\psi_x\rangle = \sum_{i\in x}
|i\rangle/\sqrt{|x|}$ over the elements of $x$. Moreover, we consider three
different ways how the algorithm can access this state:
** the algorithm can have copies of the state $|\psi_x\rangle$;
** the algorithm can execute the reflecting oracle which reflects about the
state $|\psi_x\rangle$;
** the algorithm can execute the state-generating oracle (or its inverse)
which performs the transformation $|0\rangle\mapsto |\psi_x\rangle$.
Without the second type of resources (related to $|\psi_x\rangle$), the
problem is well-understood, see Brassard et al. The study of the problem with
the second type of resources was recently initiated by Aaronson et al.
We completely resolve the problem for all values of $1/k \le \epsilon\le 1$,
giving tight trade-offs between all types of resources available to the
algorithm. Thus, we close the main open problems from Aaronson et al.
The lower bounds are proven using variants of the adversary bound by Belovs
and employing analysis closely related to the Johnson association scheme.
- Abstract（参考訳）: アーロンソン等が考える数え上げ問題の次の変種について、厳密な下界を証明する。
このタスクは、入力セット$x\subseteq [n]$が$k$か$k'=(1+\epsilon)k$であるかどうかを識別する。
私たちは、アルゴリズムが*メンバシップオラクルへのアクセスを持っていると仮定し、各$i\in [n]$に対して、$i\in x$ が成立するかどうか、*一様重ね合わせ $|\psi_x\rangle = \sum_{i\in x} |i\rangle/\sqrt{|x|}$ が$x$ の要素に対して答えられる。
さらに、アルゴリズムがこの状態にアクセスする方法を3つの異なる方法で検討する: * アルゴリズムは状態のコピーを持つことができる $|\psi_x\rangle$; * アルゴリズムは状態を反映する反射オラクルを実行できる $|\psi_x\rangle$; ** アルゴリズムは状態を生成するオラクル(またはその逆)を実行でき、変換は $|0\rangle\mapsto |\psi_x\rangle$ を実行する。
第2のタイプのリソース($|\psi_x\rangle$)がなければ、問題はよく理解されている。
第2のタイプの資源による問題の研究は、Aaronsonらによって最近始められた。
我々は1/k \le \epsilon\le 1$の全ての値の問題を完全に解決し、アルゴリズムで利用可能な全てのタイプのリソース間の密接なトレードオフを与える。
したがって、Aaronsonらの主なオープンな問題は解決する。
下位境界は、ベロフスによる逆境界の変種を用いて証明され、ジョンソンアソシエーションスキームと密接な関係を持つ解析を用いる。
関連論文リスト
- The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
この問題は通信複雑性のランダム化を$Omega(frac1kcdot n2log|mathbbF|)$とする。
アプリケーションとして、$k$パスを持つ任意のストリーミングアルゴリズムに対して、$Omega(frac1kcdot n2log|mathbbF|)$スペースローバウンドを得る。
論文 参考訳（メタデータ） (2024-10-26T06:21:42Z) - Partially Unitary Learning [0.0]
ヒルベルト空間の最適写像 $IN$ of $left|psirightrangle$ と $OUT$ of $left|phirightrangle$ が提示される。
この最適化問題の大域的な最大値を求める反復アルゴリズムを開発した。
論文 参考訳（メタデータ） (2024-05-16T17:13:55Z) - Sketching Algorithms and Lower Bounds for Ridge Regression [65.0720777731368]
リッジ回帰問題に対する1+varepsilon$近似解を計算するスケッチベース反復アルゴリズムを提案する。
また,このアルゴリズムがカーネルリッジ回帰の高速化に有効であることを示す。
論文 参考訳（メタデータ） (2022-04-13T22:18:47Z) - Almost Tight Approximation Algorithms for Explainable Clustering [16.22135057266913]
本稿では,Dasguptaらによって提案された最近の説明可能なクラスタリングの枠組みについて考察する。
具体的には、$k$-meansと$k$-mediansの問題に焦点をあて、ほぼ上と下の境界を提供する。
論文 参考訳（メタデータ） (2021-07-01T23:49:23Z) - Locally Private $k$-Means Clustering with Constant Multiplicative
Approximation and Near-Optimal Additive Error [10.632986841188]
2つの新しいアルゴリズムで加算誤差の上と下の境界における$n$の指数のギャップを埋める。
局所的にプライベートな$k$-meansの問題を、定数係数乗算近似を持つ一定数のラウンドで解くことができる。
論文 参考訳（メタデータ） (2021-05-31T14:41:40Z) - 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) - Fast digital methods for adiabatic state preparation [0.0]
ゲート型量子コンピュータにおいて,逆誤差の複雑多元対数を伴う断熱状態生成のための量子アルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-04-08T18:00:01Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。