dorsal/arxiv
View SchemaOptimal computation with non-unitary quantum walks
| Authors | Viv Kendon, Olivier Maloyer |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0610240 |
| URL | https://arxiv.org/abs/quant-ph/0610240 |
| DOI | 10.1016/j.tcs.2007.12.011 |
| Journal | Theoretical Computer Science 394(3) pp187-196 2008 |
Abstract
Quantum versions of random walks on the line and the cycle show a quadratic improvement over classical random walks in their spreading rates and mixing times respectively. Non-unitary quantum walks can provide a useful optimisation of these properties, producing a more uniform distribution on the line, and faster mixing times on the cycle. We investigate the interplay between quantum and random dynamics by comparing the resources required, and examining numerically how the level of quantum correlations varies during the walk. We show numerically that the optimal non-unitary quantum walk proceeds such that the quantum correlations are nearly all removed at the point of the final measurement. This requires only O(log T) random bits for a quantum walk of T steps
{
"annotation_id": "e681160f-97c0-4334-9fce-b146341ed5ea",
"date_created": "2026-03-02T18:02:30.559000Z",
"date_modified": "2026-03-02T18:02:30.559000Z",
"file_hash": "91c9cbcc0b14436646078c8d3982b4f9679a4211fe7d927afe33d78207ee5dad",
"private": false,
"record": {
"abstract": "Quantum versions of random walks on the line and the cycle show a quadratic\nimprovement over classical random walks in their spreading rates and mixing\ntimes respectively. Non-unitary quantum walks can provide a useful optimisation\nof these properties, producing a more uniform distribution on the line, and\nfaster mixing times on the cycle. We investigate the interplay between quantum\nand random dynamics by comparing the resources required, and examining\nnumerically how the level of quantum correlations varies during the walk. We\nshow numerically that the optimal non-unitary quantum walk proceeds such that\nthe quantum correlations are nearly all removed at the point of the final\nmeasurement. This requires only O(log T) random bits for a quantum walk of T\nsteps",
"arxiv_id": "quant-ph/0610240",
"authors": [
"Viv Kendon",
"Olivier Maloyer"
],
"categories": [
"quant-ph"
],
"doi": "10.1016/j.tcs.2007.12.011",
"journal_ref": "Theoretical Computer Science 394(3) pp187-196 2008",
"title": "Optimal computation with non-unitary quantum walks",
"url": "https://arxiv.org/abs/quant-ph/0610240"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "0ecc271f-e0b3-482d-8367-16cf44cbd149",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}