Suppose we are given two sequences of qudits, in some states unknown to us: $(|\psi_1\rangle, ... |\psi_n\rangle)$ and $(|\phi_1\rangle, ... |\phi_n\rangle)$. The qudits are not entangled to each other. What procedure can we use to determine whether these are the same sets? That is, how can we determine whether there exists a permutation $\pi$ s.t. for all $i$, $|\psi_i\rangle = |\phi_{\pi(i)}\rangle$?

As is standard we may assume multiple copies of these sets are given, and we wish to minimise the number of copies that we use.

Can we do any better than using the SWAP test on pairs of qubits $O(n^2)$ times?

  • 2
    $\begingroup$ I doubt it: let's say there exists a permutation. It would require $O(n\log n)$ bits to specify what that permutation is, so you're going to need at least that many measurements to obtain that many bits of information. At that point, $O(n^2)$ does not seem so pathological! (I look forward to being proven utterly wrong in the answers...) $\endgroup$
    – DaftWullie
    Oct 20, 2022 at 8:45
  • $\begingroup$ Hi @DaftWullie - I wonder: could you argue $\Omega(\log n)$ copies of the sets are needed based on your intuition? My thought is that since we don’t need to be able to specify the permutation, but just check that sets are equal, so it doesn’t matter so much how many bits are needed to specify a permutation. $\endgroup$
    – shashvat
    Oct 21, 2022 at 18:22


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.