Polynomials over finite rings and complexity classes
MetadataShow full item record
Polynomials modulo composite numbers are at the frontier of what is known in classical computational complexity. They correspond to the class ACC 0 of languages represented by constant-depth polynomial-sized circuits of Boolean and mod- m gates. This class is not known to be smaller than the exponential time class EXP, and only recently has been separated from nondeterministic exponential time class NEXP. Acceptance probabilities of quantum circuits also can be found by counting the number of solutions of multivariate polynomials over finite rings. This research focuses on properties of solution spaces of polynomials over composite moduli. One effect of composite moduli is that the allowed cardinalities C of solution sets are much more restricted than those obtained by the Ax-Katz theorem for polynomials over fields. In particular, modulo m = p k , C must be a multiple of p l , where l scales as kn. We show certain new symmetries in the solution spaces, with even higher divisibility, building on cosets of ideals of the ring. Those results provide additional ground for estimation and heuristic algorithms for simulation of quantum circuits. Some additional research regarding low-level circuit complexity classes is also presented.