I am reading this paper on the state separability problem, and came across the term “Permutation Test.” This is on page 7 section 2.3.
Apparently, the more famous SWAP test is a special case of permutation test; but I’ve never heard of it.
The steps are below:
- Prepare a quantum state with $ceil(nlogn)$ qubits (the paper said $n!$ dimensional, which is $O(nlogn)$. Call this state $W$
- Perform a quantum Fourier transform on this state
- “Apply a controlled-permutation unitary that permutes registers A1,...,An according to the permutation indexed in register W.” (From the paper directly, a step I don’t really understand)
- Perform an inverse Quantum Fourier Transform on $W$
How does this test work? I can’t find it on Google; does it go by a different name?
Here is an image of the paper for reference.
