We consider the problem where P is an unknown permutation on {0,1,...,2^n - 1}, y is an element of {0,1,...,2^n - 1}, and the goal is to determine the minimum r > 0 such that P^r(y) = y (where P^r is P composed with itself r times). Information about P is available only via queries that yield P^x(y) from any x in {0,1,...,2^m - 1} and y in {0,1,...,2^n - 1} (where m is polynomial in n). The main resource under consideration is the number of these queries. We show that the number of queries necessary to solve the problem in the classical probabilistic bounded-error model is exponential in n. This contrasts sharply with the quantum bounded-error model, where a constant number of queries suffices.
We consider the problem where P is an unknown permutation on {0,1,...,2^n - 1}, y is an element of {0,1,...,2^n - 1}, and the goal is to determine the minimum r > 0 such that P^r(y) = y (where P^r is P composed with itself r times). Information about P is available only via queries that yield P^x(y) from any x in {0,1,...,2^m - 1} and y in {0,1,...,2^n - 1} (where m is polynomial in n). The main resource under consideration is the number of these queries. We show that the number of queries necessary to solve the problem in the classical probabilistic bounded-error model is exponential in n. This contrasts sharply with the quantum bounded-error model, where a constant number of queries suffices.
We consider the problem where /spl pi/ is an unknown permutation on (0, 1,..., 2/sup n/-1), /spl gamma//sub 0//spl isin/(0, 1,..., 2/sup n/-1), and the goal is to determine the minimum r>0 such that /spl pi//sup r/(y/sub 0/)=y/sub 0/. Information about /spl pi/ is available only via queries that yield /spl pi//sup x/(y) from any x/spl isin/(0, 1,..., 2/sup n/-1) and /spl gamma//sub /spl isin//(0, 1,..., 2/sup n/-1) (where m is polynomial in n). The resource under consideration is the number of these queries (hence our model of computation is the decision tree). We show that the number of queries necessary to solve the problem in the classical probabilistic bounded error model is exponential in n. This contrasts sharply with the quantum bounded-error model, where a constant number of queries suffices.
Query complexity is a model of computation in which we have to compute a function f(x1,…,xN) of variables xi which can be accessed via queries. The complexity of an algorithm is measured by the number of queries that it makes. Query complexity is widely used for studying quantum algorithms, for two reasons. First, it includes many of the known quantum algorithms (including Grover's quantum search and a key subroutine of Shor's factoring algorithm). Second, one can prove lower bounds on the query complexity, bounding the possible quantum advantage. In the last few years, there have been major advances on several longstanding problems in the query complexity. In this talk, we survey these results and related work, including: - the biggest quantum-vs-classical gap for partial functions (a problem solvable with 1 query quantumly but requiring Ω(N) queries classically); - the biggest quantum-vs-determistic and quantum-vs-probabilistic gaps for total functions (for example, a problem solvable with M queries quantumly but requiring Ω~(M2.5) queries probabilistically); - the biggest probabilistic-vs-deterministic gap for total functions (a problem solvable with M queries probabilistically but requiring Ω~(M2) queries deterministically); - the bounds on the gap that can be achieved for subclasses of functions (for example, symmetric functions); - the connections between query algorithms and approximations by low-degree polynomials.
Let X = (z,, , z,-,) be a sequence of n numbers.For 6 > 0, we say that 5; is an e-approximate median if the number of elements strictly less than zi and the number of elements strictly greater than zi are each less than (1 + 6):.We consider the quantum query complexity of computing an c-approximate median, given the sequence X as an oracle.We prove a lower bound of n(min{t,n}) queries for any quantum algorithm that computes an r-approximate median with any constant probability greater than l/2.We also show how an c-approximate median may be computed with 0( $ log(t) log log( $)) oracle queries, which rep resents an improvement over an earlier algorithm due to Grover [ll, 121.Thus, the lower bound we obtain is essentially optimal.The upper and the lower bound both hold in the comparison tree model as well.Our lower bound result is an application of the polynomial paradigm recently introduced to quantum complexity theory by Be& et ol.[l].The main ingredient in the proof is a polynomial degree lower bound far real multilinear polynomials that "approximate" symmetric partial boolean functions.The degree bound extends a result of Patti[15] and also immediately yields lower bounds for the problems of approximating the kth-smallest element, approximating the mean of a sequence of numbers, and approximately counting the number of ones of a boolean function.All bounds obtained come within a polylogarithmic factor of the optimal (as we show by presenting algorithms where no such optimal or near optimal algorithms were known), thus demonstrating the power of the polynomial method.
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.
Let P = (X, < P) be a partial order on a set of n elements X = x1, x2,..., xn. Define the quantum sorting problem QSORTP as: given n distinct numbers x1, x2,..., xn consistent with P, sort them by a quantum decision tree using comparisons of the form "xi: xj". Let Qε(P) be the minimum number of queries used by any quantum decision tree for solving QSORTP with error less than ε (where 0 < ε < 1/10 is fixed). It was proved by Hoyer, Neerbek and Shi (Algorithmica 34 (2002), 429--448) that, when P0 is the empty partial order, Qε(P0) ≥ Ω (n log n), i. e., the classical information lower bound holds for quantum decision trees when the input permutations are unrestricted.In this paper we show that the classical information lower bound holds, up to an additive linear term, for quantum decision trees for any partial order P. Precisely, we prove Qε(P) ≥ c log2 e(P)-c'n where c,c' > 0 are constants and e(P) is the number of linear orderings consistent with P. Our proof builds on an interesting connection between sorting and Korner's graph entropy that was first noted and developed by Kahn and Kim (JCSS 51(1995), 390--399).
Unitary operator discrimination is a fundamental problem in quantum information theory. The basic version of this problem can be described as follows: Given a black box implementing a unitary operator U∈S:={U1, U2} under some probability distribution over S, the goal is to decide whether U=U1 or U=U2. In this paper, we consider the query complexity of this problem. We show that there exists a quantum algorithm that solves this problem with bounded error probability using ⌈6θcover−1⌉ queries to the black box in the worst case, i.e., under any probability distribution over S, where the parameter θcover, which is determined by the eigenvalues of U1†U2, represents the “closeness” between U1 and U2. We also show that this upper bound is essentially tight: we prove that for every θcover > 0 there exist operators U1 and U2 such that any quantum algorithm solving this problem with bounded error probability requires at least ⌈3θcover2⌉ queries under uniform distribution over S.