Quantum random walks in one dimension via generating functions

Andrew Bressler; Robin Pemantle

doi:10.46298/dmtcs.3533

Andrew Bressler ; Robin Pemantle - Quantum random walks in one dimension via generating functions

dmtcs:3533 - Discrete Mathematics & Theoretical Computer Science, January 1, 2007, DMTCS Proceedings vol. AH, 2007 Conference on Analysis of Algorithms (AofA 07) - https://doi.org/10.46298/dmtcs.3533

Quantum random walks in one dimension via generating functionsArticle

Authors: Andrew Bressler ¹; Robin Pemantle ¹

1 Department of Mathematics [Philadelphia]

We analyze nearest neighbor one-dimensional quantum random walks with arbitrary unitary coin-flip matrices. Using a multivariate generating function analysis we give a simplified proof of a known phenomenon, namely that the walk has linear speed rather than the diffusive behavior observed in classical random walks. We also obtain exact formulae for the leading asymptotic term of the wave function and the location probabilities.

https://doi.org/10.46298/dmtcs.3533

Source: HAL:hal-01184781v1

Volume: DMTCS Proceedings vol. AH, 2007 Conference on Analysis of Algorithms (AofA 07)

Section: Proceedings

Published on: January 1, 2007

Imported on: May 10, 2017

Keywords: Hadamard,asymptotics,rational generating function,[INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS],[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM],[MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO],[INFO.INFO-CG] Computer Science [cs]/Computational Geometry [cs.CG]

Funding:

Source : OpenAIRE Graph

Asymptotic enumeration, reinforcement, and effective limit theory; Funder: National Science Foundation; Code: 0603821

Bibliographic References

10 Documents citing this article

Yuliy Baryshnikov;Stephen Melczer;Robin Pemantle, 2021, Stationary Points at Infinity for Analytic Combinatorics, arXiv (Cornell University), 22, 5, pp. 1631-1664, 10.1007/s10208-021-09523-x, https://arxiv.org/abs/1905.05250.

Stephen Melczer, Texts & monographs in symbolic computation/Texts and monographs in symbolic computation, Multiple Points and Beyond, pp. 351-385, 2020, 10.1007/978-3-030-67080-1_9.

Miquel Montero, 2015, Quantum walk with a general coin: exact solution and asymptotic properties, arXiv (Cornell University), 14, 3, pp. 839-866, 10.1007/s11128-014-0908-6, https://arxiv.org/abs/1310.7486.

C. M. Chandrashekar;Th. Busch, 2014, Quantum percolation and transition point of a directed discrete-time quantum walk, Scientific Reports, 4, 1, 10.1038/srep06583, https://doi.org/10.1038/srep06583.

A Ali;R C Ball;S Grosskinsky;E Somfai, 2013, Interacting particle systems in time-dependent geometries, arXiv (Cornell University), 2013, 09, pp. P09006, 10.1088/1742-5468/2013/09/p09006, https://arxiv.org/abs/1306.0263.

Salvador Elías Venegas-Andraca, 2012, Quantum walks: a comprehensive review, arXiv (Cornell University), 11, 5, pp. 1015-1106, 10.1007/s11128-012-0432-5, https://arxiv.org/abs/1201.4780.

A. Ahlbrecht;H. Vogts;A. H. Werner;R. F. Werner, 2011, Asymptotic evolution of quantum walks with random coin, arXiv (Cornell University), 52, 4, 10.1063/1.3575568, https://arxiv.org/abs/1009.2019.

Yuliy Baryshnikov;Robin Pemantle, 2011, Asymptotics of multivariate sequences, part III: Quadratic points, CiteSeer X (The Pennsylvania State University), 228, 6, pp. 3127-3206, 10.1016/j.aim.2011.08.004, http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.641.5749.

M. J. Cantero;L. Moral;F. Alberto Grünbaum;L. Velázquez, 2009, Matrix‐valued Szegő polynomials and quantum random walks, Communications on Pure and Applied Mathematics, 63, 4, pp. 464-507, 10.1002/cpa.20312.

Norie Konno, Lecture notes in mathematics, Quantum Walks, pp. 309-452, 2008, 10.1007/978-3-540-69365-9_7.

Sources : OpenCitations, OpenAlex & Crossref

Share and export

Consultation statistics

This page has been seen 239 times.

This article's PDF has been downloaded 392 times.