Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > QUANTUM QUERY COMPLEXITY:
Reports tagged with quantum query complexity:
TR05-041 | 12th April 2005
Shengyu Zhang

#### (Almost) tight bounds for randomized and quantum Local Search on hypercubes and grids

Revisions: 2

The Local Search problem, which finds a
local minimum of a black-box function on a given graph, is of both
practical and theoretical importance to many areas in computer
science and natural sciences. In this paper, we show that for the
Boolean hypercube $\B^n$, the randomized query complexity of Local
more >>>

TR11-040 | 22nd March 2011
Alexander A. Sherstov

#### Strong Direct Product Theorems for Quantum Communication and Query Complexity

A strong direct product theorem (SDPT) states that solving $n$ instances of a problem requires $\Omega(n)$ times the resources for a single instance, even to achieve success probability $2^{-\Omega(n)}.$ We prove that quantum communication complexity obeys an SDPT whenever the communication lower bound for a single instance is proved by ... more >>>

TR17-169 | 24th October 2017
Mark Bun, Robin Kothari, Justin Thaler

#### The Polynomial Method Strikes Back: Tight Quantum Query Bounds via Dual Polynomials

The approximate degree of a Boolean function $f$ is the least degree of a real polynomial that approximates $f$ pointwise to error at most $1/3$. The approximate degree of $f$ is known to be a lower bound on the quantum query complexity of $f$ (Beals et al., FOCS 1998 and ... more >>>

TR18-010 | 14th January 2018
Alexander A. Sherstov

#### Algorithmic polynomials

The approximate degree of a Boolean function $f(x_{1},x_{2},\ldots,x_{n})$ is the minimum degree of a real polynomial that approximates $f$ pointwise within $1/3$. Upper bounds on approximate degree have a variety of applications in learning theory, differential privacy, and algorithm design in general. Nearly all known upper bounds on approximate degree ... more >>>

TR18-156 | 8th September 2018
Mark Bun, Robin Kothari, Justin Thaler

#### Quantum algorithms and approximating polynomials for composed functions with shared inputs

We give new quantum algorithms for evaluating composed functions whose inputs may be shared between bottom-level gates. Let $f$ be a Boolean function and consider a function $F$ obtained by applying $f$ to conjunctions of possibly overlapping subsets of $n$ variables. If $f$ has quantum query complexity $Q(f)$, we give ... more >>>

TR19-015 | 7th February 2019
William Kretschmer

#### QMA Lower Bounds for Approximate Counting

We prove a query complexity lower bound for $QMA$ protocols that solve approximate counting: estimating the size of a set given a membership oracle. This gives rise to an oracle $A$ such that $SBP^A \not\subset QMA^A$, resolving an open problem of Aaronson [2]. Our proof uses the polynomial method to ... more >>>

TR19-136 | 23rd September 2019
Sourav Chakraborty, Arkadev Chattopadhyay, Nikhil Mande, Manaswi Paraashar

#### Quantum Query-to-Communication Simulation Needs a Logarithmic Overhead

Buhrman, Cleve and Wigderson (STOC'98) observed that for every Boolean function $f : \{-1, 1\}^n \to \{-1, 1\}$ and $\bullet : \{-1, 1\}^2 \to \{-1, 1\}$ the two-party bounded-error quantum communication complexity of $(f \circ \bullet)$ is $O(Q(f) \log n)$, where $Q(f)$ is the bounded-error quantum query complexity of $f$. ... more >>>

TR19-179 | 7th December 2019
Avishay Tal

#### Towards Optimal Separations between Quantum and Randomized Query Complexities

Revisions: 1

The query model offers a concrete setting where quantum algorithms are provably superior to randomized algorithms. Beautiful results by Bernstein-Vazirani, Simon, Aaronson, and others presented partial Boolean functions that can be computed by quantum algorithms making much fewer queries compared to their randomized analogs. To date, separations of $O(1)$ vs. ... more >>>

TR20-020 | 21st February 2020
Nikhil Mande, Justin Thaler, Shuchen Zhu

#### Improved Approximate Degree Bounds For $k$-distinctness

An open problem that is widely regarded as one of the most important in quantum query complexity is to resolve the quantum query complexity of the $k$-distinctness function on inputs of size $N$. While the case of $k=2$ (also called Element Distinctness) is well-understood, there is a polynomial gap between ... more >>>

ISSN 1433-8092 | Imprint