Hacker News Reader

Comment by ftxbro | Hacker News Reader

In case anyone is wondering, this doesn't 'solve graph problems' with quantum magic any faster than a normal laptop solves them. The preprint is on arxiv: https://arxiv.org/abs/2302.00936v2 but I can't see any supplemental materials on arxiv including any code ("[26] See Supplemental Materials.")

Title and subtitle of the Synopsis on physics.aps.org:

> "Large Photonic Processor Solves Graph Problems: A quantum photonic device can perform some real-world tasks more efficiently than classical computers."

What the paper itself says, which is a "Letter" and not a normal paper with sections like introduction, methods, discussion, conclusions, etc:

> "It is an open question, however, whether the GBS can yield advantage compared to improved classical algorithms and quantum-inspired algorithm."

View on HN

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

Well I understood the first and last sentence.

Brb while I go back to uni to understand the rest.

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

Reply on news.ycombinator.com