Mixing times in quantum walks on the hypercube

F. L. Marquezino, R. Portugal, G. Abal, and R. Donangelo
Phys. Rev. A 77, 042312 – Published 16 April 2008

Abstract

The mixing time of a discrete-time quantum walk on the hypercube is considered. The mean probability distribution of a Markov chain on a hypercube is known to mix to a uniform distribution in time O(nlogn). We show that the mean probability distribution of a discrete-time quantum walk on a hypercube mixes to a (generally nonuniform) distribution π(x) in time O(n), and the stationary distribution is determined by the initial state of the walk. An explicit expression for π(x) is derived for the particular case of a symmetric walk. These results are consistent with those obtained previously for a continuous-time quantum walk. The effect of decoherence due to randomly breaking links between connected sites in the hypercube is also considered. We find that the probability distribution mixes to the uniform distribution as expected. However, the mixing time has a minimum at a critical decoherence rate p0.1. A similar effect was previously reported for a quantum walk on an N-cycle with decoherence from repeated measurements of position. A controlled amount of decoherence helps in obtaining—and preserving—a uniform distribution over the 2n sites of the hypercube in the shortest possible time.

  • Figure
  • Figure
  • Figure
  • Figure
  • Figure
  • Figure
  • Figure
  • Received 21 January 2008

DOI:https://doi.org/10.1103/PhysRevA.77.042312

©2008 American Physical Society

Authors & Affiliations

F. L. Marquezino* and R. Portugal

  • Laboratório Nacional de Computação Científica—LNCC, Avenida Getúlio Vargas 333, Petrópolis, Rio de Janeiro, 25651-075, Brazil

G. Abal and R. Donangelo§

  • Instituto de Física, Universidad de la República, Casilla de Correo 30, Código Postal 11300, Montevideo, Uruguay

  • *franklin@lncc.br
  • portugal@lncc.br
  • abal@fing.edu.uy
  • §Permanent address: Instituto de Física, Universidade Federal do Rio de Janeiro, C.P. 68528, Rio de Janeiro 21941-972, Brazil. donangel@if.ufrj.br

Article Text (Subscription Required)

Click to Expand

References (Subscription Required)

Click to Expand
Issue

Vol. 77, Iss. 4 — April 2008

Reuse & Permissions
Access Options
Author publication services for translation and copyediting assistance advertisement

Authorization Required


×
×

Images

×

Sign up to receive regular email alerts from Physical Review A

Log In

Cancel
×

Search


Article Lookup

Paste a citation or DOI

Enter a citation
×