Efficient distributed quantum computing

Robert Beals; Stephen Brierley; Oliver Gray; Aram W. Harrow; Samuel Kutin; Noah Linden; Dan Shepherd; Mark Stather

doi:10.1098/rspa.2012.0686

Efficient distributed quantum computing

Robert Beals, Stephen Brierley, Oliver Gray, Aram W. Harrow, Samuel Kutin, Noah Linden, Dan Shepherd, Mark Stather

School of Arts and Sciences, Mathematics

Research output: Contribution to journal › Article › peer-review

126 Scopus citations

Abstract

We provide algorithms for efficiently moving and addressing quantum memory in parallel. These imply that the standard circuit model can be simulated with a low overhead by a more realistic model of a distributed quantum computer. As a result, the circuit model can be used by algorithm designers without worrying whether the underlying architecture supports the connectivity of the circuit. In addition, we apply our results to existing memoryintensive quantum algorithms. We present a parallel quantum search algorithm and improve the time- space trade-off for the element distinctness and collision finding problems.

Original language	English (US)
Article number	20120686
Journal	Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences
Volume	469
Issue number	2153
DOIs	https://doi.org/10.1098/rspa.2012.0686
State	Published - May 8 2013

All Science Journal Classification (ASJC) codes

Mathematics(all)
Engineering(all)
Physics and Astronomy(all)

Keywords

Distributed quantum computing
Quantum algorithms
Quantum architectures

Access to Document

10.1098/rspa.2012.0686

Cite this

@article{b3234b84d30c474588ec0cded92566ec,

title = "Efficient distributed quantum computing",

abstract = "We provide algorithms for efficiently moving and addressing quantum memory in parallel. These imply that the standard circuit model can be simulated with a low overhead by a more realistic model of a distributed quantum computer. As a result, the circuit model can be used by algorithm designers without worrying whether the underlying architecture supports the connectivity of the circuit. In addition, we apply our results to existing memoryintensive quantum algorithms. We present a parallel quantum search algorithm and improve the time- space trade-off for the element distinctness and collision finding problems.",

keywords = "Distributed quantum computing, Quantum algorithms, Quantum architectures",

author = "Robert Beals and Stephen Brierley and Oliver Gray and Harrow, {Aram W.} and Samuel Kutin and Noah Linden and Dan Shepherd and Mark Stather",

year = "2013",

month = may,

day = "8",

doi = "10.1098/rspa.2012.0686",

language = "English (US)",

volume = "469",

journal = "Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences",

issn = "1364-5021",

publisher = "Royal Society of London",

number = "2153",

}

TY - JOUR

T1 - Efficient distributed quantum computing

AU - Beals, Robert

AU - Brierley, Stephen

AU - Gray, Oliver

AU - Harrow, Aram W.

AU - Kutin, Samuel

AU - Linden, Noah

AU - Shepherd, Dan

AU - Stather, Mark

PY - 2013/5/8

Y1 - 2013/5/8

N2 - We provide algorithms for efficiently moving and addressing quantum memory in parallel. These imply that the standard circuit model can be simulated with a low overhead by a more realistic model of a distributed quantum computer. As a result, the circuit model can be used by algorithm designers without worrying whether the underlying architecture supports the connectivity of the circuit. In addition, we apply our results to existing memoryintensive quantum algorithms. We present a parallel quantum search algorithm and improve the time- space trade-off for the element distinctness and collision finding problems.

AB - We provide algorithms for efficiently moving and addressing quantum memory in parallel. These imply that the standard circuit model can be simulated with a low overhead by a more realistic model of a distributed quantum computer. As a result, the circuit model can be used by algorithm designers without worrying whether the underlying architecture supports the connectivity of the circuit. In addition, we apply our results to existing memoryintensive quantum algorithms. We present a parallel quantum search algorithm and improve the time- space trade-off for the element distinctness and collision finding problems.

KW - Distributed quantum computing

KW - Quantum algorithms

KW - Quantum architectures

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

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

U2 - 10.1098/rspa.2012.0686

DO - 10.1098/rspa.2012.0686

M3 - Article

AN - SCOPUS:84877258273

SN - 1364-5021

VL - 469

JO - Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences

JF - Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences

IS - 2153

M1 - 20120686

ER -

Efficient distributed quantum computing

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this