Quantum circuits and low-degree polynomials over F_2

Research output: Contribution to journalArticle (Academic Journal)peer-review

62 Downloads (Pure)


In this work we explore a correspondence between quantum circuits and low-degree polynomials over the finite field F2. Any quantum circuit made up of Hadamard, Z, controlled-Z and controlled-controlled-Z gates gives rise to a degree-3 polynomial over F2 such that calculating quantum circuit amplitudes is equivalent to counting zeroes of the corresponding polynomial.
We exploit this connection, which is especially clean and simple for this particular gate set, in two directions. First, we give proofs of classical hardness results based on quantum circuit concepts. Second, we find efficient classical simulation algorithms for certain classes of quantum circuits based on efficient algorithms for classes of polynomials.
Original languageEnglish
Number of pages16
JournalJournal of Physics A: Mathematical and Theoretical
Publication statusPublished - 18 Jan 2017

Structured keywords

  • QITG
  • Bristol Quantum Information Institute


Dive into the research topics of 'Quantum circuits and low-degree polynomials over F_2'. Together they form a unique fingerprint.

Cite this