Optimal computation with non-unitary quantum walks
arXiv:quant-ph/0610240 · doi:10.1016/j.tcs.2007.12.011
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
16 pages, 3 eps figures, ELsevier style; v2 clarification added to start of Sec. 4, typos fixed & refs updated; v3 error fixed in qubit counts on p. 9, refs updated, to appear (in 2008) in TCS-A postproceedings volume of CiE 2006
References in corpus (24)
- Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
- Separability Criterion for Density Matrices
- A computable measure of entanglement
- Quantum Mechanics helps in searching for a needle in a haystack
- Separability of Mixed States: Necessary and Sufficient Conditions
- On the volume of the set of mixed entangled states
- Quantum Computation and Decision Trees
- Mixed-state entanglement and distillation: is there a ``bound'' entanglement in nature?
- A Quantum Random Walk Search Algorithm
- A Theory of Fault-Tolerant Quantum Computation
- Exponential algorithmic speedup by quantum walk
- Controlling discrete quantum walks: coins and intitial states
- Quantum walks in higher dimensions
- On the volume of the set of mixed entangled states II
- Decoherence in quantum walks - a review
- Decoherence can be useful in quantum walks
- Quantum random walks with decoherent coins
- Entanglement in coined quantum walks on regular graphs
- An introduction to measurement based quantum computation
- Quantum walks with infinite hitting times
- Quantum speedup of classical mixing processes
- Decoherence vs entanglement in coined quantum walks
- Complementarity and quantum walks
- Almost uniform sampling via quantum walks
Cited by in corpus (9)
- Almost uniform sampling via quantum walks
- Quantum search with hybrid adiabatic-quantum walk algorithms and realistic noise
- On Grover's Search Algorithm from a Quantum Information Geometry Viewpoint
- The Efficient Preparation of Normal Distributions in Quantum Registers
- Asymptotic entanglement in 1D quantum walks with a time-dependent coined
- Finite-element assembly approach of optical quantum walk networks
- Environment-induced mixing processes in quantum walks
- Tunable Tradeoff between Quantum and Classical Computation via Nonunitary Zeno-like Dynamics
- Next-generation interferometry with gauge-invariant linear optical scatterers