Bipartite Gaussian Boson Sampling for Hamiltonian Cycles in Directed Graphs
Miaomiao Yu, Jingyi Lv, Yan Wang, Kun Wang, Ping Xu · 2026
Read Bipartite Gaussian Boson Sampling for Hamiltonian Cycles in Directed Graphs by Miaomiao Yu, Jingyi Lv, Yan Wang, Kun Wang, Ping Xu (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2606-28775.txt.
Introduction
Yu, Lv, Wang, Wang and Xu put a photonic sampling device to work on a classic directed graph problem. Their device uses bipartite Gaussian boson sampling, where light passing through a circuit produces outcomes whose chances follow permanents, a matrix quantity suited to one-way connections. Most earlier sampling algorithms relied on a symmetric quantity tied to undirected problems, so directed cases were poorly served.
They define a task called Max-Perm as the natural target, and derive how much its sampling beats plain random choice in an ideal setting. Guided by those samples, a genetic algorithm then searches for a Hamiltonian cycle, a route visiting every node once in a directed graph. On random directed graphs the guided search beat a standard genetic algorithm. When no full cycle existed, it found longer valid paths, and tests showed the sampling-based start drove most of the gain.
Catalog record
| CREATOR | Miaomiao Yu, Jingyi Lv, Yan Wang, Kun Wang, Ping Xu |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 81 KB |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2606.28775
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Bipartite Gaussian Boson Sampling for Hamiltonian Cycles in Directed Graphs Miaomiao Yu, Jingyi Lv, Yan Wang, Kun Wang, Ping Xu 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. I Introduction Boson sampling and its Gaussian variants have become prominent platforms for probing photonic quantum advantage, because they connect experimentally accessible optical transformations with matrix functions whose exact sampling is believed to be classically hard. In the original boson sampling model Aaronson and Arkhipov 2011 , this hardness is associated with permanents of submatrices of a linear-optical unitary, and the model has motivated a series of experimental demonstrations Spring et al. 2013 ; Broome et al. 2013 ; Crespi et al. 2013 ; Tillmann et al. 2013 and related sampling variants Lund et al. 2014 ; Barkhofen et al. 2017 . Gaussian boson sampling (GBS) Hamilton et al. 2017 addresses part of the experimental difficulty of single-photon boson sampling by replacing single photons with Gaussian states, which can be prepared deterministically and implemented on programmable photonic platforms Kruse et al. 2019 ; Zhong et al. 2020 ; Madsen et al. 2022 ; Liu et al. 2026 ; its output probabilities are governed by Hafnians, leading to complexity-theoretic conjectures tailored to GBS Hamilton et al. 2017 ; Kruse et al. 2019 . Bipartite Gaussian boson sampling (BipartiteGBS) Grier et al. 2022 ; Arrazola et al. 2021 ; Borghi et al. 2025 further adapts this program to two-mode-squeezing platforms such as spontaneous parametric down-conversion and spontaneous four-wave mixing Arrazola et al. 2021 ; Wu et al. 2022 , while retaining the same sampling-hardness conjecture as boson sampling Grier et al. 2022 . As illustrated in Fig. 1 , standard GBS sends single-mode squeezed states through one interferometer, whereas BipartiteGBS uses two-mode squeezed states and two interferometers, making explicit the architectural distinction used throughout this work. The matrix function and its symmetry structure become central when GBS is used for graph-theoretic applications. Existing GBS-based algorithms have been developed for graph problems Arrazola and Bromley 2018 ; Schuld et al. 2020 ; Brádler et al. 2018 ; Zhu et al. 2025 , as well as related applications such as point processes Jahangiri et al. 2020 and molecular vibronic spectra Huh and Yung 2017 . However, standard GBS naturally encodes symmetric matrices and has therefore been used mainly for undirected graph problems. Directed graphs are ubiquitous in real-world systems, including social networks Wasserman and Faust 1994 , biological regulatory circuits Alon 2019 , and transportation infrastructures Bang-Jensen and Gutin 2000 , precisely because they naturally encode asymmetric relationships. In such frameworks, the existence of a feasible or preferential transition from one vertex to another does not necessitate the reverse, a property that is fundamental to capturing directed influence, causality, and flow. This asymmetry renders directed graphs indispensable for modeling processes where directionality carries intrinsic semantic or physical meaning. Although directed graphs can in principle be embedded into larger symmetric matrices, such embeddings obscure the native nonsymmetric structure of a directed adjacency matrix. BipartiteGBS output probabilities are proportional to squared permanents of submatrices of arbitrary matrices, rather than being restricted to symmetric matrices. This makes BipartiteGBS a natural candidate for directed graphs; however, to the best of our knowledge, no BipartiteGBS-based algorithm has yet been proposed specifically for directed graph problems. Figure 1: Comparison of standard GBS and BipartiteGBS optical architectures. (a) Standard GBS injects 2n single-mode squeezed states S_{1}(r_{i}) into a single interferometer W , followed by photon-number detection. (b) BipartiteGBS injects n two-mode squeezed states S_{2}(r_{i}) ; the two output arms are sent through separate interferometers U and V and measured independently. Under the SVD convention used in Sec. II , the lower interferometer implements V^{*} ; for the real matrices considered here, V^{*}=V . In the BipartiteGBS setting, the corresponding sampling probabilities are proportional to squared permanents of submatrices of the matrix encoded by the two interferometers and the squeezing parameters. We choose the directed Hamiltonian cycle problem as a concrete testbed because it is both structurally asymmetric and computationally demanding. It is one of Karp’s original 21 NP-complete problems Karp 2009 : given a directed graph, the task is to determine whether there exists a cycle that visits every vertex exactly once and returns to the starting point Gould 1991 . It is also closely related to the traveling salesman problem Matai et al. 2010 . Since no polynomial-time algorithm is known for general directed graphs, heuristic and stochastic methods, including quantum-inspired approaches Lucas 2014 , remain important for exploring practical performance. Contributions. We propose a BipartiteGBS-enhanced genetic algorithm for directed Hamiltonian cycle search. The central design principle is to use BipartiteGBS as a source of permanent-biased heuristic information: sampled vertex substructures and edge co-occurrence frequencies are converted into guidance for a classical genetic algorithm. Numerical results on Erdős–Rényi directed graphs show improved search performance compared with a standard genetic algorithm, and ablation tests identify BipartiteGBS-guided initialization as the most effective component. These results indicate that heuristic information extracted from BipartiteGBS can enhance classical search for asymmetric combinatorial problems. This enhancement is heuristic in nature and does not constitute a claim of complexity-theoretic quantum advantage. Organization. Sec. II reviews the theoretical formalism of GBS and BipartiteGBS. Sec. III analyzes the enhancement ratio of BipartiteGBS for the Max-Perm problem. Sec. IV describes the BipartiteGBS-enhanced genetic algorithm ( BipartiteGBS-GA ) for Hamiltonian cycle search, including MS-BipartiteGBS-GA . Sec. V presents numerical simulations and discussions. II GBS and BipartiteGBS In a standard GBS setup Hamilton et al. 2017 ; Kruse et al. 2019 , 2m single-mode squeezed vacuum states with squeezing parameters \{r_{1},\ldots,r_{2m}\} are injected into a linear interferometer T , as illustrated in Fig. 1 (a). All 2m output modes are measured by photon-number-resolving detectors. The probability of obtaining a photon-number pattern \bar{c}=(c_{1},\ldots,c_{2m}) is given by \displaystyle\Pr(\bar{c})=\frac{1}{\bar{c}!\sqrt{|\sigma_{Q}|}}\operatorname{Haf}(A_{S}). (1) Here A is the adjacency matrix of the Gaussian state, which takes the block-diagonal form A=B\oplus B^{*} , \sigma_{Q} is the covariance matrix of the Gaussian state, and \operatorname{Haf} is the Hafnian function. The m\times m complex symmetric matrix B encodes the interferometer W and squeezing parameters \{r_{i}\} through the Takagi decomposition Hamilton et al. 2017 \displaystyle B=W\left(\operatorname{diag}(\tanh r_{1},\ldots,\tanh r_{m})\right)W^{T}, (2) where \tanh r_{i}\in[0,1) for all i . Using the identity \operatorname{Haf}(B\oplus B^{*})=|\operatorname{Haf}(B)|^{2} , Eq. ( 1 ) simplifies to \displaystyle\Pr(\bar{c})=\frac{1}{\bar{c}!\sqrt{|\sigma_{Q}|}}|\operatorname{Haf}(B_{S})|^{2}. (3) Here, B_{S} denotes the submatrix of B formed