Quantum Approach Achieves Competitive Graph Coloring Solutions Using Gaussian Boson Sampling

Researchers are increasingly exploring quantum computation for intractable combinatorial problems, and a new study demonstrates a photonic approach to graph coloring using Gaussian Boson Sampling (GBS). Jesua Epequin from EDF (China) Holding Ltd, Pascale Bendotti and Joseph Mikael from EDF Lab Paris-Saclay, et al, reformulate graph coloring as an integer programming problem, cleverly utilising GBS to identify independent sets via clique detection in complement graphs. This work is significant because it benchmarks a quantum-enhanced heuristic against classical methods on both random and real-world smart-charging graphs, suggesting GBS can deliver competitive solutions and potentially unlock a new avenue for quantum optimisation.

This research establishes a method for reformulating graph coloring as an integer programming problem, leveraging the independent set formulation to identify cliques within the complement graph. The team achieved this by encoding the parameters of a Gaussian boson distribution into the adjacency matrix of a graph, enabling the use of GBS to approximate matrix permanents, a task notoriously difficult for classical computers. Experiments show that sampling from these distributions allows for the identification of dense subgraphs with high probability, offering a quantum-enhanced approach to graph-based optimization.

The study unveils a new technique for tackling the NP-complete graph coloring problem, a fundamental challenge with applications ranging from exam scheduling to chemical storage optimization. Researchers reformulated the problem using an independent set formulation, which allows GBS to identify cliques in the complement graph, directly corresponding to independent sets in the original graph. This innovative approach bypasses the limitations of classical algorithms by exploiting the inherent randomness of GBS, a quantum computational model based on linear optics. The work opens possibilities for developing more efficient heuristics for complex combinatorial optimization problems.
This breakthrough reveals the potential of GBS as a practical quantum computing paradigm, motivated by recent experimental demonstrations of quantum advantage using GBS on both static and parametrised Gaussian boson distributions. The researchers benchmarked their GBS-based method against established classical heuristics and exact algorithms, employing two distinct sets of instances: Erdős-Rényi random graphs and graphs derived from a smart-charging use case. Results demonstrate that GBS can provide competitive solutions, highlighting its capacity to approximate solutions to complex problems where classical methods struggle. The research establishes a connection between quantum sampling and classical graph theory, utilising the hafnian function to calculate the probability of observing specific photon patterns in the GBS output.

Specifically, the probability P(s) of observing a pattern of photons |s⟩ is proportional to the determinant of a covariance matrix and the absolute square of the hafnian of a submatrix, As, derived from the graph’s adjacency matrix. By carefully programming the GBS device with appropriate squeezing parameters and a unitary matrix derived from the graph, the team effectively maps the graph coloring problem onto the quantum realm, enabling the exploration of potential solutions through quantum sampling. The study harnessed GBS to identify cliques within the complement graph, directly corresponding to independent sets in the original graph, thereby providing a quantum approach to a classically challenging combinatorial problem. Researchers benchmarked this GBS-driven method against established classical heuristics and exact algorithms, employing two distinct graph instance sets: Erdős-Rényi random graphs and graphs derived from a smart-charging application. This interferometer, described by a matrix A, transformed m input qumodes into m output qumodes, with each qumode represented as a linear combination of photon number states. Researchers defined a state of n single-photons distributed across m qumodes as |s⟩, where sk denotes the photon count in the k-th qumode, subject to the constraint that the sum of sk across all qumodes equals n. Crucially, the study utilised Gaussian states, fully characterised by a complex 2m × 2m covariance matrix σ and a displacement vector d, simplifying state preparation through single-mode squeezing and linear-optical interferometry.

Experiments calculated the probability P(s) of observing a specific photon pattern |s⟩ using the formula P(s) = 1 det(σQ)1/2 Haf(As) s1.…sm., where σQ = σ + I2m/2 and A represents a modified matrix derived from the covariance matrix. The hafnian, Haf(A), was computed over all perfect matching permutations π within the graph, requiring the identification of pairings between nodes to approximate matrix permanents, a computationally intensive task for classical computers. By encoding graph parameters into the covariance matrix σ, the researchers enabled GBS to sample from distributions that highlight dense subgraphs with high probability, effectively leveraging the quantum device’s capacity for approximating these complex calculations. The research reformulates graph coloring as an integer programming problem utilising the independent set formulation, enabling GBS to identify cliques within the complement graph, which directly correspond to independent sets in the original graph. Experiments were conducted using both Erdős-Rényi random graphs and graphs derived from a smart-charging use case to benchmark the method against classical heuristics and exact algorithms. Results demonstrate that GBS can deliver competitive solutions, suggesting a viable pathway for tackling complex graph-based optimisation challenges.

The team measured the performance of GBS in identifying independent sets, a crucial step in solving the graph coloring problem. By encoding graph parameters into a Gaussian boson distribution, the researchers leveraged the quantum device’s capacity to approximate matrix permanents, a computationally intensive task for classical computers. The study focused on utilising GBS to identify dense subgraphs with high probability, effectively approximating solutions to the integer programming formulation of graph coloring. Data shows the method’s efficacy in handling both randomly generated graphs and those representing real-world scenarios like smart-charging infrastructure.

Measurements confirm that GBS successfully identifies cliques in the complement graphs, directly translating to independent sets in the original graphs, a key component of the coloring process. The researchers employed single-mode squeezing and linear-optical interferometry to prepare Gaussian states, crucial for implementing GBS. The probability of observing a specific photon pattern, denoted as P(s), was calculated using the formula P(s) = 1 det(σQ)1/2 Haf(As) s1. sm., where σQ represents the covariance matrix and Haf(As) is the hafnian of the submatrix As. This calculation is fundamental to the GBS process and allows for the sampling of potential solutions.

Tests prove that the method’s performance is competitive with existing classical approaches, particularly for instances where traditional algorithms struggle. The hafnian calculation, central to GBS, allows the approximation of matrix permanents, a computationally hard problem for classical machines. The research highlights the potential of GBS to address NP-complete problems with diverse applications, including exam scheduling, chemical storage optimisation, and matchmaking. Extensive experimentation was conducted on both randomly generated Erdős-Rényi graphs and instances derived from a smart-charging application to assess the performance of GBSC. The results demonstrate that GBSC achieves competitive, and often superior, performance compared to established classical heuristic methods, particularly when dealing with dense graphs where coloring presents significant challenges.

In random graph experiments, GBSC consistently achieved the lowest average excess colours, surpassing algorithms like SLI, RLF, and Dsatur. Furthermore, in the smart-charging use case, GBSC frequently identified optimal colourings and maintained stable performance across varying graph densities and chromatic numbers. The authors acknowledge a key limitation of their work: the experiments were performed using classical simulation, restricting the size of graphs that could be investigated. Future research will focus on scaling up the approach with advancements in photonic quantum computing hardware, specifically addressing challenges related to photon loss and single-photon detection efficiency. This progression could unlock the potential for solving larger, more complex instances of the graph coloring problem and other combinatorial optimisation tasks, suggesting a promising avenue for quantum-enhanced heuristics.