Bipartite Gaussian Boson Sampling for Hamiltonian Cycles in Directed Graphs

• URL: http://arxiv.org/abs/2606.28775v1
• Date: Sat, 27 Jun 2026 06:59:44 GMT
• Title: Bipartite Gaussian Boson Sampling for Hamiltonian Cycles in Directed Graphs
• Abstract summary: We propose a BipartiteGBS-based framework for directed-graph optimization.<n>We use BipartiteGBS samples to guide a genetic algorithm for the celebrated directed Hamiltonian cycle problem.
• Score: 11.39278258068721
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Bipartite Gaussian boson sampling (BipartiteGBS) produces output probabilities governed by squared permanents of submatrices of arbitrary complex matrices, matching the nonsymmetric structure of directed graphs. Most GBS-based graph algorithms, however, rely on symmetric hafnian structure and are formulated for undirected problems. Here we propose a BipartiteGBS-based framework for directed-graph heuristic optimization. We introduce Max-Perm as a canonical optimization task for BipartiteGBS and derive a closed-form sampling enhancement factor relative to uniform classical sampling in this idealized setting. We then use permanent-biased BipartiteGBS samples to guide a genetic algorithm for the celebrated directed Hamiltonian cycle problem. Numerical experiments on Erdős--Rényi random directed graphs show that the resulting BipartiteGBS-enhanced algorithms improve success rates over a standard genetic algorithm and yield longer valid paths when no Hamiltonian cycle is found, while ablation tests indicate that BipartiteGBS-guided initialization is the dominant contributor. These results show how permanent-based photonic sampling can provide useful algorithmic guidance for asymmetric combinatorial search.

Related papers

• Bregman geometry-aware split Gibbs sampling for Bayesian Poisson inverse problems [8.115032818930457]
  We propose a novel framework for solving inverse problems by a Monte Carlo sampling algorithm.<n>We show that the method achieves competitive performance in terms of reconstruction quality.
  arXiv  Detail & Related papers  (2025-11-15T15:27:31Z)
• Efficient Classical Sampling from Gaussian Boson Sampling Distributions on Unweighted Graphs [31.937752933240674]
  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.
  arXiv  Detail & Related papers  (2025-05-05T08:13:57Z)
• 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)
• A Discrete Particle Swarm Optimizer for the Design of Cryptographic Boolean Functions [1.6574413179773761]
  The algorithm is a modified version of the permutation PSO by Hu, Eberhart and Shi. The parameters for the PSO velocity equation are tuned by means of two meta-optimization techniques.
  arXiv  Detail & Related papers  (2024-01-09T14:08:42Z)
• 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)
• Accelerated Discovery of Machine-Learned Symmetries: Deriving the Exceptional Lie Groups G2, F4 and E6 [55.41644538483948]
  This letter introduces two improved algorithms that significantly speed up the discovery of symmetry transformations. Given the significant complexity of the exceptional Lie groups, our results demonstrate that this machine-learning method for discovering symmetries is completely general and can be applied to a wide variety of labeled datasets.
  arXiv  Detail & Related papers  (2023-07-10T20:25:44Z)
• 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)
• Optimal Extragradient-Based Bilinearly-Coupled Saddle-Point Optimization [116.89941263390769]
  We consider the smooth convex-concave bilinearly-coupled saddle-point problem, $min_mathbfxmax_mathbfyF(mathbfx) + H(mathbfx,mathbfy)$, where one has access to first-order oracles for $F$, $G$ as well as the bilinear coupling function $H$. We present a emphaccelerated gradient-extragradient (AG-EG) descent-ascent algorithm that combines extragrad
  arXiv  Detail & Related papers  (2022-06-17T06:10:20Z)
• Nonconvex Stochastic Scaled-Gradient Descent and Generalized Eigenvector Problems [98.34292831923335]
  Motivated by the problem of online correlation analysis, we propose the emphStochastic Scaled-Gradient Descent (SSD) algorithm. We bring these ideas together in an application to online correlation analysis, deriving for the first time an optimal one-time-scale algorithm with an explicit rate of local convergence to normality.
  arXiv  Detail & Related papers  (2021-12-29T18:46:52Z)
• Unfolding Projection-free SDP Relaxation of Binary Graph Classifier via GDPA Linearization [59.87663954467815]
  Algorithm unfolding creates an interpretable and parsimonious neural network architecture by implementing each iteration of a model-based algorithm as a neural layer. In this paper, leveraging a recent linear algebraic theorem called Gershgorin disc perfect alignment (GDPA), we unroll a projection-free algorithm for semi-definite programming relaxation (SDR) of a binary graph. Experimental results show that our unrolled network outperformed pure model-based graph classifiers, and achieved comparable performance to pure data-driven networks but using far fewer parameters.
  arXiv  Detail & Related papers  (2021-09-10T07:01:15Z)
• Spectral clustering under degree heterogeneity: a case for the random walk Laplacian [83.79286663107845]
  This paper shows that graph spectral embedding using the random walk Laplacian produces vector representations which are completely corrected for node degree. In the special case of a degree-corrected block model, the embedding concentrates about K distinct points, representing communities.
  arXiv  Detail & Related papers  (2021-05-03T16:36:27Z)
• Orbital MCMC [82.54438698903775]
  We propose two practical algorithms for constructing periodic orbits from any diffeomorphism. We also perform an empirical study demonstrating the practical advantages of both kernels.
  arXiv  Detail & Related papers  (2020-10-15T22:25:52Z)

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.