Lorentz Center - Quantum Random Walks and Quantum Algorithms from 7 Dec 2015 through 11 Dec 2015
  Current Workshop  |   Overview   Back  |   Home   |   Search   |     

    Quantum Random Walks and Quantum Algorithms
    from 7 Dec 2015 through 11 Dec 2015


Abstracts                                                                              last update: 30-11-2015


Andris Ambainis

Search by quantum walk and extended hitting time


We study search by quantum walk, a paradigm for constructing quantum algorithms by designing a random walk and then transforming this random walk into a quantum walk. Search by quantum walk provides a quadratic speedup over search by a classical random walk if the goal is to determine whether an object with a certain property (a marked

object) exists. An open problem is to extend this speedup to the case when the goal is to find the marked object.


To solve this problem, Krovi et al. (ICALP'2010, arXiv:1002.2419) proposed the notion of interpolating between two random walks (and quantizing the interpolated walk). Using this approach, they showed that a marked object can be found in time that is the square root of the extended hitting time of the classical random walk, with the extended hitting time being a mathematical expression that is resemblant of the expression for the usual hitting time and becomes equal to it if there is only one marked object. We show that, for a larger number of objects, there may be quite large gaps between the extended hitting time and the usual hitting time. As a result, the interpolated quantum walk does not work well in those cases.


Joint work with Mārtiņš Kokainis



Alexander Belov

Quantum Walks and Electric Networks


The language of electric circuits has been successfully used in the analysis of random walks.  This connection has been largely ignored in quantum walks.  In this talk, I show the properties of an electric circuit, like effective resistance, can be used in the analysis of hitting time of a quantum walk.  This talk is based on arXiv:1302.3143, but also includes more recent development.


Yimin Ge

Rapid adiabatic preparation of injective PEPS and Gibbs states


We propose a quantum algorithm for many-body state preparation. It is especially suited for injective PEPS and thermal states of local commuting Hamiltonians on a lattice. We show that for a uniform gap and sufficiently smooth paths, an adiabatic runtime and circuit depth of O(polylog(N)) can be achieved for O(N) spins. This is an almost exponential improvement over previous bounds. The total number of elementary gates scales as O(N polylog(N)). This is also faster than the best known upper bound of O(N^2) on the mixing times of Monte-Carlo Markov Chain algorithms for sampling classical systems in thermal equilibrium. [Based on arXiv:1508.00570, joint work with Andras Molnar and Ignacio Cirac]


David Gosset

Universal computation by multi-particle quantum walk






Sabine Jansen

Wigner crystallization in a one-dimensional quantum Coulomb gas


The Feynman-Kac representation of stochastic processes plays prominent role in quantum statistical mechanics, as it maps quantum problems to stochastic problems involving bridges. As an illustration we prove that a one-dimensional Coulomb system of interacting fermions in a neutralizing background displays translational symmetry breaking, for all values of the inverse temperatures, thereby extending a result by Brascamp and Lieb (1975). Key to the proof is a Markov chain of non-colliding Ornstein-Uhlenbeck bridges, constructed with the help of the Krein-Rutman-theorem, an infinite-dimensional version of the Perron-Frobenius theorem. The talk is based on joint work with Paul Jung (Comm. Math. Phys. 2014).


Stacey Jeffery

Span Programs and Graphs


In this talk I will discuss some problems at the intersection of span programs, an important quantum algorithmic framework, and graph theory. In particular, I will present some recent results relating the quantum query complexity of nand-tree evaluation to the effective resistance of certain graphs.


Roman Kotecký

Emergence of large cycles for random interchanges on a hypercube


Phase transitions for quantum spin lattice models can be shown to be linked with the existence of large cycles for random interchanges of sites of the corresponding  lattice. While for complete graphs the random interchanges are well understood (cards shuffling), the emergence of large cycles for lattices is an entirely open problem. The case of hypercube is a first step in this direction.

Based on a joint paper with P. Milos and D. Ueltschi.


Robin Kothari

Quantum linear systems algorithm with exponentially improved dependence on precision


Harrow, Hassidim, and Lloyd showed that for a suitably specified N x N matrix A and N-dimensional vector b, there is a quantum algorithm that outputs a quantum state proportional to the solution of the linear system of equations Ax=b. If A is sparse and well-conditioned, their algorithm runs in time poly(log N, 1/epsilon), where epsilon is the desired precision in the output state. We improve this to an algorithm whose running time is polynomial in log(1/epsilon), exponentially improving the dependence on precision while keeping essentially the same dependence on other parameters. Our algorithm is based on a general technique for implementing any operator with a suitable Fourier or Chebyshev series representation. This allows us to bypass the quantum phase estimation algorithm, whose dependence on epsilon is prohibitive.


Hans Maassen

Ergodic decomposition of measurement records.


We consider a general measurement on a finite quantum system, repeated infinitely often.

We show that observation of the asymptotic or `macroscopic' behavior of the record amounts

to a well-defined von Neumann (or "projective") measurement on the system.

The asymptotic behavior can be viewed as establishing itself in the course of the observation,

or as being revealed. This phenomenon was known in the `non-demolition' case and has been

named by Fröhlich et al. `the emergence of facts in quantum mechanics'.


Fred Magniez

Nested Quantum Walks


We extend the intuitive quantum walk search framework of MNRS in two separate directions. First we introduce the use of quantum data structures instead of classical ones. Then we extend the framework by showing that the data may depend not only on the current state, but on the coin (next state) as well.

As a result our framework leads to explicit algorithms whose complexities are easily understood (where the notion of complexity is not necessarily queries, but potentially time, space, or even (say) the number of non-Clifford gates).

We then use it to reproduce all known upper bounds based on the original learning graph framework of Belovs, including learning graph upper bounds for triangle finding. We also obtain an upper bound on the time complexity of 3-distinctness matching the query upper bound of Belovs up to log factors. A generalization of our 3-distinctness algorithm gives new upper bounds of on the quantum time complexity of k-distinctness for k > 3.

We also present a new framework based on the adaptive learning graphs which allows us to simplify the best known algorithm for Triangle Finding of Le Gall, and to improve its query complexity by polylog factors.

This is based on joint works arXiv:1210.1199 and arXiv:1302.7316 with Andrew M. Childs, Stacey Jeffery and Robin Kothari, and some preliminary work with Titouan Carette.


Piotr Milos

The random interchange process on the hypercube


The interchange process is defined on a finite graph. With any edge is associated the transposition of its endvertices. The outcomes of the interchange process consist of sequences of random transpositions and the main questions of interest deal with the cycle structure of the random permutation that is obtained as the composition of these transpositions. As the number of random transpositions increases, a phase transition may occur that is indicated by the emergence of cycles of diverging lengths involving a positive density of vertices.


The most relevant graphs are regular graphs with an underlying ``geometric structure'' like a finite cubic box in $Z^d$ with edges between nearest neighbours. But the problem of proving the emergence of long cycles is out of reach for now and recent studies have been devoted to simpler graphs such as trees and complete graphs.


The motivation is to move away from the complete graph towards $Z^d$. We consider the hypercube $\{0,1\}^n$ in the large $n$ limit and  establish the occurrence of a phase transition demonstrated by the emergence of cycles larger than $2^{n(1/2-\epsilon)}$. Our proof utilises the recent method of Berestycki, which was used for the complete graph but is valid more generally, with an estimate of the rate of splits that invokes the isoperimetric inequality for hypercubes.



Ashley Montanaro

Quantum walk speedup of backtracking algorithms


In this talk I will discuss how quantum walks can be used to speed up 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.


Maris Ozols

Quantum walks can find a marked element on any graph


We solve an open problem by constructing quantum walks that not only detect but also find marked vertices in a graph. In the case when the marked set M consists of a single vertex, the number of steps of the quantum walk is quadratically smaller than the classical hitting time

HT(P,M) of any reversible random walk P on the graph. In the case of multiple marked elements, the number of steps is given in terms of a related quantity HT+(P,M) which we call extended hitting time.


Our approach is new, simpler and more general than previous ones. We introduce a notion of interpolation between the random walk P and the absorbing walk P', whose marked states are absorbing. Then our quantum walk is simply the quantum analogue of this interpolation. Contrary to previous approaches, our results remain valid when the random walk P is not state-transitive. We also provide algorithms in the cases when only approximations or bounds on parameters pM (the probability of picking a marked vertex from the stationary distribution) and HT+(P,M) are known.


This is joint work with Hari Krovi, Frédéric Magniez, and Jérémie Roland.



Frank Redig

Probabilistic inequalities for KMS states


For sums of independent (or approximately independent) random variables, precise information can be obtained about the distribution of the empirical average. Large deviations provide precise information about the distribution on the exponential scale, whereas concentration inequalities provide estimates also for finite sample sizes, as well as for more general Lipschitz functions.

Large deviations are naturally connected to Gibbs measures, because large deviation probabilities can be viewed as free energy differences.

The quantum analogues of Gibbs measures are KMS states. In this context large deviations and concentration inequalities are largely unexplored. I will discuss partial results and open problems in this area.


Jeremie Roland

A universal adiabatic quantum query algorithm


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.


Mario Szegedy

"resample systems" (generalization of LLL).


Balint Toth 

Stochastic representations for the quantum Heisenberg ferromagnet. Are they of any use?


Proving long range order at positive temperature for the quantum Heisenberg ferromagnet in dimensions three and more has evaded all attempts so far. I will present some representations in terms of interacting random walks which may or may not be of any use.

Daniel Ueltschi

Random loop models and quantum spin systems


The random loop representations of quantum Heisenberg models allow to study these systems using probabilistic methods. They were introduced twenty years ago by Toth and Aizenman-Nachtergaele. I will review rigorous results and open questions. I will describe a probabilistic proof of exponential decay of transverse quantum correlations (joint work with J. Bjornberg).


Reinhard Werner
Asymptotic position distribution of quantum walks on a lattice

Let X(t) be the position of a translationally invariant quantum walk on an infinite lattice (in any dimension). Then X(t)/t converges in distribution, which is known as ballistic transport. The limiting distribution can be computed directly in any initial state as the the distribution of another observable,known as the group velocity. The distribution has compact support, and Large Deviation estimates hold for finding X(t)/t properly outside this support.

When the dynamics is modified by iid random coin choices (thus breaking translation invariance, but keeping the choice constant in time) one can get Anderson localisation, i.e., purely discrete spectrum with exponentially localized eigenfunctions and no propagation.  When coins are changed in time, controlled by some external classical Markov process, ballistic transport collapses, and in the disordered case Anderson localization is broken. After possibly subtracting some drift one gets diffusive propagation. Thus the translation invariant systems are slowed down by randomness in time, whereas the localized systems are speeded up.

Interesting effects occur, when the dynamics is not modified randomly but in a quasi-periodic way. This is the case of walks in an electric field. Depending on how rational the field is, in the sense of the continued fraction expansion, one gets Anderson localization, absolutely continuous spectrum with sharp revivals ultimately softening into ballistic transport, or singular spectrum with sharp revivals and larger and larger excursions on a hierarchy of time scales. These cases all lie dense in each other, i.e., cannot be distinguished on any finite time scale.

We also discuss a quantum analogue of Polya's theory of recurrence. In the quantum case, checking at each step whether the walker has returned, requires a modification of the dynamics. Nevertheless we give a simple spectral characterization of recurrence (eventual return with probability 1) in terms of the undisturbed evolution. The mean recurrence time is always an integer or infinite, which echoes results from Markov chain theory.

The talk is based on arXiv papers 1009.2019 (JMP), 1201.4839 (QInfProc), 1302.2081 (PRL), 1202.3903(CMP)