Gauging practical computational advantage using a classical, threshold-based Gaussian boson sampler

• URL: http://arxiv.org/abs/2507.17567v1
• Date: Wed, 23 Jul 2025 14:58:18 GMT
• Title: Gauging practical computational advantage using a classical, threshold-based Gaussian boson sampler
• Authors: Sarvesh Raghuraman, Aditya Patwardhan, Brian La Cour,
• Abstract summary: 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.
• Score: 0.10923877073891444
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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 that click when the incident amplitude falls above a given threshold. Using this model, we map several NP-Complete graph theoretic problems to equivalent Gaussian boson sampling problems and numerically explore the practical efficacy of our approach. Specifically, for a given weighted, undirected graph we examined finding the densest k-subgraph and the maximum weighted clique. We also examined the graph classification problem. Compared to traditional classical solvers, we found that our method provides better solutions in a comparable amount of samples for graphs with up to 2000 nodes.

Related papers

• Efficient Classical Algorithms for Simulating Gaussian Boson Sampling on Graphs [23.446540440518444]
  We propose Markov chain Monte Carlo-based algorithms to simulate GBS on undirected, unweighted graphs.<n>Our main contribution is a double-loop variant of Glauber dynamics, whose stationary distribution matches the GBS distribution.<n> Numerically, we conduct experiments on graphs with 256, larger than the scales in former GBS experiments as well as classical simulations.
  arXiv  Detail & Related papers  (2025-05-05T08:13:57Z)
• An Analysis of Quantum Annealing Algorithms for Solving the Maximum Clique Problem [49.1574468325115]
  We analyse the ability of quantum D-Wave annealers to find the maximum clique on a graph, expressed as a QUBO problem. We propose a decomposition algorithm for the complementary maximum independent set problem, and a graph generation algorithm to control the number of nodes, the number of cliques, the density, the connectivity indices and the ratio of the solution size to the number of other nodes.
  arXiv  Detail & Related papers  (2024-06-11T04:40:05Z)
• 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)
• Optimal Algorithms for the Inhomogeneous Spiked Wigner Model [89.1371983413931]
  We derive an approximate message-passing algorithm (AMP) for the inhomogeneous problem. We identify in particular the existence of a statistical-to-computational gap where known algorithms require a signal-to-noise ratio bigger than the information-theoretic threshold to perform better than random.
  arXiv  Detail & Related papers  (2023-02-13T19:57:17Z)
• 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)
• Unveiling the Sampling Density in Non-Uniform Geometric Graphs [69.93864101024639]
  We consider graphs as geometric graphs: nodes are randomly sampled from an underlying metric space, and any pair of nodes is connected if their distance is less than a specified neighborhood radius. In a social network communities can be modeled as densely sampled areas, and hubs as nodes with larger neighborhood radius. We develop methods to estimate the unknown sampling density in a self-supervised fashion.
  arXiv  Detail & Related papers  (2022-10-15T08:01:08Z)
• Experimentally finding dense subgraphs using a time-bin encoded Gaussian boson sampling device [0.0]
  We use a time-bin encoded interferometer to implement GBS experimentally and extract samples to enhance the search for dense subgraphs in a graph. Our results indicate an improvement over classical methods for subgraphs of sizes three and four in a graph containing ten nodes. We numerically explore the role of imperfections in the optical circuit and on the performance of the algorithm.
  arXiv  Detail & Related papers  (2022-04-11T16:56:30Z)
• Unsupervised Event Classification with Graphs on Classical and Photonic Quantum Computers [0.0]
  Photonic Quantum Computers provides several benefits over the discrete qubit-based paradigm of quantum computing. We build an anomaly detection model to use on searches for New Physics. We present a novel method of anomaly detection, combining the use of Gaussian Boson Sampling and a quantum extension to K-means known as Q-means.
  arXiv  Detail & Related papers  (2021-03-05T19:02:31Z)
• Online Dense Subgraph Discovery via Blurred-Graph Feedback [87.9850024070244]
  We introduce a novel learning problem for dense subgraph discovery. We first propose a edge-time algorithm that obtains a nearly-optimal solution with high probability. We then design a more scalable algorithm with a theoretical guarantee.
  arXiv  Detail & Related papers  (2020-06-24T11:37:33Z)
• 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)
• Generative Modeling with Denoising Auto-Encoders and Langevin Sampling [88.83704353627554]
  We show that both DAE and DSM provide estimates of the score of the smoothed population density. We then apply our results to the homotopy method of arXiv:1907.05600 and provide theoretical justification for its empirical success.
  arXiv  Detail & Related papers  (2020-01-31T23:50:03Z)

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.