Two matrices $A, B \in \mathbb R^{n \times n}$ are called unitarily equivalent if there exists an unitary matrix $U \in \mathbb C^{n \times n}$ such that $A = U B U^{\ast}$. If in addition $U$ is a permutation matrix, then we call $A$ and $B$ permutation similar.
Suppose that $A$ and $B$ are unitarily equivalent permutation matrices. Are they permutation similar too?
Here's a direct proof that if permutation matrices $A,B$ (of size $n\ge 0$) have the same characteristic polynomial (or equivalently are linearly equivalent, since these are diagonalizable) then they are conjugate as permutations, i.e., have the same cycle decomposition.
If $A,B$ have some cycle of common size, then we can "remove" it (which divides the characteristic polynomial by the same factor while reducing the matrix size). So we can suppose there are no cycles of common length in $A$ and $B$. In this case, we have to prove that $n=0$.
Consider a cycle of maximal length $m$ occurring in either $A$ or $B$, say in $A$. Then $\xi=\exp(2i\pi/m)$ is a root of the characteristic polynomial of $A$, and hence of $B$. But since $B$ has only cycles of length $<m$, its characteristic polynomial does not vanish at $\xi$, and we get a contradiction.
The answer is yes by an old theorem of Brauer. In fact, permutation matrices are conjugate over any field if and only if they are conjugate by permutation matrices. See this beautiful proof by Kovacs https://londmathsoc.onlinelibrary.wiley.com/doi/abs/10.1112/blms/14.2.127.
Edit. Let me add that this was originally proved in the paper Brauer, Richard, On the connection between the ordinary and the modular characters of groups of finite order. Ann. of Math. (2) 42 (1941), 926–935. Laci Kovacs gave a very short elegant proof that works in all characteristics in the link. I believe the easiest characteristic $0$ proof is the one I sketched in the comments to @Ycor's answer, namely that if $A$ and $B$ are conjugate matrices, then $A^m$ and $B^m$ have the same trace for all $m>0$. This means that the corresponding permutation matrices have the same number of elements with an orbit of size dividing $m$ for all $m$. An easy inductive argument (or Mobius inversion argument on the divisor poset) then shows they have the the same number of orbits of each size and hence are conjugate in the symmetric group.
