*********************************
There is now a CONTENT FREEZE for Mercury while we switch to a new platform. It began on Friday, March 10 at 6pm and will end on Wednesday, March 15 at noon. No new content can be created during this time, but all material in the system as of the beginning of the freeze will be migrated to the new platform, including users and groups. Functionally the new site is identical to the old one. webteam@gatech.edu
*********************************
Abstract:
We present variations on a polynomial construction used by Dawson et al. [2004] to simplify the proof that BQP is a subclass of PP, and by Gerdt and Severyanov [2006] to simulate quantum circuits. The constructions map additively into rings Z_m as well as multiplicatively into fields. Polynomial-time classical simulation of classes of quantum circuits thus reduces to whether certain highly-restricted subcases of the general #P-complete problem of counting solutions to polynomial equations belong to P. Ideas are given for relating BQP to the polynomial hierarchy, for quantifying multi-partite entanglement, and for algebraic complexity.
This is joint work in progress with Amlan Chakrabarti, University of Calcutta.
