Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:1612.01199 · Physical Review Letters

Gaussian Boson Sampling

Craig S. Hamilton, Regina Kruse, Linda Sansoni, Sonja Barkhofen, Christine Silberhorn, Igor Jex

Published Oct 23, 2017• 566 citations
arXivHTMLPDF

Abstract

Boson sampling has emerged as a tool to explore the advantages of quantum over classical computers as it does not require universal control over the quantum system, which favors current photonic experimental platforms. Here, we introduce Gaussian Boson sampling, a classically hard-to-solve problem that uses squeezed states as a nonclassical resource. We relate the probability to measure specific photon patterns from a general Gaussian state in the Fock basis to a matrix function called the Hafnian, which answers the last remaining question of sampling from Gaussian states. Based on this result, we design Gaussian Boson sampling, a #P hard problem, using squeezed states. This demonstrates that Boson sampling from Gaussian states is possible, with significant advantages in the photon generation probability, compared to existing protocols.

DOI
10.1103/physrevlett.119.170501

Related papers

Classical Algorithms for Function Computation in Gaussian Boson Sampling

Ruoting Dou, Hao Zhan, Shengjun Wu +2 more

Gaussian boson sampling (GBS) seeks quantum advantage by sampling photon-number patterns generated with squeezed inputs and passive linear optics. Many proposed GBS applications instead target function computation by applying functions to mode-resolved photon-number outcomes---a natural form of experimental postprocessing that produces classical outputs. Sampling hardness alone, however, does not determine the complexity of these tasks. By analyzing the irreducible decomposition of fixed-photon-number operator spaces, we prove that the expectation value of every such function in the average case over passive linear-optical networks can be classically evaluated for inputs with finite squeezing strength. We also provide a classical algorithm that estimates this value to inverse-polynomial additive error. The result provides new theoretical tools for analyzing linear-optical quantum systems, helps clarify the origin of current GBS hardness evidence, and inspires new applications of GBS with genuine quantum advantages.

quant-pharXiv:2609.38882•Oct 1, 2026•1 citation

Detailed study of Gaussian boson sampling

Regina Kruse, Craig S. Hamilton, Linda Sansoni +3 more

Since the development of boson sampling, there has been a quest to construct more efficient and experimentally feasible protocols to test the computational complexity of sampling from photonic states. In this paper, we interpret and extend the results presented previously [Phys. Rev. Lett. 119, 170501 (2017)]. We derive an expression that relates the probability to measure a specific photon output pattern from a Gaussian state to the Hafnian matrix function and use it to design a Gaussian boson sampling protocol. Then, we discuss the advantages that this protocol has relative to other photonic protocols and the experimental requirements for Gaussian boson sampling. Finally, we relate it to the previously most general protocol, scattershot boson sampling [Phys. Rev. Lett. 113, 100502 (2014)].

arXiv:1801.07488•Physical Review A•Sep 18, 2019•210 citations

Gaussian Boson Sampling Complexity

Andrew Tanggara

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.

•Jan 1, 2021•0 citations

Boson sampling from non-Gaussian states

Craig S. Hamilton, Igor Jex

Boson sampling has emerged as an important tool to demonstrate the difference between quantum and classical computers and has attracted the interest of experimentalists and theoreticians. In this work we study boson sampling from general, single-mode states using a scheme that can generate any such state by combining Gaussian states and photon number measurements. We derive a formula that can be used to calculate the output photon number probabilities of these states after they travel through a linear interferometer. This extends the Boson sampling protocol to the widest array of possible single-mode states and from this we show that the complexity scaling of all such states is similar and hence there is no complexity advantage of using complex input states over simpler ones.

arXiv:2403.17183•Physical Review A•May 15, 2024•3 citations

Non-linear Boson Sampling

Nicolò Spagnolo, Daniel J. Brod, Ernesto F. Galvão +1 more

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.

arXiv:2110.13788•npj Quantum Information•Jan 9, 2023•33 citations

Gaussian boson sampling with click-counting detectors

Gabriele Bressanini, Hyukjoon Kwon, M. S. Kim

Gaussian boson sampling constitutes a prime candidate for an experimental demonstration of quantum advantage within reach with current technological capabilities. The original proposal employs photon-number-resolving detectors, however, these are not widely available. Nevertheless, inexpensive threshold detectors can be combined into a single click-counting detector to achieve approximate photon-number resolution. We investigate the problem of sampling from a general multimode Gaussian state using click-counting detectors and show that the probability of obtaining a given outcome is related to a matrix function which is dubbed as the Kensingtonian. We show how the Kensingtonian relates to the Torontonian and the Hafnian, thus bridging the gap between known Gaussian boson sampling variants. We then prove that, under standard complexity-theoretical conjectures, the model cannot be simulated efficiently. Published by the American Physical Society 2024

arXiv:2305.00853•Physical Review A•Feb 12, 2024•4 citations
Boson sampling has emerged as a tool to explore the advantages of quantum over classical computers as it does not require universal control over the quantum system, which favors current photonic experimental platforms. Here, we introduce Gaussian Boson sampling, a classically hard-to-solve problem that uses squeezed states as a nonclassical resource. We relate the probability to measure specific photon patterns from a general Gaussian state in the Fock basis to a matrix function called the Hafnian, which answers the last remaining question of sampling from Gaussian states. Based on this result, we design Gaussian Boson sampling, a #P hard problem, using squeezed states. This demonstrates that Boson sampling from Gaussian states is possible, with significant advantages in the photon generation probability, compared to existing protocols.
Gaussian boson sampling (GBS) seeks quantum advantage by sampling photon-number patterns generated with squeezed inputs and passive linear optics. Many proposed GBS applications instead target function computation by applying functions to mode-resolved photon-number outcomes---a natural form of experimental postprocessing that produces classical outputs. Sampling hardness alone, however, does not determine the complexity of these tasks. By analyzing the irreducible decomposition of fixed-photon-number operator spaces, we prove that the expectation value of every such function in the average case over passive linear-optical networks can be classically evaluated for inputs with finite squeezing strength. We also provide a classical algorithm that estimates this value to inverse-polynomial additive error. The result provides new theoretical tools for analyzing linear-optical quantum systems, helps clarify the origin of current GBS hardness evidence, and inspires new applications of GBS with genuine quantum advantages.
Since the development of boson sampling, there has been a quest to construct more efficient and experimentally feasible protocols to test the computational complexity of sampling from photonic states. In this paper, we interpret and extend the results presented previously [Phys. Rev. Lett. 119, 170501 (2017)]. We derive an expression that relates the probability to measure a specific photon output pattern from a Gaussian state to the Hafnian matrix function and use it to design a Gaussian boson sampling protocol. Then, we discuss the advantages that this protocol has relative to other photonic protocols and the experimental requirements for Gaussian boson sampling. Finally, we relate it to the previously most general protocol, scattershot boson sampling [Phys. Rev. Lett. 113, 100502 (2014)].
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.
Boson sampling has emerged as an important tool to demonstrate the difference between quantum and classical computers and has attracted the interest of experimentalists and theoreticians. In this work we study boson sampling from general, single-mode states using a scheme that can generate any such state by combining Gaussian states and photon number measurements. We derive a formula that can be used to calculate the output photon number probabilities of these states after they travel through a linear interferometer. This extends the Boson sampling protocol to the widest array of possible single-mode states and from this we show that the complexity scaling of all such states is similar and hence there is no complexity advantage of using complex input states over simpler ones.
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.
Gaussian boson sampling constitutes a prime candidate for an experimental demonstration of quantum advantage within reach with current technological capabilities. The original proposal employs photon-number-resolving detectors, however, these are not widely available. Nevertheless, inexpensive threshold detectors can be combined into a single click-counting detector to achieve approximate photon-number resolution. We investigate the problem of sampling from a general multimode Gaussian state using click-counting detectors and show that the probability of obtaining a given outcome is related to a matrix function which is dubbed as the Kensingtonian. We show how the Kensingtonian relates to the Torontonian and the Hafnian, thus bridging the gap between known Gaussian boson sampling variants. We then prove that, under standard complexity-theoretical conjectures, the model cannot be simulated efficiently. Published by the American Physical Society 2024