QALGO 2015 Meeting in Riga, Latvia

In this talk I will discuss a general method to obtain quantum speedups of classical algorithms which are based on the technique of backtracking, a standard approach for solving constraint satisfaction problems (CSPs). Backtracking algorithms explore a tree whose vertices are partial solutions to a CSP in an attempt to find a complete solution. Assume there is a classical backtracking algorithm which finds a solution to a CSP on n variables, or outputs that none exists, and whose corresponding tree contains T nodes, each node corresponding to a test of a partial solution. I will describe a bounded-error quantum algorithm which completes the same task using O(sqrt{T} poly(n)) tests. In particular, this quantum algorithm can be used to speed up the DPLL algorithm, which is the basis of many of the most efficient SAT solvers used in practice. The quantum algorithm is based on a quantum walk algorithm of Belovs applied to search in the backtracking tree. I will also discuss how, for certain distributions on the inputs, the algorithm can lead to an average-case exponential speedup.

We present two new results on quantum query complexity.

First, we determine the largest possible separation between quantum and classical query complexities. We show that a property-testing problem called Forrelation (where one needs to decide whether one Boolean function is highly correlated with the Fourier transform of a second function) can be solved using 1 quantum query, but requires ~sqrt(N)/log(N) queries for randomized algorithms (improving an ~N^{1/4} lower bound of Aaronson). We also show that this 1 versus ~sqrt(N) separation is optimal. More generally, any t-query quantum algorithm whatsoever can be simulated by an O(N^{1-1/2t})-query randomized algorithm.

Second, we establish an equivalence between quantum query algorithms and polynomials, for the case of 1-query algorithms and polynomials of degree 2. That is, we show that any polynomial of degree 2 approximating a Boolean function f(x_1, ..., x_N) can be transformed into a quantum query algorithm of degree 1. (Since the opposite transformation, from query algorithms to polynomials was established by Beals et al. in 1998, this establishes the equivalence between the two notions.) This is the first example where the two notions (computation by a quantum query algorithm and approximation by a polynomial) turn out to be equivalent.

The first part is joint work with Scott Aaronson (http://arxiv.org/abs/1411.5729) and the second part is joint with Scott Aaronson, Jānis Iraids, Mārtiņš Kokainis and Juris Smotrovs (we expect to post it on arXiv in a few weeks).

In the k-junta testing problem, a tester has to efficiently decide whether a given function f:{0,1}^n-->{0,1} is a k-junta (i.e., depends on at most k of its input bits) or is epsilon-far from any k-junta. Our main result is a quantum algorithm for this problem with query complexity ~O(sqrt{k/epsilon}) and time complexity ~O(n*sqrt{k/epsilon}). This quadratically improves over the query complexity of the previous best quantum junta tester, due to Atici and Servedio. Our tester is based on a new quantum algorithm for a gapped version of the combinatorial group testing problem, with an up to quartic improvement over the query complexity of the best classical algorithm. For our upper bound on the time complexity we give a near-linear time implementation of a shallow variant of the quantum Fourier transform over the symmetric group, similar to the Schur-Weyl transform. We also prove a lower bound of Omega(k^{1/3}) queries for junta-testing (for constant epsilon).
Joint work with Andris Ambainis, Aleksandrs Belovs, Oded Regev

A major application of quantum communication is the distribution of entangled particles for use in quantum key distribution (QKD). Due to noise in the communication line, QKD is in practice limited to a distance of a few hundred kilometres, and can only be extended to longer distances by use of a quantum repeater, a device which performs entanglement distillation and quantum teleportation. The existence of noisy entangled states that are undistillable but nevertheless useful for QKD raises the question of the feasibility of a quantum key repeater, which would work beyond the limits of entanglement distillation, hence possibly tolerating higher noise levels than existing protocols. Here we exhibit fundamental limits on such a device in the form of bounds on the rate at which it may extract secure key. As a consequence, we give examples of states suitable for QKD but unsuitable for the most general quantum key repeater protocol.

I will describe a unitary version of Cayley's theorem which allows to embed any finite group in a continuous subgroup of the unitary group. When applied to the symmetric group, this construction can be used to permute quantum systems in a continuous fashion. For the case of two systems, I will show that the resulting continuous swap operation obeys a discrete version of the entropy power inequality. My talk is based on arXiv:1508.00860 and arXiv:1503.04213.

In its usual form, Grover's algorithm uses O(sqrt{N}) queries and O(sqrt{N} log N) other gates to find a solution in an N-bit database. Grover in 2002 showed how to reduce the number of other gates to O(sqrt{N} loglog N) for the special case where the database has a unique solution. We show how to reduce this to O(sqrt{N} exp(log^* N)) gates. This means that, on average, the gates between two queries barely touch more than a constant number of the log N qubits on which the algorithm acts. Two open problems are to get rid of the log^* N (or show this factor is required) and to generalize to the case of multiple solutions.
Joint work with Ronald de Wolf

Most quantum algorithms for linear algebra problems either work with a restricted class of inputs or require time polynomial in the matrix dimension. We show that these restrictions can be removed by pre-processing vectors before storing them into quantum memory. The pre-processing is performed using simple classical augmentations to the quantum RAM. The augmented QRAM provides a framework for the design of quantum algorithms with poly logarithmic dependence on the dimensions of matrices.

We present quantum algorithms that perform coherent estimation of singular values of a matrix M with Frobenius norm 1 up to an additive error epsilon in time O(poly(log(mn), 1/epsilon)). Quantum singular value estimation is a useful primitive for algorithm design, we discuss applications to computing projections and low rank approximation.

A canonical result about satisfiability theory is that the 2-SAT problem can be solved in linear time, despite the NP-hardness of the 3-SAT problem. In the quantum 2-SAT problem, we are given a family of 2-qubit projectors on a system of n qubits, and the task is to decide whether the Hamiltonian, defined as the sum of these projectors, has a 0-eigenvalue. The problem is not only a natural extension of the classical 2-SAT problem to the quantum case, but is also equivalent to the problem of finding the ground state of 2-local frustration-free Hamiltonians of spin 1/2, a well-studied model believed to capture certain key properties in modern condensed matter physics. While Bravyi has shown that the quantum 2-SAT problem has a classical polynomial-time algorithm, the running time of his algorithm is O(n^4). Here we present a classical algorithm with linear running time in the number of local projectors.

Zero-knowledge proofs are a powerful tool in cryptography, allowing to prove the truth of a fact without revealing anything else. However, in their most basic form, ZK proofs are interactive, which makes them difficult to use in practice. Efficient transformations exist that make a ZK proof non-interactive (Fiat-Shamir, in the random-oracle model). But those fail in the quantum setting. We explain the difficulties in the quantum setting, show how to circumvent them, and close with a quantum query complexity problem whose solution would lead to a much simpler protocol.

In 1986, Saks and Wigderson conjectured that the largest separation between deterministic and zero-error randomized query complexity for a total boolean function is given by the function $f$ on $n=2^k$ bits defined by a complete binary tree of NAND gates of depth $k$, which achieves $R_0(f) = O(D(f)^{0.7537\ldots})$. We show this is false by giving an example of a total boolean function $f$ on $n$ bits whose deterministic query complexity is $\Omega(n/\log(n))$ while its zero-error randomized query complexity is $\tilde O(\sqrt{n})$. This shows that the relations $D(f) \le R_0(f)^2$ and $D(f) \le 2R_1(f)^2$ are optimal, up to poly-logarithmic factors. We further show that the quantum query complexity of the same function is $\tilde O(n^{1/4})$, giving the first example of a total function with a super-quadratic gap between its quantum and deterministic query complexities.
Variations of this function give new separations between several other query complexity measures, including: the first super-linear separation between bounded-error and zero-error randomized complexity, larger gaps between exact quantum query complexity and deterministic/randomized query complexities, and a 4th power separation between approximate degree and bounded-error randomized complexity.
All of these examples are variants of a function recently introduced by G\"{o}\"{o}s, Pitassi, and Watson which they used to separate the unambiguous 1-certificate complexity from deterministic query complexity and to resolve the famous Clique versus Independent Set problem in communication complexity.

The lazy random walk, where the walker has some probability of staying put, is a useful tool in classical algorithms. We propose a quantum analogue, the lackadaisical quantum walk, where each vertex is given $l$ self-loops, and we investigate its effects on Grover's algorithm when formulated as search for a marked vertex on the complete graph of $N$ vertices. For the discrete-time quantum walk using the phase flip coin, adding a self-loop to each vertex boosts the success probability from 1/2 to 1. Additional self-loops, however, decrease the success probability. Using instead the Ambainis, Kempe, and Rivosh (2005) coin, adding self-loops simply slows down the search. These coins also differ in that the first is faster than classical when $l$ scales less than $N$, while the second requires that $l$ scale less than $N^2$. Finally, continuous-time quantum walks differ from both of these discrete-time examples---the self-loops make no difference at all. These behaviors generalize to multiple marked vertices.

The ground states of gapped 1D local-Hamiltonians have long been known to satisfy an area-law and be well described by Matrix Product States (MPS) of low bond dimension. This places the problem of approximating the system's ground energy inside NP for these systems. Recently, in a milestone result, Landau, Vidick & Vazirani gave an efficient algorithm for approximating the ground state and its energy, thereby placing the problem inside P. To a large extent, their algorithm can be viewed as dynamical programming performed on the space of MPSs, with the aid of an epsilon-net that discretizes the quantum problem. In this talk I will present a new algorithm for the same problem. It lets go of dynamical programming and epsilon-net discretization, and instead uses the Chebyshev polynomial to construct good approximate ground state projectors (AGSP), which is a central concept also in a recent proof of the area-law. The resultant algorithm not only scales better with the spectral gap, but is also more natural, and may pave the way for other improvements in this field.

Projected Entangled Pair States (PEPS) provide a framework for the construction of solvable models where a single tensor gives rise to both Hamiltonian and ground state wavefunction on the same footing. In this talk I will discuss 2D PEPS models with anyonic excitations which arise due to a symmetry of the PEPS tensor. I will analyse a model in which a bound electric-magnetic excitation condenses. Interestingly, the transfer operator describing the 1D boundary of this model shows protected behavior identical to that observed in 1D symmetry protected topological phases.

Quantum query complexity is known to be characterized by the so-called quantum adversary bound. While this result has been proved in the standard discrete-time model of quantum computation, it also holds for continuous-time (or Hamiltonian-based) quantum computation, due to a known equivalence between these two query complexity models. In this work, we revisit this result by providing a direct proof in the continuous-time model. One originality of our proof is that it draws new connections between the adversary bound, a modern technique of theoretical computer science, and early theorems of quantum mechanics. Indeed, the proof of the lower bound is based on Ehrenfest's theorem, while the upper bound relies on the adiabatic theorem, as it goes by constructing a universal adiabatic quantum query algorithm. Another originality is that we use for the first time in the context of quantum computation a version of the adiabatic theorem that does not require a spectral gap.