# Tracking Quantum Computations By Polynomial Arithmetic

- 14:00 12th June 2015 ( week 7, Trinity Term 2015 )Lecture Theatre A

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/