Quantum computing and polynomial equations over the finite field Z 2

Publikation: Beitrag in Fachzeitschrift › Artikel › Forschung › Peer-Review

Autoren

  • Christopher M. Dawson
  • Andrew P. Hines
  • Duncan Mortimer
  • Henry L. Haselgrove
  • Michael A. Nielsen
  • Tobias J. Osborne

Externe Organisationen

  • University of Queensland
  • University of Bristol
Forschungs-netzwerk anzeigen

Details

OriginalspracheEnglisch
Seiten (von - bis)102-112
Seitenumfang11
FachzeitschriftQuantum Information and Computation
Jahrgang5
Ausgabenummer2
PublikationsstatusVeröffentlicht - März 2005
Extern publiziertJa

Abstract

What is the computational power of a quantum computer? We show that determining the output of a quantum computation is equivalent to counting the number of solutions to an easily computed set of polynomials denned over the finite field Z2. This connection allows simple proofs to be given for two known relationships between quantum and classical complexity classes, namely BQP ⊆P#P and BQP ⊆PP.

ASJC Scopus Sachgebiete

Zitieren

Quantum computing and polynomial equations over the finite field Z 2. / Dawson, Christopher M.; Hines, Andrew P.; Mortimer, Duncan et al.
in: Quantum Information and Computation, Jahrgang 5, Nr. 2, 03.2005, S. 102-112.

Publikation: Beitrag in Fachzeitschrift › Artikel › Forschung › Peer-Review

Dawson, CM, Hines, AP, Mortimer, D, Haselgrove, HL, Nielsen, MA & Osborne, TJ 2005, 'Quantum computing and polynomial equations over the finite field Z 2', Quantum Information and Computation, Jg. 5, Nr. 2, S. 102-112.
Dawson, C. M., Hines, A. P., Mortimer, D., Haselgrove, H. L., Nielsen, M. A., & Osborne, T. J. (2005). Quantum computing and polynomial equations over the finite field Z 2. Quantum Information and Computation, 5(2), 102-112.
Dawson CM, Hines AP, Mortimer D, Haselgrove HL, Nielsen MA, Osborne TJ. Quantum computing and polynomial equations over the finite field Z 2. Quantum Information and Computation. 2005 Mär;5(2):102-112.
Dawson, Christopher M. ; Hines, Andrew P. ; Mortimer, Duncan et al. / Quantum computing and polynomial equations over the finite field Z 2. in: Quantum Information and Computation. 2005 ; Jahrgang 5, Nr. 2. S. 102-112.
Download
@article{73bec048983d47a9be35a086c65dd696,
title = "Quantum computing and polynomial equations over the finite field Z 2",
abstract = "What is the computational power of a quantum computer? We show that determining the output of a quantum computation is equivalent to counting the number of solutions to an easily computed set of polynomials denned over the finite field Z2. This connection allows simple proofs to be given for two known relationships between quantum and classical complexity classes, namely BQP ⊆P#P and BQP ⊆PP.",
keywords = "Complexity, Computing, Polynomials, Quantum",
author = "Dawson, {Christopher M.} and Hines, {Andrew P.} and Duncan Mortimer and Haselgrove, {Henry L.} and Nielsen, {Michael A.} and Osborne, {Tobias J.}",
note = "Copyright: Copyright 2005 Elsevier B.V., All rights reserved.",
year = "2005",
month = mar,
language = "English",
volume = "5",
pages = "102--112",
number = "2",

}

Download

TY - JOUR

T1 - Quantum computing and polynomial equations over the finite field Z 2

AU - Dawson, Christopher M.

AU - Hines, Andrew P.

AU - Mortimer, Duncan

AU - Haselgrove, Henry L.

AU - Nielsen, Michael A.

AU - Osborne, Tobias J.

N1 - Copyright: Copyright 2005 Elsevier B.V., All rights reserved.

PY - 2005/3

Y1 - 2005/3

N2 - What is the computational power of a quantum computer? We show that determining the output of a quantum computation is equivalent to counting the number of solutions to an easily computed set of polynomials denned over the finite field Z2. This connection allows simple proofs to be given for two known relationships between quantum and classical complexity classes, namely BQP ⊆P#P and BQP ⊆PP.

AB - What is the computational power of a quantum computer? We show that determining the output of a quantum computation is equivalent to counting the number of solutions to an easily computed set of polynomials denned over the finite field Z2. This connection allows simple proofs to be given for two known relationships between quantum and classical complexity classes, namely BQP ⊆P#P and BQP ⊆PP.

KW - Complexity

KW - Computing

KW - Polynomials

KW - Quantum

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

M3 - Article

AN - SCOPUS:16244411647

VL - 5

SP - 102

EP - 112

JO - Quantum Information and Computation

JF - Quantum Information and Computation

SN - 1533-7146

IS - 2

ER -