Timeline for What is the most efficient way to generate a random permutation from probabilistic pairwise swaps?
Current License: CC BY-SA 2.5
5 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Mar 8, 2011 at 17:54 | history | edited | Frédéric Grosshans | CC BY-SA 2.5 |
added 32 characters in body
|
| Mar 8, 2011 at 17:26 | comment | added | Frédéric Grosshans | Indeed. I forgot too check the uniformity for $n=4$... | |
| Mar 8, 2011 at 17:24 | history | edited | Frédéric Grosshans | CC BY-SA 2.5 |
added 107 characters in body
|
| Mar 8, 2011 at 16:35 | comment | added | Joe Fitzsimons | I don't believe that these do perform uniform permutations. In fact, I think it is impossible to do exactly with such gates if you fix the probability to be 1/2. The reason for this is simple: imagine a circuit which uses $m$ such gates. Then there are $2^{m}$ equiprobable computational paths, and so any permutation must occur with probability $k 2^{-m}$ for some integer $k$. However, for a uniform distribution we require that $k 2^{-m} = \frac{1}{n!}$. Clearly this can't be satisfied for an integer value of $k$ for $n\geq 3$. | |
| Mar 8, 2011 at 15:58 | history | answered | Frédéric Grosshans | CC BY-SA 2.5 |