Computational hardness for sampling a uniform matching

Question

A famous result of Jerrum, Sinclair, and Vigoda shows that there exists a polynomial-time algorithm which takes a bipartite graph $G$ and produces a random perfect matching $M$ of $G$ (assuming one exists), so that the distribution of $M$ is arbitrarily close to uniform in total variation distance. This is sufficient to give a randomized approximation scheme for the number of perfect matchings of $G$.

Since Valiant has shown that the permanent of a binary matrix is $\#\mathsf{P}$-hard, we do not expect to be able to compute the number of perfect matchings of a bipartite graph $G$ exactly. I suspect that generating a uniformly random perfect matching of $G$ is also hard, but I do not know of any complexity theory evidence for this. So my question is:

Is there any evidence that sampling a uniformly random perfect matching $M$ of a bipartite graph $G$ is computationally hard?

The important bit that differentiates between this question and the JSV result is that the distribution of $M$ is required to be exactly uniform. Any computational hardness here would have to be conditional, because if we could compute the number of perfect matchings in any bipartite graph, then we could also sample a uniformly random matching.

More generally, how does one show conditional hardness for sampling problems?

Answer 1

Concerning your general question, I think the paper by Aaronson and Arkhipov [1] on boson sampling is a good example. They show that if there exists a classical poly-time algorithm that exactly (or at least "extremely accurate" as they state it) samples from a certain distribution, then the polynomial hierarchy collapses up to some level.

To prove the same thing for an approximate sampling algorithm, they must rely on some unproven conjectures.

[1] Aaronson, Scott, and Alex Arkhipov. "The computational complexity of linear optics." Proceedings of the forty-third annual ACM symposium on Theory of computing. ACM, 2011.