As noted in the comment by James Martin, some assumption is needed on the Markov chain, e.g., that each step of the chain can be implemented on a Turing machine in polynomial time.

The Swendsen-Wang dynamics for the (Ferromagnetic) Ising model on a complete graph $K_n$ mixes in at most $O(n^{1/4})$ iterations, see [1]. More generally, on any graph, this dynamics has polynomial mixing time [2], although the sharp exponent is not known; it is possible that the bound $O(n^{1/4})$ from [1] holds true for all graphs, but the known bounds are far greater.

he Swendsen-Wang dynamics for the Potts model on a complete graph $K_n$ has exponential mixing time at ow temperatures [3].

perhaps most pertinent is the work of Alan Sly [4] that relates sampling to computational hardness.

[1] Long, Yun, Asaf Nachmias, Weiyang Ning, and Yuval Peres. A power law of order 1/4 for critical mean field Swendsen-Wang dynamics. American Mathematical Soc., 2014. https://www.google.com/books/edition/A_Power_Law_of_Order_1_4_for_Critical_Me/YNlVBQAAQBAJ?hl=en&gbpv=1&pg=PP1&printsec=frontcover

[2] Guo, Heng, and Mark Jerrum. "Random cluster dynamics for the Ising model is rapidly mixing." In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1818-1827. Society for Industrial and Applied Mathematics, 2017.

[3] Gheissari, Reza, Eyal Lubetzky, and Yuval Peres. "Exponentially slow mixing in the mean-field Swendsen-Wang dynamics." In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1981-1988. Society for Industrial and Applied Mathematics, 2018.

[4] Sly, Allan. "Computational transition at the uniqueness threshold." In 2010 IEEE 51st Annual Symposium on Foundations of Computer Science, pp. 287-296. IEEE, 2010.

As noted in the comment by James Martin, some assumption is needed on the Markov chain, e.g., that each step of the chain can be implemented on a Turing machine in polynomial time.

The Swendsen-Wang dynamics for the (Ferromagnetic) Ising model on a complete graph $K_n$ mixes in at most $O(n^{1/4})$ iterations, see [1]. More generally, on any graph, this dynamics has polynomial mixing time [2], although the sharp exponent is not known; it is possible that the bound $O(n^{1/4})$ from [1] holds true for all graphs, but the known bounds are far greater.

The Swendsen-Wang dynamics for the Potts model on a complete graph $K_n$ has exponential mixing time at low temperatures [3].

perhaps most pertinent is the work of Alan Sly [4] that relates sampling to computational hardness.

[1] Long, Yun, Asaf Nachmias, Weiyang Ning, and Yuval Peres. A power law of order 1/4 for critical mean field Swendsen-Wang dynamics. American Mathematical Soc., 2014. https://www.google.com/books/edition/A_Power_Law_of_Order_1_4_for_Critical_Me/YNlVBQAAQBAJ?hl=en&gbpv=1&pg=PP1&printsec=frontcover

[2] Guo, Heng, and Mark Jerrum. "Random cluster dynamics for the Ising model is rapidly mixing." In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1818-1827. Society for Industrial and Applied Mathematics, 2017.

[3] Gheissari, Reza, Eyal Lubetzky, and Yuval Peres. "Exponentially slow mixing in the mean-field Swendsen-Wang dynamics." In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1981-1988. Society for Industrial and Applied Mathematics, 2018.

[4] Sly, Allan. "Computational transition at the uniqueness threshold." In 2010 IEEE 51st Annual Symposium on Foundations of Computer Science, pp. 287-296. IEEE, 2010.