ﻻ يوجد ملخص باللغة العربية
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. $sqrt{N}$ between quantum and randomized query complexities remain the state-of-the-art (where $N$ is the input length), leaving open the question of whether $O(1)$ vs. $N^{1/2+Omega(1)}$ separations are possible? We answer this question in the affirmative. Our separating problem is a variant of the Aaronson-Ambainis $k$-fold Forrelation problem. We show that our variant: (1) Can be solved by a quantum algorithm making $2^{O(k)}$ queries to the inputs. (2) Requires at least $tilde{Omega}(N^{2(k-1)/(3k-1)})$ queries for any randomized algorithm. For any constant $varepsilon>0$, this gives a $O(1)$ vs. $N^{2/3-varepsilon}$ separation between the quantum and randomized query complexities of partial Boolean functions. Our proof is Fourier analytical and uses new bounds on the Fourier spectrum of classical decision trees, which could be of independent interest. Looking forward, we conjecture that the Fourier bounds could be further improved in a precise manner, and show that such conjectured bounds imply optimal $O(1)$ vs. $N^{1-varepsilon}$ separations between the quantum and randomized query complexities of partial Boolean functions.
Simons problem is one of the most important problems demonstrating the power of quantum computers, which achieves a large separation between quantum and classical query complexities. However, Simons discussion on his problem was limited to bounded-er
We study the complexity of quantum query algorithms that make p queries in parallel in each timestep. This model is in part motivated by the fact that decoherence times of qubits are typically small, so it makes sense to parallelize quantum algorithm
We investigate the randomized and quantum communication complexities of the well-studied Equality function with small error probability $epsilon$, getting the optimal constant factors in the leading terms in a number of different models. In the ran
We show a nearly quadratic separation between deterministic communication complexity and the logarithm of the partition number, which is essentially optimal. This improves upon a recent power 1.5 separation of Goos, Pitassi, and Watson (FOCS 2015). I
Simons problem is an essential example demonstrating the faster speed of quantum computers than classical computers for solving some problems. The optimal separation between exact quantum and classical query complexities for Simons problem has been p