1. Random tensor theory: extending random matrix theory to random product states
Andris Ambainis, Aram W. Harrow, Matthew B. Hastings
Commun. Math. Phys., vol. 310, no. 1, pp. 25-74 (2012)
http://arxiv.org/abs/0910.0472
We consider a problem in random matrix theory that is inspired by quantum information theory: determining the largest eigenvalue of a sum of p random product states in (C^d)^{otimes k}, where k and p/d^k are fixed while d grows. When k=1, the Marcenko-Pastur law determines (up to small corrections) not only the largest eigenvalue ((1+sqrt{p/d^k})^2) but the smallest eigenvalue (min(0,1-sqrt{p/d^k})^2) and the spectral density in between. We use the method of moments to show that for k>1 the largest eigenvalue is still approximately (1+sqrt{p/d^k})^2 and the spectral density approaches that of the Marcenko-Pastur law, generalizing the random matrix theory result to the random tensor case. Our bound on the largest eigenvalue has implications both for sampling from a particular heavy-tailed distribution and for a recently proposed quantum data-hiding and correlation-locking scheme due to Leung and Winter. Since the matrices we consider have neither independent entries nor unitary invariance, we need to develop new techniques for their analysis. The main contribution of this paper is to give three different methods for analyzing mixtures of random product states: a diagrammatic approach based on Gaussian integrals, a combinatorial method that looks at the cycle decompositions of permutations and a recursive method that uses a variant of the Schwinger-Dyson equations.
2. Universal quantum computation using the discrete time quantum walk
Neil B. Lovett, Sally Cooper, Matthew Everitt, Matthew Trevers, Viv Kendon
Phys. Rev. A. 81, 042330 (2010)
http://arxiv.org/abs/0910.1024
A proof that continuous time quantum walks are universal for quantum computation, using unweighted graphs of low degree, has recently been presented by Childs [PRL 102 180501 (2009)]. We present a version based instead on the discrete time quantum walk. We show the discrete time quantum walk is able to implement the same universal gate set and thus both discrete and continuous time quantum walks are computational primitives. Additionally we give a set of components on which the discrete time quantum walk provides perfect state transfer.
3. Limits of quantum speedup in photosynthetic light harvesting
Stephan Hoyer, Mohan Sarovar, K. Birgitta Whaley
New J. Phys. 12, 065041 (2010)
http://arxiv.org/abs/0910.1847
It has been suggested that excitation transport in photosynthetic light harvesting complexes features speedups analogous to those found in quantum algorithms. Here we compare the dynamics in these light harvesting systems to the dynamics of quantum walks, in order to elucidate the limits of such quantum speedups. For the Fenna-Matthews-Olson (FMO) complex of green sulfur bacteria, we show that while there is indeed speedup at short times, this is short lived (70 fs) despite longer lived (ps) quantum coherence. Remarkably, this time scale is independent of the details of the decoherence model. More generally, we show that the distinguishing features of light-harvesting complexes not only limit the extent of quantum speedup but also reduce rates of diffusive transport. These results suggest that quantum coherent effects in biological systems are optimized for efficiency or robustness rather than the more elusive goal of quantum speedup.
4. Decoherence in one-dimensional Quantum Walk
Mostafa Annabestani, Seyed Javad Akhtarshenas, Mohamad Reza Abolhassani
Phys. Rev. A 81, 032321 (2010)
http://arxiv.org/abs/0910.1986
In this paper we study decoherence in the quantum walk on the line. We generalize the method of decoherent coin quantum walk, introduced by Brun et al [Phys. Rev. A {\bf 67}, 32304 (2003)]. Our analytical expressions are applicable for all kinds of decoherence. As an example of the coin-position decoherence, we study the broken line quantum walk and compare our results with the numerical one. We also show that our analytical results reduce to the Brun formalism when only the coin is subjected to decoherence.
5. Photons Walking the Line: A quantum walk with adjustable coin operations
A. Schreiber, K. N. Cassemiro, V. Potocek, A. Gabris, P.J. Mosley, E. Andersson, I. Jex, Ch. Silberhorn
Phys. Rev. Lett. 104, 050502 (2010)
http://arxiv.org/abs/0910.2197
We present the first robust implementation of a coined quantum walk over five steps using only passive optical elements. By employing a fiber network loop we keep the amount of required resources constant as the walker's position Hilbert space is increased. We observed a non-Gaussian distribution of the walker's final position, thus characterizing a faster spread of the photon wave-packet in comparison to the classical random walk. The walk is realized for many different coin settings and initial states, which opens the way for the implementation of a quantum walk-based search algorithm.
6. Interacting quantum walks
Dario Tamascelli
http://arxiv.org/abs/0910.2871
In this work we present the quantum mechanical computer proposed by Feynman in 1985 and, since then, widely cited but seldom used. The main feature of the model is the presence of a built in clocking mechanism managing for the ordered application of the computational primitives to the input/output register.
7. Anyonic Quantum Walks
Gavin K. Brennen, Demosthenes Ellinas, Viv Kendon, Jiannis K. Pachos, Ioannis Tsohantjis, Zhenghan Wang
Annals of Physics (2009)
http://arxiv.org/abs/0910.2974
The one dimensional quantum walk of anyonic systems is presented. The anyonic walker performs braiding operations with stationary anyons of the same type ordered canonically on the line of the walk. Abelian as well as non-Abelian anyons are studied and it is shown that they have very different properties. Abelian anyonic walks demonstrate the expected quadratic quantum speedup. Non-Abelian anyonic walks are much more subtle. The exponential increase of the system's Hilbert space and the particular statistical evolution of non-Abelian anyons give a variety of new behaviors. The position distribution of the walker is related to Jones polynomials, topological invariants of the links created by the anyonic world-lines during the walk. Several examples such as the SU(2) level k and the quantum double models are considered that provide insight to the rich diffusion properties of anyons.
8. Index theory of one dimensional quantum walks and cellular automata
D. Gross, V. Nesme, H. Vogts, R.F. Werner
Commun. Math. Phys. 310, 419-454 (2012)
http://arxiv.org/abs/0910.3675
If a one-dimensional quantum lattice system is subject to one step of a reversible discrete-time dynamics, it is intuitive that as much "quantum information" as moves into any given block of cells from the left, has to exit that block to the right. For two types of such systems - namely quantum walks and cellular automata - we make this intuition precise by defining an index, a quantity that measures the "net flow of quantum information" through the system. The index supplies a complete characterization of two properties of the discrete dynamics. First, two systems S_1, S_2 can be pieced together, in the sense that there is a system S which locally acts like S_1 in one region and like S_2 in some other region, if and only if S_1 and S_2 have the same index. Second, the index labels connected components of such systems: equality of the index is necessary and sufficient for the existence of a continuous deformation of S_1 into S_2. In the case of quantum walks, the index is integer-valued, whereas for cellular automata, it takes values in the group of positive rationals. In both cases, the map S -> ind S is a group homomorphism if composition of the discrete dynamics is taken as the group law of the quantum systems. Systems with trivial index are precisely those which can be realized by partitioned unitaries, and the prototypes of systems with non-trivial index are shifts.
9. Black-box Hamiltonian simulation and unitary implementation
Dominic W. Berry, Andrew M. Childs
Quantum Information and Computation 12, 29 (2012)
http://arxiv.org/abs/0910.4157
We present general methods for simulating black-box Hamiltonians using quantum walks. These techniques have two main applications: simulating sparse Hamiltonians and implementing black-box unitary operations. In particular, we give the best known simulation of sparse Hamiltonians with constant precision. Our method has complexity linear in both the sparseness D (the maximum number of nonzero elements in a column) and the evolution time t, whereas previous methods had complexity scaling as D^4 and were superlinear in t. We also consider the task of implementing an arbitrary unitary operation given a black-box description of its matrix elements. Whereas standard methods for performing an explicitly specified N x N unitary operation use O(N^2) elementary gates, we show that a black-box unitary can be performed with bounded error using O(N^{2/3} (log log N)^{4/3}) queries to its matrix elements. In fact, except for pathological cases, it appears that most unitaries can be performed with only O(sqrt{N}) queries, which is optimal.
10. BQP and the Polynomial Hierarchy
Scott Aaronson
http://arxiv.org/abs/0910.4698
The relationship between BQP and PH has been an open problem since the earliest days of quantum computing. We present evidence that quantum computers can solve problems outside the entire polynomial hierarchy, by relating this question to topics in circuit complexity, pseudorandomness, and Fourier analysis. First, we show that there exists an oracle relation problem (i.e., a problem with many valid outputs) that is solvable in BQP, but not in PH. This also yields a non-oracle relation problem that is solvable in quantum logarithmic time, but not in AC0. Second, we show that an oracle decision problem separating BQP from PH would follow from the Generalized Linial-Nisan Conjecture, which we formulate here and which is likely of independent interest. The original Linial-Nisan Conjecture (about pseudorandomness against constant-depth circuits) was recently proved by Braverman, after being open for twenty years.
11. Dirac equation with ultraviolet cutoff and quantum walk
Fumihito Sato, Makoto Katori
Phys. Rev. A81 (2010) 012314/1-10
http://arxiv.org/abs/0910.4811
The weak convergence theorems of the one- and two-dimensional simple quantum walks, SQW$^{(d)}, d=1,2$, show a striking contrast to the classical counterparts, the simple random walks, SRW$^{(d)}$. The limit distributions have novel structures such that they are inverted-bell shaped and the supports of them are bounded. In the present paper we claim that these properties of the SQW$^{(d)}$ can be explained by the theory of relativistic quantum mechanics. We show that the Dirac equation with a proper ultraviolet cutoff can provide a quantum walk model in three dimensions, where the walker has a four-component qubit. We clarify that the pseudovelocity $\V(t)$ of the quantum walker, which solves the Dirac equation, is identified with the relativistic velocity. Since the quantum walker should be a tardyon, not a tachyon, $|\V(t)| < c$, where $c$ is the speed of light, and this restriction (the causality) is the origin of the finiteness of supports of the limit distributions universally found in quantum walk models. By reducing the number of components of momentum in the Dirac equation, we obtain the limit distributions of pseudovelocities for the lower dimensional quantum walks. We show that the obtained limit distributions for the one- and two-dimensional systems have the common features with those of SQW$^{(1)}$ and SQW$^{(2)}$.
12. Control by quantum dynamics on graphs
Chris Godsil, Simone Severini
Phys. Rev. A 81, 052316 (2010)
http://arxiv.org/abs/0910.5397
We address the study of controllability of a closed quantum system whose dynamical Lie algebra is generated by adjacency matrices of graphs. We characterize a large family of graphs that renders a system controllable. The key property is a novel graph-theoretic feature consisting of a particularly disordered cycle structure. Disregarding efficiency of control functions, but choosing subfamilies of sparse graphs, the results translate into continuous-time quantum walks for universal computation.
13. The effect of large-decoherence on mixing-time in Continuous-time quantum walks on long-range interacting cycles
S. Salimi, R. Radgohar
J. Phys. B: At. Mol. Opt. Phys. 43 (2010) 025503.
http://arxiv.org/abs/0910.5795
In this paper, we consider decoherence in continuous-time quantum walks on long-range interacting cycles (LRICs), which are the extensions of the cycle graphs. For this purpose, we use Gurvitz's model and assume that every node is monitored by the corresponding point contact induced the decoherence process. Then, we focus on large rates of decoherence and calculate the probability distribution analytically and obtain the lower and upper bounds of the mixing time. Our results prove that the mixing time is proportional to the rate of decoherence and the inverse of the distance parameter ($\emph{m}$) squared. This shows that the mixing time decreases with increasing the range of interaction. Also, what we obtain for $\emph{m}=0$ is in agreement with Fedichkin, Solenov and Tamon's results \cite{FST} for cycle, and see that the mixing time of CTQWs on cycle improves with adding interacting edges.