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

  • Level: Graduate 
  • Thread starter Thread starter Dragonfall
  • Start date Start date
  • Tags Tags
    Qubits
Join the discussion
Registration is free. Start your own thread to ask a follow-up.
Sign up Log in
2 replies · 2K views
Dragonfall
Messages
1,023
Reaction score
5
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.
 
Physics news on Phys.org

Discussion

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?