Universal quantum computation by discontinuous quantum walk
- 7 October 2010
- journal article
- research article
- Published by American Physical Society (APS) in Physical Review A
- Vol. 82 (4)
Abstract
Quantum walks are the quantum-mechanical analog of random walks, in which a quantum ``walker'' evolves between initial and final states by traversing the edges of a graph, either in discrete steps from node to node or via continuous evolution under the Hamiltonian furnished by the adjacency matrix of the graph. We present a hybrid scheme for universal quantum computation in which a quantum walker takes discrete steps of continuous evolution. This ``discontinuous'' quantum walk employs perfect quantum-state transfer between two nodes of specific subgraphs chosen to implement a universal gate set, thereby ensuring unitary evolution without requiring the introduction of an ancillary coin space. The run time is linear in the number of simulated qubits and gates. The scheme allows multiple runs of the algorithm to be executed almost simultaneously by starting walkers one time step apart.Keywords
All Related Versions
This publication has 16 references indexed in Scilit:
- Universal Computation by Quantum WalkPhysical Review Letters, 2009
- Quantum networks on cubelike graphsPhysical Review A, 2008
- Quantum communication through spin chain dynamics: an introductory overviewContemporary Physics, 2007
- Perfect Quantum State Transfer with Spinor Bosons on Weighted GraphsPhysical Review Letters, 2006
- Perfect transfer of arbitrary states in quantum spin networksPhysical Review A, 2005
- Perfect State Transfer in Quantum Spin NetworksPhysical Review Letters, 2004
- QUANTUM WALKS AND THEIR ALGORITHMIC APPLICATIONSInternational Journal of Quantum Information, 2003
- Quantum random walks: An introductory overviewContemporary Physics, 2003
- Quantum random-walk search algorithmPhysical Review A, 2003
- Quantum computation and decision treesPhysical Review A, 1998