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

Physical Review A

Performance of randomized estimators of the Hafnian of a non-negative matrix

Alexey Uvarov, Dmitry Vinichenko

Published Apr 17, 2024• 0 citations
Publisher

Abstract

Gaussian boson samplers aim to demonstrate quantum advantage by performing a sampling task believed to be classically hard. The probabilities of individual outcomes in the sampling experiment are determined by the Hafnian of an appropriately constructed symmetric matrix. For non-negative matrices, there is a family of randomized estimators of the Hafnian based on generating a particular random matrix and calculating its determinant. While these estimators are unbiased (the mean of the determinant is equal to the Hafnian of interest), their variance may be so high as to prevent an efficient estimation. Here we investigate the performance of two such estimators, which we call the Barvinok and Godsil-Gutman estimators. We find that, in general, both estimators perform well for adjacency matrices of random graphs, demonstrating a slow growth of variance with the size of the problem. Nonetheless, there are simple examples where both estimators show high variance, requiring an exponential number of samples. In addition, we calculate the asymptotic behavior of the variance for the complete graph. Finally, we simulate the Gaussian boson sampling using the Godsil-Gutman estimator and show that this technique can successfully reproduce low-order correlation functions.

DOI
10.1103/physreva.109.042415

Related papers

On randomized estimators of the Hafnian of a nonnegative matrix

Alexey Uvarov, Dmitry Vinichenko

Gaussian Boson Samplers aim to demonstrate quantum advantage by performing a sampling task believed to be classically hard. The probabilities of individual outcomes in the sampling experiment are determined by the Hafnian of an appropriately constructed symmetric matrix. For nonnegative matrices, there is a family of randomized estimators of the Hafnian based on generating a particular random matrix and calculating its determinant. While these estimators are unbiased (the mean of the determinant is equal to the Hafnian of interest), their variance may be so high as to prevent an efficient estimation. Here we investigate the performance of two such estimators, which we call the Barvinok and Godsil-Gutman estimators. We find that in general both estimators perform well for adjacency matrices of random graphs, demonstrating a slow growth of variance with the size of the problem. Nonetheless, there are simple examples where both estimators show high variance, requiring an exponential number of samples. In addition, we calculate the asymptotic behavior of the variance for the complete graph. Finally, we simulate the Gaussian Boson Sampling using the Godsil-Gutman estimator and show that this technique can successfully reproduce low-order correlation functions.

arXiv:2312.10143•Dec 15, 2023•0 citations

Gaussian boson sampling for perfect matchings of arbitrary graphs

Kamil Brádler, Pierre-Luc Dallaire-Demers, Patrick Rebentrost +2 more

A famously hard graph problem with a broad range of applications is computing the number of perfect matchings, that is, the number of unique and complete pairings of the vertices of a graph. We propose a method to estimate the number of perfect matchings of undirected graphs based on the relation between Gaussian boson sampling and graph theory. The probability of measuring zero or one photons in each output mode is directly related to the hafnian of the adjacency matrix, and thus to the number of perfect matchings of a graph. We present encodings of the adjacency matrix of a graph into a Gaussian state and show strategies to boost the sampling success probability for the studied graphs. With our method, a Gaussian boson sampling device can be used to estimate the number of perfect matchings significantly faster and with lower-energy consumption compared to a classical computer.

arXiv:1712.06729•Physical Review A•Sep 10, 2018•96 citations

Using Gaussian Boson Samplers to Approximate Gaussian Expectation Problems

Jørgen Ellegaard Andersen, Shan Shan

Gaussian Boson Sampling (GBS) have shown advantages over classical methods for performing some specific sampling tasks. To fully harness the computational power of GBS, there has been great interest in identifying their practical applications. In this study, we explore the use of GBS samples for computing a numerical approximation to the Gaussian expectation problem, that is to integrate a multivariate function against a Gaussian distribution. We propose two estimators using GBS samples, and show that they both can bring an exponential speedup over the plain Monte Carlo (MC) estimator. Precisely speaking, the exponential speedup is defined in terms of the guaranteed sample size for these estimators to reach the same level of accuracy $ε$ and the same success probability $δ$ in the $(ε, δ)$ multiplicative error approximation scheme. We prove that there is an open and nonempty subset of the Gaussian expectation problem space for such computational advantage.

arXiv:2502.19336•Feb 26, 2025•0 citations

Using an imperfect photonic network to implement random unitaries

Roel Burgwal, William R. Clements, Devin H. Smith +4 more

Boson Sampling has emerged as a tool to explore the advantages of quantum over classical computers as it does not require a universal control over the quantum system, which favours current photonic experimental platforms.Here, we introduce Gaussian Boson Sampling, a classically hard-to-solve problem that uses squeezed states as a non-classical 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 approach leads to a more efficient photonic boson sampler with significant advantages in generation probability and measurement time over currently existing protocols.

Optics Express•Oct 31, 2017•103 citations

Gaussian Boson Sampling

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

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.

arXiv:1612.01199•Physical Review Letters•Oct 23, 2017•503 citations

Efficient classical algorithm for estimating linear statistics of Boson Sampling

Benoit Seron, Hugo Thomas, Eduardo Araujo +3 more

Boson Sampling is a prominent candidate for the demonstration of quantum computational advantage but it remains unclear whether a large-scale boson sampler can find useful computational applications. The challenge is that to use a boson sampler to estimate, for example, a physical observable, it is necessary to coarse grain the outcome distribution, owing to the exponential size of the outcome space and the anti-concentration properties of the Boson Sampling distribution. In this work, we analyse the complexity of a specific type of coarse-graining of Boson Sampling distributions based on linear functions of the output photon occupation numbers, which we refer to as linear statistics. We present an efficient classical algorithm for approximating linear statistics of boson samplers within additive error for different kinds of input states, such as Fock states and squeezed states. This allows us to unify in the same framework recent results on efficient quantum-inspired classical algorithms for simulating molecular vibronic spectra, or efficient classical approximations of coarse-grained distributions based on detector binning. Additionally, we show how our algorithm can be used to classically evaluate a proposed one-way function based on Boson Sampling, while other proposals for cryptographic applications escape our classical simulation techniques. We leave open the question of classical simulability of non-linear statistics and connect it to the problem of computing transition amplitudes of linear-optical circuits with one layer of interactions.

quant-pharXiv:2609.35447•Sep 29, 2026•0 citations
Gaussian boson samplers aim to demonstrate quantum advantage by performing a sampling task believed to be classically hard. The probabilities of individual outcomes in the sampling experiment are determined by the Hafnian of an appropriately constructed symmetric matrix. For non-negative matrices, there is a family of randomized estimators of the Hafnian based on generating a particular random matrix and calculating its determinant. While these estimators are unbiased (the mean of the determinant is equal to the Hafnian of interest), their variance may be so high as to prevent an efficient estimation. Here we investigate the performance of two such estimators, which we call the Barvinok and Godsil-Gutman estimators. We find that, in general, both estimators perform well for adjacency matrices of random graphs, demonstrating a slow growth of variance with the size of the problem. Nonetheless, there are simple examples where both estimators show high variance, requiring an exponential number of samples. In addition, we calculate the asymptotic behavior of the variance for the complete graph. Finally, we simulate the Gaussian boson sampling using the Godsil-Gutman estimator and show that this technique can successfully reproduce low-order correlation functions.
Gaussian Boson Samplers aim to demonstrate quantum advantage by performing a sampling task believed to be classically hard. The probabilities of individual outcomes in the sampling experiment are determined by the Hafnian of an appropriately constructed symmetric matrix. For nonnegative matrices, there is a family of randomized estimators of the Hafnian based on generating a particular random matrix and calculating its determinant. While these estimators are unbiased (the mean of the determinant is equal to the Hafnian of interest), their variance may be so high as to prevent an efficient estimation. Here we investigate the performance of two such estimators, which we call the Barvinok and Godsil-Gutman estimators. We find that in general both estimators perform well for adjacency matrices of random graphs, demonstrating a slow growth of variance with the size of the problem. Nonetheless, there are simple examples where both estimators show high variance, requiring an exponential number of samples. In addition, we calculate the asymptotic behavior of the variance for the complete graph. Finally, we simulate the Gaussian Boson Sampling using the Godsil-Gutman estimator and show that this technique can successfully reproduce low-order correlation functions.
A famously hard graph problem with a broad range of applications is computing the number of perfect matchings, that is, the number of unique and complete pairings of the vertices of a graph. We propose a method to estimate the number of perfect matchings of undirected graphs based on the relation between Gaussian boson sampling and graph theory. The probability of measuring zero or one photons in each output mode is directly related to the hafnian of the adjacency matrix, and thus to the number of perfect matchings of a graph. We present encodings of the adjacency matrix of a graph into a Gaussian state and show strategies to boost the sampling success probability for the studied graphs. With our method, a Gaussian boson sampling device can be used to estimate the number of perfect matchings significantly faster and with lower-energy consumption compared to a classical computer.
Gaussian Boson Sampling (GBS) have shown advantages over classical methods for performing some specific sampling tasks. To fully harness the computational power of GBS, there has been great interest in identifying their practical applications. In this study, we explore the use of GBS samples for computing a numerical approximation to the Gaussian expectation problem, that is to integrate a multivariate function against a Gaussian distribution. We propose two estimators using GBS samples, and show that they both can bring an exponential speedup over the plain Monte Carlo (MC) estimator. Precisely speaking, the exponential speedup is defined in terms of the guaranteed sample size for these estimators to reach the same level of accuracy εεε and the same success probability δδδ in the (ε,δ)(ε, δ)(ε,δ) multiplicative error approximation scheme. We prove that there is an open and nonempty subset of the Gaussian expectation problem space for such computational advantage.
Boson Sampling has emerged as a tool to explore the advantages of quantum over classical computers as it does not require a universal control over the quantum system, which favours current photonic experimental platforms.Here, we introduce Gaussian Boson Sampling, a classically hard-to-solve problem that uses squeezed states as a non-classical 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 approach leads to a more efficient photonic boson sampler with significant advantages in generation probability and measurement time over currently existing protocols.
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.
Boson Sampling is a prominent candidate for the demonstration of quantum computational advantage but it remains unclear whether a large-scale boson sampler can find useful computational applications. The challenge is that to use a boson sampler to estimate, for example, a physical observable, it is necessary to coarse grain the outcome distribution, owing to the exponential size of the outcome space and the anti-concentration properties of the Boson Sampling distribution. In this work, we analyse the complexity of a specific type of coarse-graining of Boson Sampling distributions based on linear functions of the output photon occupation numbers, which we refer to as linear statistics. We present an efficient classical algorithm for approximating linear statistics of boson samplers within additive error for different kinds of input states, such as Fock states and squeezed states. This allows us to unify in the same framework recent results on efficient quantum-inspired classical algorithms for simulating molecular vibronic spectra, or efficient classical approximations of coarse-grained distributions based on detector binning. Additionally, we show how our algorithm can be used to classically evaluate a proposed one-way function based on Boson Sampling, while other proposals for cryptographic applications escape our classical simulation techniques. We leave open the question of classical simulability of non-linear statistics and connect it to the problem of computing transition amplitudes of linear-optical circuits with one layer of interactions.