This is neither an answer nor new information. Here I will try to summarize the discussions which occurred in comments about relations between this problem and sorting networks. In this post, all times are in UTC and a “comment” means a comment on the question unless stated otherwise.

A circuit consisting of probabilistic swap gates (which swap two values randomly) naturally reminds us of a sorting network, which is nothing but a circuit consisting of comparators (which swap two values depending on the order between them). Indeed, circuits for the current problem and sorting networks are related to each other in the following ways:

• The solution by Anthony Leverrier with n(n−1)/2 probabilistic swap gates can be understood as the sorting network for the bubble sort with the comparators replaced by probabilistic swap gates with suitable probabilities. See mkatkov’s comment at March 10 4:53 on that answer for details. The sorting network for the selection sort can also be used in the same way. (In the comment at March 7 23:04, I described Anthony’s circuit as the selection sort, but that was not correct.)
• If we just want every permutation with nonzero probability and do not care about the distribution being uniform, then every sorting network does the job when all the comparators are replaced with probability-1/2 swap gates. If we use a sorting network with O(n log n) comparators, the resulting circuit generates every permutation with probability at least 1/2^{O(n log n)} = 1/poly(n!), as observed in my comment at March 7 22:59.
• In this problem, it is required that the probabilistic swap gates fire independently. If we remove this restriction, every sorting network can be converted to a circuit which generates the uniform distribution, as I mentioned in the comment at March 7 23:08 and user1749 described in greater details at March 8 14:07.

These facts apparently suggest that this problem is closely related to sorting networks. However, Peter Taylor found an evidence that the relation may not be very close. Namely, not every sorting network can be converted to a desired circuit by replacing the comparators with probabilistic swap gates with suitable probabilities. The five-comparator sorting network for n=4 is a counterexample. See his comments at March 10 11:08 and March 10 14:01.

This is neither an answer nor new information. Here I will try to summarize the discussions which occurred in comments about relations between this problem and sorting networks. In this post, all times are in UTC and a “comment” means a comment on the question unless stated otherwise.

A circuit consisting of probabilistic swap gates (which swap two values randomly) naturally reminds us of a sorting network, which is nothing but a circuit consisting of comparators (which swap two values depending on the order between them). Indeed, circuits for the current problem and sorting networks are related to each other in the following ways:

• The solution by Anthony Leverrier with n(n−1)/2 probabilistic swap gates can be understood as the sorting network for the bubble sort with the comparators replaced by probabilistic swap gates with suitable probabilities. See mkatkov’s comment at March 10 4:53 on that answer for details. The sorting network for the selection sort can also be used in the same way. (In the comment at March 7 23:04, I described Anthony’s circuit as the selection sort, but that was not correct.)
• If we just want every permutation with nonzero probability and do not care about the distribution being uniform, then every sorting network does the job when all the comparators are replaced with probability-1/2 swap gates. If we use a sorting network with O(n log n) comparators, the resulting circuit generates every permutation with probability at least 1/2^{O(n log n)} = 1/poly(n!), as observed in my comment at March 7 22:59.
• In this problem, it is required that the probabilistic swap gates fire independently. If we remove this restriction, every sorting network can be converted to a circuit which generates the uniform distribution, as I mentioned in the comment at March 7 23:08 and user1749 described in greater details at March 8 14:07.

These facts apparently suggest that this problem is closely related to sorting networks. However, Peter Taylor found an evidence that the relation may not be very close. Namely, not every sorting network can be converted to a desired circuit by replacing the comparators with probabilistic swap gates with suitable probabilities. The five-comparator sorting network for n=4 is a counterexample. See his comments at March 10 11:08 and March 10 14:01.

This is neither an answer nor new information. Here I will try to summarize the discussions which occurred in comments about relations between this problem and sorting network. In this post, all times are in UTC and a “comment” means a comment on the question unless stated otherwise.

A circuit consisting of probabilistic swap gates (which swap two values randomly) naturally reminds us of sorting network, which is nothing but a circuit consisting of comparators (which swap two values depending on the order between them). Indeed, there are the following relations between circuits for the current problem and sorting networks:

• The solution by Anthony Leverrier can be understood as the sorting network for the bubble sort with the comparators replaced by probabilistic swap gates with suitable probabilities. See mkatkov’s comment at March 10 4:53 on that answer for details. The sorting network for the selection sort can also be used in the same way. (In the comment at March 7 23:04, I described Anthony’s circuit as the selection sort, but that was not correct.)
• If we just want every permutation with nonzero probability and do not care about the distribution being uniform, then every sorting network does the job when all the comparators are replaced with probability-1/2 swap gates. If we use a sorting network with O(n log n) comparators, the resulting circuit generates every permutation with probability at least 1/2^{O(n log n)} = 1/poly(n!), as observed in my comment at March 7 22:59.
• In this problem, it is required that the probabilistic swap gates fire independently. If we remove this restriction, every sorting network can be converted to a circuit which generates the uniform distribution, as I mentioned in the comment at March 7 23:08 and user1749 described in greater details at March 8 14:07.

However, if we require the probabilistic swap gates to fire independently as in the original problem, not every sorting network can be converted to a circuit which generates the uniform distribution by replacing the comparators with probabilistic swap gates with suitable probabilities. The five-comparator sorting network for n=4 is a counterexample. This was shown by Peter Taylor in the comments at March 10 11:08 and March 10 14:01.

This is neither an answer nor new information. Here I will try to summarize the discussions which occurred in comments about relations between this problem and sorting networks. In this post, all times are in UTC and a “comment” means a comment on the question unless stated otherwise.

A circuit consisting of probabilistic swap gates (which swap two values randomly) naturally reminds us of a sorting network, which is nothing but a circuit consisting of comparators (which swap two values depending on the order between them). Indeed, circuits for the current problem and sorting networks are related to each other in the following ways:

• The solution by Anthony Leverrier with n(n−1)/2 probabilistic swap gates can be understood as the sorting network for the bubble sort with the comparators replaced by probabilistic swap gates with suitable probabilities. See mkatkov’s comment at March 10 4:53 on that answer for details. The sorting network for the selection sort can also be used in the same way. (In the comment at March 7 23:04, I described Anthony’s circuit as the selection sort, but that was not correct.)
• If we just want every permutation with nonzero probability and do not care about the distribution being uniform, then every sorting network does the job when all the comparators are replaced with probability-1/2 swap gates. If we use a sorting network with O(n log n) comparators, the resulting circuit generates every permutation with probability at least 1/2^{O(n log n)} = 1/poly(n!), as observed in my comment at March 7 22:59.
• In this problem, it is required that the probabilistic swap gates fire independently. If we remove this restriction, every sorting network can be converted to a circuit which generates the uniform distribution, as I mentioned in the comment at March 7 23:08 and user1749 described in greater details at March 8 14:07.

These facts apparently suggest that this problem is closely related to sorting networks. However, Peter Taylor found an evidence that the relation may not be very close. Namely, not every sorting network can be converted to a desired circuit by replacing the comparators with probabilistic swap gates with suitable probabilities. The five-comparator sorting network for n=4 is a counterexample. See his comments at March 10 11:08 and March 10 14:01.