Performance of Gaussian Boson Sampling on Planted Bipartite Clique Detection

Basic Information

• Paper ID: 2510.12774
• Title: Performance of Gaussian Boson Sampling on Planted Bipartite Clique Detection
• Authors: Yu-Zhen Janice Chen (University of Massachusetts Amherst), Laurent Massoulié (Inria, Paris), Don Towsley (University of Massachusetts Amherst)
• Classification: quant-ph cs.CC cs.DS math.CO
• Publication Date: October 15, 2025 (arXiv preprint)
• Paper Link: https://arxiv.org/abs/2510.12774

Abstract

This paper investigates whether Gaussian Boson Sampling (GBS) can provide computational advantages for solving the planted bipartite clique problem. The planted bipartite clique problem is a graph-theoretic problem widely believed to be computationally hard classically when the planted structure is small. Although GBS has been observed heuristically and experimentally to tend to sample dense subgraphs, its theoretical performance on this classically hard problem remains largely unexplored. The paper focuses on a natural statistic derived from GBS output: the frequency of node appearance in GBS samples, termed node weight. The work rigorously analyzes whether this signal is sufficiently strong to distinguish planted bipartite clique nodes from background nodes. The analysis characterizes the distribution of node weights under GBS and quantifies the bias introduced by the planted structure. The results reveal a sharp limitation: when the planted bipartite clique size falls within the conjectured hard region, natural fluctuations in node weights dominate the bias signal, making detection unreliable using simple ranking strategies.

Research Background and Motivation

Problem Background

1. Planted Bipartite Clique Problem: This is a classical graph-theoretic problem requiring detection of whether a planted complete bipartite subgraph exists in a random bipartite graph. The problem has important applications in molecular property identification, social network community detection, and financial fraud detection.
2. Computational Complexity: When the planted clique size K satisfies 2log n ≪ K ≪ √n (where n is the number of graph nodes), the problem is conjectured to be computationally hard classically. Polynomial-time algorithms are known to exist when K = Ω(√n), while information-theoretic detectability fails when K ≤ 2log n.
3. Potential of Quantum Computing: Gaussian Boson Sampling, as a special-purpose linear optical quantum computing paradigm, has demonstrated potential advantages for graph-theoretic structures, particularly in sampling subgraphs with multiple perfect matchings.

Research Motivation

• Theoretical Gap: Despite heuristic and experimental evidence of GBS's advantages in dense subgraph sampling, rigorous theoretical analysis is lacking
• Practical Significance: If GBS provides advantages, it would have direct implications for molecular discovery, community detection, and related applications
• Theoretical Significance: Negative results would further support the average-case hardness conjecture for the planted clique problem

Core Contributions

1. Theoretical Framework Establishment: First rigorous theoretical analysis of GBS performance on planted bipartite clique detection, establishing a statistical framework based on node weights
2. Distribution Characterization: Proves that centered and rescaled node weights' joint moments converge to a multivariate Gaussian distribution with explicit covariance structure
3. Bias Quantification: Derives precise asymptotic expressions for weight bias between planted bipartite clique nodes and background nodes, with bias scaling as K/n
4. Computational Limitation Proof: In the region K = o(√n), proves that bias becomes negligible relative to standard deviation, indicating that simple frequency-based GBS strategies cannot reliably detect planted bipartite cliques in this region
5. Byproduct Results: As a byproduct of the analysis, characterizes the distribution of the Hafnian in bipartite Erdős-Rényi graphs

Methodology Details

Task Definition

Input: Bipartite graph Ĝ, either a pure random Erdős-Rényi graph G ~ ER(n,n,p) or a graph G' containing a planted K×K bipartite clique Output: Determine whether a planted bipartite clique exists in the graph or locate its position Constraints: Planted bipartite clique size K = ε√n, sampled subgraph size 2m = ε'√2n

Core Statistic: Node Weight

For node i ∈ V, its weight is defined as:

$W(i) = \frac{1}{\binom{n-1}{m-1}\binom{n}{m}} \sum_{\substack{A \in \binom{V}{m} \\ i \in A}} \sum_{B \in \binom{V'}{m}} Y(A,B)^2$

where Y(A,B) is the normalized expected number of perfect matchings:

$Y(A,B) = \frac{1}{p^m m!} \sum_{\sigma \in Bij(A,B)} \prod_{u \in A} \xi_{u\sigma(u)}$

GBS Sampling Mechanism

According to GBS theory, the probability of sampling subgraph (A,B) is proportional to the square of its Hafnian: $P_{kcf}(s) \propto |Haf(M_s)|^2$

This means subgraphs with more perfect matchings are more likely to be sampled.

Theoretical Analysis Framework

1. Moment Analysis

Define centered weight: Z(i) = W(i) - EW(i) Study scaled joint moments: $\phi_\ell(i^{(1)}, \ldots, i^{(\ell)}) = E\left[\prod_{j=1}^\ell \sqrt{n}Z(i^{(j)})\right]$

2. Key Lemmas

• Lemma 1 (Vertex Subset Intersection Size): Intersection sizes of random vertex subsets can be approximated by independent Poisson distributions
• Lemma 2 (Bijection Intersection Size): The number of agreements between two independent bijections on their overlap domain approximately follows a Poisson distribution with parameter 1

Experimental Setup

Theoretical Verification Rather Than Numerical Experiments

This paper primarily conducts theoretical analysis through mathematical proofs rather than numerical experiments. The main "experiments" are theoretical derivations and asymptotic analyses.

Parameter Settings

• Graph scale: Bipartite graph with n nodes
• Planted bipartite clique size: K = ε√n
• Sampling size: 2m = ε'√2n, where ε' ∈ (0,1)
• Edge probability: p ∈ (0,1) as a fixed constant

Analysis Region

Focus on the conjectured hard region: 2log n ≪ K ≪ √n

Experimental Results

Main Theoretical Results

1. Joint Moment Convergence (Theorem 3)

$\phi_\ell(i^{(1)}, \ldots, i^{(\ell)}) = o(1) + \sum_{\mu \in P_\ell^2} \prod_{\{j,j'\} \in \mu} C_{i^{(j)},i^{(j')}}$

where the covariance structure is: $C_{i^{(j)},i^{(j')}} = 4(p^{-1}-1)e^{2(p^{-1}-1)}\left[I_{i^{(j)}=i^{(j')}} + \frac{m^2}{n}\right]$

2. Bias Quantification (Proposition 6)

Weight bias between planted node i ∈ A₀ and non-planted node i' ∉ A₀: $E[W(i)] - E[W(i')] = (1+o(1))e^{p^{-1}-1}[p^{-1}-1]\frac{2K}{n}$

3. Variance Analysis (Corollary 7)

• Weight variance: $Var(W(i)) = \frac{1}{n}\Theta([EW(i)]^2)$
• Covariance between different nodes: $i \neq j \Rightarrow Cov(W(i),W(j)) = \frac{m^2}{n^2}\Theta([EW(i)]^2)$

Detection Performance Analysis

Signal-to-Noise Ratio Analysis

• Signal Strength: Bias ~ K/n
• Noise Strength: Standard deviation ~ 1/√n
• Signal-to-Noise Ratio: When K = o(√n), K/n ≪ 1/√n, signal is overwhelmed by noise

Ranking Strategy Effectiveness (Corollary 9)

Under simple ranking strategy, when K = ε√n with small ε, the expected number of planted nodes appearing in the top c·n rankings is: $\varepsilon\sqrt{n}(1-\tilde{\Phi}(\tilde{\Phi}^{-1}(1-c)-\varepsilon))$

As ε→0, this quantity approaches the baseline proportion c, indicating weak detection performance.

Related Work

Planted Clique Problem Research

• Classical Algorithms: Current best algorithms are quasi-polynomial time brute-force search
• Information-Theoretic Bounds: Information-theoretic non-detectability when K ≤ 2log n
• Computational Complexity: Computational gap exists in the intermediate region 2log n ≪ K ≪ √n

GBS-Related Research

• Theoretical Foundations: Connections between GBS and graph structures established by Hamilton et al. and Kruse et al.
• Application Exploration: Perfect matching counting, graph similarity measurement, dense subgraph identification, etc.
• Experimental Verification: Multiple proof-of-concept experiments have been reported

Quantum Advantage Research

• Specialized Sampling: GBS originally designed to demonstrate quantum advantage
• Graph-Theoretic Applications: Subsequent discovery of deep connections with graph structures
• Computational Limitations: This paper first rigorously analyzes GBS limitations on classically hard problems

Conclusions and Discussion

Main Conclusions

1. Theoretical Limitations: In the conjectured hard region K = o(√n), frequency-based GBS strategies cannot provide significant advantages
2. Signal-to-Noise Analysis: Bias signal (~ K/n) is dominated by natural fluctuations (~ 1/√n)
3. Threshold Phenomenon: GBS only begins to show detection advantages when K = Θ(√n)

Limitations

1. Strategy Limitations: Analysis restricted to simple frequency-based strategies
2. Ideal Assumptions: Assumes ideal GBS devices; actual devices have noise
3. Problem-Specific: Conclusions specific to the planted bipartite clique problem

Future Directions

1. Advanced Algorithms: Explore more sophisticated GBS post-processing algorithms
2. Alternative Quantum Methods: Investigate potential of other quantum computing paradigms
3. Practical Implementation: Consider noise effects on performance
4. Related Problems: Extend to other graph-theoretic problems

In-Depth Evaluation

Strengths

1. Theoretical Rigor: Provides the first rigorous theoretical analysis of GBS on the planted clique problem
2. Mathematical Depth: Employs sophisticated techniques from probability theory, combinatorics, and random graph theory
3. Clear Results: Provides precise asymptotic expressions and explicit computational limitations
4. Methodological Innovation: Establishes new framework for analyzing GBS statistical performance

Technical Contributions

1. Moment Method Application: Skillfully applies Wick's formula for joint moment analysis
2. Poisson Approximation: Effectively uses Poisson approximation to handle complex combinatorial structures
3. Asymptotic Analysis: Precise asymptotic expansions with error control

Weaknesses

1. Limited Scope: Only considers one specific statistic
2. Practical Applicability: Limited guidance for actual GBS implementations
3. Absence of Positive Results: Does not propose effective GBS-based detection algorithms

Impact

1. Theoretical Contribution: Provides new mathematical tools for GBS theoretical analysis
2. Computational Complexity: Supports hardness conjectures for the planted clique problem
3. Quantum Computing: Provides insights into the boundaries of quantum sampling advantages

Applicable Scenarios

1. Theoretical Research: Provides foundation for further research on GBS and planted clique problems
2. Algorithm Design: Provides negative baseline for designing better quantum graph algorithms
3. Complexity Theory: Offers quantum perspective for average-case complexity research

Technical Details Supplement

Mathematical Techniques

• Stein-Chen Method: Error control for Poisson approximation
• Derangement Asymptotics: Analysis of fixed points in random permutations
• Conditional Construction: Control of matching structures through edge switching

Proof Strategy

1. Decomposition Technique: Decompose complex joint moments into dominant and negligible terms
2. Probabilistic Bounds: Use Chernoff bounds and moment inequalities to control tail probabilities
3. Combinatorial Enumeration: Precisely calculate contributions of various graph structures

This paper is theoretically rigorous and profound, providing important theoretical foundations for understanding GBS limitations on classically hard problems. Although the results are negative, they are of significant importance for the development of the field.