1. Graph identification by quantum walks
J.B. Wang, B.L. Douglas
http://arxiv.org/abs/quant-ph/0701033
This paper has been withdrawn by the authors; replaced by arXiv:0705.2531v2 [quant-ph].
2. Localization of coherent exciton transport in phase space
Oliver Muelken, Veronika Bierbaum, Alexander Blumen
Phys. Rev. E 75, 031121 (2007)
http://arxiv.org/abs/quant-ph/0701034
We study numerically the dynamics of excitons on discrete rings in the presence of static disorder. Based on continuous-time quantum walks we compute the time evolution of the Wigner function (WF) both for pure diagonal (site) disorder, as well as for diagonal and off-diagonal (site and transfer) disorder. In both cases, large disorder leads to localization and destroys the characteristic phase space patterns of the WF found in the absence of disorder.
3. Quantum Walks, Quantum Gates and Quantum Computers
Andrew P. Hines, P.C.E. Stamp
http://arxiv.org/abs/quant-ph/0701088
The physics of quantum walks on graphs is formulated in Hamiltonian language, both for simple quantum walks and for composite walks, where extra discrete degrees of freedom live at each node of the graph. It is shown how to map between quantum walk Hamiltonians and Hamiltonians for qubit systems and quantum circuits; this is done for both a single- and multi-excitation coding, and for more general mappings. Specific examples of spin chains, as well as static and dynamic systems of qubits, are mapped to quantum walks, and walks on hyperlattices and hypercubes are mapped to various gate systems. We also show how to map a quantum circuit performing the quantum Fourier transform, the key element of Shor's algorithm, to a quantum walk system doing the same. The results herein are an essential preliminary to a Hamiltonian formulation of quantum walks in which coupling to a dynamic quantum environment is included.
4. Quantum t-designs: t-wise independence in the quantum world
Andris Ambainis, Joseph Emerson
http://arxiv.org/abs/quant-ph/0701126
A t-design for quantum states is a finite set of quantum states with the property of simulating the Haar-measure on quantum states, w.r.t. any test that uses at most t copies of a state. We give efficient constructions for approximate quantum t-designs for arbitrary t. We then show that an approximate 4-design provides a derandomization of the state-distinction problem considered by Sen (quant-ph/0512085), which is relevant to solving certain instances of the hidden subgroup problem.
5. Quantum walks on quotient graphs
Hari Krovi, Todd A. Brun
Physical Review A 75, 062332 (2007)
http://arxiv.org/abs/quant-ph/0701173
A discrete-time quantum walk on a graph is the repeated application of a unitary evolution operator to a Hilbert space corresponding to the graph. If this unitary evolution operator has an associated group of symmetries, then for certain initial states the walk will be confined to a subspace of the original Hilbert space. Symmetries of the original graph, given by its automorphism group, can be inherited by the evolution operator. We show that a quantum walk confined to the subspace corresponding to this symmetry group can be seen as a different quantum walk on a smaller quotient graph. We give an explicit construction of the quotient graph for any subgroup of the automorphism group and illustrate it with examples. The automorphisms of the quotient graph which are inherited from the original graph are the original automorphism group modulo the subgroup used to construct it. We then analyze the behavior of hitting times on quotient graphs. Hitting time is the average time it takes a walk to reach a given final vertex from a given initial vertex. It has been shown in earlier work [Phys. Rev. A {\bf 74}, 042334 (2006)] that the hitting time can be infinite. We give a condition which determines whether the quotient graph has infinite hitting times given that they exist in the original graph. We apply this condition for the examples discussed and determine which quotient graphs have infinite hitting times. All known examples of quantum walks with fast hitting times correspond to systems with quotient graphs much smaller than the original graph; we conjecture that the existence of a small quotient graph with finite hitting times is necessary for a walk to exhibit a quantum speed-up.