The no fast-forwarding principle states roughly that, given that we can simulate a Hamiltonian for time $t$ using $r$ gates, in order to perform the Hamiltonian simulation for time $2t$, we must in general use $2r$ gates. But, there are some noteworthy exceptions to this principle, such as Shor's use of modular exponentiation by repeated squaring, and finding out precisely when many-body systems be fast-forwarded is an interesting open problem.

Applying these I initially had a SWAP circuit to rotate colors on the vertices of a square by $90^\circ$, using three SWAP gates with depth three. Naively and following the principle above, I would have guess that a $180^\circ$ degree rotation would require six SWAP gates, but, indeed, we can do a $180^\circ$ rotation of the vertices of a square with only two gates, with depth only one!

Square Rotation

Is it fair to call this (mostly curious) observation an example of a mild fast-forward? Letting $H$ be the circuit for a ninety degree rotation and $H^2$ be the for the 180 degree rotation, we can do $H^2$ quicker than we can even do $H$, so can we say that we can fast-forward the evolution of $H^2$?


1 Answer 1


All swap circuits can be fast forwarded efficiently. In fact any power of any permutation can be done in at most $n-1$ swaps gates with a circuit depth of exactly 2.

An n-qubit permutation can be represented as a list of n integers, where the integer at position $k$ says which position the qubit at position $k$ ends up in the output.

Take an $n$ qubit circuit containing swap gates. Compute its permutation $P$ by starting from a sorted list of integers from 0 to $k-1$, and applying each swap gate to the list.

Given a permutation $P$, you can compute $P^2$ by following the list entries twice. For entry $k$ of $P^2$, look up $r = P_k$ and then look up $P_r$. In other words, $P^2_k = P_{P_k}$. This is efficient to compute. More generally, $(P \cdot Q)_k = P_{Q_k}$.

You can repeat this squaring process to get $P$, $P^2$, $P^4$, $P^8$, $P^{16}$, and so forth up to $P^{2^m}$ for any reasonable sized $m$ you'd like. If you want to simulate for $t$ steps, set $m = \lceil \lg t \rceil$. You can then compute $P^t$ by multiplying together the powers of 2 with a corresponding bit in $t$'s binary representation. For example, if $t = 10000101_2 = 2^8 + 2^3 + 2^1$ then $P^t = P^8 \cdot P^3 \cdot P^1$. This strategy for computing $P^t$ is called repeated squaring. It takes time $O(n \lg t)$.

Once you have the permutation, you can efficiently decompose it into a set of $n-1$ swaps as follows. First, find the disjoint cycles in the permutation by tracking each element forward through the permutation repeatedly until it runs into itself. Doing all cycles this way takes time $O(n)$ total. Each cycle is decomposed separately. To decompose a cycle into two layers, number the cycle's entries in order around the cycle starting from some arbitrary point. Apply one layer of swaps to reverse their order. Then another layer of swaps to reverse the order again, but excluding the first entry. This implements the cycle. Implementing all the cycles implements the permutation. This also takes time $O(n)$ to do.

So in total by using $O(n \lg t)$ classical computation, you found an $O(n)$ cost quantum circuit to fast forward iterating the swap network.

  • $\begingroup$ Thanks! What’s the depth of a circuit to square the rotation of a pentagon $(23451)$? $\endgroup$ Apr 19, 2023 at 18:47
  • $\begingroup$ In the answer I already said all permutations have depth at most 2. So... 2. $\endgroup$ Apr 19, 2023 at 19:35
  • $\begingroup$ Oh snap. I see now. Cool! $\endgroup$ Apr 19, 2023 at 19:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.