Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userTowards Optimal Separations between Quantum and Randomized Query Complexities
76
0
0.0
(
0
)
Authors
Avishay Tal
Ask ChatGPT about the research
No Arabic abstract
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.
rate research
Read More
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-error setting, which means his algorithm can not always get the correct answer. Exact quantum algorithms for Simons problem have also been proposed, which deterministically solve the problem with O(n) queries. Also the quantum lower bound Omega(n) for Simons problem is known. Although these algorithms are either complicated or specialized, their results give an O(n) versus Omega(sqrt{2^{n}}) separation in exact query complexities for Simons problem (Omega(sqrt{2^{n}}) is the lower bound for classical probabilistic algorithms), but it has not been proved whether this separation is optimal. In this paper, we propose another exact quantum algorithm for solving Simons problem with O(n) queries, which is simple, concrete and does not rely on special query oracles. Our algorithm combines Simons algorithm with the quantum amplitude amplification technique to ensure its determinism. In particular, we show that Simons problem can be solved by a classical deterministic algorithm with O(sqrt{2^{n}}) queries (as we are aware, there were no classical deterministic algorithms for solving Simons problem with O(sqrt{2^{n}}) queries). Combining some previous results, we obtain the optimal separation in exact query complexities for Simons problem: Theta({n}) versus Theta({sqrt{2^{n}}}).
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 algorithms as much as possible. We show tight bounds for a number of problems, specifically Theta((n/p)^{2/3}) p-parallel queries for element distinctness and Theta((n/p)^{k/(k+1)} for k-sum. Our upper bounds are obtained by parallelized quantum walk algorithms, and our lower bounds are based on a relatively small modification of the adversary lower bound method, combined with recent results of Belovs et al. on learning graphs. We also prove some general bounds, in particular that quantum and classical p-parallel complexity are polynomially related for all total functions f when p is small compared to fs block sensitivity.
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 randomized model, 1) we give a general technique to convert public-coin protocols to private-coin protocols by incurring a small multiplicative error, at a small additive cost. This is an improvement over Newmans theorem [Inf. Proc. Let.91] in the dependence on the error parameter. 2) Using this we obtain a $(log(n/epsilon^2)+4)$-cost private-coin communication protocol that computes the $n$-bit Equality function, to error $epsilon$. This improves upon the $log(n/epsilon^3)+O(1)$ upper bound implied by Newmans theorem, and matches the best known lower bound, which follows from Alon [Comb. Prob. Comput.09], up to an additive $loglog(1/epsilon)+O(1)$. In the quantum model, 1) we exhibit a one-way protocol of cost $log(n/epsilon)+4$, that uses only pure states and computes the $n$-bit Equality function to error $epsilon$. This bound was implicitly already shown by Nayak [PhD thesis99]. 2) We show that any $epsilon$-error one-way protocol for $n$-bit Equality that uses only pure states communicates at least $log(n/epsilon)-loglog(1/epsilon)-O(1)$ qubits. 3) We exhibit a one-way protocol of cost $log(sqrt{n}/epsilon)+3$, that uses mixed states and computes the $n$-bit Equality function to error $epsilon$. This is also tight up to an additive $loglog(1/epsilon)+O(1)$, which follows from Alons result. Our upper bounds also yield upper bounds on the approximate rank and related measures of the Identity matrix. This also implies improved upper bounds on these measures for the distributed SINK function, which was recently used to refute the randomized and quant
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). In query complexity, we establish a nearly quadratic separation between deterministic (and even randomized) query complexity and subcube partition complexity, which is also essentially optimal. We also establish a nearly power 1.5 separation between quantum query complexity and subcube partition complexity, the first superlinear separation between the two measures. Lastly, we show a quadratic separation between quantum query complexity and one-sided subcube partition complexity. Our query complexity separations use the recent cheat sheet framework of Aaronson, Ben-David, and the author. Our query functions are built up in stages by alternating function composition with the cheat sheet construction. The communication complexity separation follows from lifting the query separation to communication complexity.
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 proved by Cai $&$ Qiu. Generalized Simons problem can be described as follows. Given a function $f:{{0, 1}}^n to {{0, 1}}^m$, with the property that there is some unknown hidden subgroup $S$ such that $f(x)=f(y)$ iff $x oplus yin S$, for any $x, yin {{0, 1}}^n$, where $|S|=2^k$ for some $0leq kleq n$. The goal is to find $S$. For the case of $k=1$, it is Simons problem. In this paper, we propose an exact quantum algorithm with $O(n-k)$ queries and an non-adaptive deterministic classical algorithm with $O(ksqrt{2^{n-k}})$ queries for solving the generalized Simons problem. Also, we prove that their lower bounds are $Omega(n-k)$ and $Omega(sqrt{k2^{n-k}})$, respectively. Therefore, we obtain a tight exact quantum query complexity $Theta(n-k)$ and an almost tight non-adaptive classical deterministic query complexities $Omega(sqrt{k2^{n-k}}) sim O(ksqrt{2^{n-k}})$ for this problem.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
