jkernel-docker VS pygraphblas

I put this together about a year ago to run J/Jupyter in binder https://github.com/joebo/jkernel-docker

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

Yes, multiplying graph adjacency matrices over a min-tropical semiring produces shortest paths. APL supports this syntactically, but how does it function in the real world? What if the matrices are extremely sparse, like almost all real world graphs are? Syntax is the easy the problem. The hard problem is having very sparse graphs with billions of nodes and many billions of edges. How is your square matrix going to deal with that? Sparse and hypersparse graph computing is hard, which is not syntactically relevant.

Python does not have this terse a syntax, but it gets very close with multiple bindings to the SuiteSparse GraphBLAS Hypersparse graph processing libraries, which intrinsically supports sparse graphs and a very large number of operators, including the tropical min/max ones. Suitesparse doesn't provide syntax (that's the easy part), it provides the hard part, sparse and hypersparse data structures and very complex dynamic, parallel graph processing optimizations including JIT compilation of GPU accelerated operations.

Here's a notebook that shows your shortest path example using Python and the GraphBLAS. While it's a trivial example, it can scale the the largest graphs possible to use today using SuiteSparse:

https://github.com/Graphegon/pygraphblas/blob/main/demo/Intr...

Using Linear Algebra to solve Graph problems, in particular, algebra over Tropical Semirings. Here's a great, but not graph specific, introduction to the advanced math behind the subject by Madeline Brandt:

https://www.youtube.com/watch?v=S_bVv7Lau-s

There is an open source effort to bring this style of mathematical analysis to graph optimization problems (shortest path, resource scheduling, etc) called the GraphBLAS:

https://graphblas.github.io/

I am the author of the pygraphblas Python binding around the GraphBLAS library, you can find a lot of examples in the demo notebooks shown in the README:

https://github.com/Graphegon/pygraphblas