Quantum random walks in one dimension via generating functions
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 classic...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Discrete Mathematics & Theoretical Computer Science
2007-01-01
|
| Series: | Discrete Mathematics & Theoretical Computer Science |
| Subjects: | |
| Online Access: | https://dmtcs.episciences.org/3533/pdf |
| _version_ | 1827324060816637952 |
|---|---|
| author | Andrew Bressler Robin Pemantle |
| author_facet | Andrew Bressler Robin Pemantle |
| author_sort | Andrew Bressler |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-04-25T02:03:49Z |
| format | Article |
| id | doaj.art-3f0571442ad446faab25078c34296ab0 |
| institution | Directory Open Access Journal |
| issn | 1365-8050 |
| language | English |
| last_indexed | 2024-04-25T02:03:49Z |
| publishDate | 2007-01-01 |
| publisher | Discrete Mathematics & Theoretical Computer Science |
| record_format | Article |
| series | Discrete Mathematics & Theoretical Computer Science |
| spelling | doaj.art-3f0571442ad446faab25078c34296ab02024-03-07T14:34:52ZengDiscrete Mathematics & Theoretical Computer ScienceDiscrete Mathematics & Theoretical Computer Science1365-80502007-01-01DMTCS Proceedings vol. AH,...Proceedings10.46298/dmtcs.35333533Quantum random walks in one dimension via generating functionsAndrew Bressler0Robin Pemantle1Department of Mathematics [Philadelphia]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://dmtcs.episciences.org/3533/pdfhadamardasymptoticsrational 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] |
| spellingShingle | Andrew Bressler Robin Pemantle Quantum random walks in one dimension via generating functions Discrete Mathematics & Theoretical Computer Science 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] |
| title | Quantum random walks in one dimension via generating functions |
| title_full | Quantum random walks in one dimension via generating functions |
| title_fullStr | Quantum random walks in one dimension via generating functions |
| title_full_unstemmed | Quantum random walks in one dimension via generating functions |
| title_short | Quantum random walks in one dimension via generating functions |
| title_sort | quantum random walks in one dimension via generating functions |
| topic | 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] |
| url | https://dmtcs.episciences.org/3533/pdf |
| work_keys_str_mv | AT andrewbressler quantumrandomwalksinonedimensionviageneratingfunctions AT robinpemantle quantumrandomwalksinonedimensionviageneratingfunctions |