Tracking Quantum Computations By Polynomial Arithmetic

Quantum computers can perform computations whose results we do not know
how to achieve in comparable time on "classical" computers.  How, then,
can we possibly verify these results by classical means?  In important
cases the result is a "finding a key in a haystack" kind---once you find
it, you can tell it's a key and try it in the lock. In the case of
factoring a given huge number N you can easy multiply the returned factors
to verify.  Are there ways to verify in general cases, or even carry out
the same solving task classically?  This talk will present a system for
translating a quantum circuit into an ordinary multi-variable polynomial
of comparable size such that the results of the circuit can be inferred
from the distribution of values of the polynomial.  Questions about the
distribution have high classical complexity in general, but in some
situations they are easy.  This work includes a new proof of the
well-known theorem (Gottesman-Knill) that all circuits over a restricted
"stabilizer set" of quantum gates can be quickly simulated classically,
and a new proposal for a multi-way entanglement measure.

Part of this is joint work with Dr. Amlan Chakrabarti, University of
Calcutta, and was covered in a post "Grilling Quantum Circuits" on the
"Goedel's Lost Letter and P=NP" blog,
https://rjlipton.wordpress.com/2012/07/08/grilling-quantum-circuits/