Fast Mixing with Quantum Walks vs. Classical Processes

Simon Apers 1 Alain Sarlette 2 Francesco Ticozzi 3, 4
2 QUANTIC - QUANTum Information Circuits
ENS Paris - École normale supérieure - Paris, Inria Paris-Rocquencourt, UPMC - Université Pierre et Marie Curie - Paris 6, MINES ParisTech - École nationale supérieure des mines de Paris, CNRS - Centre National de la Recherche Scientifique : UMR8551
Abstract : Quantum walks have been linked to acceleration in various information processing tasks, and proposed as a possible model for quantum-enhanced behavior in biological systems. These links and acceleration claims have been made with various levels of detail. Here we consider discrete-time quantum walks, and focus on the task of mixing, i.e., distributing the state over a graph. Previous papers have observed that the so-called coined quantum walks can accelerate mixing on certain graphs with respect to the optimal classical Markov chain. We here show that the same speedup can be attained with a classical process, if a similar classical coin is added. We establish a precise correspondence between the mixing performance of quantum walks and such " lifted walks " for all (finite) graphs, and thereby improve known bounds on quantum walk mixing time. We conclude that the advantage of quantum walks with respect to classical processes is not in the mixing speed of the optimal design. However, a notable quantum advantage might reside in the fact that the mixing speed obtained with suboptimal designs, due to for instance limited graph knowledge, appears to be generically faster.
Type de document :
Quantum Information Processing (QIP) 2017, Jan 2017, Seattle, United States
Liste complète des métadonnées

Littérature citée [15 références]  Voir  Masquer  Télécharger
Contributeur : Alain Sarlette <>
Soumis le : vendredi 11 novembre 2016 - 01:35:32
Dernière modification le : jeudi 22 novembre 2018 - 14:23:37
Document(s) archivé(s) le : jeudi 16 mars 2017 - 11:54:45


Fichiers produits par l'(les) auteur(s)


  • HAL Id : hal-01395592, version 1


Simon Apers, Alain Sarlette, Francesco Ticozzi. Fast Mixing with Quantum Walks vs. Classical Processes. Quantum Information Processing (QIP) 2017, Jan 2017, Seattle, United States. 〈hal-01395592〉



Consultations de la notice


Téléchargements de fichiers