1
$\begingroup$

Given a unitary $U$, which implements a random permutation $\sigma$, such that the input to the unitary permutes as here: $|v_1\rangle\otimes\ldots\otimes|v_n\rangle$ becomes $|v_{\sigma(1)}\rangle\otimes\ldots\otimes|v_{\sigma(n)}\rangle$ using $U$.

  1. Is it possible to find the whole permutation using a quantum algorithm? Why? If yes, how?
  2. It is possible to retrieve the fixpoints of the permutation. How can we find them using a quantum algorithm that doesn't need to know the number of fixpoints (nor uses quantum counting)? What can be said about its efficiency*

*: This paper shows how it can be done, however, it needs the number of fixpoints in advance.

If one does not know the number of fixed points, quantum counting can be used to find it.

Thanks.

$\endgroup$
3
  • 1
    $\begingroup$ For (1), what's wrong with the obvious "Try the basis states $|1000\ldots 0\rangle,|0100\ldots 0\rangle,\ldots,|00\ldots 01\rangle$ and measure the output"? When you initialise the single qubit $i$ in $|1\rangle$, the output qubit which is $|1\rangle$ is $\sigma(i)$. $\endgroup$
    – DaftWullie
    Feb 19 at 9:11
  • $\begingroup$ @DaftWullie I would also think so, but a naive counting argument (unlike what I thought initially) does not seem to show that this is optimal: After all, you get $\log(n)$ bits of information per run, while you could get $n$ bits. $\endgroup$ Feb 19 at 11:17
  • $\begingroup$ @DaftWullie The initial state $|v_i\rangle$ may be in a superposition of $|0\rangle$ and $|1\rangle$ $\endgroup$
    – schmector
    Feb 19 at 11:36

1 Answer 1

3
$\begingroup$

To answer 1: Find the smallest Hamming code that acts on $n$ or more bits. Write out its parity-check matrix. Remove as many columns as you need (doesn't matter which ones) so that it only has $n$ columns.

Enter each of the rows of the matrix as a different binary string to your permutation. Read out the answers. This is sufficient to tell you the permutation using only $\lceil\log n\rceil$ queries because the trick is that every column in the parity check matrix is unique. Therefore, when we write out the output strings as a matrix, we will be able to see which column is which, and hence know what mapping has happened.

Example: Consider the Hamming 7 bit code, which has parity check matrix

1 2 3 4 5 6 7
0 0 0 1 1 1 1
0 1 1 0 0 1 1
1 0 1 0 1 0 1

So, we feed the state $|0001111\rangle$ in, and get some output out. We repeat for each of the rows. Now, let's imagine we write these outputs as a table, and found $111$ in column 1. That tells us that $\sigma(7)=1$.

This is a classical algorithm, which is information theoretically optimal, so there's no quantum algorithm that beats it.

$\endgroup$
7
  • $\begingroup$ Nice! -- In fact, this can be explained without knowing about Hamming codes, all one needs is to fill in bit strings representing in binary $0,\dots,n-1$ in the columns. $\endgroup$ Feb 19 at 15:33
  • 2
    $\begingroup$ ... in principle, $\lfloor \log n\rfloor$ queries should even suffice ($\log n! \approx n(\log n-1)$), is there any way to get this one query less? $\endgroup$ Feb 19 at 15:35
  • $\begingroup$ @NorbertSchuch You're just getting greedy! I was really quite pleased with that solution. $\endgroup$
    – DaftWullie
    Feb 19 at 16:18
  • $\begingroup$ And rightfully so, it is remarkably simple and elegant. $\endgroup$ Feb 19 at 17:40
  • $\begingroup$ @DaftWullie Thanks for thinking about this problem! I may be wrong but your algorithm can't differentiate between 0011 and 0011. Abstractly speaking, a permutation may permute abcd to abdc, or even abcd to badc. (as stated in my question). Also your I can't accept your answer either way since it didn't answer point 2. $\endgroup$
    – schmector
    Feb 20 at 1:00

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.