• Featured in Physics
  • Editors' Suggestion

Experimental Realization of a One-Way Quantum Computer Algorithm Solving Simon’s Problem

M. S. Tame, B. A. Bell, C. Di Franco, W. J. Wadsworth, and J. G. Rarity
Phys. Rev. Lett. 113, 200501 – Published 11 November 2014
Physics logo See Synopsis: Simon Says Speed Up
PDFHTMLExport Citation

Abstract

We report an experimental demonstration of a one-way implementation of a quantum algorithm solving Simon’s problem—a black-box period-finding problem that has an exponential gap between the classical and quantum runtime. Using an all-optical setup and modifying the bases of single-qubit measurements on a five-qubit cluster state, key representative functions of the logical two-qubit version’s black box can be queried and solved. To the best of our knowledge, this work represents the first experimental realization of the quantum algorithm solving Simon’s problem. The experimental results are in excellent agreement with the theoretical model, demonstrating the successful performance of the algorithm. With a view to scaling up to larger numbers of qubits, we analyze the resource requirements for an n-qubit version. This work helps highlight how one-way quantum computing provides a practical route to experimentally investigating the quantum-classical gap in the query complexity model.

  • Figure
  • Figure
  • Received 21 March 2014

DOI:https://doi.org/10.1103/PhysRevLett.113.200501

© 2014 American Physical Society

Synopsis

Key Image

Simon Says Speed Up

Published 11 November 2014

A function finder called Simon’s algorithm has been experimentally tested on a prototype quantum computer for the first time.

See more in Physics

Authors & Affiliations

M. S. Tame1,2,*, B. A. Bell3, C. Di Franco4, W. J. Wadsworth5, and J. G. Rarity3

  • 1University of KwaZulu-Natal, School of Chemistry and Physics, Durban 4001, South Africa
  • 2National Institute for Theoretical Physics, University of KwaZulu-Natal, Durban 4001, South Africa
  • 3Photonics Group, Department of Electrical and Electronic Engineering, University of Bristol, Merchant Venturers Building, Woodland Road, Bristol BS8 1UB, United Kingdom
  • 4Quantum Optics and Laser Science Group, Imperial College London, Blackett Laboratory, London SW7 2AZ, United Kingdom
  • 5CPPM, Department of Physics, University of Bath, Claverton Down, Bath BA2 7AY, United Kingdom

  • *markstame@gmail.com

Article Text (Subscription Required)

Click to Expand

Supplemental Material (Subscription Required)

Click to Expand

References (Subscription Required)

Click to Expand
Issue

Vol. 113, Iss. 20 — 14 November 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 Letters

Log In

Cancel
×

Search


Article Lookup

Paste a citation or DOI

Enter a citation
×