1. Quantum Computing and Hidden Variables I: Mapping Unitary to Stochastic Matrices
Scott Aaronson
http://arxiv.org/abs/quant-ph/0408035
This paper initiates the study of hidden variables from the discrete, abstract perspective of quantum computing. For us, a hidden-variable theory is simply a way to convert a unitary matrix that maps one quantum state to another, into a stochastic matrix that maps the initial probability distribution to the final one in some fixed basis. We list seven axioms that we might want such a theory to satisfy, and then investigate which of the axioms can be satisfied simultaneously. Toward this end, we construct a new hidden-variable theory that is both robust to small perturbations and indifferent to the identity operation, by exploiting an unexpected connection between unitary matrices and network flows. We also analyze previous hidden-variable theories of Dieks and Schrodinger in terms of our axioms. In a companion paper, we will show that actually sampling the history of a hidden variable under reasonable axioms is at least as hard as solving the Graph Isomorphism problem; and indeed is probably intractable even for quantum computers.
2. Relation between coined quantum walks and quantum cellular automata
Masatoshi Hamada, Norio Konno, Etsuo Segawa
RIMS Kokyuroku, No.1422, pp.1-11 (2005)
http://arxiv.org/abs/quant-ph/0408100
Motivated by the recent work of Patel et al., this paper clarifies a connection between coined quantum walks and quantum cellular automata in a general setting. As a consequence, their result is naturally derived from the connection.
3. Quantum Computing and Hidden Variables II: The Complexity of Sampling Histories
Scott Aaronson
http://arxiv.org/abs/quant-ph/0408119
This paper shows that, if we could examine the entire history of a hidden variable, then we could efficiently solve problems that are believed to be intractable even for quantum computers. In particular, under any hidden-variable theory satisfying a reasonable axiom called "indifference to the identity," we could solve the Graph Isomorphism and Approximate Shortest Vector problems in polynomial time, as well as an oracle problem that is known to require quantum exponential time. We could also search an N-item database using O(N^{1/3}) queries, as opposed to O(N^{1/2}) queries with Grover's search algorithm. On the other hand, the N^{1/3} bound is optimal, meaning that we could probably not solve NP-complete problems in polynomial time. We thus obtain the first good example of a model of computation that appears slightly more powerful than the quantum computing model.
4. Limit Theorem for Continuous-Time Quantum Walk on the Line
Norio Konno
Physical Review E, Vol.72, 026113 (2005)
http://arxiv.org/abs/quant-ph/0408140
Concerning a discrete-time quantum walk X^{(d)}_t with a symmetric distribution on the line, whose evolution is described by the Hadamard transformation, it was proved by the author that the following weak limit theorem holds: X^{(d)}_t /t \to dx / \pi (1-x^2) \sqrt{1 - 2 x^2} as t \to \infty. The present paper shows that a similar type of weak limit theorems is satisfied for a {\it continuous-time} quantum walk X^{(c)}_t on the line as follows: X^{(c)}_t /t \to dx / \pi \sqrt{1 - x^2} as t \to \infty. These results for quantum walks form a striking contrast to the central limit theorem for symmetric discrete- and continuous-time classical random walks: Y_{t}/ \sqrt{t} \to e^{-x^2/2} dx / \sqrt{2 \pi} as t \to \infty. The work deals also with issue of the relationship between discrete and continuous-time quantum walks. This topic, subject of a long debate in the previous literature, is treated within the formalism of matrix representation and the limit distributions are exhaustively compared in the two cases.
5. Generalized Quantum Walk in Momentum Space
A. Romanelli, A. Auyuanet, R. Siri, G. Abal, R. Donangelo
http://arxiv.org/abs/quant-ph/0408183
We consider a new model of quantum walk on a one-dimensional momentum space that includes both discrete jumps and continuous drift. Its time evolution has two stages; a Markov diffusion followed by localized dynamics. As in the well known quantum kicked rotor, this model can be mapped into a localized one-dimensional Anderson model. For exceptional (rational) values of its scale parameter, the system exhibits resonant behavior and reduce to the usual discrete time quantum walk on the line.