We explain why linear optics is of interest to complexity theory. We show that under plausible conjectures, one cannot classically simulate the outputs of linear optical systems, even approximately. This suggests a gap in computational power between quantum and classical.

This talk is based on work done with Scott Aaronson that includes the paper “The Computational Complexity of Linear Optics”[1].

© 2014 Optical Society of America

PDF Article


You do not have subscription access to this journal. Citation lists with outbound citation links are available to subscribers only. You may subscribe either as an OSA member, or as an authorized user of your institution.

Contact your librarian or system administrator
Login to access OSA Member Subscription