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...