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?

  • 3
    $\begingroup$ 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$. $\endgroup$ Jul 24 at 8:51
  • $\begingroup$ @MartinSeysen But can you transform your comment into a rigorous proof for an answer to my question? $\endgroup$
    – Learner
    Jul 24 at 16:16
  • $\begingroup$ 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. $\endgroup$ Jul 26 at 14:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.