We present a comprehensive study of the impact of non-uniform, i.e. path-dependent, photonic losses on the computational complexity of linear-optical processes. Our main result states that, if each beam splitter in a network induces some loss probability, non-uniform network designs cannot circumvent the efficient classical simulations based on losses.To achieve our result we obtain new intermediate results that can be of independent interest. First we show that, for any network of lossy beam-splitters, it is possible to extract a layer of non-uniform losses that depends on the network geometry. We prove that, for every input mode of the network it is possible to commute si layers of losses to the input, where si is the length of the shortest path connecting the i th input to any output. We then extend a recent classical simulation algorithm due to P. Clifford and R. Clifford to allow for arbitrary n -photon input Fock states (i.e. to include collision states). Consequently, we identify two types of input states where boson sampling becomes classically simulable: (A) when n input photons occupy a constant number of input modes; (B) when all but O(logn) photons are concentrated on a single input mode, while an additional O(logn) modes contain one photon each.
We present a comprehensive study of the impact of non-uniform, i.e. path-dependent, photonic losses on the computational complexity of linear-optical processes. Our main result states that, if each beam splitter in a network induces some loss probability, non-uniform network designs cannot circumvent the efficient classical simulations based on losses.To achieve our result we obtain new intermediate results that can be of independent interest. First we show that, for any network of lossy beam-splitters, it is possible to extract a layer of non-uniform losses that depends on the network geometry. We prove that, for every input mode of the network it is possible to commute si layers of losses to the input, where si is the length of the shortest path connecting the i th input to any output. We then extend a recent classical simulation algorithm due to P. Clifford and R. Clifford to allow for arbitrary n -photon input Fock states (i.e. to include collision states). Consequently, we identify two types of input states where boson sampling becomes classically simulable: (A) when n input photons occupy a constant number of input modes; (B) when all but O(logn) photons are concentrated on a single input mode, while an additional O(logn) modes contain one photon each.
We explore the possibility of efficient classical simulation of linear optics experiments under the effect of particle losses.Specifically, we investigate the canonical boson sampling scenario in which an nparticle Fock input state propagates through a linear-optical network and is subsequently measured by particle-number detectors in the m output modes.We examine two models of losses.In the first model a fixed number of particles is lost.We prove that in this scenario the output statistics can be well approximated by an efficient classical simulation, provided that the number of photons that is left grows slower than n .In the second loss model, every time a photon passes through a beamsplitter in the network, it has some probability of being lost.For this model the relevant parameter is s, the smallest number of beamsplitters that any photon traverses as it propagates through the network.We prove that it is possible to approximately simulate the output statistics already if s grows logarithmically with m, regardless of the geometry of the network.The latter result is obtained by proving that it is always possible to commute s layers of uniform losses to the input of the network regardless of its geometry, which could be a result of independent interest.We believe that our findings put strong limitations on future experimental realizations of quantum computational supremacy proposals based on boson sampling.
Understanding how photon loss changes the classical complexity of BosonSampling is central to assessing the robustness of near-term photonic quantum advantage. In this work, we present a polynomial-time classical simulation algorithm for lossy BosonSampling that applies whenever a constant fraction of the input photons survives. We consider the standard fixed-loss model, where N input photons propagate through an M-mode interferometer and exactly N−n photons are lost uniformly at random, leaving n surviving photons at the output. For any constant surviving fraction n/N∈(0,1), the algorithm samples from a distribution within total variation distance ε of the fixed-loss BosonSampling distribution with probability at least 1−δ over Haar-random interferometers, in time poly(M,N,ε−1,δ−1). We further extend the fixed-loss analysis to the uniform-transmission-loss model and obtain analogous polynomial-time simulability for any fixed transmission rate η∈(0,1). These results substantially extend the known provably simulable regime of n=O(εN) surviving photons or η=O(ε/N) transmission rate, and demonstrate that even the experimentally relevant linear-survival regime can admit efficient classical simulation under the conditions considered here.
Boson sampling is a candidate for quantum protocols to truly realize the quantum computation advantage and to be used in advanced fields where complex computations are needed, such as quantum chemistry. However, this proposal is hard to achieve due to the existence of noise sources such as photon losses. In order to quantificationally analyze the influences of photon losses in optical networks, boson sampling is classically simulated based on the equivalent beam splitter mechanism, where the photon loss happening in optical units is equivalent to the photon transmission into the environmental paths through a virtual beam splitter. In our simulation, networks corresponding to random unitary matrices are made up, considering both the Reck structure and the Clements structure. The photon loss probability in an optical unit is well controlled by adjusting the parameters of the virtual beam splitter. Therefore, to simulate boson sampling with photon losses in optical networks is actually to simulate ideal boson sampling with more modes. It is found that when the photon loss probability is constant, boson sampling with Clements structures distinctly performs much better than that with Reck structures. Furthermore, the photon loss probability is also set to follow the normal distribution, which is thought to be closer to the situation in reality. It is found that when the mean value of photon loss probability is constant, for both network structures, errors of outputs become more obvious with the increase of standard deviation. It can be inferred that the increase of error rate can be explained by the network depth and the conclusion is suitable for larger-scale boson sampling. Finally, the number of output photons is taken into consideration, which is directly related to the classical computation complexity. It is found that with the photon loss probability, the ratio of output combinations without photon losses decreases sharply, implying that photon losses can obviously affect the quantum computation advantage of boson sampling. Our results indicate that photon losses can result in serious errors for boson sampling, even with a stable network structure such as that of Clements. This work is helpful for boson sampling experiments in reality and it is desired to develop a better protocol, for example, a well-designed network or excellent optical units, to well suppress photon losses.
Sampling from probability distributions of quantum circuits is a fundamentally and practically important task which can be used to demonstrate quantum supremacy using noisy intermediate-scale quantum devices. In the present work, we examine classical simulability of sampling from the output photon-number distribution of linear-optical circuits composed of random beam splitters with equally distributed squeezed vacuum states and single-photon states input. We provide efficient classical algorithms to simulate linear-optical random circuits and show that the algorithms' error is exponentially small up to a depth less than quadratic in the distance between sources using a classical random walk behavior of random linear-optical circuits. Notably, the average-case depth allowing an efficient classical simulation is larger than the worst-case depth limit, which is linear in the distance. Besides, our results together with the hardness of boson sampling give a lower-bound on the depth for constituting global Haar-random unitary circuits.
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.
Boson sampling experiments aim to demonstrate quantum computational advantage with increasing numbers of interfering photons. A central question is whether their computational hardness survives under photon loss. We show that even an arbitrarily small nonzero uniform loss rate permits efficient classical sampling in the average case when the rate remains fixed as the system grows. We exploit how loss suppresses correlations involving many photons to approximate the full output distribution using low correlation orders. The resulting samplers run in time polynomial in system size and inverse total variation error, with the error averaged over Haar random interferometers. The results apply to Fock state boson sampling with single-photon states in distinct input modes and arbitrary additional vacuum inputs, and to Gaussian boson sampling with equal squeezing of bounded strength in every input mode. Classical sampling is efficient even when the mean detected photon number grows linearly with system size, showing that large photon counts alone do not ensure computational hardness.