1. Decoherence induced by a chaotic environment: A quantum walker with a complex coin
Leonardo Ermann, Juan Pablo Paz, Marcos Saraceno
Phys. Rev. A 73, 012302 (2006).
http://arxiv.org/abs/quant-ph/0510037
We study the differences between the process of decoherence induced by chaotic and regular environments. For this we analyze a family of simple models wich contain both regular and chaotic environments. In all cases the system of interest is a "quantum walker", i.e. a quantum particle that can move on a lattice with a finite number of sites. The walker interacts with an environment wich has a D dimensional Hilbert space. The results we obtain suggest that regular and chaotic environments are not distinguishable from each other in a (short) timescale t*, wich scales with the dimensionality of the environment as t*~log(D). Howeber, chaotic environments continue to be effective over exponentially longer timescales while regular environments tend to reach saturation much sooner. We present both numerical and analytical results supporting this conclusion. The family of chaotic evolutions we consider includes the so-called quantum multi-baker-map as a particular case.
2. Quantum Walk with a time-dependent coin
M.C. Banuls, C. Navarrete, A. Perez, Eugenio Roldan, J.C. Soriano
http://arxiv.org/abs/quant-ph/0510046
We introduce quantum walks with a time-dependent coin, and show how they include, as a particular case, the generalized quantum walk recently studied by Wojcik et al. {[}Phys. Rev. Lett. \textbf{93}, 180601(2004){]} which exhibits interesting dynamical localization and quasiperiodic dynamics. Our proposal allows for a much easier implementation of this particular rich dynamics than the original one. Moreover, it allows for an additional control on the walk, which can be used to compensate for phases appearing due to external interactions. To illustrate its feasibility, we discuss an example using an optical cavity. We also derive an approximated solution in the continuous limit (long--wavelength approximation) which provides physical insight about the process.
3. Quantization and Asymptotic Behaviour of $��_{V^{k}}$ Quantum Random Walk on Integers
Demosthenes Ellinas, Ioannis Smyrnakis
http://arxiv.org/abs/quant-ph/0510098
Quantization and asymptotic behaviour of a variant of discrete random walk on integers are investigated. This variant, the $\epsilon_{V^{k}}$ walk, has the novel feature that it uses many identical quantum coins keeping at the same time characteristic quantum features like the quadratically faster than the classical spreading rate, and unexpected distribution cutoffs. A weak limit of the position probability distribution (pd) is obtained, and universal properties of this arch sine asymptotic distribution function are examined. Questions of driving the walk are investigated by means of a quantum optical interaction model that reveals robustness of quantum features of walker's asymptotic pd, against stimulated and spontaneous quantum noise on the coin system.
4. Asymptotics of Quantum Random Walk Driven by Optical Cavity
Demosthenes Ellinas, Ioannis Smyrnakis
Journal of Optics B: Quantum Semiclass. Opt. 7 (2005) S152 - S157
http://arxiv.org/abs/quant-ph/0510112
We investigate a novel quantum random walk (QRW) model, possibly useful in quantum algorithm implementation, that achieves a quadratically faster diffusion rate compared to its classical counterpart. We evaluate its asymptotic behavior expressed in the form of a limit probability distribution of a double horn shape. Questions of robustness and control of that limit distribution are addressed by introducing a quantum optical cavity in which a resonant Jaynes-Cummings type of interaction between the quantum walk coin system realized in the form of a two-level atom and a laser field is taking place. Driving the optical cavity by means of the coin-field interaction time and the initial quantum coin state, we determine two types of modification of the asymptotic behavior of the QRW. In the first one the limit distribution is robustly reproduced up to a scaling, while in the second one the quantum features of the walk, exemplified by enhanced diffusion rate, are washed out and Gaussian asymptotics prevail. Verification of these findings in an experimental setup that involves two quantum optical cavities that implement the driven QRW and its quantum to classical transition is discussed.
5. On Algebraic and Quantum Random Walks
Demosthenes Ellinas
http://arxiv.org/abs/quant-ph/0510128
Algebraic random walks (ARW) and quantum mechanical random walks (QRW) are investigated and related. Based on minimal data provided by the underlying bialgebras of functions defined on e. g the real line R, the abelian finite group Z_N, and the canonical Heisenberg-Weyl algebra hw, and by introducing appropriate functionals on those algebras, examples of ARWs are constructed. These walks involve short and long range transition probabilities as in the case of R walk, bistochastic matrices as for the case of Z_N walk, or coherent state vectors as in the case of hw walk. The increase of classical entropy due to majorization order of those ARWs is shown, and further their corresponding evolution equations are obtained. Especially for the case of hw ARW, the diffusion limit of evolution equation leads to a quantum master equation for the density matrix of a boson system interacting with a bath of quantum oscillators prepared in squeezed vacuum state. A number of generalizations to other types of ARWs and some open problems are also stated. Next, QRWs are briefly presented together with some of their distinctive properties, such as their enhanced diffusion rates, and their behavior in respect to the relation of majorization to quantum entropy. Finally, the relation of ARWs to QRWs is investigated in terms of the theorem of unitary extension of completely positive trace preserving (CPTP) evolution maps by means of auxiliary vector spaces. It is applied to extend the CPTP step evolution map of a ARW for a quantum walker system into a unitary step evolution map for an associated QRW of a walker+quantum coin system. Examples and extensions are provided.
6. Hitting time for quantum walks on the hypercube
Hari Krovi, Todd A. Brun
Phys. Rev. A 73, 032341 (2006)
http://arxiv.org/abs/quant-ph/0510136
Hitting times for discrete quantum walks on graphs give an average time before the walk reaches an ending condition. To be analogous to the hitting time for a classical walk, the quantum hitting time must involve repeated measurements as well as unitary evolution. We derive an expression for hitting time using superoperators, and numerically evaluate it for the discrete walk on the hypercube. The values found are compared to other analogues of hitting time suggested in earlier work. The dependence of hitting times on the type of unitary ``coin'' is examined, and we give an example of an initial state and coin which gives an infinite hitting time for a quantum walk. Such infinite hitting times require destructive interference, and are not observed classically. Finally, we look at distortions of the hypercube, and observe that a loss of symmetry in the hypercube increases the hitting time. Symmetry seems to play an important role in both dramatic speed-ups and slow-downs of quantum walks.
7. Investigation of Continuous-Time Quantum Walk Via Spectral Distribution Associated with Adjacency Matrix
M.A.Jafarizadeh, S. Salimi
http://arxiv.org/abs/quant-ph/0510174
Using the spectral distribution associated with the adjacency matrix of graphs, we introduce a new method of calculation of amplitudes of continuous-time quantum walk on some rather important graphs, such as line, cycle graph $C_n$, complete graph $K_n$, graph $G_n$, finite path and some other finite and infinite graphs, where all are connected with orthogonal polynomials such as Hermite, Laguerre, Tchebichef and some other orthogonal polynomials. It is shown that using the spectral distribution, one can obtain the infinite time asymptotic behavior of amplitudes simply by using the method of stationary phase approximation(WKB approximation), where as an example, the method is applied to star, two-dimensional comb lattices, infinite Hermite and Laguerre graphs. Also by using the Gauss quadrature formula one can approximate infinite graphs with finite ones and vice versa, in order to derive large time asymptotic behavior by WKB method. Likewise, using this method, some new graphs are introduced, where their amplitude are proportional to product of amplitudes of some elementary graphs, even though the graphs themselves are not the same as Cartesian product of their elementary graphs. Finally, via calculating mean end to end distance of some infinite graphs at large enough times, it is shown that continuous time quantum walk at different infinite graphs belong to different universality classes which are also different than those of the corresponding classical ones.
8. On the quantum hardness of solving isomorphism problems as nonabelian hidden shift problems
Andrew M. Childs, Pawel Wocjan
Quantum Information and Computation, Vol. 7, No. 5-6 (2007) 504-521
http://arxiv.org/abs/quant-ph/0510185
We consider an approach to deciding isomorphism of rigid n-vertex graphs (and related isomorphism problems) by solving a nonabelian hidden shift problem on a quantum computer using the standard method. Such an approach is arguably more natural than viewing the problem as a hidden subgroup problem. We prove that the hidden shift approach to rigid graph isomorphism is hard in two senses. First, we prove that Omega(n) copies of the hidden shift states are necessary to solve the problem (whereas O(n log n) copies are sufficient). Second, we prove that if one is restricted to single-register measurements, an exponential number of hidden shift states are required.
9. QMA/qpoly Is Contained In PSPACE/poly: De-Merlinizing Quantum Protocols
Scott Aaronson
http://arxiv.org/abs/quant-ph/0510230
This paper introduces a new technique for removing existential quantifiers over quantum states. Using this technique, we show that there is no way to pack an exponential number of bits into a polynomial-size quantum state, in such a way that the value of any one of those bits can later be proven with the help of a polynomial-size quantum witness. We also show that any problem in QMA with polynomial-size quantum advice, is also in PSPACE with polynomial-size classical advice. This builds on our earlier result that BQP/qpoly is contained in PP/poly, and offers an intriguing counterpoint to the recent discovery of Raz that QIP/qpoly = ALL. Finally, we show that QCMA/qpoly is contained in PP/poly and that QMA/rpoly = QMA/poly.