Relation graph isomorphism to discrete logarithm $\DeclareMathOperator\ora{ora}$Let $A_0$ be the adjacency matrix of graph $G$ and $P_0$
permutation matrix of multiplicative order $\rho$.
Let $X$ be positive integer and $B_0=P_0^X A_0 P_0^{-X}$.

Q1 Given $A_0,P_0,B_0$ can we find $X$ efficiently?

Positive answer need not mean graph isomorphism is efficient,
since in GI we don't know $P_0$.
Related problem:
Given $P_0$ and $C_0=P_0^Y$ we can find $Y$ efficiently since
$\rho$ is divisor of factorial $n$ and $n$-smooth.
Another relation:
Assume $\ora(U)$ is an oracle which computes $P_0^{U X} A_0 P_0^{-U X}$
given integer $U$.
Assume $X=d d'$ where $d$ is factor of $\rho$.
Then $\ora(\frac{\rho}{d})=P_0^{\rho d'} A_0 P_0^{-\rho d'}=A_0$ and we have information about $X$.
Repeat the same idea for other factors of $\rho$ and multiplying
by small powers of $P_0$ to get congruences and $X$ via crt.
In an answer Joseph Van Name appears to claim the following
which is very close to computational diffie-hellman problem (CDH).
Given $P_0^X A_0 P_0^{-X}$ and $P_0^Y A_0 P_0^{-Y}$, he can efficiently
compute $P_0^{X+Y} A_0 P_0^{-X-Y}$
Setting $X=Y$, he can double $P_0^X, P_0^{2X},P_0^{4X} \ldots P_0^{2^kX}$  and by repeated doublings,
he can compute $\ora(U)$.

Q2 Does Joseph's attack works for Q1?


Q3 Can we drop knowing $P_0$ and find $P_0^X$ efficiently from only $A_0,B_0$?

 A: Yes. We can efficiently find all integer solutions $X$ to the equation $B_{0}=P_{0}^{X}A_{0}P_{0}^{-X}$ since we can either conclude that there is no integer $X$ with $B_{0}=P_{0}^{X}A_{0}P_{0}^{-X}$ or we can show that $B_{0}=P_{0}^{X}A_{0}P_{0}^{-X}$ precisely when $X$ satisfies a system of linear congruence equations.
Suppose that the permutation corresponding to $P_{0}$ can be written as a product of $r$ disjoint cycles of lengths $n_{1},\dots,n_{r}$. Without loss of generality, we may therefore assume that $P_{0}$ is a block matrix $(P_{i,j})_{1\leq i\leq r,1\leq j\leq r}$ where each entry $P_{i,j}$ is the $n_{i}\times n_{j}$-zero matrix whenever $i\neq j$ and where each $P_{i,i}$ is an $n_{i}\times n_{i}$-permutation matrix corresponding to the cycle permutation.
Let us make $A_{0},B_{0}$ as well into block matrices. Suppose that $A_{0}=(A_{i,j})_{1\leq i\leq r,1\leq j\leq r}$ and
$B_{0}=(B_{i,j})_{1\leq i\leq r,1\leq j\leq r}$ where each $A_{i,j},B_{i,j}$ is an $n_{i}\times n_{j}$-matrix.
Then $$P_{0}^{X}A_{0}P_{0}^{-X}=(P_{i,i}^{X}A_{i,j}P_{j,j}^{-X})_{1\leq i\leq r,1\leq j\leq r}.$$ Therefore, $P_{0}^{X}A_{0}P_{0}^{-X}=B_{0}$ if and only if
$B_{i,j}=P_{i,i}^{X}A_{i,j}P_{j,j}^{-X}$ for each $i,j$.
If there exists $i,j$ where $B_{i,j}\neq P_{i,i}^{X}A_{i,j}P_{j,j}^{-X}$ for all integers $X$ with $0\leq X<\text{Lcm}(m_{i},m_{j})$, then there does not exist an integer $X$ with $B_{i,j}\neq P_{i,i}^{X}A_{i,j}P_{j,j}^{-X}$, and therefore the equation $B_{0}=P_{0}^{X}A_{0}P_{0}^{-X}$ has no solution.
On the other hand, if for each pair $i,j$, there exists an integer $X_{0}$ with $0\leq X_{0}<\text{Lcm}(m_{i},m_{j})$ where $B_{i,j}=P_{i,i}^{X_{0}}A_{i,j}P_{j,j}^{-X_{0}}$, then
$$H=\{Y\in\mathbb{Z}\mid B_{i,j}=P_{i,i}^{X}B_{i,j}P_{j,j}^{-X}\}$$ is a subgroup of $\mathbb{Z}$ of index at most $\text{Lcm}(m_{i},m_{j})$. If $v_{i,j}$ is the index of $H$, and $u_{i,j}=X_{0}$, then
$B_{i,j}=P_{i,i}^{X}A_{i,j}P_{j,j}^{-X}$ if and only if $X=u_{i,j}\mod v_{i,j}.$ Therefore, $P_{0}^{X}A_{0}P_{0}^{-X}=B_{0}$ if and only if
$X=u_{i,j}\mod v_{i,j}$ for $1\leq i\leq r,1\leq j\leq r.$ One can easily find the (possibly empty) set of all integer solutions $X$ to the equation $B_{0}=P_{0}^{X}A_{0}P_{0}^{-X}$.
A: This is more of a comment than a new answer because it uses no more technique than Joseph's answer. The expression of the problem in terms of graphs or 0-1 matrices is a red herring and I suggest a more natural formulation is as follows.
Let $\varOmega$ be a finite set and let $\gamma$ be a permutation acting on $\varOmega$. Let $X,Y\subseteq \varOmega$ be two subsets. The question is: Does there exist $k$ such that $\gamma^k(X)=Y$, and if so how do we find it?
I'll show it is equivalent. Given the matrix problem, let $\varOmega$ be the set of matrix positions, and let $\gamma$ be the action of $P_0$ on them. In the other direction, consider matrices of order $|\varOmega\times\varOmega|$ with only zeros off the diagonal.
To solve it, use Joseph's approach. If anything goes wrong in the following there is no solution. Say $C_1,\ldots,C_n$ are the cycles of $\gamma$ and $X_i,Y_i$ are the restriction of $X,Y$ to cycle $C_i$. For each cycle $C_i$ there are $u_i,v_i$ such that
$$K_i := \{ k \mid \gamma^k(X_i)=Y_i\} = \{u_i + jv_i\mid j\in\mathbb{N}\}.$$
The constants $u_i$ and $v_i$ are no larger than $|C_i|$ so finding them is trivial. Now we just use Chinese Remainder Theorem technology to find an integer that lies in every $K_i$.
