⚛️ quantum physics

Simulating Gaussian boson sampling on graphs in polynomial time

The paper demonstrates that specific distributions related to Gaussian Boson Sampling and Boson Sampling on graphs, which are commonly used in practical applications, can be efficiently sampled classically in polynomial time, thereby negating the possibility of exponential quantum speedup for these scenarios.

Original author: Konrad Anand, Zongchen Chen, Mary Cryan, Graham Freifeld, Leslie Ann Goldberg, Heng Guo, Xinyuan Zhang

Published 2026-11-09

📖 5 min read🧠 Deep dive

CC BY 4.0

Original author: Konrad Anand, Zongchen Chen, Mary Cryan, Graham Freifeld, Leslie Ann Goldberg, Heng Guo, Xinyuan Zhang

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the author. For technical accuracy, refer to the original paper. Read full disclaimer

In the strange world of quantum physics, there are particles called bosons that behave in ways no everyday object ever could. When scientists send these particles through a complex network of mirrors and beam splitters, they create a pattern of outcomes that is incredibly difficult to predict. This setup, known as boson sampling, has long been considered a promising way to prove that quantum computers can do things ordinary computers simply cannot. The hope has been that while a quantum machine could generate these patterns in a flash, a classical computer would need to spend more time than the age of the universe to figure them out. This potential gap between the two types of machines is what researchers call "quantum advantage," a holy grail that would signal a new era of computing power.

Recently, a specific version of this experiment called Gaussian boson sampling has gained significant attention. Instead of using simple single particles, this method uses a more complex state of light that is easier to produce in a lab. Because it is easier to build, many teams have rushed to construct these machines, hoping to use them to solve difficult problems in mathematics and science, such as finding the best way to group data or analyzing the structure of complex networks. The prevailing belief was that these machines were on the verge of outperforming the best supercomputers. However, a new study challenges this assumption, suggesting that for the specific tasks these machines are currently being used for, a standard computer might actually be just as fast.

A team of researchers from the University of Oxford, Georgia Institute of Technology, and the University of Edinburgh has demonstrated that the specific patterns generated by Gaussian boson sampling on graphs can be recreated by a classical computer in a reasonable amount of time. Their work focuses on the mathematical structure behind these experiments, showing that the probability of getting a certain result is tied to a counting problem involving perfect pairings within a network. While this counting problem is notoriously hard for general cases, the researchers found a clever way to simplify it for the specific graphs used in these experiments. They proved that by transforming the graph into a slightly larger, two-layered version of itself, they could use a well-known classical algorithm to sample the results efficiently.

The team showed that this classical method works for any graph, regardless of how dense or complex it is, and does so in a time that grows polynomially with the size of the input. In practical terms, this means that as the problem gets bigger, the time it takes for the computer to solve it increases at a manageable rate, rather than exploding into an impossible task. This finding directly addresses the question of whether these quantum machines offer an exponential speedup for the graph problems they are designed to solve. The authors conclude that for these specific applications, the quantum machine does not provide the massive advantage that was hoped for, because a classical computer can do the same job just as quickly.

The researchers also extended their findings to a related model of boson sampling where the input numbers are all positive. They constructed a similar bridge between the quantum distribution and a classical sampling problem, proving that this too can be solved efficiently. Their approach relies on a technique that has been around for decades but had not been applied in this specific way before. By carefully adjusting the weights of connections in a constructed network, they ensured that the classical algorithm could find the right answers without getting stuck. This work does not rule out the possibility of quantum advantage in other areas, but it draws a clear line around the current generation of graph-based experiments, showing that they are not the breakthrough some had anticipated.

The implications of this discovery are significant for the field of quantum computing. It suggests that the path to demonstrating a clear quantum advantage may be narrower than previously thought, at least for the applications that are currently being pursued. The researchers did not claim that quantum computers are useless; rather, they showed that for the specific task of sampling from these graph distributions, the quantum edge is not there. Their proof is rigorous and covers all possible graphs, leaving no room for the idea that a faster classical algorithm might be found later to replace their method. Instead, they have shown that the classical method already exists and is efficient.

This study serves as a crucial reality check for the field. It reminds us that while quantum mechanics offers incredible possibilities, the specific problems we choose to solve with it matter immensely. The researchers have provided a clear, mathematical demonstration that for the popular graph-based applications of Gaussian boson sampling, the quantum machine is not the only game in town. The classical computer, armed with the right strategy, can play the same game just as well. This does not diminish the value of the quantum hardware being built, but it does shift the focus, urging scientists to look for different types of problems where the quantum machine might truly shine. The work stands as a testament to the power of careful mathematical analysis in understanding the true capabilities of our emerging technologies.

Technical Summary: Simulating Gaussian Boson Sampling on Graphs in Polynomial Time

Problem Statement
The paper addresses the computational complexity of sampling from distributions related to Boson Sampling (BS) and Gaussian Boson Sampling (GBS). While Aaronson and Arkhipov [1] proposed BS as a model for demonstrating quantum advantage, assuming the permanent anti-concentration and permanent of Gaussian conjectures, classical sampling from the exact output distribution is believed to be intractable (collapsing the polynomial hierarchy). Similarly, GBS, a variant utilizing squeezed states to avoid specific photon source costs, has been proposed for solving hard graph problems such as counting perfect matchings, finding densest subgraphs, and graph isomorphism.

The central open question addressed is whether efficient classical algorithms exist for sampling from the GBS distribution on graphs, specifically the distribution $\mu_{GBS,G}$ , which is proportional to $c^{2|S|} \text{PM}(S)^2$ (where $\text{PM}(S)$ is the number of perfect matchings in the induced subgraph $G[S]$ ). Previous work by Zhang et al. [12] provided a fast algorithm only for very dense graphs, and Oh et al. [13] proposed a classical algorithm for a slightly different distribution (proportional to $\text{PM}(S)$ rather than $\text{PM}(S)^2$ ), leaving the non-negative GBS case open.

Methodology
The authors employ a reduction strategy that maps the target sampling distributions to the problem of sampling weighted perfect matchings in graphs. They leverage the Markov chain Monte Carlo (MCMC) algorithms developed by Jerrum and Sinclair [14] and Jerrum, Sinclair, and Vigoda [17], which allow for efficient approximate sampling of perfect matchings under specific conditions.

For Non-Negative Boson Sampling (Theorem 1.3):
The authors construct a bipartite graph $G$ from a given non-negative real matrix $A$ . The construction involves creating vertex sets $L_1, L_2$ and $R_1, R_2$ , with edges weighted by the entries of $A$ . By sampling a perfect matching from this constructed graph with specific edge weights, the marginal distribution over the matched vertices in $R_1$ approximates the Boson Sampling distribution $\mu_{BS}$ . The approximation error is controlled by a parameter $k$ (the number of copies of vertices), which is chosen to be sufficiently large ( $O(n^2/\varepsilon)$ ).
For Gaussian Boson Sampling on Graphs (Theorem 1.1):
The authors define the GBS distribution $\mu_{GBS,G}(S) \propto c^{2|S|} \text{PM}(S)^2$ . To sample this, they construct the Cartesian product of the input graph $G$ and an edge, denoted $G \square K_2$ .
- Construction: $G \square K_2$ consists of two copies of $G$ ( $G$ and $G'$ ) with edges connecting corresponding vertices.
- Weighting: Edges within the copies of $G$ and $G'$ (sets $E$ and $E'$ ) are assigned weight $c^2$ , while the edges connecting the copies (set $E_0$ ) are assigned weight $1$.
- Reduction: A perfect matching in $G \square K_2$ induces a subset $S \subseteq V$ (vertices in the original graph matched within their own copy). The probability of inducing a specific set $S$ is shown to be proportional to $c^{2|S|} \text{Haf}(A_S)^2$ , which equals $c^{2|S|} \text{PM}(S)^2$ for the induced subgraph.
- Efficiency Condition: The Jerrum-Sinclair algorithm requires that the ratio of near-perfect matchings to perfect matchings be bounded by a polynomial. To ensure this, the authors define a new weight function $\lambda'$ (scaled by $4n^2$ ) and prove that the ratio of the total weight of near-perfect matchings ( $Z'_{n-1}$ ) to the total weight of perfect matchings ( $Z'_n$ ) under this new weighting is bounded by a constant (specifically, $Z'_{n-1} \le Z'_n/2$ ). This is derived from Lemma 4.2, which establishes that the weighted sum ratio $Z_{n-1} < 2n^2 Z_n$ for the original weights, combined with the log-concavity of the matching polynomial (Heilmann and Lieb [20]) and the AM-GM inequality. This ensures the Markov chain mixes in polynomial time.

Key Contributions and Results
The paper presents two main theorems establishing polynomial-time classical algorithms:

Theorem 1.1 (GBS on Graphs): There exists an algorithm that, given a graph $G$ and a real parameter $c > 0$ , samples from a distribution $\varepsilon$ -close to $\mu_{GBS,G}$ in total variation distance. The running time is $O(\bar{c}mn^4 \log^2(nc/\varepsilon))$ , where $m=|E|$ , $n=|V|$ , and $\bar{c} = \max\{1, c\}$ . This result holds for all graphs, not just dense ones, and for any positive real $c$ .
Theorem 1.3 (Non-Negative Boson Sampling): There exists an algorithm that, given a non-negative real matrix $A$ (where $A$ is not necessarily a truncated unitary matrix), samples from a distribution $\varepsilon$ -close to the Boson Sampling distribution $\mu_{BS}$ in time $O(m^7 n^{14} \varepsilon^{-7} \log^4(mn/\varepsilon))$ .

Significance and Claims
The authors claim that their results demonstrate that quantum algorithms do not provide an exponential speedup for applications based on sampling from the distribution $\mu_{GBS,G}$ . Since many proposed GBS applications (e.g., graph isomorphism, counting perfect matchings) rely on sampling from this specific distribution, the existence of a polynomial-time classical sampler implies these specific tasks do not exhibit quantum advantage under the standard GBS model.

The paper notes that while the Jerrum-Sinclair-Vigoda algorithm is not directly applicable to general Boson Sampling (where the input matrix is a truncated unitary matrix with complex entries), their construction reduces the sampling problem to approximating the permanent of complex weighted matrices. Since approximating the permanent is generally NP-hard, the classical simulation of general Boson Sampling remains difficult. However, for the specific case of non-negative matrices and the graph-based GBS distribution, the authors have shown that efficient classical simulation is possible.

The work distinguishes itself from previous approaches (such as Zhang et al. [12]) by being applicable to all graphs, not just dense ones, and by utilizing a simpler, faster algorithm based on the Cartesian product construction.

Technical Summary: Simulating Gaussian Boson Sampling on Graphs in Polynomial Time

More like this