1. Properties of Open Quantum Walks on $\mathbb{Z}$
I. Sinayskiy, F. Petruccione
Phys. Scr. T151 014077 (2012)
http://arxiv.org/abs/1402.1468
A connection between the asymptotic behavior of the open quantum walk and the spectrum of a generalized quantum coins is studied. For the case of simultaneously diagonalizable transition operators an exact expression for probability distribution of the position of the walker for arbitrary number of steps is found. For a large number of steps the probability distribution consist of maximally two "soliton"-like solution and a certain number of Gaussian distributions. The number of different contributions to the final probability distribution is equal to the number of distinct absolute values in the spectrum of the transition operators. The presence of the zeros in spectrum is an indicator of the "soliton"-like solutions in the probability distribution.
2. Path integral Monte Carlo on a lattice: extended states
Mark O’Callaghan, Bruce N. Miller
http://arxiv.org/abs/1402.1820
The equilibrium properties of a single quantum particle (qp) interacting with a classical gas for a wide range of temperatures that explore the system's behavior in the classical as well as in the quantum regime is investigated. Both the quantum particle and atoms are restricted to the sites of a one-dimensional lattice. A path-integral formalism is developed within the context of the canonical ensemble in which the quantum particle is represented by a closed, variable-step random walk on the lattice. Monte Carlo methods are employed to determine the system's properties. For the case of a free particle, analytical expressions for the energy, its fluctuations, and the qp-qp correlation function are derived and compared with the Monte Carlo simulations. To test the usefulness of the path integral formalism, the Metropolis algorithm is employed to determine the equilibrium properties of the qp for a periodic interaction potential, forcing the qp to occupy extended states. We consider a striped potential in one dimension, where every other lattice site is occupied by an atom with potential $\epsilon$, and every other lattice site is empty. This potential serves as a stress test for the path integral formalism because of its rapid site-to-site variation. An analytical solution was determined in this case by utilizing Bloch's theorem due to the periodicity of the potential. Comparisons of the potential energy, the total energy, the energy fluctuations and the correlation function are made between the results of the Monte Carlo simulations and the analytical calculations.
3. Open Quantum Walks: a short introduction
I. Sinayskiy, F. Petruccione
J. Phys.: Conf. Ser. 442 012003 (2013)
http://arxiv.org/abs/1402.2146
The concept of open quantum walks (OQW), quantum walks exclusively driven by the interaction with the external environment, is reviewed. OQWs are formulated as discrete completely positive maps on graphs. The basic properties of OQWs are summarised and new examples of OQWs on $\mathbb{Z}$ and their simulation by means of quantum trajectories are presented.
4. Open Quantum Random Walks
S. Attal, F. Petruccione, C. Sabot, I. Sinayskiy
Journal of Statistical Physics, Vol. 147, Issue 4, pp 832-852 (2012)
http://arxiv.org/abs/1402.3253
A new model of quantum random walks is introduced, on lattices as well as on finite graphs. These quantum random walks take into account the behavior of open quantum systems. They are the exact quantum analogues of classical Markov chains. We explore the "quantum trajectory" point of view on these quantum random walks, that is, we show that measuring the position of the particle after each time- step gives rise to a classical Markov chain, on the lattice times the state space of the particle. This quantum trajectory is a simulation of the master equation of the quantum random walk. The physical pertinence of such quantum random walks and the way they can be concretely realized is discussed. Differences and connections with the already well-known quantum random walks, such as the Hadamard random walk, are established.
5. Quantum Walks of Two Interacting Particles in One Dimension
Xizhou Qin, Yongguan Ke, Xiwen Guan, Zhibing Li, Natan Andrei, Chaohong Lee
http://arxiv.org/abs/1402.3349
We investigate continuous-time quantum walks of two indistinguishable particles (bosons, fermions or hard-core bosons) in one-dimensional lattices with nearest-neighbour interactions. The two interacting particles can undergo independent- and/or co-walking dependent on both quantum statistics and interaction strength. We find that two strongly interacting particles may form a bound state and then co-walk like a single composite particle with statistics-dependent propagation speed. Such an effective single-particle picture of co-walking is analytically derived in the context of degenerate perturbation and the analytical results are well consistent with direct numerical simulation. In addition to implementing universal quantum computation and observing bound states, two-particle quantum walks offer a novel route to detecting quantum statistics. Our theoretical results can be examined in experiments of light propagations in two-dimensional waveguide arrays or spin-impurity dynamics of ultracold atoms in one-dimensional optical lattices.
6. Applications of the Adversary Method in Quantum Query Algorithms
Aleksandrs Belovs
http://arxiv.org/abs/1402.3858
In the thesis, we use a recently developed tight characterisation of quantum query complexity, the adversary bound, to develop new quantum algorithms and lower bounds. Our results are as follows: * We develop a new technique for the construction of quantum algorithms: learning graphs. * We use learning graphs to improve quantum query complexity of the triangle detection and the $k$-distinctness problems. * We prove tight lower bounds for the $k$-sum and the triangle sum problems. * We construct quantum algorithms for some subgraph-finding problems that are optimal in terms of query, time and space complexities. * We develop a generalisation of quantum walks that connects electrical properties of a graph and its quantum hitting time. We use it to construct a time-efficient quantum algorithm for 3-distinctness.
7. Entangling Power of Disordered Quantum Walks
Rafael Vieira, Edgard P. M. Amorim, Gustavo Rigolin
Phys. Rev. A 89, 042307 (2014)
http://arxiv.org/abs/1402.5092
We investigate how the introduction of different types of disorder affects the generation of entanglement between the internal (spin) and external (position) degrees of freedom in one-dimensional quantum random walks (QRW). Disorder is modeled by adding another random feature to QRW, i.e., the quantum coin that drives the system's evolution is randomly chosen at each position and/or at each time step, giving rise to either dynamic, fluctuating, or static disorder. The first one is position-independent, with every lattice site having the same coin at a given time, the second has time and position dependent randomness, while the third one is time-independent. We show for several levels of disorder that dynamic disorder is the most powerful entanglement generator, followed closely by fluctuating disorder. Static disorder is the less efficient entangler, being almost always less efficient than the ordered case. Also, dynamic and fluctuating disorder lead to maximally entangled states asymptotically in time for any initial condition while static disorder has no asymptotic limit and, similarly to the ordered case, has a long time behavior highly sensitive to the initial conditions.
8. Entropy rate of message sources driven by quantum walks
B��lint Koll��r, M��ty��s Koniorczyk
Phys. Rev. A 89, 022338 (2014)
http://arxiv.org/abs/1402.6731
The amount of information generated by a discrete time stochastic processes in a single step can be quantified by the entropy rate. We investigate the differences between two discrete time walk models, the discrete time quantum walk and the classical random walk in terms of entropy rate. We develop analytical methods to calculate and approximate it. This allows us to draw conclusions about the differences between classical stochastic and quantum processes in terms of the classical information theory.
9. Alternation in Quantum Programming: From Superposition of Data to Superposition of Programs
Mingsheng Ying, Nengkun Yu, Yuan Feng
http://arxiv.org/abs/1402.5172
We extract a novel quantum programming paradigm - superposition of programs - from the design idea of a popular class of quantum algorithms, namely quantum walk-based algorithms. The generality of this paradigm is guaranteed by the universality of quantum walks as a computational model. A new quantum programming language QGCL is then proposed to support the paradigm of superposition of programs. This language can be seen as a quantum extension of Dijkstra's GCL (Guarded Command Language). Surprisingly, alternation in GCL splits into two different notions in the quantum setting: classical alternation (of quantum programs) and quantum alternation, with the latter being introduced in QGCL for the first time. Quantum alternation is the key program construct for realizing the paradigm of superposition of programs. The denotational semantics of QGCL are defined by introducing a new mathematical tool called the guarded composition of operator-valued functions. Then the weakest precondition semantics of QGCL can straightforwardly derived. Another very useful program construct in realizing the quantum programming paradigm of superposition of programs, called quantum choice, can be easily defined in terms of quantum alternation. The relation between quantum choices and probabilistic choices is clarified through defining the notion of local variables. We derive a family of algebraic laws for QGCL programs that can be used in program verification, transformations and compilation. The expressive power of QGCL is illustrated by several examples where various variants and generalizations of quantum walks are conveniently expressed using quantum alternation and quantum choice. We believe that quantum programming with quantum alternation and choice will play an important role in further exploiting the power of quantum computing.