Let $A_G,A_H$ be the adjacency matrices of two non-isomorphic graphs.

Let $P$ be orthogonal matrix with rational entries.

Is it possible $A_G = P^{-1}A_H P$?

Paper gives algorithm for recognizing rational orthogonal similarity which appears to involve computing the splitting field, which in sage is quite slow.

Is the algorithm in the paper polynomial?