ROM-based computation: Quantum versus classical

B. C. Travaglione; M. A. Nielsen; H. M. Wiseman; A. Ambainis

doi:10.26421/qic2.4-5

ROM-based computation: Quantum versus classical

B. C. Travaglione^*
, M. A. Nielsen
, H. M. Wiseman
, A. Ambainis

^*Corresponding author for this work

University of Queensland
Griffith University Queensland
University of California at Berkeley

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

10 Citations (Scopus)

Abstract

We introduce a model of computation based on read only memory (ROM), which allows us to compare the space-efficiency of reversible, error-free classical computation with reversible, error-free quantum computation. We show that a ROM-based quantum computer with one writable qubit is universal, whilst two writable bits are required for a universal classical ROM-based computer. We also comment on the time-efficiency advantages of quantum computation within this model.

Original language	English
Pages (from-to)	324-332
Number of pages	9
Journal	Quantum Information and Computation
Volume	2
Issue number	4
DOIs	https://doi.org/10.26421/qic2.4-5
Publication status	Published - Jul 2002
Externally published	Yes

Keywords

Quantum space complexity
Read only memory
Reversible computation

Access to Document

10.26421/qic2.4-5

Cite this

@article{f77b6c4191774d5c8855ce798cef0eea,

title = "ROM-based computation: Quantum versus classical",

abstract = "We introduce a model of computation based on read only memory (ROM), which allows us to compare the space-efficiency of reversible, error-free classical computation with reversible, error-free quantum computation. We show that a ROM-based quantum computer with one writable qubit is universal, whilst two writable bits are required for a universal classical ROM-based computer. We also comment on the time-efficiency advantages of quantum computation within this model.",

keywords = "Quantum space complexity, Read only memory, Reversible computation",

author = "Travaglione, \{B. C.\} and Nielsen, \{M. A.\} and Wiseman, \{H. M.\} and A. Ambainis",

year = "2002",

month = jul,

doi = "10.26421/qic2.4-5",

language = "English",

volume = "2",

pages = "324--332",

journal = "Quantum Information and Computation",

issn = "1533-7146",

publisher = "Paradigm Publishing Services",

number = "4",

}

TY - JOUR

T1 - ROM-based computation

T2 - Quantum versus classical

AU - Travaglione, B. C.

AU - Nielsen, M. A.

AU - Wiseman, H. M.

AU - Ambainis, A.

PY - 2002/7

Y1 - 2002/7

N2 - We introduce a model of computation based on read only memory (ROM), which allows us to compare the space-efficiency of reversible, error-free classical computation with reversible, error-free quantum computation. We show that a ROM-based quantum computer with one writable qubit is universal, whilst two writable bits are required for a universal classical ROM-based computer. We also comment on the time-efficiency advantages of quantum computation within this model.

AB - We introduce a model of computation based on read only memory (ROM), which allows us to compare the space-efficiency of reversible, error-free classical computation with reversible, error-free quantum computation. We show that a ROM-based quantum computer with one writable qubit is universal, whilst two writable bits are required for a universal classical ROM-based computer. We also comment on the time-efficiency advantages of quantum computation within this model.

KW - Quantum space complexity

KW - Read only memory

KW - Reversible computation

UR - https://www.scopus.com/pages/publications/0000669823

U2 - 10.26421/qic2.4-5

DO - 10.26421/qic2.4-5

M3 - Article

AN - SCOPUS:0000669823

SN - 1533-7146

VL - 2

SP - 324

EP - 332

JO - Quantum Information and Computation

JF - Quantum Information and Computation

IS - 4

ER -

ROM-based computation: Quantum versus classical

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this