Boson sampling is a computational problem that has recently been proposed as a candidate to obtain an unequivocal quantum computational advantage. The problem consists in sampling from the output distribution of indistinguishable bosons in a linear interferometer. There is strong evidence that such an experiment is hard to classically simulate, but it is naturally solved by dedicated photonic quantum hardware, comprising single photons, linear evolution, and photodetection. This prospect has stimulated much effort resulting in the experimental implementation of progressively larger devices. We review recent advances in photonic boson sampling, describing both the technological improvements achieved and the future challenges. We also discuss recent proposals and implementations of variants of the original problem, theoretical issues occurring when imperfections are considered, and advances in the development of suitable techniques for validation of boson sampling experiments. We conclude by discussing the future application of photonic boson sampling devices beyond the original theoretical scope.
Boson sampling is a computational problem that has recently been proposed as a candidate to obtain an unequivocal quantum computational advantage. The problem consists in sampling from the output distribution of indistinguishable bosons in a linear interferometer. There is strong evidence that such an experiment is hard to classically simulate, but it is naturally solved by dedicated photonic quantum hardware, comprising single photons, linear evolution, and photodetection. This prospect has stimulated much effort resulting in the experimental implementation of progressively larger devices. We review recent advances in photonic boson sampling, describing both the technological improvements achieved and the future challenges. We also discuss recent proposals and implementations of variants of the original problem, theoretical issues occurring when imperfections are considered, and advances in the development of suitable techniques for validation of boson sampling experiments. We conclude by discussing the future application of photonic boson sampling devices beyond the original theoretical scope.
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.
The strong efforts towards the realization of scalable quantum computing are motivated by the promise of super-polynomial speed-up in several computational tasks. A first fundamental step in this route is to provide concrete evidence of ‘quantum supremacy'. Such a regime is obtained when a quantum device is capable of solving a specific problem faster than the best classical hardware. A serious attempt to provide a first demonstration of quantum speed-up with affordable resources is represented by boson sampling [1,2], a non-universal quantum-computational protocol exploiting indistinguishable single photons and linear optical devices. In this context, strong theoretical evidence has been reported that the interference pattern generated by a boson sampler is hard to simulate with classical resources, this pattern being related to the calculation of a hard-to-compute quantity known as a matrix permanent. Formal achievement of the regime of quantum supremacy will answer two very relevant questions: Are we able to benefit from the power of quantum mechanics or does there exist a fundamental reason why this achievement is forbidden? Once this regime has been achieved, are we able to certify the correct functioning of the quantum boson samplers or do we face an undecidability problem? Starting from these intriguing and promising theoretical results, an experimental race kicked off with the aim of reaching the quantum supremacy regime with boson sampling by employing a photonic platform [3]. A large amount of effort has been devoted to pushing the limits of current photonic systems [1], in order to significantly increase the size (number of photons and optical modes) that can be handled with a quantum device. In parallel to this quest for improved quantum performance, it is fundamental to benchmark the limits of a classical simulation of boson sampling. More specifically, in the race for quantum supremacy, what is the best possible classical simulation that can be performed? Such an analysis would be necessary to define the computational capacity possessed by such a classical agent to perform the task (see Fig. 1). In the race for quantum supremacy, a user who employs the best classical hardware and software, and a second agent who exploits a quantum device compete to solve the boson sampling task faster. In a recent article, Wu et al. [4] have provided a fundamental step to define and push the limits of a classical simulation of boson sampling. The authors have employed Tianhe-2, one of the world's most powerful super-computers, to perform such a task. More specifically, by using such high-performance computing hardware and by employing the fastest algorithm to date, Wu et al. have shown that calculating the permanent of a |50×50| matrix can be performed in 100 min. Recent results [5] have shown that this computation corresponds to the classical hardness of drawing a 50-photon sample from a boson sampling distribution. The strong computational capacity of Tianhe-2 also allowed us to address the precision that the known fastest classical algorithms can reach in such a large-scale calculation. This latter aspect is indeed of fundamental importance, since any reliable classical computation must be accompanied by an appropriate error analysis. The study reported in Ref. [4] represents by far the largest calculation to date related to the classical simulation of boson sampling, whose relevance can be found in two different but related aspects. First, it raises the bar for any quantum implementation aimed at reaching quantum advantage, and provides a fundamental benchmark to which any photonic hardware must compare. This result suggests that a larger effort must be dedicated to pushing quantum technologies in this direction. Second, improved classical simulation also has important consequences in the context of boson sampling certification, i.e. the verification that a quantum device is correctly performing the required task. Indeed, first validation procedures in the quantum advantage regime must be assisted by powerful classical computational resources that, while requiring longer processing time than quantum hardware, will necessarily have to perform complex calculations.
Photonics is a promising platform for demonstrating a quantum computational advantage (QCA) by outperforming the most powerful classical supercomputers on a well-defined computational task. Despite this promise, existing proposals and demonstrations face challenges. Experimentally, current implementations of Gaussian boson sampling (GBS) lack programmability or have prohibitive loss rates. Theoretically, there is a comparative lack of rigorous evidence for the classical hardness of GBS. In this work, we make progress in improving both the theoretical evidence and experimental prospects. We provide evidence for the hardness of GBS, comparable to the strongest theoretical proposals for QCA. We also propose a QCA architecture we call high-dimensional GBS, which is programmable and can be implemented with low loss using few optical components. We show that particular algorithms for simulating GBS are outperformed by high-dimensional GBS experiments at modest system sizes. This work thus opens the path to demonstrating QCA with programmable photonic processors.
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.
Quantum computation, aiming at tackling hard problems beyond classical approaches, has been flourishing with each passing day. Unfortunately, a fully scalable and fault-tolerant universal quantum computer remains challenging based on the current technology. Boson sampling, first proposed by Aaronson and Arkhipov, is commonly believed as the most promising candidate to reach the intermediate quantum computational milestone, namely, quantum supremacy. Following this leading proposal, many experimental implementations as well as variants of boson sampling have been shown. However, most of these works are limited to small scale and cannot fulfill the permanent-of-Gaussians conjecture. Here, we experimentally demonstrate the largest scale boson sampling in the collision-free dominant regime using multi-port interferometer in a 3D photonic chip. We measure all 6,545 no-collision output combinations and validate the experimental results. Our work shows the potential of 3D photonic chip platform and represents a solid step toward large scale boson sampling.
Boson Sampling is a computational paradigm representing one of the most viable and pursued approaches to demonstrate the regime of quantum advantage. Recent results have demonstrated significant technological leaps in single-photon generation and detection, leading to progressively larger experimental instances of Boson Sampling experiments in different photonic systems. However, a crucial requirement for a fully-fledged platform solving this problem is the capability of implementing large scale interferometers, that must simultaneously exhibit low losses, high degree of reconfigurability and the realization of arbitrary transformations. In this work, we move a step forward in this direction by demonstrating the adoption of a novel compact and reconfigurable 3D-integrated platform for photonic Boson Sampling. We perform 3- and 4-photon experiments by using such platform, showing the possibility of programming the circuit to implement a large number of unitary transformations. These results show that such compact and highly-reconfigurable layout can be scaled up to experiments with larger number of photon and modes, and can provide a viable direction for hybrid computing with photonic processors.