Quantum computing and polynomial equations over the finite field Z 2

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

Authors

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

External Research Organisations

  • University of Queensland
  • University of Bristol
View graph of relations

Details

Original languageEnglish
Pages (from-to)102-112
Number of pages11
JournalQuantum Information and Computation
Volume5
Issue number2
Publication statusPublished - Mar 2005
Externally publishedYes

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

ASJC Scopus subject areas

Cite this

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, Vol. 5, No. 2, 03.2005, p. 102-112.

Research output: Contribution to journal › Article › Research › 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, vol. 5, no. 2, pp. 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 Mar;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 ; Vol. 5, No. 2. pp. 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 -