Quantum computing and polynomial equations over the finite field Z_2

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

Quantum computing and polynomial equations over the finite field Z_2

Authors

Dawson, Christopher M.

Description

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 defined over the finite field Z_2. This connection allows simple proofs to be given for two known relationships between quantum and classical complexity classes.
7 pages, 3 figures