Optimization and experimental realization of the quantum permutation algorithm

Understand

The quantum permutation algorithm provides computational speed-up over classical algorithms in determining the parity of a given cyclic permutation.

• For its $n$-qubit implementations, the number of required quantum gates scales quadratically with $n$ due to the quantum Fourier transforms included.
• We show here for the $n$-qubit case that the algorithm can be simplified so that it requires only $O(n)$ quantum gates, which theoretically reduces the complexity of the implementation.
• In order to test our results experimentally, we utilize IBM's $5$-qubit quantum processor to realize the algorithm by using the original and simplified recipes for the $2$-qubit case.