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, J. G. Rarity

Research output: Contribution to journalArticle

12 Citations (Scopus)
71 Downloads (Pure)

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.

Original languageEnglish
Article number200501
JournalPhysical Review Letters
Volume113
DOIs
Publication statusPublished - 11 Nov 2014

Fingerprint

quantum computers
problem solving
boxes
quantum computation
resources
routes
scaling
requirements

Cite this

Experimental realization of a one-way quantum computer algorithm solving Simon's problem. / Tame, M. S.; Bell, B. A.; Di Franco, C.; Wadsworth, W. J.; Rarity, J. G.

In: Physical Review Letters, Vol. 113, 200501, 11.11.2014.

Research output: Contribution to journalArticle

@article{f362d60fe7d24457a9d274c70fa039db,
title = "Experimental realization of a one-way quantum computer algorithm solving Simon's problem",
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.",
author = "Tame, {M. S.} and Bell, {B. A.} and {Di Franco}, C. and Wadsworth, {W. J.} and Rarity, {J. G.}",
year = "2014",
month = "11",
day = "11",
doi = "10.1103/PhysRevLett.113.200501",
language = "English",
volume = "113",
journal = "Physical Review Letters",
issn = "0031-9007",
publisher = "American Physical Society",

}

TY - JOUR

T1 - Experimental realization of a one-way quantum computer algorithm solving Simon's problem

AU - Tame, M. S.

AU - Bell, B. A.

AU - Di Franco, C.

AU - Wadsworth, W. J.

AU - Rarity, J. G.

PY - 2014/11/11

Y1 - 2014/11/11

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=84910609353&partnerID=8YFLogxK

UR - http://dx.doi.org/10.1103/PhysRevLett.113.200501

UR - http://arxiv.org/abs/1410.3859

U2 - 10.1103/PhysRevLett.113.200501

DO - 10.1103/PhysRevLett.113.200501

M3 - Article

VL - 113

JO - Physical Review Letters

JF - Physical Review Letters

SN - 0031-9007

M1 - 200501

ER -