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].
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].
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.
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.
We investigate the computational complexity of quantum computing with identical noninteracting bosons, such as that in a linear optical system.We explore the challenges in building devices that implement this model and in certifying their correctness.In work done with Scott Aaronson, we introduce BOSONSAMPLING, a computational model of quantum linear optics [1].We argue that the statistical distribution of outcomes cannot be reproduced by any classical device in a reasonable time span.This gives hands-on evidence of quantum advantage, that there are quantum phenomena are prohibitive to simulate in the classical world.Moreover, this quantum advantage is already present in limited optical systems, suggesting a lower bar to building devices that exhibit super-classical computation.We lay out the computational complexity argument for the classical difficulty of simulating BOSONSAM-PLING.An efficient classical simulation would have unlikely complexity consequences for the polynomial hierarchy PH.We look into the difficulties in proving an analogous approximate result, including the conjectures that seem to be needed to push it through.We then discuss experimental implementations of BOSONSAMPLING.The scalability of current implementations is limited by various sources of noise that accumulate as the problem size grows.We prove a result [51 that pertains to the inexactnesses of components that comprise the linear optical network, giving bounds on the tolerances that suffice to obtain an output distribution close to the ideal one.Finally, we look at the challenge of certifying a BOSONSAMPLING device.We show the impossibility of one technique, to use a submatrix whose permanent is so large that its corresponding outcome appears very frequently.Joint work with Aaronson [21 argues that the outputs of a BOSONSAMPLING device can be verified not to come from a uniform distribution.Results on the statistical bunching of bosons obtained with Kuperberg [61 are another approach to certification.We further present a novel certification technique based on classically estimating the distribution of integer combinations of the boson counts.
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=BPPNP, and hence the polynomial hierarchy collapses to the third level. Unfortunately, this result assumes an extremely accurate simulation.
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.
One of the most important problems in linear optics quantum computing is to find the origin of its computational complexity. This work shows that the majorization of photon distributions is one of the crucial factors that affect the complexity of multimode passive linear optics, which explains one aspect of the boson sampling hardness. As a preliminary to the main discussion, a majorization-dependent quantity that can measure the quantum complexity of identical particle distributions is introduced, which we name \emph{the Boltzmann entropy of elementary quantum complexity SBq.} It decreases as the majorization of the photon distribution vector increases (Schur concavity). Using the properties of majorization and SBq, we analyze two quantities that are important criteria for the photon scattering process, $\cT$ (the runtime of a generalized classical algorithm for calculating the permanent) and $\cE$ (the additive error bound for an approximated permanent estimator). First, for all the known algorithms for computing the permanents of matrices with repeated rows and columns, the runtime $\cT$ becomes shorter as the input and output distribution vectors are more majorized. Second, the error bound $\cE$ decreases as the majorization difference of input and output states increases. In addition, SBq turns out to be an underlying quantity of $\cT$ and $\cE$, which implies that SBq is an essential resource for the computational complexity of linear optics. We expect that our current results would provide a clue to find the genuine resource of quantum supremacy and its operational mechanism in linear optics.