Tight Quantum Lower Bound for Approximate Counting with Quantum States

• URL: http://arxiv.org/abs/2002.06879v2
• Date: Tue, 7 May 2024 15:35:22 GMT
• Title: Tight Quantum Lower Bound for Approximate Counting with Quantum States
• Authors: Aleksandrs Belovs, Ansis Rosmanis,
• Abstract summary: 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 $xsubseteq [n]$ has size either $k$ or $k'=(1+varepsilon)k$.
• Score: 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}$.

Related papers

• The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
  We show that this problem has randomized communication complexity $Omega(frac1kcdot n2log|mathbbF|)$. As an application, we obtain an $Omega(frac1kcdot n2log|mathbbF|)$ space lower bound for any streaming algorithm with $k$ passes.
  arXiv  Detail & Related papers  (2024-10-26T06:21:42Z)
• On Partially Unitary Learning [0.0]
  An optimal mapping between Hilbert spaces $IN$ of $left|psirightrangle$ and $OUT$ of $left|phirightrangle$ is presented. An algorithm finding the global maximum of this optimization problem is developed and it's application to a number of problems is demonstrated.
  arXiv  Detail & Related papers  (2024-05-16T17:13:55Z)
• Sketching Algorithms and Lower Bounds for Ridge Regression [65.0720777731368]
  We give a sketching-based iterative algorithm that computes $1+varepsilon$ approximate solutions for the ridge regression problem. We also show that this algorithm can be used to give faster algorithms for kernel ridge regression.
  arXiv  Detail & Related papers  (2022-04-13T22:18:47Z)
• Almost Tight Approximation Algorithms for Explainable Clustering [16.22135057266913]
  We study a recent framework of explainable clustering first suggested by Dasgupta et al. Specifically, we focus on the $k$-means and $k$-medians problems and provide nearly tight upper and lower bounds.
  arXiv  Detail & Related papers  (2021-07-01T23:49:23Z)
• Locally Private $k$-Means Clustering with Constant Multiplicative Approximation and Near-Optimal Additive Error [10.632986841188]
  We bridge the gap between the exponents of $n$ in the upper and lower bounds on the additive error with two new algorithms. It is possible to solve the locally private $k$-means problem in a constant number of rounds with constant factor multiplicative approximation.
  arXiv  Detail & Related papers  (2021-05-31T14:41:40Z)
• An Optimal Separation of Randomized and Quantum Query Complexity [67.19751155411075]
  We prove that for every decision tree, the absolute values of the Fourier coefficients of a given order $ellsqrtbinomdell (1+log n)ell-1,$ sum to at most $cellsqrtbinomdell (1+log n)ell-1,$ where $n$ is the number of variables, $d$ is the tree depth, and $c>0$ is an absolute constant.
  arXiv  Detail & Related papers  (2020-08-24T06:50:57Z)
• Fast digital methods for adiabatic state preparation [0.0]
  We present a quantum algorithm for adiabatic state preparation on a gate-based quantum computer, with complexity polylogarithmic in the inverse error.
  arXiv  Detail & Related papers  (2020-04-08T18:00:01Z)
• Agnostic Q-learning with Function Approximation in Deterministic Systems: Tight Bounds on Approximation Error and Sample Complexity [94.37110094442136]
  We study the problem of agnostic $Q$-learning with function approximation in deterministic systems. We show that if $delta = Oleft(rho/sqrtdim_Eright)$, then one can find the optimal policy using $Oleft(dim_Eright)$.
  arXiv  Detail & Related papers  (2020-02-17T18:41:49Z)
• On the Complexity of Minimizing Convex Finite Sums Without Using the Indices of the Individual Functions [62.01594253618911]
  We exploit the finite noise structure of finite sums to derive a matching $O(n2)$-upper bound under the global oracle model. Following a similar approach, we propose a novel adaptation of SVRG which is both emphcompatible with oracles, and achieves complexity bounds of $tildeO(n2+nsqrtL/mu)log (1/epsilon)$ and $O(nsqrtL/epsilon)$, for $mu>0$ and $mu=0$
  arXiv  Detail & Related papers  (2020-02-09T03:39:46Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.