Quantum information theory: Trading classical for quantum computation using indirection

Rodney Van Meter

doi:10.1142/9789812701619_0007

Quantum information theory: Trading classical for quantum computation using indirection

Rodney Van Meter

Faculty of Environment and Information Studies

Research output: Chapter in Book/Report/Conference proceeding › Chapter

Abstract

Modular exponentiation is the most expensive portion of Shor’s algorithm. We show that it is possible to reduce the number of quantum modular multiplications necessary by a factor of ω, at a cost of adding temporary storage space and associated machinery for a table of 2^ωentries, and performing 2^ωtimes as many classical modular multiplications. The storage space may be a quantum-addressable classical memory, or pure quantum memory. With classical computation as much as 10¹³times as fast as quantum computation, values of ω from 2 to 30 seem attractive; physically feasible values depend on the implementation of the memory.

Original language	English
Title of host publication	Realizing Controllable Quantum States
Subtitle of host publication	Mesoscopic Superconductivity and Spintronics - In the Light of Quantum Computation
Publisher	World Scientific Publishing Co.
Pages	316-321
Number of pages	6
ISBN (Electronic)	9789812701619
ISBN (Print)	9789812564689
DOIs	https://doi.org/10.1142/9789812701619_0007
Publication status	Published - 2005 Jan 1

ASJC Scopus subject areas

Physics and Astronomy(all)

Access to Document

10.1142/9789812701619_0007

Cite this

@inbook{db18b0e8e81b4341ac790cf26cf4cfd1,

title = "Quantum information theory: Trading classical for quantum computation using indirection",

abstract = "Modular exponentiation is the most expensive portion of Shor{\textquoteright}s algorithm. We show that it is possible to reduce the number of quantum modular multiplications necessary by a factor of ω, at a cost of adding temporary storage space and associated machinery for a table of 2ωentries, and performing 2ωtimes as many classical modular multiplications. The storage space may be a quantum-addressable classical memory, or pure quantum memory. With classical computation as much as 1013times as fast as quantum computation, values of ω from 2 to 30 seem attractive; physically feasible values depend on the implementation of the memory.",

author = "{Van Meter}, Rodney",

note = "Publisher Copyright: {\textcopyright} 2005 by World Scientific Publishing Co. Pte. Ltd.",

year = "2005",

month = jan,

day = "1",

doi = "10.1142/9789812701619_0007",

language = "English",

isbn = "9789812564689",

pages = "316--321",

booktitle = "Realizing Controllable Quantum States",

publisher = "World Scientific Publishing Co.",

}

TY - CHAP

T1 - Quantum information theory

T2 - Trading classical for quantum computation using indirection

AU - Van Meter, Rodney

PY - 2005/1/1

Y1 - 2005/1/1

N2 - Modular exponentiation is the most expensive portion of Shor’s algorithm. We show that it is possible to reduce the number of quantum modular multiplications necessary by a factor of ω, at a cost of adding temporary storage space and associated machinery for a table of 2ωentries, and performing 2ωtimes as many classical modular multiplications. The storage space may be a quantum-addressable classical memory, or pure quantum memory. With classical computation as much as 1013times as fast as quantum computation, values of ω from 2 to 30 seem attractive; physically feasible values depend on the implementation of the memory.

AB - Modular exponentiation is the most expensive portion of Shor’s algorithm. We show that it is possible to reduce the number of quantum modular multiplications necessary by a factor of ω, at a cost of adding temporary storage space and associated machinery for a table of 2ωentries, and performing 2ωtimes as many classical modular multiplications. The storage space may be a quantum-addressable classical memory, or pure quantum memory. With classical computation as much as 1013times as fast as quantum computation, values of ω from 2 to 30 seem attractive; physically feasible values depend on the implementation of the memory.

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

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

U2 - 10.1142/9789812701619_0007

DO - 10.1142/9789812701619_0007

M3 - Chapter

AN - SCOPUS:84967386553

SN - 9789812564689

SP - 316

EP - 321

BT - Realizing Controllable Quantum States

PB - World Scientific Publishing Co.

ER -

Quantum information theory: Trading classical for quantum computation using indirection

Abstract

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this