Decoherence in the quantum walk on the line

https://doi.org/10.1016/j.physa.2004.08.070Get rights and content

Abstract

We investigate the quantum walk on the line when decoherences are introduced either through simultaneous measurements of the chirality and particle position, or as a result of broken links. Both mechanisms drive the system to a classical diffusive behavior. In the case of measurements, we show that the diffusion coefficient is proportional to the variance of the initially localized quantum random walker just before the first measurement. When links between neighboring sites are randomly broken with probability p per unit time, the evolution becomes decoherent after a characteristic time that scales as 1/p. The fact that the quadratic increase of the variance is eventually lost even for very small frequencies of disrupting events suggests that the implementation of a quantum walk on a real physical system may be severely limited by thermal noise and lattice imperfections.

Introduction

One of the most challenging problems in quantum computation has been the design of quantum algorithms which outperform their classical counterparts in meaningful tasks. Few quantum codes in this category have been discovered after the well-known examples by Shor and Grover [1], [2]. Since the classical codes based on the random walk process have been extremely well succeeded in certain tasks [3], the hope that the quantum random walk [4] may provide a similar insight for quantum coding has generated a great interest in this model. However, the dynamical properties of the quantum random walk are rich enough so that this system is physically interesting in its own right [5]. For instance, due to quantum coherence effects, the position distribution of the quantum random walker spreads out linearly in time. In contrast, the classical random walker spreads out only as the square root of time.

Several systems have been proposed as candidates to implement quantum random walks. These proposals include atoms trapped in optical lattices [6], cavity quantum electrodynamics (CQED) [7] and nuclear magnetic resonance (NMR) in solid substrates [8], [9]. In liquid-state NMR systems [10], time-resolved observations of spin waves has been done [11]. It has also been pointed out that a quantum walk can be simulated using classical waves instead of matter waves [12], [13].

All these proposed implementations face the obstacle of decoherence due to environmental noise and imperfections. Decoherence in the quantum walk on the line has been considered recently by several authors. Numerical simulations of the effect of different kinds of measurements have shown that the quantum walk properties are highly sensitive to decoherent events and in particular that the quadratic increase of the variance is eventually suppressed [14]. Other studies focused on the effect of measurements in chirality and reached similar conclusions [15], [16]. A different decoherent mechanism, unitary noise, also leads to a crossover from a quantum behavior at short times to a classical-like behavior at longer times [17]. It is clear that the quadratic increase in the variance of the quantum walk with time is a direct consequence of the coherence of the quantum evolution [4]. This can also be visualized through the separation of the evolution equation for a quantum system into a Markovian term and a quantum interference term as proposed in [18]. In this work, besides the study of the effect of measurements on the evolution of quantum random walkers, we also consider the decoherences generated by a different process, namely the influence of randomly broken links on the dynamics of the quantum walk. These mechanisms may be relevant in experimental realizations of quantum computers based on Ising spin-12 chains in solid-state substrates [9].

The paper is organized as follows. In the next section, we briefly introduce the basic notions and notation relative to the discrete-time quantum walk on the line. Then, in Section 3, we consider joint periodic measurements of chirality and position and show how the resulting evolution can be described in terms of a master equation. In Section 4 decoherence is introduced through random failures in the links between neighboring sites. In Section 5, we show how the stochastic classical model of Brownian motion can be used to describe the time dependence of the variance of the decoherent quantum walk. Finally, in Section 6, we summarize our conclusions.

Section snippets

Quantum random walk on the line

Let us consider a particle that can move freely over a series of interconnected sites. The discrete quantum walk on the line may be implemented by introducing an additional degree of freedom, the chirality, which can take two values: “left” or “right”, |L or |R, respectively. This is the quantum analog of the coin-flipping decision procedure for the classical random walker. At every time step, a rotation (or, more generally, a unitary transformation) of the chirality takes place and the

Periodic measurements

Let us take as an initial condition the random walker starting from the position eigenstate |0 with chirality 12(1,i)T. This choice results in a symmetric evolution with Pn(t)=P-n(t) [22]. The position and chirality of the walker are jointly measured every T steps. Among the several alternatives for measuring chirality, we choose to measure it in such a way that the chirality is projected on the y direction by the σy Pauli operator. Then, the qubit states 12(1,i)T and 12(1,-i)T are

Broken links

Let us now consider a different mechanism for introducing decoherence in the quantum walk. Suppose that, at time t, a given site n has one or both of the links connecting it to its neighboring sites broken. If site n has no broken links, as in Fig. 3a, the evolution law (5), which implies a Hadamard operation in chirality space followed by a conditional translation (upper spinor component to the left and the lower component to the right) is applied. When one or both links at site n are opened

Brownian motion

The periodic measurement model discussed in Section 3 can be easily generalized to the case where the time intervals between consecutive measurements are randomly distributed. In this case the diffusion coefficient is given byDrm=CT¯22T¯,where T¯ (T¯2) is the average of the (squared) time intervals between measurements. The evolution of the average variance when the distribution of time intervals between measurements is uniform in [1], [10] is shown in Fig. 8. In this case, T¯=5.5, T¯2=38.5 and

Conclusions

Two instances of decoherent quantum walks have been considered. In one of them, decoherence is introduced through frequent measurements of position and chirality. In the other, decoherence results from randomly breaking a few links in the line. Through comparison of the results obtained with these two models and their classical counterparts, we have drawn some interesting conclusions about the diffusion rates and the decay of correlations in decoherent quantum walks.

In the case of the quantum

Acknowledgements

G.A. and R.D. thank H. Pastawski for useful discussions. We acknowledge support of PEDECIBA and CONICYT (Uruguay). R.D. acknowledges partial financial support from the Brazilian Research Council (CNPq). A.R, G.A. and R.D. acknowledge financial support from the Brazilian Millennium Institute for Quantum Information-CNPq.

References (23)

  • H. Jeong et al.

    Phys. Rev. A

    (2004)
  • T.A. Brun et al.

    Phys. Rev. Lett.

    (2003)
    T.A. Brun et al.

    Phys. Rev. A

    (2003)
  • D. Shapira, O. Biham, A.J. Bracken, M. Hackett, Phys. Rev. A 68 (2003) 062315 arXiv:...
  • P.W. Shor, in: S. Goldwasser (Ed.), Proceedings of the 35th Annual Symposium on the Foundations of Computer Science,...
  • L. Grover, Proceedings of the 28th STOC, 212, Philadelphia, PA,...
  • A. Sinclair, M. Dyer, A. Frieze, R. Kannan (Eds.), Algorithms for random generation and counting: a Markov chain...A. Sinclair, M. Dyer, A. Frieze, R. Kannan (Eds.), J. the ACM, 38, 1...U. Schöning, A probabilistic algorithm for k-SAT and constraint satisfaction problems, 40th Annual Symposium on...M. Jerrum, A. Sinclair, E. Vigoda, Proceedings of the 33th STOC (2001)...
  • A. Romanelli, A.C. Sicardi Schifino, R. Siri, G. Abal, A. Auyuanet, R. Donangelo, Physica A 338 (2004) 395...
  • J. Kempe

    Contemp. Phys.

    (2003)
  • W. Dür et al.

    Phys. Rev. A

    (2002)
  • B. Sanders et al.

    Phys. Rev. A

    (2003)
  • J. Du et al.

    Phys. Rev. A

    (2003)
  • Cited by (0)

    View full text