Quantum computing aims to use quantum mechanical effects for the efficient performance of computational tasks. A popular research direction is enlarging the gap between classical and quantum algorithm complexity of the same computational problem. We present new results in quantum query algorithm design for multivalued functions that allow to achieve a large quantum versus classical complexity separation. To compute a basic finite multifunction in a quantum model only one query is enough while classically three queries are required. Then, we present two generalizations and a modification of the original algorithm, and obtain the following complexity gaps: QUD(M') ≤ N versus CUD(M') ≥ 3N, and QRD(M'') = 1 versus N/2 + 1 ≤ CRD(M'') ≤ N.
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.
Query complexity is one of the several notions of complexity de ned to measure the cost \nof algorithms. It plays an important role in demonstrating the quantum advantage, that \nquantum computing is faster than classical computation in solving some problems. Kempe \nshowed that a discrete time quantum walk on hypercube hits the antipodal point with \nexponentially fewer queries than a simple random walk [K05]. Childs et al. showed that a \ncontinuous time quantum walk on \\Glued Trees" detects the label of a special vertex with \nexponentially fewer queries than any classical algorithm [CCD03], and the result translates \nto discrete time quantum walk by an e cient simulation. \nBuilding on these works, we examine the query complexity of variations of the hyper- \ncube and Glued Tree problems. We rst show the gap between quantum and classical query \nalgorithms for a modi ed hypercube problem is at most polynomial. We then strengthen \nthe query complexity gap for the Glued Tree label detection problem by improving a classical lower bound technique; and we prove such a lower bound is nearly tight by giving a \nclassical query algorithm whose query complexity matches the lower bound, up to a polylog \nfactor.