The role of complexity theory in quantum optics—a tutorial for BosonSampling. (13th November 2018)

• Record Type: Journal Article
• Authors: Olson, Jonathan
• Is Part Of: Journal of optics. Volume 20:Number 12(2018:Dec.)
• Publication Date: 2018-11-13
• Subjects: boson -- sampling -- complexity theory -- quantum optics -- quantum supremacy -- photon; Optics -- Periodicals; 535.05
• DOI: 10.1088/2040-8986/aae74a
• Languages: English
• ISSNs: 2040-8978

Abstract

Abstract: 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 whichBosonSampling 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 forBosonSampling 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 theBosonSampling problem. This begins with a historical introduction and a background of quantum optics. We then progress to the physical system—quantum optical networks—whereBosonSampling is defined. Finally, we provide a short introduction to computational complexity theory to provide a structure where the essence behind theBosonSampling result can be discerned. The second section focuses on theBosonSampling 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 theBosonSampling 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 betweenBosonSampling and other quantum computing protocols. Namely, other settings and architectures that inherit the same complexity asBosonSampling will be presented, as well as giving a summary of experimental efforts to implementBosonSampling . We discuss similarities betweenBosonSampling 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.