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”.
© 2014 Optical Society of AmericaPDF Article