Center for Scientific Workshops in All Disciplines

Current Workshop | Overview | Back | Home | Search | | ||||||||||

## Quantum Random Walks and Quantum Algorithms |

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
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.
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]
Universal computation by multi-particle
quantum walk
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).
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.
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.
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.
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'.
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.
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.
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.
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. http://arxiv.org/abs/1002.2419
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.
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.
"resample systems" (generalization of LLL).
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.
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).
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) [Back] |