4 ms·

This is interesting to me because it's advancing the work on the notion of quantum graph problem solving. I'm sure we've all heard how quantum computers can be

This is interesting to me because it's advancing the work on the notion of quantum graph problem solving. I'm sure we've all heard how quantum computers can be used in the future to decrypt information from today. There's a lot of research out there on how QC may be able to efficiently factor large semiprimes and bust our existing cryptographic algorithms, but to me this is the more mundane side of QC. The exciting side to me is that many graph problems, particularly whole graph problems like connectivity and shortest paths have a potential quantum advantage. This is particularly advantageous for sparse and hypersparse graphs that have billions of nodes but relatively low node degree. Language Models, chemical assay databases, proteomics, causal inference, and fraud detection are just a few problems that involve huge sparse graphs that could get a huge boost from quantum. And to show my own bias here [1], I think the future of graph algorithms, including quantum, is expressing them in Linear Algebraic form with the GraphBLAS API. Using the GraphBLAS, you can write your algorithm in a mathematical form using the multiplication of adjacency matrices that is then synthesized to some optimal form for a given architecture. The same code you write can then be run on a variety of backends, currently CPUs and CUDA using SuiteSparse's new JIT, but soon FPGAs and yes, quantum computers. Parallelism will become so broad and conceptually divergent that you won't even be able to conceive of an efficient hand written single function for all possible platforms. [1] https://github.com/Graphegon/pygraphblas https://github.com/Graphegon/pygraphblas

vlovich123 3y ago
FWIW while existing graph algorithms can't solve it optimally, but they do approach it quite closely using heuristics. It's unclear how much benefit something like this would have for online (i.e. latency-sensitive) applications such as internet routing if the time-constant to setup the QC + execute + get the result is higher compared to a heuristic approach. My hunch is that it won't be useful there for a long time if ever. That being said, for FPGA/ASIC layout & similar problems, it's possible that QC is worth it as an extra optimization level even if slower to get a result in absolute terms to eek out that last bit of optimality (e.g. LTO equivalent). It may also be useful as a way to evaluate how good existing heuristics perform against the true optimal route to see if there's any improvements that can be made to the heuristic algorithms or the heuristics being used themselves.
- michelpp 3y ago
  Yes that's true, there are efficient heuristic graph algorithms for many problems, for example the travelling salesman problem has several good heuristic algorithms that gives you a short path, but perhaps not the exact shortest. But for problems like connected components, there is only one right answer, a component is connected or it is not, there is no useful heuristic solution. Same goes for all shortest paths, yes A* is heuristic for finding an optimally short path from a specific source to a specific destination, but to get all destination shortest paths you have to visit all the nodes anyway, so there is only one useful solution.

vlovich123 3y ago

FWIW while existing graph algorithms can't solve it optimally, but they do approach it quite closely using heuristics. It's unclear how much benefit something like this would have for online (i.e. latency-sensitive) applications such as internet routing if the time-constant to setup the QC + execute + get the result is higher compared to a heuristic approach. My hunch is that it won't be useful there for a long time if ever. That being said, for FPGA/ASIC layout & similar problems, it's possible that QC is worth it as an extra optimization level even if slower to get a result in absolute terms to eek out that last bit of optimality (e.g. LTO equivalent). It may also be useful as a way to evaluate how good existing heuristics perform against the true optimal route to see if there's any improvements that can be made to the heuristic algorithms or the heuristics being used themselves.

michelpp 3y ago
Yes that's true, there are efficient heuristic graph algorithms for many problems, for example the travelling salesman problem has several good heuristic algorithms that gives you a short path, but perhaps not the exact shortest. But for problems like connected components, there is only one right answer, a component is connected or it is not, there is no useful heuristic solution. Same goes for all shortest paths, yes A* is heuristic for finding an optimally short path from a specific source to a specific destination, but to get all destination shortest paths you have to visit all the nodes anyway, so there is only one useful solution.