Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userQuantum Lower Bounds for Approximate Counting via Laurent Polynomials
217
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
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.
rate research
Read More
We examine the number T of queries that a quantum network requires to compute several Boolean functions on {0,1}^N in the black-box model. We show that, in the black-box model, the exponential quantum speed-up obtained for partial functions (i.e. problems involving a promise on the input) by Deutsch and Jozsa and by Simon cannot be obtained for any total function: if a quantum algorithm computes some total Boolean function f with bounded-error using T black-box queries then there is a classical deterministic algorithm that computes f exactly with O(T^6) queries. We also give asymptotically tight characterizations of T for all symmetric f in the exact, zero-error, and bounded-error settings. Finally, we give new precise bounds for AND, OR, and PARITY. Our results are a quantum extension of the so-called polynomial method, which has been successfully applied in classical complexity theory, and also a quantum extension of results by Nisan about a polynomial relationship between randomized and deterministic decision tree complexity.
We prove a query complexity lower bound for $mathsf{QMA}$ protocols that solve approximate counting: estimating the size of a set given a membership oracle. This gives rise to an oracle $A$ such that $mathsf{SBP}^A otsubset mathsf{QMA}^A$, resolving an open problem of Aaronson [2]. Our proof uses the polynomial method to derive a lower bound for the $mathsf{SBQP}$ query complexity of the $mathsf{AND}$ of two approximate counting instances. We use Laurent polynomials as a tool in our proof, showing that the Laurent polynomial method can be useful even for problems involving ordinary polynomials.
We prove lower bounds on the error probability of a quantum algorithm for searching through an unordered list of N items, as a function of the number T of queries it makes. In particular, if T=O(sqrt{N}) then the error is lower bounded by a constant. If we want error <1/2^N then we need T=Omega(N) queries. We apply this to show that a quantum computer cannot do much better than a classical computer when amplifying the success probability of an RP-machine. A classical computer can achieve error <=1/2^k using k applications of the RP-machine, a quantum computer still needs at least ck applications for this (when treating the machine as a black-box), where c>0 is a constant independent of k. Furthermore, we prove a lower bound of Omega(sqrt{log N}/loglog N) queries for quantum bounded-error search of an ordered list of N items.
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.
Function inversion is the problem that given a random function $f: [M] to [N]$, we want to find pre-image of any image $f^{-1}(y)$ in time $T$. In this work, we revisit this problem under the preprocessing model where we can compute some auxiliary information or advice of size $S$ that only depends on $f$ but not on $y$. It is a well-studied problem in the classical settings, however, it is not clear how quantum algorithms can solve this task any better besides invoking Grovers algorithm, which does not leverage the power of preprocessing. Nayebi et al. proved a lower bound $ST^2 ge tildeOmega(N)$ for quantum algorithms inverting permutations, however, they only consider algorithms with classical advice. Hhan et al. subsequently extended this lower bound to fully quantum algorithms for inverting permutations. In this work, we give the same asymptotic lower bound to fully quantum algorithms for inverting functions for fully quantum algorithms under the regime where $M = O(N)$. In order to prove these bounds, we generalize the notion of quantum random access code, originally introduced by Ambainis et al., to the setting where we are given a list of (not necessarily independent) random variables, and we wish to compress them into a variable-length encoding such that we can retrieve a random element just using the encoding with high probability. As our main technical contribution, we give a nearly tight lower bound (for a wide parameter range) for this generalized notion of quantum random access codes, which may be of independent interest.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
