⚛️ quantum physics

Bipartite Gaussian Boson Sampling for Hamiltonian Cycles in Directed Graphs

This paper proposes a Bipartite Gaussian Boson Sampling framework that leverages permanent-biased photonic sampling to enhance genetic algorithms for solving the directed Hamiltonian cycle problem, demonstrating improved success rates and path quality on random directed graphs compared to standard classical approaches.

Original authors: Miaomiao Yu, Jingyi Lv, Yan Wang, Kun Wang, Ping Xu

Published 2026-06-30

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Miaomiao Yu, Jingyi Lv, Yan Wang, Kun Wang, Ping Xu

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Big Picture: Finding a Route in a One-Way City

Imagine you are a delivery driver in a massive, chaotic city where every street is a one-way street. Your goal is to find a route that visits every single building exactly once and returns to your starting point. In math terms, this is called the Directed Hamiltonian Cycle problem.

This is a notoriously difficult puzzle. If you try to guess routes randomly, you might spend your whole life driving in circles without ever finding the perfect loop.

The authors of this paper asked a question: Can a special type of quantum computer help us guess better routes?

The Tool: A "Quantum Dice" for One-Way Streets

Most previous attempts to use quantum computers for graph problems relied on a tool called Gaussian Boson Sampling (GBS). Think of standard GBS as a magical dice roller that is great at finding patterns in two-way streets (where if you can go from A to B, you can also go from B to A).

However, real-world problems (like traffic flow, social media influence, or biological signals) are usually one-way. The "magic dice" of standard GBS doesn't work well here because it expects symmetry that doesn't exist.

The authors used a different tool called Bipartite Gaussian Boson Sampling (BipartiteGBS).

The Analogy: If standard GBS is a dice that only rolls even numbers, BipartiteGBS is a dice that can roll any number. It is specifically designed to handle the messy, asymmetric nature of one-way streets.
How it works: It shoots particles of light (photons) through a complex maze of mirrors. The way these particles land creates a pattern that is mathematically linked to the "permanents" of the city's map. In simple terms, the quantum machine naturally "prefers" to land on routes that look like they have a lot of connections, even if they aren't perfect yet.

The Strategy: The Quantum Coach and the Human Runner

The paper doesn't claim the quantum computer solves the puzzle all by itself. Instead, it acts as a smart coach for a human runner (a classical computer algorithm called a Genetic Algorithm).

Here is how they worked together:

The Coach (Quantum Machine): The BipartiteGBS machine takes a quick look at the city map and generates a list of "promising" starting points. It says, "Hey, these specific buildings seem to be in a cluster where a good route might exist."
The Runner (Genetic Algorithm): The classical computer takes these suggestions and starts running. It tries to build a full route, testing different combinations, swapping parts of the route, and keeping the ones that work best.
The Result: Because the runner started with the coach's "smart suggestions" rather than random guesses, it found the perfect loop much faster and more often than a runner starting with no help.

The Surprising Discovery: Less is More

The researchers tested different ways to mix the Quantum Coach and the Human Runner. They found something counter-intuitive:

The "Full Control" Approach: They tried letting the Quantum Coach tell the Runner everything—what to start with, how to judge a route, and how to fix mistakes. This actually made the runner slower and less effective. It was like having a coach who micromanages every step, causing the runner to get confused.
The "Smart Start" Approach: The most successful method was simply letting the Quantum Coach pick the starting lineup (the initial guesses) and then letting the Human Runner do the rest of the work using its own standard rules.

The Takeaway: The quantum computer is best used as a guide for the beginning, not a controller for the whole journey. It provides a "head start" that helps the classical computer find the solution faster.

What They Actually Found (The Results)

The team tested this on random maps of cities with 15 to 40 buildings.

Success Rate: The method using the Quantum Coach found the perfect route significantly more often than the method without it.
When it failed: Even when they couldn't find the perfect loop, the Quantum-assisted method found longer valid paths (getting further before getting stuck) than the standard method.
The Verdict: This proves that quantum sampling can give useful "hints" for difficult, one-way puzzles, but it is a heuristic (a smart guess) tool, not a magic wand that solves the problem instantly.

Summary

The paper introduces a new way to use a specific quantum light-based computer to help solve hard routing problems in one-way networks. By using the quantum machine to generate smart starting guesses for a classical computer, they can solve these puzzles more efficiently. The key lesson is that the quantum tool works best when it sets the stage, rather than trying to direct the entire play.

Problem Statement

The paper addresses the challenge of solving the directed Hamiltonian cycle problem, a classic NP-complete problem where the goal is to determine if a directed graph contains a cycle visiting every vertex exactly once. While standard Gaussian Boson Sampling (GBS) has been successfully applied to undirected graph problems by leveraging the Hafnian function (which encodes symmetric matrices), it is ill-suited for directed graphs. Directed graphs possess an intrinsic asymmetric structure (non-symmetric adjacency matrices) that standard GBS cannot naturally encode without obscuring the native structure through symmetric embeddings. Furthermore, existing heuristic methods for directed graphs often struggle with the exponential scaling of the search space.

Methodology

The authors propose a framework that utilizes Bipartite Gaussian Boson Sampling (BipartiteGBS) to generate heuristic information for a classical genetic algorithm (GA).

Theoretical Foundation (BipartiteGBS):
- Unlike standard GBS, which uses single-mode squeezed states and yields probabilities proportional to the squared Hafnian of symmetric matrices, BipartiteGBS utilizes two-mode squeezed states and two interferometers.
- This architecture allows the output probabilities to be proportional to the squared permanents of submatrices of arbitrary (non-symmetric) complex matrices. This makes BipartiteGBS a natural candidate for encoding directed graph adjacency matrices.
- The authors define the Max-Perm problem: finding a $k \times k$ submatrix that maximizes the squared permanent. They derive a closed-form expression for the sampling enhancement factor ( $R_{Per}$ ), demonstrating that BipartiteGBS provides a significant bias toward submatrices with large permanents compared to uniform classical sampling.
Heuristic Mapping:
- The paper establishes a connection between the permanent of a directed graph's adjacency matrix and its edge density. While a large permanent does not guarantee a Hamiltonian cycle, it suggests the presence of dense local substructures (cycle covers) that may contain cycle edges.
- The authors treat BipartiteGBS samples as "informative" local evidence. Specifically, they extract:
  - Vertex Subsets: Sets of vertices ( $S \cup T$ ) that frequently co-occur in collision-free, balanced samples.
  - Edge Co-occurrence Frequencies: The empirical frequency with which the endpoints of a directed edge appear together in these sampled vertex pools.
Algorithmic Integration (BipartiteGBS-GA):
- A Genetic Algorithm (GA) is enhanced using the data derived from BipartiteGBS.
- Guided Initialization: The initial population is seeded with permutations constructed from BipartiteGBS-sampled subgraphs and high-frequency edges, rather than purely random permutations.
- Enhanced Fitness: The fitness function combines the standard metric (fraction of valid edges in a path) with a weighted term based on the BipartiteGBS-derived edge co-occurrence frequencies.
- Guided Mutation: The mutation operator occasionally targets low-frequency edges for repair, guided by the quantum sampling data.
- Multi-Stage Variant (MS-BipartiteGBS-GA): A two-stage approach is proposed where a fast classical GA runs first to find a good path; the edges of this path are then reinforced, and a BipartiteGBS-guided GA runs subsequently to refine the search.

Key Contributions

Novel Application of BipartiteGBS: The paper is the first to propose a BipartiteGBS-based algorithm specifically for directed graph problems, moving beyond the symmetric constraints of standard GBS.
Max-Perm Problem Formulation: It introduces the Max-Perm problem as a canonical optimization task for BipartiteGBS and derives a theoretical sampling enhancement factor relative to uniform classical sampling.
Hybrid Quantum-Classical Framework: It demonstrates a practical pipeline where quantum sampling provides structural priors (subgraphs and edge frequencies) to guide a classical stochastic optimizer.
Ablation Analysis: Through rigorous component-level testing, the paper identifies that BipartiteGBS-guided initialization is the dominant contributor to performance gains, while continuous biasing of fitness and mutation operators yields diminishing or neutral returns.

Results

Numerical simulations were conducted on Erdős–Rényi random directed graphs with sizes ranging from $n=15$ to $n=40$ and edge probability $p=0.3$ .

Success Rates: The BipartiteGBS-enhanced algorithms (BipartiteGBS-GA and MS-BipartiteGBS-GA) consistently achieved higher success rates in finding Hamiltonian cycles compared to a standard GA and a degree-centrality-based GA (Degree-GA). For example, at $n=40$ , MS-BipartiteGBS-GA achieved a ~71.3% success rate versus ~60.0% for the standard GA.
Path Length: In cases where a full Hamiltonian cycle was not found, the BipartiteGBS-enhanced methods produced significantly longer valid paths, indicating a superior ability to extract and exploit partial structural information.
Ablation Findings: The "InitOnly" variant (using BipartiteGBS data only for initialization) often outperformed the full BipartiteGBS-GA (which also modified fitness and mutation). This suggests that the quantum sampling is most effective as a proposal mechanism for the initial population, while standard evolutionary operators are better suited for subsequent refinement.
Baseline Comparison: The Degree-GA (using simple vertex degree statistics) underperformed the standard GA, confirming that the improvement comes from the structural information (subgraphs and co-occurrence) provided by BipartiteGBS, not just simple vertex centrality.

Significance and Claims

The paper claims that permanent-based photonic sampling can provide useful algorithmic guidance for asymmetric combinatorial search problems.

Heuristic Nature: The authors explicitly state that their results represent a heuristic enhancement and do not constitute a claim of complexity-theoretic quantum advantage for solving the Hamiltonian cycle problem. The method improves the efficiency of classical search by providing better starting points and structural priors.
Scalability: The approach is designed to be scalable, as the quantum sampling step is a one-time preprocessing cost per graph instance, while the heavy lifting of the search is performed by the classical GA.
Future Directions: The authors suggest that the framework could naturally extend to other directed graph problems, such as the Traveling Salesman Problem (TSP), and note that experimental implementation on photonic chips is a necessary next step to evaluate the impact of real-world noise and loss.