Find Min Copies Needed for Certainty of Permuted Qubits w/ General State

[Dragonfall]

Suppose you have a general state of n-qubits, and you have a second copy with the same state, but with the qubits permuted in some order. Suppose you have given lots of copies of these pairs. What is the minimum number of such copies needed to find the permutation with high certainty as a function of n?

Note that this is a GENERAL state, not a tensor product of n qubits. In the case of a tensor product, the number of copies needed to be almost certain grows linearly with n.

 

[Dragonfall]

Need input fast!

 

[Dragonfall]

I have some very, very bad bounds for it:

Upper: O(M!)
Lower: O(log M)

Now the upper bound is obvious. The lower bound is O(log M) because each permutaiton on M objects takes MlogM bits to describe. By Holevo's theorem M qubits can contain at most M usable classical bits of information. Therefore at least log M copies of the pair is needed.

Of course these bounds might as well not exist for how bad they are. Does anyone have any suggestions on how to improve them?