Search

We introduce a new tool for quantum algorithms called quantum fast-forwarding (QFF). The tool uses quantum walks as a means to quadratically fast-forward a reversible Markov chain. More specifically, with $P$ the Markov chain transition matrix and $D = \sqrt{P\circ P^T}$ its discriminant matrix ($D=P$ if $P$ is symmetric), we construct a quantum walk algorithm that for any quantum state $|v\rangle$ and integer $t$ returns a quantum state $\epsilon$-close to the state $D^t|v\rangle/\|D^t|v\rangle\|$. The algorithm uses $O\Big(\|D^t|v\rangle\|^{-1}\sqrt{t\log(\epsilon\|D^t|v\rangle\|)^{-1}}\Big)$ expected quantum walk steps and $O(\|D^t|v\rangle\|^{-1})$ expected reflections around $|v\rangle$. This shows that quantum walks can accelerate the transient dynamics of Markov chains, complementing the line of results that proves the acceleration of their limit behavior. We show that this tool leads to speedups on random walk algorithms in a very natural way. Specifically we consider random walk algorithms for testing the graph expansion and clusterability, and show that we can quadratically improve the dependency of the classical property testers on the random walk runtime. Moreover, our quantum algorithm exponentially improves the space complexity of the classical tester to logarithmic. As a subroutine of independent interest, we use QFF for determining whether a given pair of nodes lies in the same cluster or in separate clusters. This solves a robust version of $s$-$t$ connectivity, relevant in a learning context for classifying objects among a set of examples. The different algorithms crucially rely on the quantum speedup of the transient behavior of random walks., Comment: 24 pages, 5 pages appendix. 2nd version: exponentially improved error dependency, added application to graph property testing

In critical systems, the effect of a localized perturbation affects points that are arbitrarily far from the perturbation location. In this paper, we study the effect of localized perturbations on the solution of the random dimer problem in $2D$. By means of an accurate numerical analysis, we show that a local perturbation of the optimal covering induces an excitation whose size is extensive with finite probability. We compute the fractal dimension of the excitations and scaling exponents. In particular, excitations in random dimer problems on non-bipartite lattices have the same statistical properties of domain walls in the $2D$ spin glass. Excitations produced in bipartite lattices, instead, are compatible with a loop-erased self-avoiding random walk process. In both cases, we find evidence of conformal invariance of the excitations that is compatible with $\mathrm{SLE}_\kappa$ with parameter $\kappa$ depending on the bipartiteness of the underlying lattice only., Comment: 8 pages

Accepted manuscript version. Published version available at https://doi.org/10.1007/s00205-018-1245-1. Prolongating our previous paper on the Einstein relation, we study the motion of a particle diffusing in a random reversible environment when subject to a small external forcing. In order to describe the long time behavior of the particle, we introduce the notions of steady state and weak steady state. We establish the continuity of weak steady states for an ergodic and uniformly elliptic environment. When the environment has finite range of dependence, we prove the existence of the steady state and weak steady state and compute its derivative at a vanishing force. Thus we obtain a complete ‘fluctuation–dissipation Theorem’ in this context as well as the continuity of the effective variance.

We initiate the study of a fundamental combinatorial problem: Given a capacitated graph $$G=(V,E)$$G=(V,E), find a shortest walk (“route”) from a source $${s\in V}$$s∈V to a destination $$t\in V$$t∈V that includes all vertices specified by a set $$WP \subseteq V$$WP⊆V: the waypoints. This Waypoint Routing Problem finds immediate applications in the context of modern networked systems. Our main contribution is an exact polynomial-time algorithm for graphs of bounded treewidth. We also show that if the number of waypoints is logarithmically bounded, exact polynomial-time algorithms exist even for general graphs. Our two algorithms provide an almost complete characterization of what can be solved exactly in polynomial time: we show that more general problems (e.g., on grid graphs of maximum degree 3, with slightly more waypoints) are computationally intractable.

The diagonal of a multivariate power series F is the univariate power series Diag(F) generated by the diagonal terms of F. Diagonals form an important class of power series; they occur frequently in number theory, theoretical physics and enumerative combinatorics. We study algorithmic questions related to diagonals in the case where F is the Taylor expansion of a bivariate rational function. It is classical that in this case Diag(F) is an algebraic function. We propose an algorithm that computes an annihilating polynomial for Diag(F). We give a precise bound on the size of this polynomial and show that generically, this polynomial is the minimal polynomial and that its size reaches the bound. The algorithm runs in time quasi-linear in this bound, which grows exponentially with the degree of the input rational function. We then address the related problem of enumerating directed lattice walks. The insight given by our study leads to a new method for expanding the generating power series of bridges, excursions and meanders. We show that their first N terms can be computed in quasi-linear complexity in N, without first computing a very large polynomial equation., Comment: This is an extended version of arXiv:1510.04080 with more precise results and more detailed proofs

Trace monoids provide a powerful tool to study graphs, viewing walks as words whose letters, the edges of the graph, obey a specific commutation rule. A particular class of traces emerges from this framework, the hikes, whose alphabet is the set of simple cycles on the graph. We show that hikes characterize undirected graphs uniquely, up to isomorphism, and satisfy remarkable algebraic properties such as the existence and unicity of a prime factorization. Because of this, the set of hikes partially ordered by divisibility hosts a plethora of relations in direct correspondence with those found in number theory. Some applications of these results are presented, including an immanantal extension to MacMahon's master theorem and a derivation of the Ihara zeta function from an abelianization procedure.

We consider symmetric powers of a graph. In particular, we show that the spectra of the symmetric square of strongly regular graphs with the same parameters are equal. We also provide some bounds on the spectra of the symmetric squares of more general graphs. The connection with generic exchange Hamiltonians in quantum mechanics is discussed in Appendix A.

L’étude des sentiers périurbains de Balagne en haute Corse à travers leur appréhension par les habitants doit nous permettre d’analyser le rôle des cheminements à la lisière de l’urbanité et de la ruraalité dans la dynamique d’appropriation territoriale. Après avoir présenté le contexte particulier de l’enquête ethnographique menée depuis 2013, cet article s’intéresse aux postures des corps lors des promenades ainsi qu’à la mobilisation des sens. Il s’agit de comprendre la relation sensible qui se noue aux lieux et ce qu’elle dit de l’attachement au territoire. De la même façon, les registres discursifs mobilisés par les usagers sont analysés afin de déterminer en quoi la marche en littoral urbain permet à la fois de définir une appartenance à l’écoumène et de se redécouvrir soi-même., Studying the perception of inhabitants about the outer-urban paths in Balagne (Corsica) should allow us to analyse the impact of progressions on the edge of urbanity and durality on the dynamic of territorial appropriation. This article starts by presenting the ethnographic study conducted since 2013. It then focuses on body postures during the walks and the mobilization of a sensitive approach. The point is to understand how people relate to places emotionnaly and what it tells us about their attachement to the territory. In a similar way, walkers’ discourses are analysed in order to determine how walking on the urban littoral allow one to define a belonging to the oeukoumène and rediscover oneself.

Swiss National Foundation : FN 200020-149871/1. CIMI (Centre International de Mathematiques et d'Informatique) : ANR-11-LABX-0040-CIMI, ANR-11-IDEX-0002-02; International audience; This work is concerned with the analysis of a stochastic approximation algorithm for the simulation of quasi-stationary distributions on finite state spaces. This is a generalization of a method introduced by Aldous, Flannery and Palacios. It is shown that the asymptotic behavior of the empirical occupation measure of this process is precisely related to the asymptotic behavior of some deterministic dynamical system induced by a vector field on the unit simplex. This approach provides new proof of convergence as well as precise asymptotic rates for this type of algorithm. In the last part, our convergence results are compared with those of a particle system algorithm (a discrete-time version of the Fleming-Viot algorithm).

Boson samplers—set-ups that generate complex many-particle output states through the transmission of elementary many-particle input states across a multitude of mutually coupled modes—promise the efficient quantum simulation of a classically intractable computational task, and challenge the extended Church–Turing thesis, one of the fundamental dogmas of computer science. However, as in all experimental quantum simulations of truly complex systems, one crucial problem remains: how to certify that a given experimental measurement record unambiguously results from enforcing the claimed dynamics, on bosons, fermions or distinguishable particles? Here we offer a statistical solution to the certification problem, identifying an unambiguous statistical signature of many-body quantum interference upon transmission across a multimode, random scattering device. We show that statistical analysis of only partial information on the output state allows to characterise the imparted dynamics through particle type-specific features of the emerging interference patterns. The relevant statistical quantifiers are classically computable, define a falsifiable benchmark for BosonSampling, and reveal distinctive features of many-particle quantum dynamics, which go much beyond mere bunching or anti-bunching effects., New Journal of Physics, 18, ISSN:1367-2630