Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userTight Quantum Lower Bound for Approximate Counting with Quantum States
112
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic 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 $xsubseteq [n]$ has size either $k$ or $k=(1+epsilon)k$. We assume the algorithm has access to * the membership oracle, which, for each $iin [n]$, can answer whether $iin x$, or not; and * the uniform superposition $|psi_xrangle = sum_{iin x} |irangle/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_xrangle$; ** the algorithm can execute the reflecting oracle which reflects about the state $|psi_xrangle$; ** the algorithm can execute the state-generating oracle (or its inverse) which performs the transformation $|0ranglemapsto |psi_xrangle$. Without the second type of resources (related to $|psi_xrangle$), 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 epsilonle 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.
rate research
Read More
We study quantum algorithms that are given access to trusted and untrusted quantum witnesses. We establish strong limitations of such algorithms, via new techniques based on Laurent polynomials (i.e., polynomials with positive and negative integer exponents). Specifically, we resolve the complexity of approximate counting, the problem of multiplicatively estimating the size of a nonempty set $S subseteq [N]$, in two natural generalizations of quantum query complexity. Our first result holds in the standard Quantum Merlin--Arthur ($mathsf{QMA}$) setting, in which a quantum algorithm receives an untrusted quantum witness. We show that, if the algorithm makes $T$ quantum queries to $S$, and also receives an (untrusted) $m$-qubit quantum witness, then either $m = Omega(|S|)$ or $T=Omega bigl(sqrt{N/left| Sright| } bigr)$. This is optimal, matching the straightforward protocols where the witness is either empty, or specifies all the elements of $S$. As a corollary, this resolves the open problem of giving an oracle separation between $mathsf{SBP}$, the complexity class that captures approximate counting, and $mathsf{QMA}$. In our second result, we ask what if, in addition to a membership oracle for $S$, a quantum algorithm is also given QSamples -- i.e., copies of the state $left| Srightrangle = frac{1}{sqrt{left| Sright| }} sum_{iin S}|irangle$ -- or even access to a unitary transformation that enables QSampling? We show that, even then, the algorithm needs either $Theta bigl(sqrt{N/left| Sright| }bigr)$ queries or else $Theta bigl(min bigl{left| Sright| ^{1/3}, sqrt{N/left| Sright| }bigr}bigr)$ QSamples or accesses to the unitary. Our lower bounds in both settings make essential use of Laurent polynomials, but in different ways.
In 1998, Brassard, Hoyer, Mosca, and Tapp (BHMT) gave a quantum algorithm for approximate counting. Given a list of $N$ items, $K$ of them marked, their algorithm estimates $K$ to within relative error $varepsilon$ by making only $Oleft( frac{1}{varepsilon}sqrt{frac{N}{K}}right) $ queries. Although this speedup is of Grover type, the BHMT algorithm has the curious feature of relying on the Quantum Fourier Transform (QFT), more commonly associated with Shors algorithm. Is this necessary? This paper presents a simplified algorithm, which we prove achieves the same query complexity using Grover iterations only. We also generalize this to a QFT-free algorithm for amplitude estimation. Related approaches to approximate counting were sketched previously by Grover, Abrams and Williams, Suzuki et al., and Wie (the latter two as we were writing this paper), but in all cases without rigorous analysis.
Approximate Counting refers to the problem where we are given query access to a function $f : [N] to {0,1}$, and we wish to estimate $K = #{x : f(x) = 1}$ to within a factor of $1+epsilon$ (with high probability), while minimizing the number of queries. In the quantum setting, Approximate Counting can be done with $Oleft(minleft(sqrt{N/epsilon}, sqrt{N/K}/epsilonright)right)$ queries. It has recently been shown that this can be achieved by a simple algorithm that only uses Grover iterations; however the algorithm performs these iterations adaptively. Motivated by concerns of computational simplicity, we consider algorithms that use Grover iterations with limited adaptivity. We show that algorithms using only nonadaptive Grover iterations can achieve $Oleft(sqrt{N/epsilon}right)$ query complexity, which is tight.
The Index Erasure problem asks a quantum computer to prepare a uniform superposition over the image of an injective function given by an oracle. We prove a tight $Omega(sqrt{n})$ lower bound on the quantum query complexity of the non-coherent case of the problem, where, in addition to preparing the required superposition, the algorithm is allowed to leave the ancillary memory in an arbitrary function-dependent state. This resolves an open question of Ambainis, Magnin, Roetteler, and Roland (CCC 2011), who gave a tight bound for the coherent case, the case where the ancillary memory must return to its initial state. The proof is based on evaluating certain Krein parameters of a symmetric association scheme defined over partial permutations. The study of this association scheme may be of independent interest.
We show that an improvement to the best known quantum lower bound for GRAPH-COLLISION problem implies an improvement to the best known lower bound for TRIANGLE problem in the quantum query complexity model. In GRAPH-COLLISION we are given free access to a graph $(V,E)$ and access to a function $f:Vrightarrow {0,1}$ as a black box. We are asked to determine if there exist $(u,v) in E$, such that $f(u)=f(v)=1$. In TRIANGLE we have a black box access to an adjacency matrix of a graph and we have to determine if the graph contains a triangle. For both of these problems the known lower bounds are trivial ($Omega(sqrt{n})$ and $Omega(n)$, respectively) and there is no known matching upper bound.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
