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

  • Context: Graduate 
  • Thread starter Thread starter Dragonfall
  • Start date Start date
  • Tags Tags
    Qubits
Click For Summary
SUMMARY

The discussion focuses on determining the minimum number of copies required to identify the permutation of n-qubits in a general state with high certainty. The upper bound is established at O(M!) and the lower bound at O(log M), based on the principles of information theory and Holevo's theorem. The participants emphasize the inadequacy of these bounds and seek methods to enhance them for better accuracy in permutation identification.

PREREQUISITES
  • Understanding of quantum computing principles, specifically n-qubits.
  • Familiarity with permutation theory in combinatorics.
  • Knowledge of Holevo's theorem and its implications on quantum information.
  • Basic grasp of algorithmic complexity, particularly factorial and logarithmic growth.
NEXT STEPS
  • Research advanced quantum algorithms for permutation identification.
  • Study the implications of Holevo's theorem on quantum information limits.
  • Explore combinatorial optimization techniques to refine bounds on copies needed.
  • Investigate existing literature on quantum state discrimination and its applications.
USEFUL FOR

Quantum computing researchers, theoretical physicists, and anyone involved in quantum information theory looking to optimize permutation identification processes in quantum states.

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
Need input fast!
 
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?
 

Similar threads

Undergrad Bloch Sphere generalization for more than one qubit
  • · Replies 4 ·
Replies
4
Views
1K
Graduate Shor's algorithm - need to uncompute auxiliary qubits?
  • · Replies 2 ·
Replies
2
Views
3K
Graduate Can anyone give me the details of creating a cat state in Circuit QED?
  • · Replies 16 ·
Replies
16
Views
4K
Sending drive Pulse in CQED and visualize the state by QuTip
  • · Replies 6 ·
Replies
6
Views
4K
Undergrad Schmidt decomposition and entropy of the W state
  • · Replies 1 ·
Replies
1
Views
2K
High School Time-reversal of an unknown quantum state
  • · Replies 1 ·
Replies
1
Views
2K
Graduate Quantum Teleportation - Misconceptions and QM fundamentals
  • · Replies 5 ·
Replies
5
Views
2K
High School How to teach beginners in quantum theory the POVM concept
  • · Replies 62 ·
3
Replies
62
Views
10K
Graduate Question about factoring the Klein-Gordon equation
  • · Replies 6 ·
Replies
6
Views
2K
Graduate Math suggestions for learning QM
  • · Replies 4 ·
Replies
4
Views
3K