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 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.
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 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.
This thesis is intended in part to summarize and also to contribute to the newest developments in passive linear optics that have resulted, directly or indirectly, from the somewhat shocking discovery in 2010 that the BosonSampling problem is likely hard for a classical computer to simulate. In doing so, I hope to provide a historic context for the original result, as well as an outlook on the future of technology derived from these newer developments. An emphasis is made in each section to provide a broader conceptual framework for understanding the consequences of each result in light of the others. This framework is intended to be comprehensible even without a deep understanding of the topics themselves. The fi_x000C_rst three chapters focus more closely on the BosonSampling result itself, seeking to understand the computational complexity aspects of passive linear optical networks, and what consequences this may have. Some e_x000B_ort is spent discussing a number of issues inherent in the BosonSampling problem that limit the scope of its applicability, and that are still active topics of research. Finally, we describe two other linear optical settings that inherit the same complexity as BosonSampling. The _x000C_final chapters focus on how an intuitive understanding of BosonSampling has led to developments in optical metrology and other closely related _x000C_fields. These developments suggest the exciting possibility that quantum sensors may be viable in the next few years with only marginal improvements in technology. Lastly, some open problems are presented which are intended to lay out a course for future research that would allow for a more complete picture of the scalability of the architecture developed in these chapters.
Abstract There is a large body of evidence for the potential of greater computational power using information carriers that are quantum mechanical over those governed by the laws of classical mechanics. But the question of the exact nature of the power contributed by quantum mechanics remains only partially answered. Furthermore, there exists doubt over the practicality of achieving a large enough quantum computation that definitively demonstrates quantum supremacy. Recently the study of computational problems that produce samples from probability distributions has added to both our understanding of the power of quantum algorithms and lowered the requirements for demonstration of fast quantum algorithms. The proposed quantum sampling problems do not require a quantum computer capable of universal operations and also permit physically realistic errors in their operation. This is an encouraging step towards an experimental demonstration of quantum algorithmic supremacy. In this paper, we will review sampling problems and the arguments that have been used to deduce when sampling problems are hard for classical computers to simulate. Two classes of quantum sampling problems that demonstrate the supremacy of quantum algorithms are BosonSampling and Instantaneous Quantum Polynomial-time Sampling. We will present the details of these classes and recent experimental progress towards demonstrating quantum supremacy in BosonSampling.
In this work, we discuss the classical theory of computation, focusing specifically on the so-called computational complexity theory. We develop a theoretical background on this subject which is very useful for discussions on quantum computational supremacy, the main topic of this work, and which is currently researched very actively. It is expected that linear optics without post-selection is not universal for quantum computation, and thus is an insteresting system to try to simulate classically or to search
for evidence of quantum supremacy. To set up this discussion, however, we must first, define what is linear optics, how it can be used for quantum information processing, and how this information can be encoded into photons. It is more usual to address these topics using the circuit model of computation, although the Turing model will also be briefly introduced here. Finally, by the end of this work, all tools introduced can be combined in the study of quantum computational supremacy using other restricted quantum systems.
BosonSampling, which we proposed three years ago, is a scheme for using linear-optical networks to solve sampling problems that appear to be intractable for a classical computer. \ In a recent manuscript, Gogolin et al.\ claimed that even an ideal BosonSampling device's output would be operationally indistinguishable\textquotedblright\ from a uniform random outcome, at least \textquotedblleft without detailed a priori knowledge; or at any rate, that telling the two apart might itself be a hard problem. We first answer these claims---explaining why the first is based on a definition of a priori knowledge such that, were it adopted, almost no quantum algorithm could be distinguished from a pure random-number source; while the second is neither new nor a practical obstacle to interesting BosonSampling experiments.However, we then go further, and address some interesting research questions inspired by Gogolin et al.'s arguments. We prove that, with high probability over a Haar-random matrix A, the BosonSampling distribution induced by A is far from the uniform distribution in total variation distance. More surprisingly, and counter to Gogolin et al., we give an efficient algorithm that distinguishes these two distributions with constant bias. Finally, we offer three bonus results about BosonSampling. First, we report an observation of Fernando Brandao: that one can efficiently sample a distribution that has large entropy and that's indistinguishable from a BosonSampling distribution by any circuit of fixed polynomial size. Second, we show that BosonSampling distributions can be efficiently distinguished from uniform even with photon losses and for general initial states. Third, we offer the simplest known proof that Fermion Sampling is solvable in classical polynomial time, and we reuse techniques from our Boson Sampling analysis to characterize random FermionSampling distributions.
BosonSampling is the leading candidate for demonstrating quantum computational advantage in photonic systems. While we have recently seen many impressive experimental demonstrations, there is still a formidable distance between the complexity-theoretic hardness arguments and current experiments. One of the largest gaps involves the ratio of particles to modes—all current hardness evidence assumes a “dilute” regime in which the number of linear optical modes scales at least quadratically in the number of particles. By contrast, current experiments operate in a “saturated” regime with a linear number of modes. In this paper, we bridge this gap, bringing the hardness evidence for experiments in the saturated regime to the same level as had been previously established for the dilute regime. This involves proving a worst-to-average-case reduction for computing the permanent, which is robust both to large numbers of row repetitions and also to distributions over matrices with correlated entries. We also apply similar arguments to give evidence for hardness of Gaussian BosonSampling in the saturated regime.
We give new evidence that quantum computers -- moreover, rudimentary quantum computers built entirely out of linear-optical elements -- cannot be efficiently simulated by classical computers. In particular, we define a model of computation in which identical photons are generated, sent through a linear-optical network, then nonadaptively measured to count the number of photons in each mode. This model is not known or believed to be universal for quantum computation, and indeed, we discuss the prospects for realizing the model using current technology. On the other hand, we prove that the model is able to solve sampling problems and search problems that are classically intractable under plausible assumptions. Our first result says that, if there exists a polynomial-time classical algorithm that samples from the same probability distribution as a linear-optical network, then P^#P=BPP^NP, and hence the polynomial hierarchy collapses to the third level. Unfortunately, this result assumes an extremely accurate simulation. Our main result suggests that even an approximate or noisy classical simulation would already imply a collapse of the polynomial hierarchy. For this, we need two unproven conjectures: the "Permanent-of-Gaussians Conjecture", which says that it is #P-hard to approximate the permanent of a matrix A of independent N(0,1) Gaussian entries, with high probability over A; and the "Permanent Anti-Concentration Conjecture", which says that |Per(A)|>=sqrt(n!)/poly(n) with high probability over A. We present evidence for these conjectures, both of which seem interesting even apart from our application. This paper does not assume knowledge of quantum optics. Indeed, part of its goal is to develop the beautiful theory of noninteracting bosons underlying our model, and its connection to the permanent function, in a self-contained way accessible to theoretical computer scientists.