Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Permuting Qubits

  1. Aug 24, 2008 #1
    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.
  2. jcsd
  3. Aug 24, 2008 #2
    Need input fast!
  4. Aug 27, 2008 #3
    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?
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook