4 ms·
It'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
by gilleain 4y ago
It'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