# Is there an efficient quantum circuit that create a random permuntation matrix?

Suppose we want to generate a random, random according to some probability distribution, unitary permutation matrix that is applied to an input of $$n$$ qubits. So is there an efficient polynomial time and polynomial space circuit that can generate a random unitary permutation matrix (which is of course dimension a positive power of $$2$$ or $$2^n$$)? If there is no polynomial algorithm (in the above question) then what is the most efficient algorithm instead?

• The number of such random permutation matrices is $f(n) =(2^n)!$. The logarithm of $f(n)$ grows (more than) exponentially with $n$. So you cannot even write down such a random permutation matrix (in any encoding) in space growing polynomially with $n$. Jul 24 at 8:51
• @MartinSeysen But can you transform your comment into a rigorous proof for an answer to my question? Jul 24 at 16:16
• My argument is purely information theroretic: There is no language in which you can encode each matrix of the given set in space polynomial in $n$. I assume that the output of the desired algorithm is a circuit for a specific (uniform distributed) unitary permutation matrix matrix selected at random. Then there is no polynimial-time algorithm that outputs such a circuit, since the average output would be too long. But I'm not sure whether this is what you are looking for. Jul 26 at 14:32