Are there non-isomorphic graphs with rationally orthogonal similar adjacency matrices?

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?

Yes, there are. The smallest pair are the subdivision graph of $K_{1,3}$ and $C_6$ with an isloated vertex. There are many more, look up "Godsil-McKay switching". The original source is at http://cs.anu.edu.au/~Brendan.McKay/papers/GodsilMcKayCospectral.pdf