Advanced search
1 file | 549.91 KB

Simulation of quantum walks and fast mixing with classical processes

Author
Organization
Abstract
We compare discrete-time quantum walks on graphs to their natural classical equivalents, which we argue are lifted Markov chains (LMCs), that is, classical Markov chains with added memory. We show that LMCs can simulate the mixing behavior of any quantum walk, under a commonly satisfied invariance condition. This allows us to answer an open question on how the graph topology ultimately bounds a quantum walk's mixing performance, and that of any stochastic local evolution. The results highlight that speedups in mixing and transport phenomena are not necessarily diagnostic of quantum effects, although superdiffusive spreading is more prominent with quantum walks. The general simulating LMC construction may lead to large memory, yet we show that for the main graphs under study (i.e., lattices) this memory can be brought down to the same size employed in the quantum walks proposed in the literature.
Keywords
COMPUTATION

Downloads

  • DS164.pdf
    • full text
    • |
    • open access
    • |
    • PDF
    • |
    • 549.91 KB

Citation

Please use this url to cite or link to this publication:

Chicago
Apers, Simon, Alain Sarlette, and Francesco Ticozzi. 2018. “Simulation of Quantum Walks and Fast Mixing with Classical Processes.” Physical Review A 98 (3).
APA
Apers, S., Sarlette, A., & Ticozzi, F. (2018). Simulation of quantum walks and fast mixing with classical processes. PHYSICAL REVIEW A, 98(3).
Vancouver
1.
Apers S, Sarlette A, Ticozzi F. Simulation of quantum walks and fast mixing with classical processes. PHYSICAL REVIEW A. College pk: Amer Physical Soc; 2018;98(3).
MLA
Apers, Simon, Alain Sarlette, and Francesco Ticozzi. “Simulation of Quantum Walks and Fast Mixing with Classical Processes.” PHYSICAL REVIEW A 98.3 (2018): n. pag. Print.
@article{8576041,
  abstract     = {We compare discrete-time quantum walks on graphs to their natural classical equivalents, which we argue are lifted Markov chains (LMCs), that is, classical Markov chains with added memory. We show that LMCs can simulate the mixing behavior of any quantum walk, under a commonly satisfied invariance condition. This allows us to answer an open question on how the graph topology ultimately bounds a quantum walk's mixing performance, and that of any stochastic local evolution. The results highlight that speedups in mixing and transport phenomena are not necessarily diagnostic of quantum effects, although superdiffusive spreading is more prominent with quantum walks. The general simulating LMC construction may lead to large memory, yet we show that for the main graphs under study (i.e., lattices) this memory can be brought down to the same size employed in the quantum walks proposed in the literature.},
  articleno    = {032115},
  author       = {Apers, Simon and Sarlette, Alain and Ticozzi, Francesco},
  issn         = {2469-9926},
  journal      = {PHYSICAL REVIEW A},
  keywords     = {COMPUTATION},
  language     = {eng},
  number       = {3},
  pages        = {14},
  publisher    = {Amer Physical Soc},
  title        = {Simulation of quantum walks and fast mixing with classical processes},
  url          = {http://dx.doi.org/10.1103/PhysRevA.98.032115},
  volume       = {98},
  year         = {2018},
}

Altmetric
View in Altmetric
Web of Science
Times cited: