Andris Ambainis

We study quantum algorithms for problems in computational geometry, such as Point-On-3-Lines problem. In this problem, we are given a set of lines and we are asked to find a point that lies on at least 3 of these lines. Point-On-3-Lines and many other computational geometry problems are known to be 3Sum-Hard. That is, solving them classically requires time \Omega(n^{2-o(1)}), unless there is faster algorithm for the well known 3Sum problem (in which we are given a set S of n integers and have to determine if there are a, b, c \in S such that a + b + c = 0). Quantumly, 3Sum can be solved in time O(n log n) using Grover’s quantum search algorithm. This leads to a question: can we solve Point-On-3-Lines and other 3Sum-Hard problems in O(n^c) time quantumly, for c<2? We answer this question affirmatively, by constructing a quantum algorithm that solves Point-On-3-Lines in time O(n^{1 + o(1)}). The algorithm combines recursive use of amplitude amplification with geometrical ideas. We show that the same ideas give O(n^{1 + o(1)}) time algorithm for many 3Sum-Hard geometrical problems.

I will present two new quantum algorithms based on quantum walks: - an O(N^{2/3}) query algorithm for element distinctness (the problem of finding two equal elements among N given elements). - an O(N^{1/2}\log N) step quantum algorithm for finding a marked item on 2-dimensional grid. Both algorithms are based on the same general technique. I will also describe this technique and show how to decompose it into a sequence of steps which can then be applied to other problems. The second algorithm is joint work with Julia Kempe, Alexander Rivosh and Neil Shenvi.

In a recent work [Phys. Rev. Lett. 114, 170502 (2015)], Tavakoli et al. derived interesting results by studying classical and quantum random access codes (RACs) in which the parties communicate higher-dimensional systems. They construct quantum RACs with a greater advantage over classical RACs compared to previously considered RACs with binary alphabets. However, these results crucially hinge upon an unproven assertion that the classical strategy "majority-encoding-identity-decoding" leads to the maximum average success probability achievable for classical RACs; in this work we provide a proof of this intuition. We characterize all optimal classical RACs and show that indeed ``majority-encoding-identity-decoding" is one among the several optimal strategies. Along with strengthening the results in Tavakoli et al., our result provides a firm basis for future research on this topic.

We show an equivalence between 1-query quantum algorithms and representations by degree-2 polynomials. Namely, a partial Boolean function $f$ is computable by a 1-query quantum algorithm with error bounded by $\epsilon\lt1/2$ iff $f$ can be approximated by a degree-2 polynomial with error bounded by $\epsilon'\lt1/2$. This result holds for two different notions of approximation by a polynomial: the standard definition of Nisan and Szegedy \cite{NS} and the approximation by block-multilinear polynomials recently introduced by Aaronson and Ambainis \cite{AA}.