論文の概要: Tight Quantum Lower Bound for Approximate Counting with Quantum States

• arxiv url: http://arxiv.org/abs/2002.06879v2
• Date: Tue, 7 May 2024 15:35:22 GMT
• ステータス: 処理完了
• システム内更新日: 2024-05-08 20:57:01.552161
• Title: Tight Quantum Lower Bound for Approximate Counting with Quantum States
• Title（参考訳）: 量子状態を考慮した近似計数のためのタイト量子ローバウンド
• Authors: Aleksandrs Belovs, Ansis Rosmanis,
• Abstract要約: Aaronson, Kothari, Kretschmer, Thaler (2020) が考える数え上げ問題の次の変種に対する厳密な下界を証明する。 このタスクは、入力セット$xsubseteq [n]$が$k$か$k'=(1+varepsilon)k$であるかどうかを識別する。
• 参考スコア（独自算出の注目度）: 49.6558487240078
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We prove tight lower bounds for the following variant of the counting problem considered by Aaronson, Kothari, Kretschmer, and Thaler (2020). The task is to distinguish whether an input set $x\subseteq [n]$ has size either $k$ or $k'=(1+\varepsilon)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 \item 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 (the ones related to $|\psi_x\rangle$), the problem is well-understood. 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 \varepsilon\le 1$, giving tight trade-offs between all types of resources available to the algorithm. We also demonstrate that our lower bounds are tight. Thus, we close the main open problems from Aaronson et al. The lower bounds are proven using variants of the adversary bound from Belovs (2015) and employing representation theory of the symmetric group applied to the $S_n$-modules $\mathbb{C}^{\binom{[n]}k}$ and $\mathbb{C}^{\binom{[n]}k}\otimes \mathbb{C}$.
• Abstract（参考訳）: Aaronson, Kothari, Kretschmer, Thaler (2020) が考える数え上げ問題の次の変種について、厳密な下界を証明する。 このタスクは、入力セット$x\subseteq [n]$が$k$か$k'=(1+\varepsilon)k$であるかどうかを識別する。 i\in x$, and \item the uniform superposition $|\psi_x\rangle = \sum_{i\in x} |i\rangle/\sqrt{|x|}$ over the element of $x$。 さらに、アルゴリズムはこの状態にどのようにアクセスできるかを3つの異なる方法で検討する: - アルゴリズムは状態のコピーを持つことができる $|\psi_x\rangle$; - アルゴリズムは状態に関する反射オラクルを実行できる $|\psi_x\rangle$; - アルゴリズムは状態を生成するオラクル(またはその逆)を実行でき、変換は$|0\rangle\mapsto|\psi_x\rangle$。 第2のタイプのリソース($|\psi_x\rangle$に関連するもの)がなければ、問題はよく理解される。 第2のタイプのリソースによる問題の研究は、最近Aaronsonらによって始められ、我々は1/k \le \varepsilon\le 1$の全ての値の問題を完全に解決した。 また、下限が厳密であることも示している。 したがって、Aaronson et al の主な開問題を閉じる 下界は、Belovs (2015) の逆境界の不変量を用いて証明され、$S_n$-加群 $\mathbb{C}^{\binom{[n]}k}$ および $\mathbb{C}^{\binom{[n]}k}\otimes \mathbb{C}$ に適用される対称群の表現理論が用いられる。

関連論文リスト

• The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
  この問題は通信複雑性のランダム化を$Omega(frac1kcdot n2log|mathbbF|)$とする。 アプリケーションとして、$k$パスを持つ任意のストリーミングアルゴリズムに対して、$Omega(frac1kcdot n2log|mathbbF|)$スペースローバウンドを得る。
  論文  参考訳（メタデータ） (2024-10-26T06:21:42Z)
• On 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)

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

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