ﻻ يوجد ملخص باللغة العربية
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.
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 ex
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}{vare
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 queri
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
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