The QALGO 2015 project meeting will take place in Riga, Latvia from 2123 September.
The sessions are in the University of Latvia's Museum of History, which is located on the fourth floor the university's main building. The museum is rather hard to find, since there is only one staircase from the third floor that goes to the museum. Signs will be posted throughout the third floor. The main university building's address is:
Raiņa bulvāris 19
Rīga, LV1050
Latvia
9:30 
Ashley Montanaro (Bristol) • Slides
"Quantum walk speedup of backtracking algorithms"
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 boundederror 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 averagecase exponential speedup.

10:15 
Andris Ambainis (Latvia) • Slides
"Quantum algorithms vs. polynomials and the maximum quantumclassical gap in the query model"
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 propertytesting 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 tquery quantum algorithm whatsoever can be simulated by an O(N^{11/2t})query randomized algorithm. Second, we establish an equivalence between quantum query algorithms and polynomials, for the case of 1query 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). 
11:00  Coffee Break 
11:30 
Ronald de Wolf (CWI) • Slides
"Efficient Quantum Algorithms for (Gapped) Group Testing and Junta Testing"
In the kjunta testing problem, a tester has to efficiently decide whether a given function f:{0,1}^n>{0,1} is a kjunta (i.e., depends on at most k of its input bits) or is epsilonfar from any kjunta. 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 nearlinear time implementation of a shallow variant of the quantum Fourier transform over the symmetric group, similar to the SchurWeyl transform. We also prove a lower bound of Omega(k^{1/3}) queries for juntatesting (for constant epsilon).
Joint work with Andris Ambainis, Aleksandrs Belovs, Oded Regev 
12:15  Lunch Break 
14:00 
Matthias Christandl (Copenhagen)
"Limitations on Quantum Key Repeaters"
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.

14:45 
Maris Ozols (Cambridge)
"Continuous permutations and entropy power inequalities"
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.

15:30  Coffee Break 
16:00 
Open problem session Srinivasan Arunachalam (CWI)
"Optimizing the Number of Gates in Quantum Search"
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 Nbit 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 
10:00 
Anupam Prakash (Singapore) • Slides
"Quantum algorithms for linear algebra"
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 preprocessing vectors before storing them into quantum memory. The preprocessing 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. 
10:45  Coffee Break 
11:15 
Iordanis Kerenidis (Paris)
"An application of quantum algorithms for linear algebra"

11:45 
Miklos Santha (Paris)
"Linear time algorithm for quantum 2SAT"
A canonical result about satisfiability theory is that the 2SAT problem can be solved in linear time, despite the NPhardness of the 3SAT problem. In the quantum 2SAT problem, we are given a family of 2qubit 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 0eigenvalue. The problem is not only a natural extension of the classical 2SAT problem to the quantum case, but is also equivalent to the problem of finding the ground state of 2local frustrationfree Hamiltonians of spin 1/2, a wellstudied model believed to capture certain key properties in modern condensed matter physics. While Bravyi has shown that the quantum 2SAT problem has a classical polynomialtime 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.

12:15  Lunch Break 
14:00 
Dominique Unruh (Tartu) • Slides
"Noninteractive quantum zeroknowledge proofs"
Zeroknowledge 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 noninteractive (FiatShamir, in the randomoracle 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.

14:45 
Aleksandrs Belovs (Latvia) • Slides
"Separations in Query Complexity Based on Pointer Functions"
In 1986, Saks and Wigderson conjectured that the largest separation between deterministic and zeroerror 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 zeroerror 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 polylogarithmic 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 superquadratic gap between its quantum and deterministic query complexities.
Variations of this function give new separations between several other query complexity measures, including: the first superlinear separation between boundederror and zeroerror randomized complexity, larger gaps between exact quantum query complexity and deterministic/randomized query complexities, and a 4th power separation between approximate degree and boundederror 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 1certificate complexity from deterministic query complexity and to resolve the famous Clique versus Independent Set problem in communication complexity. 
15:30  Coffee Break 
16:00 
Open problem session Tom Wong (Latvia) • Slides
"Grover Search with Lackadaisical Quantum Walks"
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$ selfloops, 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 discretetime quantum walk using the phase flip coin, adding a selfloop to each vertex boosts the success probability from 1/2 to 1. Additional selfloops, however, decrease the success probability. Using instead the Ambainis, Kempe, and Rivosh (2005) coin, adding selfloops 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, continuoustime quantum walks differ from both of these discretetime examplesthe selfloops make no difference at all. These behaviors generalize to multiple marked vertices.

19:00  Dinner 
9:30 
Itai Arad (Singapore) • Slides
"A new classical algorithm for approximating the ground state of gapped 1D local Hamiltonians"
The ground states of gapped 1D localHamiltonians have long been known to satisfy an arealaw 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 epsilonnet 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 epsilonnet 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 arealaw. 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.

10:15 
Kasper Duivenvoorden (Aachen) • Slides
"Boundary physics of topological PEPS"
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 electricmagnetic 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.

11:00  Coffee Break 
11:30 
Mathieu Brandeho (ULB) • Slides
"A universal adiabatic quantum query algorithm"
Quantum query complexity is known to be characterized by the socalled quantum adversary bound. While this result has been proved in the standard discretetime model of quantum computation, it also holds for continuoustime (or Hamiltonianbased) 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 continuoustime 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.

12:15  End of Workshop 