PaperlayerView exact revision on arXiv

Source-linked AI summary

Using Gaussian Boson Sampling to Find Dense Subgraphs

Juan Miguel Arrazola, Thomas R. Bromley

arXiv:1803.10730v2quant-ph

TL;DR

The paper examines whether Gaussian boson sampling can help identify dense subgraphs, an NP-hard optimization problem. It encodes graphs so GBS favors subgraphs with many perfect matchings, then tests GBS-enhanced stochastic search methods. In simulations, GBS improves random search and simulated annealing, with random search particularly effective at low sample counts.

Abstract

from arXiv · show

Boson sampling devices are a prime candidate for exhibiting quantum supremacy, yet their application for solving problems of practical interest is less well understood. Here we show that Gaussian boson sampling (GBS) can be used for dense subgraph identification. Focusing on the NP-hard densest k-subgraph problem, we find that stochastic algorithms are enhanced through GBS, which selects dense subgraphs with high probability. These findings rely on a link between graph density and the number of perfect matchings -- enumerated by the Hafnian -- which is the relevant quantity determining sampling probabilities in GBS. We test our findings by constructing GBS-enhanced versions of the random search and simulated annealing algorithms and apply them through numerical simulations of GBS to identify the densest subgraph of a 30 vertex graph.

S. The function Haf(AS) is the Hafnian of AS [39].

Gaussian boson sampling (GBS) biases stochastic search toward dense subgraphs because output probabilities depend on perfect-matching counts, which track graph density. In simulations on a 30-vertex graph, GBS-enhanced random search and simulated annealing improved over uniform sampling, with GBS random search especially effective at low sample counts.

Applying GBS to the DkS problem

  • For a graph adjacency matrix A, the method sets A := c(A ⊕ A), then post-selects even-k collision-free outputs whose probabilities depend on the selected subgraph’s squared Hafnian.The scale c is chosen below the inverse of A’s largest eigenvalue; the collision-free probability is expected to be close to one when k is much smaller than n.Source: S. The function Haf(AS) is the Hafnian… · p. 2
  • GBS output probability grows with a subgraph’s perfect-matching count, and the increasing relationship between matching count and edge count makes likely samples dense.Dense graphs can have Hafnians many orders of magnitude larger than sparse graphs, while sparse graphs may have zero or negligible Hafnians.Source: S. The function Haf(AS) is the Hafnian… · p. 2

Enhancing stochastic algorithms through GBS

  • GBS can guide both exploration and exploitation: sample candidate subgraphs, then use Hafnian-weighted subsets to choose vertices to keep and replace during tweaks.The tweak routine varies the number of vertices changed using a random parameter m.Source: S. The function Haf(AS) is the Hafnian… · p. 3
  • The enhancement applies across stochastic routines that combine exploration and exploitation, while simulated annealing accepts some lower-density candidates early and becomes more selective as temperature falls.The authors also describe GBS-enhanced random search, which uses exploration alone.Source: S. The function Haf(AS) is the Hafnian… · pp. 2–3

Example DkS problem

  • Below 50 samples, GBS random search outperforms both uniform search and GBS simulated annealing; GBS improves both stochastic methods, while annealing typically beats random search.Simulated annealing also extends beyond the region accessible to the deterministic algorithm, which found 32 edges.Source: Figure 2 · p. 4, S. The function Haf(AS) is the Hafnian… · p. 4

Discussion

  • The planted low-degree structure defeats degree-based deterministic algorithms, although the paper notes that more advanced deterministic methods can address this graph family.The authors frame GBS as a possible enhancement to stochastic optimization, not as a demonstrated speedup over the best optimized classical deterministic methods.Source: Figure 3 · p. 4, S. The function Haf(AS) is the Hafnian… · pp. 4–5

Example DkS problem

  • The numerical test uses brute-force simulation of GBS on a 30-vertex graph with a planted 10-vertex dense subgraph whose vertices have lower average degree than the rest.The planted subgraph is constructed with edge probability 0.875, while the 20-vertex background graph uses probability 0.5; eight edges connect randomly selected vertices across the two graphs.Source: S. The function Haf(AS) is the Hafnian… · pp. 3–4

Discussion

  • The authors identify comparison with highly optimized classical deterministic algorithms as an open question and call for further research on GBS-enhanced optimization.Their heuristics-based approach does not establish a rigorous speedup over the best known classical algorithms.Source: S. The function Haf(AS) is the Hafnian… · p. 5

Appendix

The algorithm initializes with a GBS-sampled subgraph, repeatedly proposes GBS-based vertex replacements, and tracks the best subgraph found.

Appendix

  • The search starts from a submatrix generated by GBS-Explore(k, A).The algorithm takes the graph adjacency matrix A and submatrix dimension k as inputs.Source: Appendix · p. 6
  • Each iteration tweaks the current submatrix by randomly replacing vertices using GBS.Source: Appendix · p. 6
  • A proposed submatrix replaces the current one when its density is higher.Source: Appendix · p. 6
  • The algorithm compares the current submatrix with Best and updates Best when the current density is higher.Source: Appendix · p. 6
Loading 1803.10730v2…