Abstract Boson sampling is the problem of sampling from the same distribution as indistinguishable single photons at the output of a linear optical interferometer. It is an example of a non-universal quantum computation which is believed to be feasible in the near term and cannot be simulated on a classical machine. Like all purported demonstrations of ‘quantum computational supremacy’, this motivates optimising classical simulation schemes for a realistic model of the problem, in this case boson sampling when the implementations experience lost or distinguishable photons. Although current simulation schemes for sufficiently imperfect boson sampling are classically efficient, in principle the polynomial runtime can be infeasibly large. In this work, we develop a scheme for classical simulation of boson sampling under uniform distinguishability and loss, based on the idea of sampling from distributions where at most k photons are indistinguishable. We show that asymptotically this scheme can provide a polynomial improvement in the runtime compared to classically simulating idealised boson sampling. More significantly, we show that in the regime considered experimentally relevant, our approach gives an substantial improvement in runtime over other classical simulation approaches.
Abstract Boson sampling is the problem of sampling from the same distribution as indistinguishable single photons at the output of a linear optical interferometer. It is an example of a non-universal quantum computation which is believed to be feasible in the near term and cannot be simulated on a classical machine. Like all purported demonstrations of ‘quantum computational supremacy’, this motivates optimising classical simulation schemes for a realistic model of the problem, in this case boson sampling when the implementations experience lost or distinguishable photons. Although current simulation schemes for sufficiently imperfect boson sampling are classically efficient, in principle the polynomial runtime can be infeasibly large. In this work, we develop a scheme for classical simulation of boson sampling under uniform distinguishability and loss, based on the idea of sampling from distributions where at most k photons are indistinguishable. We show that asymptotically this scheme can provide a polynomial improvement in the runtime compared to classically simulating idealised boson sampling. More significantly, we show that in the regime considered experimentally relevant, our approach gives an substantial improvement in runtime over other classical simulation approaches.
Boson Sampling is the problem of sampling from the same output probability distribution as a collection of indistinguishable single photons input into a linear interferometer. It has been shown that, subject to certain computational complexity conjectures, in general the problem is difficult to solve classically, motivating optical experiments aimed at demonstrating quantum computational ``supremacy.'' There are a number of challenges faced by such experiments, including the generation of indistinguishable single photons. We provide a quantum circuit that simulates Boson Sampling with arbitrarily distinguishable particles. This makes clear how distinguishabililty leads to decoherence in the standard quantum circuit model, allowing insight to be gained. At the heart of the circuit is the quantum Schur transform, which follows from a representation theoretic approach to the physics of distinguishable particles in first quantization. The techniques are quite general and have application beyond Boson Sampling.
We demonstrate how boson sampling with photons of partial distinguishability can be expressed in terms of interference of fewer photons. We use this observation to propose a classical algorithm to simulate the output of a boson sampler fed with photons of partial distinguishability. We find conditions for which this algorithm is efficient, which gives a lower limit on the required indistinguishability to demonstrate a quantum advantage. Under these conditions, adding more photons only polynomially increases the computational cost to simulate a boson sampling experiment.
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.
Gaussian boson sampling (GBS) allows for a way to demonstrate quantum supremacy with the relatively modest experimental resources of squeezed light sources, linear optics, and photon detection. In a realistic experimental setting, numerous effects can modify the complexity of the sampling, in particular loss, partial distinguishability of the photons, and the use of threshold detectors rather than photon counting detectors. In this paper, we investigate GBS with partial distinguishability using an approach based on virtual modes and indistinguishability efficiency. We develop a model using these concepts and derive the probabilities of measuring a specific output pattern from partially distinguishable and lossy GBS for both types of detectors. In the case of threshold detectors, the probability as calculated by the Torontonian is a special case under our framework. By analyzing the expressions of these probabilities we propose an efficient auxiliary classical simulation algorithm which can be used to calculate the probabilities. Our model and the auxiliary algorithm provide foundations for an approximation method for the probability calculation and simulation algorithms not only compatible with existing state-of-the-art simulation algorithms for ideal GBS but also reduce their complexities exponentially depending on the indistinguishability. Using the approximation method and the simulation algorithms we show how the boundary of quantum supremacy in GBS can be pushed further by partial distinguishability.
Abstract Boson Sampling is a task that is conjectured to be computationally hard for a classical computer, but which can be efficiently solved by linear-optical interferometers with Fock state inputs. Significant advances have been reported in the last few years, with demonstrations of small- and medium-scale devices, as well as implementations of variants such as Gaussian Boson Sampling. Besides the relevance of this class of computational models in the quest for unambiguous experimental demonstrations of quantum advantage, recent results have also proposed the first applications for hybrid quantum computing. Here, we introduce the adoption of non-linear photon–photon interactions in the Boson Sampling framework, and analyze the enhancement in complexity via an explicit linear-optical simulation scheme. By extending the computational expressivity of Boson Sampling, the introduction of non-linearities promises to disclose novel functionalities for this class of quantum devices. Hence, our results are expected to lead to new applications of near-term, restricted photonic quantum computers.
We present a classical algorithm that approximately samples from the output distribution of certain noisy Boson Sampling experiments. This algorithm is inspired by a recent result of Aharonov, Gao, Landau, Liu and Vazirani and makes use of an observation originally due to Kalai and Kindler that the output probability of Boson Sampling experiments with a Gaussian noise model can be approximated by sparse low-degree polynomials. This observation alone does not suffice for classical sampling, because its marginal probabilities might not be approximated by sparse low-degree polynomials, and furthermore, the approximated probabilities might be negative. We solve this problem by employing the first quantization representation to give an algorithm for computing the marginal probabilities of these experiments. We prove that when the overall noise rate is constant, the algorithm runs in time quasi-polynomial in the number of input photons N and accuracy. When the overall noise rate scales as 1−x1γ for constant x1 and γ=Ω(logN), the running time becomes polynomial. Furthermore, we study noisy Boson Sampling with practically relevant noise models such as partial distinguishability and photon loss. We show that the same technique does not immediately apply in these settings, leaving open the possibility of a scalable demonstration of noisy quantum advantage for these noise models in certain parameter regimes.