2 ms·
These are the two problems they solve stochastically: The Max-Haf problem is, for a complex-valued matrix B of any dimension, to find a submatrix BS of fixed e
by tromp 3y ago
These are the two problems they solve stochastically:
The Max-Haf problem is, for a complex-valued matrix B of any dimension, to
find a submatrix BS of fixed even dimension k = 2m, with
the largest Hafnian in square of absolute value. Hafnian was
originally introduced in interacting quantum field theory and
plays a variety of roles in physics and chemistry [8, 30–36].
When the matrix is an adjacency matrix composed of 0s and
1s, Hafnian can be interpreted as the number of perfect matching of the graph [11].
The dense k-subgraph problem is, for an n-vertex graph
G with adjacency matrix ∆, to find its subgraph of k < n
vertices GS with the largest density
W (GS) = X k i,j=1 (∆S) i,j , (4)
where ∆S is the adjacency matrix of GS.
The dense k-subgraph problem is of fundamental interest
in both mathematics [37] and applied fields like data mining,
bioinformatics, finance and network analysis [38–45].
Their use of a 144-node fully-connected photonic processor means they're limited to solving graphs on 144 nodes...
- inhumantsar 3y agoWell I understood the first and last sentence. Brb while I go back to uni to understand the rest.
- CaptainNegative 3y agoDense k-Subgraph, eh? I wrote a dissertation on that in a past life. From a quick read of the paper, it looks like the only classical algorithms they compare to are greedy, random search, and simulated annealing (which is more or less random plus greedy). For random or semi-random instances like those described in this writeup, there are oftentimes substantially better classical algorithms (both random and deterministic) that one can use to try to find dense components (including, ironically, so-called "spectral" algorithms which are entirely classical). They don't provide the specific parameter setting so I can't give a single definitively better method, but I'm relatively unimpressed by their finding that a somewhat heavily engineered approach can defeat a handful of braindead classical algorithms.