We achieve essentially the largest possible separation between quantum and classical
query complexities. We do so using a property-testing problem called Forrelation, where one …

Query complexity is a model of computation in which we have to compute a function f (x 1,…,
x N) of variables xi which can be accessed via queries. The complexity of an algorithm is …

Abstract The Deutsch-Jozsa algorithm is essentially faster than any possible deterministic
classical algorithm for solving a promise problem that is in fact a symmetric partial Boolean …

We prove a characterization of t-query quantum algorithms in terms of the unit ball of a
space of degree-(2t) polynomials. Based on this, we obtain a refined notion of approximate …

Quantum query complexity mainly studies the number of queries needed to learn some
property of a black box with high probability. A closely related question is how well an …

We consider the problem of learning low-degree quantum objects up to $\varepsilon $-error
in $\ell_2 $-distance. We show the following results: $(i) $ unknown $ n $-qubit degree-$ d …

We consider the reversible processes between two one-to-one correlated measurement
outcomes which underlie both problem solving and quantum nonlocality. In the former case …

We give a new presentation of the main result of Arunachalam, Bri\" et and Palazuelos
(SICOMP'19) and show that quantum query algorithms are characterized by a new class of …

We give and prove an optimal exact quantum query algorithm with complexity $ k+ 1$ for
computing the promise problem (ie, symmetric and partial Boolean function) $ DJ_n^ k …

We provide two sufficient and necessary conditions to characterize any n-bit partial Boolean
function with exact quantum query complexity 1. Using the first characterization, we present …