1. Quantum fast-forwarding: Markov chains and graph property testing
- Author
-
Simon Apers, Alain Sarlette, Department of Electronics and Information Systems - Ghent University (ELIS), Universiteit Gent = Ghent University [Belgium] (UGENT), QUANTum Information Circuits (QUANTIC), École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-MINES ParisTech - École nationale supérieure des mines de Paris, Université Paris sciences et lettres (PSL)-Sorbonne Université (SU)-Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Sarlette, Alain, Centrum Wiskunde & Informatica, Amsterdam (CWI), The Netherlands, Universiteit Gent = Ghent University (UGENT), Mines Paris - PSL (École nationale supérieure des mines de Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Sorbonne Université (SU)-Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire de physique de l'ENS - ENS Paris (LPENS), Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Cité (UPCité)-Département de Physique de l'ENS-PSL, École normale supérieure - Paris (ENS-PSL), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-École normale supérieure - Paris (ENS-PSL), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Cité (UPCité)-Département de Physique de l'ENS-PSL, Université Paris sciences et lettres (PSL), MINES ParisTech - École nationale supérieure des mines de Paris, and Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-École normale supérieure - Paris (ENS Paris)
- Subjects
Property testing ,Nuclear and High Energy Physics ,Speedup ,F.2 ,FOS: Physical sciences ,General Physics and Astronomy ,property testing ,G.2.2 ,01 natural sciences ,010305 fluids & plasmas ,Theoretical Computer Science ,[PHYS.QPHY]Physics [physics]/Quantum Physics [quant-ph] ,Quantum state ,SEARCH ,0103 physical sciences ,WALKS ,quantum walks ,Quantum walk ,ALGORITHM ,010306 general physics ,quantum algorithms ,[PHYS.QPHY] Physics [physics]/Quantum Physics [quant-ph] ,ComputingMilieux_MISCELLANEOUS ,Mathematical Physics ,Quantum walks ,Mathematics ,Discrete mathematics ,Quantum Physics ,Quantum algorithms ,Markov chain ,Stochastic matrix ,Statistical and Nonlinear Physics ,EXPANSION ,HAMILTONIAN SIMULATION ,Random walk ,Mathematics and Statistics ,Physics and Astronomy ,Computational Theory and Mathematics ,Quantum algorithm ,Quantum Physics (quant-ph) ,05C85, 60G50, 60J10, 68R10 - Abstract
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
- Published
- 2019
- Full Text
- View/download PDF