1. Quantum Walks with Non-Orthogonal Position States
R. Matjeschk, A. Ahlbrecht, M. Enderlein, Ch. Cedzich, A. H. Werner, M. Keyl, T. Schaetz, R. F. Werner
Phys. Rev. Lett. 109, 240503 (2012)
http://arxiv.org/abs/1206.0220
Quantum walks have by now been realized in a large variety of different physical settings. In some of these, particularly with trapped ions, the walk is implemented in phase space, where the corresponding position states are not orthogonal. We develop a general description of such a quantum walk and show how to map it into a standard one with orthogonal states, thereby making available all the tools developed for the latter. This enables a variety of experiments, which can be implemented with smaller step sizes and more steps. Tuning the non-orthogonality allows for an easy preparation of extended states such as momentum eigenstates, which travel at a well-defined speed with low dispersion. We introduce a method to adjust their velocity by momentum shifts, which allows to investigate intriguing effects such as the analog of Bloch oscillations.
2. How Low Can Approximate Degree and Quantum Query Complexity be for Total Boolean Functions?
Andris Ambainis, Ronald de Wolf
Proceedings of IEEE Conference on Computational Complexity (CCC’13), 2013
http://arxiv.org/abs/1206.0717
It has long been known that any Boolean function that depends on n input variables has both degree and exact quantum query complexity of Omega(log n), and that this bound is achieved for some functions. In this paper we study the case of approximate degree and bounded-error quantum query complexity. We show that for these measures the correct lower bound is Omega(log n / loglog n), and we exhibit quantum algorithms for two functions where this bound is achieved.
3. Continuous deformations of the Grover walk preserving localization
Martin Stefanak, Iva Bezdekova, Igor Jex
Eur. Phys. J. D 66 5 (2012) 142
http://arxiv.org/abs/1206.0881
The three-state Grover walk on a line exhibits the localization effect characterized by a non-vanishing probability of the particle to stay at the origin. We present two continuous deformations of the Grover walk which preserve its localization nature. The resulting quantum walks differ in the rate at which they spread through the lattice. The velocities of the left and right-traveling probability peaks are given by the maximum of the group velocity. We find the explicit form of peak velocities in dependence on the coin parameter. Our results show that localization of the quantum walk is not a singular property of an isolated coin operator but can be found for entire families of coins.
4. Non-interacting multi-particle quantum random walks applied to the graph isomorphism problem for strongly regular graphs
Kenneth Rudinger, John King Gamble, Mark Wellons, Eric Bach, Mark Friesen, Robert Joynt, S. N. Coppersmith
Phys. Rev. A 86, 022334 (2012)
http://arxiv.org/abs/1206.2999
We investigate the quantum dynamics of particles on graphs ("quantum random walks"), with the aim of developing quantum algorithms for determining if two graphs are isomorphic (related to each other by a relabeling of vertices). We focus on quantum random walks of multiple non-interacting particles on strongly regular graphs (SRGs), a class of graphs with high symmetry that is known to have pairs of graphs that are hard to distinguish. Previous work has already demonstrated analytically that two-particle non-interacting quantum walks cannot distinguish non-isomorphic SRGs of the same family. Here, we demonstrate numerically that three-particle non-interacting quantum walks have significant, but not universal, distinguishing power for pairs of SRGs, proving a fundamental difference between the distinguishing power of two-particle and three-particle non-interacting walks. We analytically show why this distinguishing power is possible, whereas it is forbidden for two-particle non-interacting walks. Based on sampling of SRGs with up to 64 vertices, we find no difference in the distinguishing power of bosonic and fermionic walks. In addition, we find that the four-fermion non-interacting walk has greater distinguishing power than the three-particle walks on SRGs, showing that increasing particle number increases distinguishing power. However, we also analytically show that no non-interacting walk with a fixed number of particles can distinguish all SRGs, thus demonstrating a potential fundamental difference between the distinguishing power of interacting and noninteracting walks.
5. Quantum Walks on Trees with Disorder: Decay, Diffusion, and Localization
Steven R. Jackson, Teng Jian Khoo, Frederick W. Strauch
http://arxiv.org/abs/1206.3178
Quantum walks have been shown to have impressive transport properties compared to classical random walks. However, imperfections in the quantum walk algorithm can destroy any quantum mechanical speed-up due to Anderson localization. We numerically study the effect of static disorder on a quantum walk on the glued trees graph. For small disorder, we find that the dominant effect is a type of quantum decay, and not quantum localization. For intermediate disorder, there is a crossover to diffusive transport, while a localization transition is observed at large disorder, in agreement with Anderson localization on the Cayley tree.
6. Fourier processing of quantum light
Eilon Poem, Yehonatan Gilead, Yoav Lahini, Yaron Silberberg
Phys. Rev. A 86, 023836 (2012)
http://arxiv.org/abs/1206.4204
It is shown that a classical optical Fourier processor can be used for the shaping of quantum correlations between two or more photons, and the class of Fourier masks applicable in the multiphoton Fourier space is identified. This concept is experimentally demonstrated using two types of periodic phase masks illuminated with path-entangled photon pairs, a highly non-classical state of light. Applied first were sinusoidal phase masks, emulating two-particle quantum walk on a periodic lattice, yielding intricate correlation patterns with various spatial bunching and anti-bunching effects depending on the initial state. Then, a periodic Zernike-like filter was applied on top of the sinusoidal phase masks. Using this filter, phase information lost in the original correlation measurements was retrieved.
7. Localization of the Grover walks on spidernets and free Meixner laws
Norio Konno, Nobuaki Obata, Etsuo Segawa
Communications in Mathematical Physics, 322 (2013) 667-695
http://arxiv.org/abs/1206.4422
A spidernet is a graph obtained by adding large cycles to an almost regular tree and considered as an example having intermediate properties of lattices and trees in the study of discrete-time quantum walks on graphs. We introduce the Grover walk on a spidernet and its one-dimensional reduction. We derive an integral representation of the $n$-step transition amplitude in terms of the free Meixner law which appears as the spectral distribution. As an application we determine the class of spidernets which exhibit localization. Our method is based on quantum probabilistic spectral analysis of graphs.
8. A framework for bounding nonlocality of state discrimination
Andrew M. Childs, Debbie Leung, Laura Mancinska, Maris Ozols
Communications in Mathematical Physics 323, 1121-1153 (2013)
http://arxiv.org/abs/1206.5822
We consider the class of protocols that can be implemented by local quantum operations and classical communication (LOCC) between two parties. In particular, we focus on the task of discriminating a known set of quantum states by LOCC. Building on the work in the paper "Quantum nonlocality without entanglement" [BDF+99], we provide a framework for bounding the amount of nonlocality in a given set of bipartite quantum states in terms of a lower bound on the probability of error in any LOCC discrimination protocol. We apply our framework to an orthonormal product basis known as the domino states and obtain an alternative and simplified proof that quantifies its nonlocality. We generalize this result for similar bases in larger dimensions, as well as the "rotated" domino states, resolving a long-standing open question [BDF+99].
9. Non-equilibrium transition from dissipative quantum walk to classical random walk
Marco Nizama, Manuel O. C��ceres
http://arxiv.org/abs/1206.6061
We have investigated the time-evolution of a free particle in interaction with a phonon thermal bath, using the tight-binding approach. A dissipative quantum walk can be defined and many important non-equilibrium decoherence properties can be investigated analytically. The non-equilibrium statistics of a pure initial state have been studied. Our theoretical results indicate that the evolving wave-packet shows the suppression of Anderson's boundaries (ballistic peaks) by the presence of dissipation. Many important relaxation properties can be studied quantitatively, such as von Neumann's entropy and quantum purity. In addition, we have studied Wigner's function. The time-dependent behavior of the quantum entanglement between a free particle -in the lattice- and the phonon bath has been characterized analytically. This result strongly suggests the non-trivial time-dependence of the off-diagonal elements of the reduced density matrix of the system. We have established a connection between the quantum decoherence and the dissipative parameter arising from interaction with the phonon bath. The time-dependent behavior of quantum correlations has also been pointed out, showing continuous transition from quantum random walk to classical random walk, when dissipation increases.
10. Quantum walks as a probe of structural anomalies in graphs
Mark Hillery, Hongjun Zheng, Edgar Feldman, Daniel Reitzner, Vladimir Buzek
Physical Review A 85, 062325 (2012)
http://arxiv.org/abs/1206.6298
We study how quantum walks can be used to find structural anomalies in graphs via several examples. Two of our examples are based on star graphs, graphs with a single central vertex to which the other vertices, which we call external vertices, are connected by edges. In the basic star graph, these are the only edges. If we now connect a subset of the external vertices to form a complete subgraph, a quantum walk can be used to find these vertices with a quantum speedup. Thus, under some circumstances, a quantum walk can be used to locate where the connectivity of a network changes. We also look at the case of two stars connected at one of their external vertices. A quantum walk can find the vertex shared by both graphs, again with a quantum speedup. This provides an example of using a quantum walk in order to find where two networks are connected. Finally, we use a quantum walk on a complete bipartite graph to find an extra edge that destroys the bipartite nature of the graph.