The final Theory Weekly Meeting for this semester will happen today between 4:30 – 5:00 pm at 203 Davis Hall(Theory Lab). The schedule will be as follows :
4:30 – 5:00 pm – A talk by Ken Regan. The abstract for the talk is as follows –
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, anda 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/
Hoping to see you all!