1. Universal quantum walks and adiabatic algorithms by 1D Hamiltonians
Bradley A. Chase, Andrew J. Landahl
http://arxiv.org/abs/0802.1207
We construct a family of time-independent nearest-neighbor Hamiltonians coupling eight-state systems on a 1D ring that enables universal quantum computation. Hamiltonians in this family can achieve universality either by driving a continuous-time quantum walk or by terminating an adiabatic algorithm. In either case, the universality property can be understood as arising from an efficient simulation of a programmable quantum circuit. Using gadget perturbation theory, one can demonstrate the same kind of universality for related Hamiltonian families acting on qubits in 2D. Our results demonstrate that simulating 1D chains of spin-7/2 particles is BQP-hard, and indeed BQP-complete because the outputs of decision problems can be encoded in the outputs of such simulations.
2. Random Quantum Circuits are Approximate 2-designs
Aram W. Harrow, Richard A. Low
Comm. Math. Phys. Vol. 291, No. 1, pp. 257–302 (2009)
http://arxiv.org/abs/0802.1919
Given a universal gate set on two qubits, it is well known that applying random gates from the set to random pairs of qubits will eventually yield an approximately Haar-distributed unitary. However, this requires exponential time. We show that random circuits of only polynomial length will approximate the first and second moments of the Haar distribution, thus forming approximate 1- and 2-designs. Previous constructions required longer circuits and worked only for specific gate sets. As a corollary of our main result, we also improve previous bounds on the convergence rate of random walks on the Clifford group.
3. Large Qudit Limit of One-dimensional Quantum Walks
Mitsunori Sato, Naoki Kobayashi, Makoto Katori, Norio Konno
http://arxiv.org/abs/0802.1997
We study a series of one-dimensional discrete-time quantum-walk models labeled by half integers $j=1/2, 1, 3/2, ...$, introduced by Miyazaki {\it et al.}, each of which the walker's wave function has $2j+1$ components and hopping range at each time step is $2j$. In long-time limit the density functions of pseudovelocity-distributions are generally given by superposition of appropriately scaled Konno's density function. Since Konno's density function has a finite open support and it diverges at the boundaries of support, limit distribution of pseudovelocities in the $(2j+1)$-component model can have $2j+1$ pikes, when $2j+1$ is even. When $j$ becomes very large, however, we found that these pikes vanish and a universal and monotone convex structure appears around the origin in limit distributions. We discuss a possible route from quantum walks to classical diffusion associated with the $j \to \infty$ limit.
4. The Fibonacci quantum walk and its cassical trace map
Alejandro Romanelli
http://arxiv.org/abs/0802.2289
We study the quantum walk in momentum space using a coin arranged in quasi-periodic sequences following a Fibonacci prescription. We build for this system a classical map based on the trace of the evolution operator. The sub-ballistic behavior of this quantum walk is connected with the power-law decay of the time correlations of the trace map.
5. Limit distributions of two-dimensional quantum walks
Kyohei Watabe, Naoki Kobayashi, Makoto Katori, Norio Konno
Phys. Rev. A77 (2008) 062331/1-9
http://arxiv.org/abs/0802.2749
One-parameter family of discrete-time quantum-walk models on the square lattice, which includes the Grover-walk model as a special case, is analytically studied. Convergence in the long-time limit $t \to \infty$ of all joint moments of two components of walker's pseudovelocity, $X_t/t$ and $Y_t/t$, is proved and the probability density of limit distribution is derived. Dependence of the two-dimensional limit density function on the parameter of quantum coin and initial four-component qudit of quantum walker is determined. Symmetry of limit distribution on a plane and localization around the origin are completely controlled. Comparison with numerical results of direct computer-simulations is also shown.
6. Quantum walks on circles in phase space via superconducting circuit quantum electrodynamics
Peng Xue, Barry C. Sanders, Alexandre Blais, Kevin Lalumiere
Physical Review A 78, 042334 (2008)
http://arxiv.org/abs/0802.2750
We show how a quantum walk can be implemented for the first time in a quantum quincunx created via superconducting circuit quantum electrodynamics (QED), and how interpolation from quantum to random walk is implemented by controllable decoherence using a two resonator system. Direct control over the coin qubit is difficult to achieve in either cavity or circuit QED, but we show that a Hadamard coin flip can be effected via direct driving of the cavity, with the result that the walker jumps between circles in phase space but still exhibits quantum walk behavior over 15 steps.
7. Dynamical kickback and non commuting impurities in a spin chain
Diego de Falco, Dario Tamascelli
http://arxiv.org/abs/0802.3567
In an interacting continuous time quantum walk, while the walker (the cursor) is moving on a graph, computational primitives (unitary operators associated with the edges) are applied to ancillary qubits (the register). The model with one walker was originally proposed by R. Feynman, who thus anticipated many features of the Continuous Time Quantum Walk (CTWQ) computing paradigm. In this note we examine the behaviour of an interacting CTQW with two walkers and examine the interaction of the walkers with noncommuting primitives. We endow such a walk with a notion of trajectory, in the sense of sample path of an associated Markov process, in order to use such notions as sojourn time and first passage time as heuristic tools for gaining intuition about its behaviour.
8. Quantum walk on circles in phase space
Peng Xue, Barry C. Sanders
New Journal of Physics 10, 053025 (2008)
http://arxiv.org/abs/0802.3749
We propose a variation of the quantum walk on a circle in phase space by conjoining the Hadamard coin flip with simultaneous displacement of the walker's location in phase space and show that this generalization is a proper quantum walk albeit over multiple concentric circles in phase instead of just over one circle. We motivate the conjoining of Hadamard and displacement operations by showing that the Jaynes-Cummings model for coin+walker approximately yields this description in the dispersive limit. The quantum walk signature is evident in the phase distribution of the walker provided that appropriate pulse durations are applied for each coin flip.