Quantum computing and polynomial equations over the finite field Z_2
Dawson, C M, Haselgrove, H L, Hines, A P, Mortimer, D, Nielsen, M A, Osborne, T J · CERN Document Server (European Organization for Nuclear Research) · 2004
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.