ﻻ يوجد ملخص باللغة العربية
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.
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. pro
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
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.
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
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 in