Quantum circuits and low-degree polynomials over F2
By Ashley Montanaro. 2016
326 citations recorded by the source corpus.
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.
Subfields: Artificial Intelligence, Computational Theory and Mathematics
View Paper: https://www.semanticscholar.org/paper/1848813ff053975d6b744c38760e1b3001c7fd30
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Artificial Intelligence
In Computational Theory and Mathematics
Citations in the corpus
- Introduction to the Pontryagin Maximum Principle for Quantum Optimal Control (2020, background): “Quantum control encompasses a set of techniques to find the time evolution of control parameters which perform specific tasks in quantum physics [2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19].”
- Hydrodynamics of operator spreading and quasiparticle diffusion in interacting integrable systems (2018, unknown): “From the explicit form of the quasiparticle velocity in terms of generalized Fermi factors, we find the functional derivative [58, 64] ρ α,kδvα,k/δnβ,k′ = (vα,k − vβ,k′)ρ β,k′K αβ(k, k′), where Kdr αβ(k, k′) is a “dressed” version of the scattering kernel, which satisfies the integral equation Kdr α”