If $G$ and $H$ are isomorphic then a bijection between them does what you want (Though I could assure you that two graphs are isomorphic, be telling the truth, and yet it could be hard to find a bijection.) You seem to be interested in the situation that $G$ and $H$ are $n$ vertex graphs which are not isomorphic yet $(A_g)^k$ and ($A_H)^k$ have equal trace for all $1 \leq k \leq n.$
Do you have examples? Do you have examples that don't differ by an obvious switch? Even if you have a compact description of cycles, that doesn't give you a bijection short of ordering them somehow.
Here is a kind of silly example but tell me what bijection you would want:
Both graphs have two vertices and multiple parallel directed edges. The adjacency matrices are
$A_G=\begin{bmatrix} 0 & 1 \\ 4 & 0 \end{bmatrix}$ and $A_H=\begin{bmatrix} 0 & 2 \\ 2 & 0 \end{bmatrix}$
Even for very large $k>n$ the powers have the same trace , and are equal when the trace is not zero:
$A_G^k=A_H^k=\begin{bmatrix} 2^k &0 \\ 0 & 2^k \end{bmatrix}$ for $k$ even.
For odd $k$ we have $A_G^k=\begin{bmatrix} 0 & 1 \\ 4^k & 0 \end{bmatrix}$ and $A_H^k=\begin{bmatrix} 0 & 2^k \\ 2^k & 0 \end{bmatrix}$ both with trace $0.$
A picture is hardly needed but here is one with edge labels.
If you do not want multiple directed edges with the same head and tail then put a vertex at each letter.
LATER
Here is another silly example. The vertices named by letters have indegree=outdegree=$1$ whereas vertex k has indegree=outdegree=$k$
For $j=1,2,3,4,5$ the number of $j$ cycles is $0,9,0,25,0$ in both graphs. Not fully what you wanted, but what would your bijections be for $j=2$ and $j=4$?
We have $|G|=11$ with the $25$ $4$-cycles falling into $10$ of type $2d_i2d_j$ and $15$ of type $5e_i5e_j$
We have $|H|=12$ with the $25$ $4$-cycles falling into $1$ of type $1a1a,$ $3$ of type $4b_i4b_j$ and $21$ of type $6c_i6c_j$
Q: What is your bijection?
NOTES:
One could replace directed $2$-cycles by directed $3$-cycles without changing the example in an essential way.
I'm sure a way could be found to make a similar example such that the traces of $A_G^j$ and $A_H^j$ are equal for $1 \leq j \leq |G|.$