Quantum walks on embedded hypercubes

Adi Makmal, Manran Zhu, Daniel Manzano, Markus Tiersch, and Hans J. Briegel
Phys. Rev. A 90, 022314 – Published 14 August 2014

Abstract

It has been proved by Kempe that discrete quantum walks on the hypercube (HC) hit exponentially faster than the classical analog. The same was also observed numerically by Krovi and Brun for a slightly different property, namely, the expected hitting time. Yet, to what extent this striking result survives in more general graphs is to date an open question. Here, we tackle this question by studying the expected hitting time for quantum walks on HCs that are embedded into larger symmetric structures. By performing numerical simulations of the discrete quantum walk and deriving a general expression for the classical hitting time, we observe an exponentially increasing gap between the expected classical and quantum hitting times, not only for walks on the bare HC, but also for a large family of embedded HCs. This suggests that the quantum speedup is stable with respect to such embeddings.

  • Figure
  • Figure
  • Figure
  • Figure
  • Figure
  • Figure
  • Figure
4 More
  • Received 4 December 2013
  • Revised 11 June 2014

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

©2014 American Physical Society

Authors & Affiliations

Adi Makmal1,2, Manran Zhu3,*, Daniel Manzano1,†, Markus Tiersch1,2, and Hans J. Briegel1,2

  • 1Institut für Theoretische Physik, Universität Innsbruck, Technikerstraße 25, A-6020 Innsbruck, Austria
  • 2Institut für Quantenoptik und Quanteninformation der Österreichischen Akademie der Wissenschaften, Innsbruck, Austria
  • 3University of Science and Technology of China, Hefei, Anhui, 230026, P. R. China

  • *Part of the work was carried while visiting the Institut für Quantenoptik und Quanteninformation, Innsbruck. Now at Department of Physics, Swiss Federal Institute of Technology in Zurich, 8093 Zurich, Switzerland.
  • Now at Department of Chemistry, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139, USA and Engineering Product Development, Singapore University of Technology and Design, 20 Dover Drive 138643, Singapore.

Article Text (Subscription Required)

Click to Expand

References (Subscription Required)

Click to Expand
Issue

Vol. 90, Iss. 2 — August 2014

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
×