The role of complexity theory in quantum optics-a tutorial for BosonSampling

BOSONSAMPLING is a recent development in linear optics which has stimulated a number of new computational models and algorithms in quantum computing. Much of this interest follows from the computational complexity arguments which show that the particular quantum system in which BOSONSAMPLING resides is difficult to simulate with a classical computer (assuming highly plausible conjectures) Arkhipov and Aaronson (2011 Proc. ACM STOC (New York), p 333). These arguments, however, require some understanding of both quantum optics and complexity theory-topics that are rarely seen together. This tutorial is intended to introduce a reader to the topic who has at least a basic knowledge of quantum mechanics or quantum information theory, but may be unfamiliar with either quantum optics or complexity theory. Included is some historic context as well as an outlook on the potential for BOSONSAMPLING to be the first experimental demonstration of quantum supremacy. The emphasis of the first section is to develop a general context for the subfields of quantum optics and computer science that intersect to form the BOSONSAMPLING problem. This begins with a historical introduction and a background of quantum optics. We then progress to the physical system-quantum optical networks-where BOSONSAMPLING is defined. Finally, we provide a short introduction to computational complexity theory to provide a structure where the essence behind the BOSONSAMPLING result can be discerned. The second section focuses on the BOSONSAMPLING result itself, seeking to understand the computational complexity aspects of passive linear optical networks, and what consequences this may have. Some effort is spent discussing a number of issues inherent in the BOSONSAMPLING problem that are roadblocks to limiting the scope of its applicability, but that have made progress recently and remain active topics of research. The third short section touches on the relationship between BOSONSAMPLING and other quantum computing protocols. Namely, other settings and architectures that inherit the same complexity as BOSONSAMPLING will be presented, as well as giving a summary of experimental efforts to implement BOSONSAMPLING. We discuss similarities between BOSONSAMPLING and other quantum algorithms. In the final section, some comments are presented considering future research related to the problems and protocols found in this tutorial. We suggest other unexplored directions of study which may have some bearing on the complexity of quantum optics. Also included is a glossary of complexity terms used throughout the tutorial.