3 ms·
Did they actually find a quantum algorithm for graph isomorphism? I was under the impression that was a major unsolved problem and would be a pretty big deal.
by bawolff 4y ago
Did they actually find a quantum algorithm for graph isomorphism? I was under the impression that was a major unsolved problem and would be a pretty big deal.
I have my doubts...
- gilleain 4y agoIt's now a _solved_ problem - both theoretically (with Babai et al's paper a few years ago) and practically (with nAUTy/Bliss, and similar software). Not sure what the key paper is, but "Graph isomorphism in quasipolynomial time" is at leas relevant: https://dl.acm.org/doi/10.1145/2897518.2897542 https://dl.acm.org/doi/10.1145/2897518.2897542 or perhaps, this arxiv paper: https://arxiv.org/abs/1512.03547 https://arxiv.org/abs/1512.03547 No idea about a quantum algorithm for GI