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.
In this note we study the number of quantum queries required to identify an unknown multilinear polynomial of degree d in n variables over a finite field F_q. Any bounded-error classical algorithm for this task requires Omega(n^d) queries to the polynomial. We give an exact quantum algorithm that uses O(n^(d-1)) queries for constant d, which is optimal. In the case q=2, this gives a quantum algorithm that uses O(n^(d-1)) queries to identify a codeword picked from the binary Reed-Muller code of order d.
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.
We obtain the strongest separation between quantum and classical query complexity known to date -- specifically, we define a black-box problem that requires exponentially many queries in the classical bounded-error case, but can be solved exactly in the quantum case with a single query (and a polynomial number of auxiliary operations). The problem is simple to define and the quantum algorithm solving it is also simple when described in terms of certain quantum Fourier transforms (QFTs) that have natural properties with respect to the algebraic structures of finite fields. These QFTs may be of independent interest, and we also investigate generalizations of them to noncommutative finite rings.