Gaussian boson sampling (GBS) is a promising candidate for an experimental demonstration of quantum advantage using photons. However, sufficiently large noise might hinder a GBS implementation from entering the regime where quantum speedup is achievable. Here, we investigate how thermal noise affects the classical intractability of generic quantum optical sampling experiments, GBS being a particular instance of the latter. We do so by establishing sufficient conditions for an efficient simulation to be feasible, expressed in the form of inequalities between the relevant parameters that characterize the system and its imperfections. We demonstrate that the addition of thermal noise—modeled by (passive) linear optical interaction between the system and a Markovian thermal bath—has the effect of tightening the constraints on the remaining noise parameters, required to show quantum advantage. Furthermore, we show that there exists a threshold temperature, under the assumption of a uniform loss rate, at which quantum sampling experiments become classically simulable, and provide an intuitive physical interpretation by relating this occurrence with the disappearance of the quantum state's nonclassical properties. Published by the American Physical Society 2024
Gaussian boson sampling (GBS) is a promising candidate for an experimental demonstration of quantum advantage using photons. However, sufficiently large noise might hinder a GBS implementation from entering the regime where quantum speedup is achievable. Here, we investigate how thermal noise affects the classical intractability of generic quantum optical sampling experiments, GBS being a particular instance of the latter. We do so by establishing sufficient conditions for an efficient simulation to be feasible, expressed in the form of inequalities between the relevant parameters that characterize the system and its imperfections. We demonstrate that the addition of thermal noise—modeled by (passive) linear optical interaction between the system and a Markovian thermal bath—has the effect of tightening the constraints on the remaining noise parameters, required to show quantum advantage. Furthermore, we show that there exists a threshold temperature, under the assumption of a uniform loss rate, at which quantum sampling experiments become classically simulable, and provide an intuitive physical interpretation by relating this occurrence with the disappearance of the quantum state's nonclassical properties. Published by the American Physical Society 2024
As a promising candidate for exhibiting quantum computational supremacy, Gaussian boson sampling (GBS) is designed to exploit the ease of experimental preparation of Gaussian states. However, sufficiently large and inevitable experimental noise might render GBS classically simulable. In this work, we formalize this intuition by establishing a sufficient condition for approximate polynomial-time classical simulation of noisy GBS-in the form of an inequality between the input squeezing parameter, the overall transmission rate, and the quality of photon detectors. Our result serves as a nonclassicality test that must be passed by any quantum computational supremacy demonstration based on GBS. We show that, for most linear-optical architectures, where photon loss increases exponentially with the circuit depth, noisy GBS loses its quantum advantage in the asymptotic limit. Our results thus delineate intermediate-sized regimes where GBS devices might considerably outperform classical computers for modest noise levels. Finally, we find that increasing the amount of input squeezing is helpful to evade our classical simulation algorithm, which suggests a potential route to mitigate photon loss.
Gaussian boson sampling (GBS) is a prominent candidate for the experimental demonstration of quantum advantage. However, while the current implementations of GBS are unavoidably subject to noise, the robustness of the classical intractability of GBS against noise remains largely unexplored. In this work, we establish the complexity-theoretic foundations for the classical intractability of noisy GBS under photon loss, which is a dominant source of imperfection in current implementations. We identify the loss threshold below which lossy GBS maintains the same complexity-theoretic level as ideal GBS, and show that this holds when at most a logarithmic fraction of photons is lost. We additionally derive an intractability criterion for the loss rate through a direct quantification of the statistical distance between ideal and lossy GBS. This work presents the first rigorous characterization of classically intractable regimes of lossy GBS, thereby serving as a crucial step toward demonstrating quantum advantage with near-term implementations.
Quantum computers solve intractable problems which classically require an exponentially long time to compute. With the development of large-scale experiments that claim quantum advantage, a vital issue has now emerged. What are the errors, and how do they affect the complexity of the problem solved? Large-scale Gaussian boson sampling (GBS) experiments give an example in which random numbers are generated. Despite classical hardness, these have computable benchmarks for checking data validity. While there are other quantum computing architectures, Gaussian boson sampling is uniquely testable at all scales. Several large, pioneering quantum computing (QC) experiments have been carried out to investigate quantum advantage. Here, we introduce a highly scalable but classical algorithm that can solve GBS approximately. Our numerical simulation of the output count data is closer to the exact solution than current experiments up to 1152 modes. This algorithm outperforms all previous classical, approximate algorithms and scales efficiently to larger experiments. Our results show that effects beyond losses can cause the errors that allow classical simulability. This work will lead to more precise algorithms and is a step towards understanding how QC quantum advantage is affected by the underlying physics.
Boson sampling, a computational problem conjectured to be hard to simulate on a classical machine, is a promising candidate for an experimental demonstration of quantum advantage using bosons. However, inevitable experimental noise and imperfections, such as loss in the interferometer and random counts at the detectors, could challenge the sampling task from entering the regime where quantum advantage is achievable. In this work we introduce higher-order nonlinearities as a means to enhance the computational complexity of the problem and the protocol's robustness against noise, i.e., to increase the noise threshold that allows us to perform an efficient classical simulation of the problem. Using a phase-space method based on the negativity volume of the relevant quasiprobability distributions, we establish a necessary nonclassicality condition that any experimental proof of quantum advantage must satisfy. Our results indicate that the addition of single-mode Kerr nonlinearity at the input-state preparation level, while retaining a linear-optical evolution, makes the boson-sampling protocol more robust against noise and consequently relaxes the constraints on the noise parameters required to show quantum advantage.
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.
It remains questionable whether all physically realizable computational model can be simulated by currently available digital computer in an efficient manner. The theory of Quantum Mechanics offers an answer to this question through one of its branches that intersects with Computer Science, known as Quantum Computing. It claims that current computers, which is operating based on classical mechanics cannot efficiently simulate quantum mechanical process. Under this claim, a computer that is operating based on quantum mechanics holds more computational power than classical computers, promising a possibility to computationally solve problems that are classically intractable. To show that this claim holds, numerous quantum computational models have been proposed and analyzed through the lens of Computational Complexity Theory, providing a rigorous notion of efficiency. Models that are more feasible experimentally, although not necessarily universal, have also been of a particular interests given the numerous complicated challenges surrounding the experimental implementation of a universal quantum computer. One of this non-universal models is called Gaussian Boson Sampling (GBS), which embraces the methods of Quantum Optics by sampling the number of photon outputs from a linear optical network as a means to process quantum information. Compared to its prototype model, Boson Sampling, GBS is more experimentally feasible due to its method of generating photon that is based on the Continuous Variable (CV) paradigm of Quantum Information. Nevertheless as with Boson Sampling, it was also shown that classical simulation of GBS cannot be performed efficiently under some highly plausible conjectures. In the work presented in this thesis, we probe the complexity of classically constructing the probability distribution induced by GBS using the method of Quantum Homodyne Tomography. Instead of photon number measurement, this method further embraces the CV paradigm in the measurement of GBS by using Homodyne measurements that outputs real numbers. Sample data obtained from the measurement outcomes is then classically processed using Pattern Functions, which we use to approximate the probability distribution of GBS. A series of computer simulations that approximates some probability values of GBS are presented here, which shows that the number of samples needed to decrease the error of the approximation increases rapidly for more accurate approximation. We have derived a bound for the approximation error which can be achieved given that the sampled data satisfies a certain statistical property. This statistical property can eventually be satisfied as the number of Homodyne samples increases. Having shown another evidence for the complexity of approximating GBS using Homodyne Tomography, we further investigate the nature of the complexity of GBS by analyzing its classical-quantum computational boundary in the spectrum of amount of noise present in a GBS setup. In doing this, we built our discussions on the measure of non-classicality using the presence of negative values in the Quasi-probability distribution (QPD) representation of states of a quantum system. We then discuss existing results that shows the possibility of efficient classical simulation of a quantum computational model given a sufficient amount of noise. These results impose a necessary criteria of the minimum amount of noise that an experiment has to surpass in order for it to be impossible to simulate classically in an efficient manner. We extend this idea for GBS, where we propose a modified GBS where we consider noise in its measurements that opens a way for a possible formulation of a noise condition that a GBS experiment has to fulfill to rule out possible efficient classical simulation. To further probe the classical-quantum computational boundary, we also propose a different quantum computational model called the Photon-added Thermal State CV-Sampling (PATS CVS), which can be formulated similarly to our noisy GBS model. We then discuss existing results that analyzes the negativity of the QPD representation of a noisy Photon-added Thermal state (PATS), which constitutes the inputs for PATS CVS. Using the result that shows the quantum-classical transition in terms of the QPD negativity for a PATS state when the amount of noise changes, we discuss the potential of PATS CVS model as a possible avenue to further probe the transition between efficiently simulable and non-efficiently simulable quantum mechanical experiment.