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.


[![enter image description here][1]][1]

 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$


[![enter image description here][2]][2]

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|.$




  [1]: https://i.sstatic.net/BUW9z.png
  [2]: https://i.sstatic.net/OEJ65.png