Displaced Gaussian Boson Sampling for enhanced max-clique search

• URL: http://arxiv.org/abs/2605.27522v1
• Date: Tue, 26 May 2026 18:00:21 GMT
• Title: Displaced Gaussian Boson Sampling for enhanced max-clique search
• Abstract summary: A GBS device has been shown to provide an enhancement in the search of cliques in undirected weighted graphs over classical algorithms.<n>We report an enhancement of the success rate of GBS in finding maximum weighted cliques by adding displacements under lossy conditions or when a limited amount of squeezing is available.
• Score: 1.3244654316770816
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Gaussian Boson Sampling (GBS) is capable of solving certain classes of graph problems owing to the samples produced by such a device having a connection to the hafnian matrix function. In particular, a GBS device has been shown to provide an enhancement in the search of cliques -- or complete subgraphs -- in undirected weighted graphs over classical algorithms. A graph can be mapped to a GBS experiment by configuring the squeezing parameters of the input states and programming the linear optical network. In practice, limited squeezing and photon loss degrade the performance of the GBS device for max-clique search. In comparison, coherent states -- often considered a classical resource due to their Poissonian statistics -- can be readily prepared across many modes using an attenuated laser. In this paper, we report an enhancement of the success rate of GBS in finding maximum weighted cliques by adding displacements under lossy conditions or when a limited amount of squeezing is available. Moreover, we report that this enhancement can be scaled up to large graphs with limited resource overheads.

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)
• Boosting Gaussian Boson Sampling using Optical Parametric Amplification Networks [0.0]
  We propose a nonlinear photonic architecture based on optical parametric amplifiers arranged in an interferometer network.<n>We numerically show that entanglement scales linearly with both the OPA gain and network depth in the lossless limit.<n>Our results demonstrate that OPA-boosted GBS preserves computational hardness in noisy environments.
  arXiv  Detail & Related papers  (2025-11-30T06:13:58Z)
• Learning Grouped Lattice Vector Quantizers for Low-Bit LLM Compression [57.54335545892155]
  We introduce a Grouped Lattice Vector Quantization (GLVQ) framework that assigns each group of weights a customized lattice codebook.<n>Our approach achieves a better trade-off between model size and accuracy compared to existing post-training quantization baselines.
  arXiv  Detail & Related papers  (2025-10-23T20:19:48Z)
• 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)
• Once-for-All: Controllable Generative Image Compression with Dynamic Granularity Adaptation [52.82508784748278]
  This paper proposes a Control Generative Image Compression framework, termed Control-GIC.<n>Control-GIC is capable of fine-grained adaption across a broad spectrum while ensuring high-fidelity and generality compression.<n>Our experiments show that Control-GIC allows highly flexible and controllable adaption where the results demonstrate its superior performance over recent state-of-the-art methods.
  arXiv  Detail & Related papers  (2024-06-02T14:22:09Z)
• GES: Generalized Exponential Splatting for Efficient Radiance Field Rendering [112.16239342037714]
  GES (Generalized Exponential Splatting) is a novel representation that employs Generalized Exponential Function (GEF) to model 3D scenes. With the aid of a frequency-modulated loss, GES achieves competitive performance in novel-view synthesis benchmarks.
  arXiv  Detail & Related papers  (2024-02-15T17:32:50Z)
• On the Privacy of Selection Mechanisms with Gaussian Noise [44.577599546904736]
  We revisit the analysis of Report Noisy Max and Above Threshold with Gaussian noise. We find that it is possible to provide pure ex-ante DP bounds for Report Noisy Max and pure ex-post DP bounds for Above Threshold.
  arXiv  Detail & Related papers  (2024-02-09T02:11:25Z)
• 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)
• 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)
• Solving Graph Problems Using Gaussian Boson Sampling [22.516585968074146]
  We use a noisy intermediate-scale quantum computer to solve graph problems. We experimentally observe the presence of GBS enhancement with large photon-click number and an enhancement under certain noise. Our work is a step toward testing real-world problems using the existing intermediate-scale quantum computers.
  arXiv  Detail & Related papers  (2023-02-02T08:25:47Z)
• Gaussian-boson-sampling-enhanced dense subgraph finding shows limited advantage over efficient classical algorithms [0.0]
  We investigate the effects of sources of error including loss and spectral impurity on GBS applied to dense subgraph finding algorithms. We find that the effectiveness of these algorithms is remarkably robust to errors, to such an extent that there exist efficient classical algorithms that can simulate the underlying GBS.
  arXiv  Detail & Related papers  (2023-01-30T19:00:03Z)
• Decision Forest Based EMG Signal Classification with Low Volume Dataset Augmented with Random Variance Gaussian Noise [51.76329821186873]
  We produce a model that can classify six different hand gestures with a limited number of samples that generalizes well to a wider audience. We appeal to a set of more elementary methods such as the use of random bounds on a signal, but desire to show the power these methods can carry in an online setting.
  arXiv  Detail & Related papers  (2022-06-29T23:22:18Z)

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.