Efficient Classical Sampling from Gaussian Boson Sampling Distributions on Unweighted Graphs

• URL: http://arxiv.org/abs/2505.02445v2
• Date: Wed, 17 Sep 2025 14:26:08 GMT
• Title: Efficient Classical Sampling from Gaussian Boson Sampling Distributions on Unweighted Graphs
• Authors: Yexin Zhang, Shuo Zhou, Xinzhao Wang, Ziruo Wang, Ziyi Yang, Rui Yang, Yecheng Xue, Tongyang Li,
• Abstract summary: We propose Markov chain Monte Carlo-based algorithms to sample from GBS distributions on undirected, unweighted graphs.<n>Our main contribution is a double-loop variant of Glauber dynamics, whose stationary distribution matches the GBS distribution.<n>Our approach offers both theoretical guarantees and practical advantages for efficient classical sampling from GBS distributions on unweighted graphs.
• Score: 31.937752933240674
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Gaussian Boson Sampling (GBS) is a promising candidate for demonstrating quantum computational advantage and can be applied to solving graph-related problems. In this work, we propose Markov chain Monte Carlo-based algorithms to sample from GBS distributions on undirected, unweighted graphs. Our main contribution is a double-loop variant of Glauber dynamics, whose stationary distribution matches the GBS distribution. We further prove that it mixes in polynomial time for dense graphs using a refined canonical path argument. Numerically, we conduct experiments on unweighted graphs with 256 vertices, larger than the scales in former GBS experiments as well as classical simulations. In particular, we show that both the single-loop and double-loop Glauber dynamics improve the performance of original random search and simulated annealing algorithms for the max-Hafnian and densest $k$-subgraph problems up to 10$\times$. Overall, our approach offers both theoretical guarantees and practical advantages for efficient classical sampling from GBS distributions on unweighted graphs.

Related papers

• A Quantum Photonic Approach to Graph Coloring [0.688204255655161]
  Gaussian Boson Sampling (GBS) is a quantum computational model that leverages linear optics to solve sampling problems.<n>Recent experimental breakthroughs have demonstrated quantum advantage using GBS, motivating its application to real-world optimization problems.
  arXiv  Detail & Related papers  (2026-01-28T05:18:27Z)
• Gauging practical computational advantage using a classical, threshold-based Gaussian boson sampler [0.10923877073891444]
  We describe an efficient scalable Gaussian boson sampler based on a classical description of squeezed quantum light and a deterministic model of single-photon detectors.<n>We map several NP-Complete graph theoretic problems to equivalent Gaussian boson sampling problems and numerically explore the practical efficacy of our approach.
  arXiv  Detail & Related papers  (2025-07-23T14:58:18Z)
• A Spectral Interpretation of Redundancy in a Graph Reservoir [51.40366905583043]
  This work revisits the definition of the reservoir in the Multiresolution Reservoir Graph Neural Network (MRGNN)<n>It proposes a variant based on a Fairing algorithm originally introduced in the field of surface design in computer graphics.<n>The core contribution of the paper lies in the theoretical analysis of the algorithm from a random walks perspective.
  arXiv  Detail & Related papers  (2025-07-17T10:02:57Z)
• Scalable Equilibrium Sampling with Sequential Boltzmann Generators [60.00515282300297]
  We extend the Boltzmann generator framework with two key contributions.<n>The first is a highly efficient Transformer-based normalizing flow operating directly on all-atom Cartesian coordinates.<n>In particular, we perform inference-time scaling of flow samples using a continuous-time variant of sequential Monte Carlo.
  arXiv  Detail & Related papers  (2025-02-25T18:59:13Z)
• Gaussian boson sampling for binary optimization [0.0]
  We propose to use a parametrized Gaussian Boson Sampler (GBS) with threshold detectors to address binary optimization problems.<n> Numerical experiments on 3-SAT and Graphing problems show significant performance gains over random guessing.
  arXiv  Detail & Related papers  (2024-12-19T12:12:22Z)
• Generating Graphs via Spectral Diffusion [48.70458395826864]
  We present GGSD, a novel graph generative model based on 1) the spectral decomposition of the graph Laplacian matrix and 2) a diffusion process.<n>An extensive set of experiments on both synthetic and real-world graphs demonstrates the strengths of our model against state-of-the-art alternatives.
  arXiv  Detail & Related papers  (2024-02-29T09:26:46Z)
• Gaussian Boson Sampling to Accelerate NP-Complete Vertex-Minor Graph Classification [0.9935277311162707]
  We propose a hybrid quantum-classical algorithm for the NP-complete problem of determining if two graphs are minor of one another. We find a graph embedding that allows trading between the one-shot classification accuracy and the amount of input squeezing. We introduce a new classical algorithm based on graph spectra, which we show outperforms various well-known graph-similarity algorithms.
  arXiv  Detail & Related papers  (2024-02-05T21:24:11Z)
• Boost clustering with Gaussian Boson Sampling: a full quantum approach [0.09437521840642138]
  We propose a novel clustering approach based on Gaussian Boson Sampling (GBS) We benchmark our approach with two well-known classical clustering algorithms. Results show that our approach outperforms the two classical algorithms in two out of the three chosen metrics.
  arXiv  Detail & Related papers  (2023-07-25T09:05:24Z)
• Graph Signal Sampling for Inductive One-Bit Matrix Completion: a Closed-form Solution [112.3443939502313]
  We propose a unified graph signal sampling framework which enjoys the benefits of graph signal analysis and processing. The key idea is to transform each user's ratings on the items to a function (signal) on the vertices of an item-item graph. For the online setting, we develop a Bayesian extension, i.e., BGS-IMC which considers continuous random Gaussian noise in the graph Fourier domain.
  arXiv  Detail & Related papers  (2023-02-08T08:17:43Z)
• Quantum-inspired classical algorithm for graph problems by Gaussian boson sampling [2.5496329090462626]
  We present a quantum-inspired classical algorithm that can be used for graph-theoretical problems. A given graph's adjacency matrix to be encoded in a Gaussian boson sampler is nonnegative, which does not necessitate quantum interference.
  arXiv  Detail & Related papers  (2023-02-01T16:02:31Z)
• NAG-GS: Semi-Implicit, Accelerated and Robust Stochastic Optimizer [45.47667026025716]
  We propose a novel, robust and accelerated iteration that relies on two key elements. The convergence and stability of the obtained method, referred to as NAG-GS, are first studied extensively. We show that NAG-arity is competitive with state-the-art methods such as momentum SGD with weight decay and AdamW for the training of machine learning models.
  arXiv  Detail & Related papers  (2022-09-29T16:54:53Z)
• Langevin Monte Carlo for Contextual Bandits [72.00524614312002]
  Langevin Monte Carlo Thompson Sampling (LMC-TS) is proposed to directly sample from the posterior distribution in contextual bandits. We prove that the proposed algorithm achieves the same sublinear regret bound as the best Thompson sampling algorithms for a special case of contextual bandits.
  arXiv  Detail & Related papers  (2022-06-22T17:58:23Z)
• Sampling in Combinatorial Spaces with SurVAE Flow Augmented MCMC [83.48593305367523]
  Hybrid Monte Carlo is a powerful Markov Chain Monte Carlo method for sampling from complex continuous distributions. We introduce a new approach based on augmenting Monte Carlo methods with SurVAE Flows to sample from discrete distributions. We demonstrate the efficacy of our algorithm on a range of examples from statistics, computational physics and machine learning, and observe improvements compared to alternative algorithms.
  arXiv  Detail & Related papers  (2021-02-04T02:21:08Z)
• Hybrid quantum-classical algorithms for approximate graph coloring [65.62256987706128]
  We show how to apply the quantum approximate optimization algorithm (RQAOA) to MAX-$k$-CUT, the problem of finding an approximate $k$-vertex coloring of a graph. We construct an efficient classical simulation algorithm which simulates level-$1$ QAOA and level-$1$ RQAOA for arbitrary graphs.
  arXiv  Detail & Related papers  (2020-11-26T18:22:21Z)
• Plug-And-Play Learned Gaussian-mixture Approximate Message Passing [71.74028918819046]
  We propose a plug-and-play compressed sensing (CS) recovery algorithm suitable for any i.i.d. source prior. Our algorithm builds upon Borgerding's learned AMP (LAMP), yet significantly improves it by adopting a universal denoising function within the algorithm. Numerical evaluation shows that the L-GM-AMP algorithm achieves state-of-the-art performance without any knowledge of the source prior.
  arXiv  Detail & Related papers  (2020-11-18T16:40:45Z)
• Bandit Samplers for Training Graph Neural Networks [63.17765191700203]
  Several sampling algorithms with variance reduction have been proposed for accelerating the training of Graph Convolution Networks (GCNs) These sampling algorithms are not applicable to more general graph neural networks (GNNs) where the message aggregator contains learned weights rather than fixed weights, such as Graph Attention Networks (GAT)
  arXiv  Detail & Related papers  (2020-06-10T12:48:37Z)
• Gaussianization Flows [113.79542218282282]
  We propose a new type of normalizing flow model that enables both efficient iteration of likelihoods and efficient inversion for sample generation. Because of this guaranteed expressivity, they can capture multimodal target distributions without compromising the efficiency of sample generation.
  arXiv  Detail & Related papers  (2020-03-04T08:15:06Z)
• Block-Approximated Exponential Random Graphs [77.4792558024487]
  An important challenge in the field of exponential random graphs (ERGs) is the fitting of non-trivial ERGs on large graphs. We propose an approximative framework to such non-trivial ERGs that result in dyadic independence (i.e., edge independent) distributions. Our methods are scalable to sparse graphs consisting of millions of nodes.
  arXiv  Detail & Related papers  (2020-02-14T11:42:16Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.