Schedule for: 19w5146 - Quantum Walks and Information Tasks

A buffet dinner is served daily between 5:30pm and 7:30pm in the Vistas Dining Room, the top floor of the Sally Borden Building.

Breakfast is served daily between 7 and 9am in the Vistas Dining Room, the top floor of the Sally Borden Building.

A brief introduction to BIRS with important logistical information, technology instruction, and opportunity for participants to ask questions.

Light is a fascinating medium. It is interesting on its own but is equally well suited to be the tool for mimicking other physical systems. Recently considerable attention was given to processes called quantum walks. The quantum walk [1-2] is an excellent tool for modeling, simulating and testing a wide range of physical processes and effects. Quantum walks are defined as specific generalizations of classical (random) walks. The simplest model of a walk-the one dimensional discrete quantum walk (on a line)-is based on the combination of the dynamics of the internal degree of freedom defined by the coin operator and the conditioned shift in position space (step operator). The evolution of the walk is given by the repeated application of the resulting evolution operator. The coin as well as the step operator can suffer from imperfections and this leads to deviations from the ideal situation. The way how the ideal situation is alternated leads to additional interesting effects. We present results on theoretical and experimental studies of ideal and perturbed quantum walks [3-8] based on the all optical implementation of quantum walks. We point out the main results and future trends.

References
[1] Y. Aharonov, L. Davidovich, N. Zagury, Phys. Rev. A 48, 1687 (1993).
[2] D. A. Meyer, J. Stat. Phys. 85, 551 (1996).
[3] A. Schreiber, K. N. Cassemiro, V. Potocek, A. Gabris, P.J. Mosley, E. Andersson, I. Jex, Ch. Silberhorn, Phys. Rev. Lett. 104, 050502 (2010).
[4] A. Schreiber, K. N. Cassemiro, V. Potocek, A. Gábris, E, I. Jex, Ch. Silberhorn, Phys. Rev. Lett. 104, 050502 (2011).
[5] A. Schreiber, A. Gábris, P. P. Rohde, K. Laiho, M. Štefanák, V. Potocek, C. Hamilton, I. Jex, Ch. Silberhorn,. Science 336, 55 (2012).
[6] F. Elster, S. Barkhofen, T. Nitsche, J. Novotný, A. Gábris, I. Jex, Ch. Silberhorn, Sci. Rep. 5 (2015) 13495.
[7] T. Nitsche, F. Elster, J. Novotný, A. Gábris, I. Jex, S. Barkhofen, Ch. Silberhorn, New J. Phys. 18 (2016) 063017.
[8] T. Nitsche, S. Barkhofen, R. Kruse, L. Sansoni, M. Štefanák, A. Gábris, V. Potocek, T. Kiss, I. Jex, Ch. Silberhorn, Science Adv. 4, eaar6444 (2018).

We are considering a quantum system initially prepared in a pure state, that is repeatedly projectively measured in some detection state with a fixed inter-detection period. We investigate the distribution and the statistics of the time of the first successful detection event. The such obtained first detection time gives an operational definition to the time-of-arrival in the detection state. The probability of first detection can be obtained by means of a renewal equation. For systems with an absolutely continuous energy spectrum, we demonstrate how the asymptotics of this first detection probability are dominated by singularities in the spectral measures. For generic initial and detection states, these singularities can be identified with the system's van-Hove singularities. Furthermore, we give a detailed discussion of the transition problem in the tight-binding model on the infinite line, where the initial and detection position of a single quantum walker are separated.
Joint work with David A. Kessler and Eli Barkai.

In this talk we discuss the model of quantum Markov chains, due to S. Gudder, and most particularly the subset of open quantum walks, due to S. Attal et al., acting on finite graphs. As an iterative process, we use a monitoring procedure to determine the mean time for a quantum walker to visit some chosen vertex for the first time. We are interested in ways of calculating such hitting times besides making direct use of its definition and here we notice algebraic similarities and differences with the classical case. The case of unitary quantum walks remains an interesting open problem for which a solution could have potential applications to the associated theory of Schur functions.

Lunch is served daily between 11:30am and 1:30pm in the Vistas Dining Room, the top floor of the Sally Borden Building.

Meet in foyer of TCPL to participate in the BIRS group photo. The photograph will be taken outdoors, so dress appropriately for the weather. Please don't be late, or you might not be in the official group photo!

This talk is about a class of classical random processes on graphs that include the discrete Bak-Sneppen process, introduced in 1993, and the several versions of the contact process. These processes are parametrized by a probability $0\leq p\leq 1$ that controls a local update rule. Numerical simulations reveal a phase transition when $p$ goes from 0 to 1, which I will discuss in the talk. Analytically little is known about the phase transition threshold, even for one-dimensional chains. In this talk we consider a power-series approach based on representing certain quantities, such as the survival probability or expected hitting times, as a power-series in $p$. We prove that the coefficients of those power series stabilize as the length $n$ of the chain grows, and I will give a sketch of this proof in the talk. This stabilization of coefficients is a phenomenon that has been used in the physics community but was not yet proven. We show that for local events A, B of which the support is a distance $d$ apart we have cor$(A, B) = O(p^d)$. The stabilization is useful because it allows for the (exact) computation of coefficients for arbitrary large systems which can then be analyzed using the wide range of existing methods of power series analysis.

A buffet dinner is served daily between 5:30pm and 7:30pm in the Vistas Dining Room, the top floor of the Sally Borden Building.

Locality is the key property that ties a quantum walk to the underlying lattice. By this we mean that matrix elements of the unitary one-step operator become small between distant sites. The extreme case of this is a nearest neighbour walk, where matrix elements become zero for distance >1. We are interested here in the notions of locality for infinite lattices, allowing some decay of matrix elements, and focusing on the large scale propagation behaviour. The mathematical notion for a locality structure, which takes due note of composition properties, is called a coarse structure. I will describe this and show how even in one dimension there are different natural choices, which subtly differ even in the translation invariant case. I will then go to higher dimension, and discuss the relation to compactifications, C*-algebras, and their classification via K-theory.

Describing a particle in an external electromagnetic field is a basic task of quantum mechanics. The standard scheme for this is known as "minimal coupling", and consists of replacing the momentum operators in the Hamiltonian by modified ones with an added vector potential. In lattice systems it is not so clear how to do this, because there is no continuous translation symmetry, and hence there are no momenta. Moreover, when time is also discrete, as in quantum walk systems, there is no Hamiltonian, only a unitary step operator. We present a unified framework of gauge theory for such discrete systems, keeping a close analogy to the continuum case. In particular, we show how to implement minimal coupling in a way that automatically guarantees unitary dynamics. The scheme works in any lattice dimension, for any number of internal degree of freedom, for walks that allow jumps to a finite neighborhood rather than to nearest neighbors, is naturally gauge invariant, and prepares possible extensions to non-abelian gauge groups. We then focus on the case of constant magnetic fields. Although the magnetic field is constant, the translation system which realizes the field is no longer translation invariant. If, however, the entries of the field-strength tensor are rational multiples of $2\pi$, translation invariance can by retrieved by regrouping the underlying lattice in an appropriate way, resulting in a translation invariant translation system with respect to a coarser sublattice. This renders the possibility of classifying the resulting eigenbundles via Chern classes [2]. As the possible regroupings are highly non-unique, the question arises whether the characteristic classes of the eigenbundles are invariant under the chosen regrouping. We answer this question in the affirmative, by showing that any two minimally regrouped translation system for a given rational magnetic field are unitarily equivalent.

References
[1] C. Cedzich, T. Geib, A. H. Werner, and R. F. Werner. Quantum walks in external gauge fields. Journal of Mathematical Physics, 60(1):012107, 2019. arXiv:1808.10850.
[2] M. Sajid, J. K. Asbóth, D. Meschede, R. Werner, and A. Alberti. Creating floquet chern insulators with magnetic quantum walks. 2018. arxiv:1808.08923.

Quantum informational protocols involve coherent evolution, measurement, and postselection of qubits. A typical example is entanglement distillation. The resulting conditional dynamics is nonlinear, in contrast to the usual evolution of both closed and open quantum systems. Already the simplest types of such protocols may result in rich, complex chaotic dynamics when applied iteratively. An important property of these iterated dynamical systems is that initially pure quantum states remain pure throughout the evolution. For single-qubit systems, there is a one to one correspondence of the pure-state quantum dynamics to the iterated dynamics of quadratic rational maps with one complex variable. For two-qubit systems LOCC operations may lead to dynamics, where the evolution of entanglement is chaotic in the sense of crucially depending infinitely fine details of the initial state. Sensitivity to initial states in quantum systems, stemming from such non-linear dynamics, is a promising perspective for applications. They provide for example a solution to the quantum state matching problem, i.e. the task of deciding whether an unknown qubit state falls in a prescribed neighborhood of a reference state. We determine that such protocols may exhibit sensitive, quasi-chaotic evolution not only for pure initial states but also for mixed states, i.e., the complex dynamical behavior is not destroyed by small initial uncertainty. We show that the appearance of sensitive, complex dynamics associated with a fractal structure in the parameter space of the system has the character of a phase transition. The purity of the initial state plays the role of the control parameter, and the dimension of the fractal structure is independent of the purity value after passing the phase transition point.

References
[1] A. Gilyén, T. Kiss, and I. Jex, Sci. Rep. 6, 20076 (2016).
[2] O. Kálmán and T. Kiss, Phys. Rev. A 97, 032125 (2018).
[3]Martin Malachov, Igor Jex, Orsolya Kálmán, and Tamás Kiss, Chaos 29, 033107 (2019).

Topological insulators have Hamiltonians with bulk topological invariants, which control the interesting processes at the surface of the system, but are hard to measure directly. We have found a way to measure the bulk topological invariant (winding number) of one-dimensional topological insulator Hamiltonians and quantum walks with chiral symmetry: it is given by the displacement of a single particle, observed via losses [1]. Losses represent the effect of repeated weak measurements on one sublattice only, which interrupt the dynamics periodically. When these do not detect the particle, they realize negative measurements. In our repeated measurement scheme these losses occur at the end of every timestep. In the limit of rapidly repeated, vanishingly weak measurements, this corresponds to non-Hermitian Hamiltonians, such as the lossy Su-Schrieffer-Heeger model [2]. Contrary to intuition, the time needed to detect the winding number can be made shorter by decreasing the efficiency of the measurement. Our scheme has since been used to measure the bulk topological invariants of a discrete-time quantum walk on photons [3].

References
[1] T Rakovszky, JK Asboth, and A Alberti, Phys. Rev. B 95, 201407 (2017).
[2] MS Rudner and LS Levitov, Phys. Rev. Lett. 102, 065703 (2009).
[3] X Zhan et al, Phys. Rev. Lett. 119, 130501 (2017).

We show that the evolution of two-component particles under a continuous-time quantum walk can reveal topological phases. A kink in the mean width of the walker distribution signals the closing of the energy gap, a prerequisite for a quantum phase transition between topological phases. For realistic and experimentally motivated Hamiltonians, the distribution in topologically non-trivial phases displays characteristic rings in the vicinity of the origin that are absent in topologically trivial phases. The results are expected to have immediate application to systems of ultracold atoms and photonic lattices, and should aid in the realization of topological states suitable for quantum computation.

A quantum walk algorithm can detect the presence of a marked vertex on a graph quadratically faster than the corresponding random walk algorithm (Szegedy, FOCS 2004). However, quantum algorithms that actually find a marked element quadratically faster than a classical random walk were only known for the special case when the marked set consists of just a single vertex, or in the case of some specific graphs. We present a new quantum algorithm for finding a marked vertex in any graph, with any set of marked vertices, that is (up to a log factor) quadratically faster than the corresponding classical random walk.
Joint work with András Gilyén, Stacey Jeffery, Martins Kokainis, arxiv preprint 1903.07493.

We provide a new spatial search algorithm by continuous-time quantum walk which can find a marked node on any ergodic, reversible Markov chain P, in a time that is quadratically faster than the corresponding classical random walk on P. In the scenario where multiple nodes are marked, the running time of our algorithm scales as the square root of a quantity known as the extended hitting time. This solves an open problem concerning the difference between the running time of spatial search by discrete-time and continuous time quantum walk. We also show that the widely used Childs and Goldstone algorithm for spatial search by continuous-time quantum walk is quite restrictive: we identify limitations in its applicability whenever P is not state-transitive. We subsequently improve and extend this algorithm to be applicable for any P. Our generalizations imply that most hitherto published results on the performance of quantum spatial search in the Childs and Goldstone framework on specific graphs are particular cases of our result. However, we prove that the running time of the Childs and Goldstone algorithm and its subsequent improvement is suboptimal: our spatial search algorithm outperforms it. Our results can be adapted to a number of Markov chain-based quantum algorithms and will lead to exploring other connections between discrete-time and continuous-time quantum walks.
Joint work with Shantanav Chakraborty and Leonardo Novo.

I will present several open problems in the context of continuous-time quantum walks in graphs. To each problem, I will try to outline their technical nature, and I will speculate which techniques could be applied to solve them.

A quantum walk is governed by its transition matrix which is unitary; since this process is necessarily non-ergodic and one cannot speak of a stationary distribution, we study the average behaviour of the quantum walk. The average of the mixing matrices contains relevant information about the quantum walk and about the graph. There has been a considerable amount of success in approaching questions about continuous-time quantum walks with tools in linear algebra and algebraic graph theory and we will discuss several recent works in this area, based on joint work with Chris Godsil, Gabriel Coutinho, Harmony Zhan and John Sinkovic.

Let $X$ be a graph, and denote its Laplacian matrix by $L$. Let $U(t) = e^{itL}$. Then $U(t)$ is a complex symmetric unitary matrix. We say that $X$ admits Laplacian fractional revival between vertices $j$ and $k$ at time $t = t_0$, if $U(t_0)e_j = \alpha e_j + \beta e_k$ for some complex numbers $\alpha$ and $\beta$ with $\beta\neq0$. In the special case where $\alpha=0$, we say there is perfect state transfer between vertices $j$ and $k$ at time $t = t_0$. Assume that a graph $X$ admits Laplacian fractional revival at time $t=t_0$ between vertices $1$ and $2$. We prove that for the spectral decomposition $L=\sum_{r=0}^q\theta_rE_r$ of $L$, for each $r=0,1,\ldots, q$, either $E_re_1=E_re_2$, or $E_re_1=-E_re_2$, depending on whether $e^{it_0\theta_r}$ equals to 1 or not. That is to say, vertices 1 and 2 are strongly cospectral with respect to $L$. We give a characterization of the parameters of threshold graphs that allow for Laplacian fractional revival between two vertices; those graphs can be used to generate more graphs with Laplacian fractional revival. We also characterize threshold graphs that admit Laplacian fractional revival between a subset of more than two vertices.

Some quantum walks can be modeled using weighted graphs, where each vertex represents a qubit, each weighted edge indicates the coupling strength between two qubits, and each weighted loop indicates the strength of the magnetic field of a qubit. In this talk, I will discuss two analytic approaches to quantum walks: orthogonal polynomials, which have been applied mostly to weighted paths, and spectral graphs theory, which has been applied mostly to simple unweighted graphs. I will also talk about some interesting relations between quantum walks on weights paths and quantum walks on simple unweighted graphs.
Part of this talk is joint work with Gabriel Coutinho, Luv Vinet and Alexei Zhedanov.

It is known that Krawtchouk polynomials play a central role in the analysis of (continuous-time) quantum walk on hypercube. Such walk also gives the spin lattice Hamiltonian where perfect state transfer occurs. In this talk (or presentation), we will start with multivariate Krawtchouk polynomials. We will introduce the associated graph and show that some spin lattice Hamiltonian in multi-dimension can be described as projections of quantum walk on this graph. In the model, fractional revival in addition to perfect state transfer is shown to take place.
This is based on the joint-work with Satoshi Tsujimoto and Luc Vinet.

The subject starts with C. Shannon questions at Bell Labs and the amazing answers found in the 60's by Slepian, Landau and Pollak. The crux of the matter is that in some naturally appearing problems in signal processing a certain integral operator admits an explicit commuting second order differential one, or a full matrix admits a commuting tridiagonal one. These operators are parametrized by the duration of the signal and its bandwidth. I have been trying to understand and extend this miracle for a long time, mainly in "non translation invariant cases". All the examples from Bell Labs involve Fourier analysis in different setups. I have managed to extend this to a few other cases. My "new motivation" comes from looking at two papers: "Maximal violations of Bell inequalities by position measurements" , J. Kiukas and R. Werner 2009 and "Properties of the entanglement Hamiltonian for finite free-fermion chains", V. Eisler and I. Peschel 2018. Both of these papers exploit the commutativity property in some physically important cases. My hope is that some members of the audience may point out a few more cases where this very exceptional mathematical phenomenon plays a physically relevant role.

Tensor network states provide successful descriptions of strongly correlated quantum systems with applications ranging from condensed matter physics to cosmology. Any family of tensor network states possesses an underlying entanglement structure given by a graph of maximally entangled states along the edges that identify the indices of the tensors to be contracted. Recently, more general tensor networks have been considered, where the maximally entangled states on edges are replaced by multipartite entangled states on plaquettes. Both the structure of the underlying graph and the dimensionality of the entangled states influence the computational cost of contracting these networks. Using the geometrical properties of entangled states, we provide a method to construct tensor network representations with smaller effective bond dimension. We illustrate our method with the resonating valence bond state on the kagome lattice.

5-day workshop participants are welcome to use BIRS facilities (BIRS Coffee Lounge, TCPL and Reading Room) until 3 pm on Friday, although participants are still required to checkout of the guest rooms by 12 noon.