The textbook adversary bound for function evaluation states that to evaluate a function $f\colon D\to C$ with success probability $\frac{1}{2}+δ$ in the quantum query model, one needs at least $\left( 2δ-\sqrt{1-4δ^2} \right) Adv(f)$ queries, where $Adv(f)$ is the optimal value of a certain optimization problem. For $δ\ll 1$, this only allows for a bound of $Θ\left(δ^2 Adv(f)\right)$ even after a repetition-and-majority-voting argument. In contrast, the polynomial method can sometimes prove a bound that doesn't converge to $0$ as $δ\to 0$. We improve the $δ$-dependent prefactor and achieve a bound of $2δAdv(f)$. The proof idea is to "turn the output condition into an input condition": From an algorithm that transforms perfectly input-independent initial to imperfectly distinguishable final states, we construct one that transforms imperfectly input-independent initial to perfectly distinguishable final states in the same number of queries by projecting onto the "correct" final subspaces and uncomputing. The resulting $δ$-dependent condition on initial Gram matrices, compared to the original algorithm's condition on final Gram matrices, allows deriving the tightened prefactor.
One Weird Trick Tightens the Quantum Adversary Bound, Especially for Success Probability Close to 1/2
The textbook adversary bound for function evaluation states that to evaluate a function f:D→C with success probability 21+δ in the quantum query model, one needs at least (2δ−1−4δ2)Adv(f) queries, where Adv(f) is the optimal value of a certain optimization problem. For δ≪1, this only allows for a bound of Θ(δ2Adv(f)) even after a repetition-and-majority-voting argument. In contrast, the polynomial method can sometimes prove a bound that doesn't converge to 0 as δ→0. We improve the δ-dependent prefactor and achieve a bound of 2δAdv(f). The proof idea is to "turn the output condition into an input condition": From an algorithm that transforms perfectly input-independent initial to imperfectly distinguishable final states, we construct one that transforms imperfectly input-independent initial to perfectly distinguishable final states in the same number of queries by projecting onto the "correct" final subspaces and uncomputing. The resulting δ-dependent condition on initial Gram matrices, compared to the original algorithm's condition on final Gram matrices, allows deriving the tightened prefactor.
The quantum adversary method is one of the most successful techniques for proving lower bounds on quantum query complexity. It gives optimal lower bounds for many problems, has application to classical complexity in formula size lower bounds, and is versatile with equivalent formulations interms of weight schemes, eigen values, and Kolmogorov complexity. All these formulations rely on the principlethat if an algorithm successfully computes a function then, in particular, itis able to distinguish between inputs which map to different values.
We study the two-weight decision version of quantum approximate counting: given oracle access to x∈{0,1}N, distinguish ∣x∣=M from ∣x∣=M+Δ with success probability 1/2+ζ. Using the multiplicative adversary method, we prove Ω(max{ζ(N−M)(M+Δ)/Δ,ζN/Δ}). The same parameter dependence follows from the polynomial-method characterization of the two-layer symmetric function by Podder, Yao, and Ye. Our contribution is a multiplicative-adversary derivation that tracks the progress produced by individual oracle queries. For the first term, after complementing the input if necessary, we assume M+Δ≤N−M. We use the Hamming-layer subspaces from the eigenspace method of Ambainis, Spalek, and de Wolf and compose their adjacent-layer unitary maps to relate the two nonadjacent promise layers. After fixing the queried coordinate, the analysis block-diagonalizes into four-dimensional subspaces. An exact calculation of the one-query progress ratio gives the first lower bound. The same estimate also implies (I−Πbad)∣ΨT⟩2=O(T2Δ2/((N−M)(M+Δ))) for the coherent input superposition used in the adversary argument. For the second term, we prove directly using a three-eigenvalue multiplicative adversary that unique OR on n bits with success probability 1/2+ζ requires Ω(ζn) queries, and then reduce unique OR to the two-weight counting problem.
We give a new version of the adversary method for proving lower bounds on quantum query algorithms. The new method is based on analyzing the eigenspace structure of the problem at hand. We use it to prove a new and optimal strong direct product theorem for 2-sided error quantum algorithms computing k independent instances of a symmetric Boolean function: if the algorithm uses significantly less than k times the number of queries needed for one instance of the function, then its success probability is exponentially small in k. We also use the polynomial method to prove a direct product theorem for 1-sided error algorithms for k threshold functions with a stronger bound on the success probability. Finally, we present a quantum algorithm for evaluating solutions to systems of linear inequalities, and use our direct product theorems to show that the time-space tradeoff of this algorithm is close to optimal.
The general adversary bound is a semi-definite program that lower-bounds the number of input queries needed by a quantum algorithm to evaluate a function. It is known to be tight up to constant factors for functions (total or partial) with boolean output and binary input alphabet. We show that the general adversary bound is tight for any function whatsoever, with potentially non-boolean input or output alphabets. We also show that quantum query complexity exhibits a remarkable composition property: Q ( f(g(x), . . . , g(x)) ) = O ( Q(f)Q(g) ) for any compatible functions f, g. This was previously known only in the boolean case. Both of these results are obtained by defining a new, but closely related, semi-definite program that we call the witness size. The minimization formulation of the witness size adds constraints compared with the general adversary bound to enable dual solutions to correspond to eigenvalue-zero eigenvectors of certain graphs. While the witness size can be strictly larger than the adversary bound, we show that it can be at most a factor of two larger.
The general adversary dual is a powerful tool in quantum computing because it gives a query-optimal bounded-error quantum algorithm for deciding any Boolean function. Unfortunately, the algorithm uses linear qubits in the worst case, and only works if the constraints of the general adversary dual are exactly satisfied. The challenge of improving the algorithm is that it is brittle to arbitrarily small errors since it relies on a reflection over a span of vectors. We overcome this challenge and build a robust dual adversary algorithm that can handle approximately satisfied constraints. As one application of our robust algorithm, we prove that for any Boolean function with polynomially many 1-valued inputs (or in fact a slightly weaker condition) there is a query-optimal algorithm that uses logarithmic qubits. As another application, we prove that numerically derived, approximate solutions to the general adversary dual give a bounded-error quantum algorithm under certain conditions. Further, we show that these conditions empirically hold with reasonable iterations for Boolean functions with small domains. We also develop several tools that may be of independent interest, including a robust approximate spectral gap lemma, a method to compress a general adversary dual solution using the Johnson-Lindenstrauss lemma, and open-source code to find solutions to the general adversary dual.
Given a Boolean function f:{0,1}n→{0,1}, the goal in the usual query model is to compute f on an unknown input x∈{0,1}n while minimizing the number of queries to x. One can also consider a "distinguishing" problem denoted by fsab: given an input x∈f−1(0) and an input y∈f−1(1), either all differing locations are replaced by a ∗, or all differing locations are replaced by †, and an algorithm's goal is to identify which of these is the case while minimizing the number of queries. Ben-David and Kothari [ToC'18] introduced the notion of randomized sabotage complexity of a Boolean function to be the zero-error randomized query complexity of fsab. A natural follow-up question is to understand Q(fsab), the quantum query complexity of fsab. In this paper, we initiate a systematic study of this. The following are our main results: ∙ If we have additional query access to x and y, then Q(fsab)=O(min{Q(f),n}). ∙ If an algorithm is also required to output a differing index of a 0-input and a 1-input, then Q(fsab)=O(min{Q(f)1.5,n}). ∙Q(fsab)=Ω(fbs(f)), where fbs(f) denotes the fractional block sensitivity of f. By known results, along with the results in the previous bullets, this implies that Q(fsab) is polynomially related to Q(f). ∙ The bound above is easily seen to be tight for standard functions such as And, Or, Majority and Parity. We show that when f is the Indexing function, Q(fsab)=Θ(fbs(f)), ruling out the possibility that Q(fsab)=Θ(fbs(f)) for all f.