---
title: "A First Runtime Analysis of Parallel Tempering in Quadratic Optimization"
authors:
  - "Tiago Paixão"
  - "Jorge Pérez Heredia"
  - "Dirk Sudholt"
  - "Andrew M. Sutton"
doi: "10.24963/ijcai.2026/706"
url: "https://ijcai.org/proceedings/2026/706"
pdf: "https://ijcai.org/proceedings/2026/0706.pdf"
venue: "Proceedings of the Thirty-Fifth International Joint Conference on Artificial Intelligence"
year: 2026
pages: "6343-6351"
track: "Main Track"
keywords:
  - "Search: Evolutionary computation"
  - "Search: Combinatorial search and optimisation"
  - "Search: Local search"
---

# A First Runtime Analysis of Parallel Tempering in Quadratic Optimization

Tiago Paixão, Jorge Pérez Heredia, Dirk Sudholt, Andrew M. Sutton

*Proceedings of the Thirty-Fifth International Joint Conference on Artificial Intelligence*, pages 6343-6351. DOI: [10.24963/ijcai.2026/706](https://doi.org/10.24963/ijcai.2026/706)

## Abstract

Parallel tempering, or the replica exchange method, is a Markov Chain Monte Carlo (MCMC) sampling technique for finding low-energy states in complex landscapes by executing multiple processes at different temperatures and allowing for states to migrate between parallel processes based on the Metropolis criterion. Despite a growing interest in the technique as a randomized search heuristic, it is not clear when and why parallel tempering is effective. We conduct a first runtime analysis of the parallel tempering algorithm on a simple quadratic unconstrained binary optimization problem that induces a rugged energy landscape with tunable parameters. We prove that a single-temperature Metropolis process fails to efficiently optimize the problem at any temperature. In sharp contrast, a two-state parallel tempering approach using a low and a high temperature typically solves the problem in O(n^2 log n) iterations. The low-temperature process ensures stability, as it is unlikely to accept worsenings, whereas the high-temperature process facilitates exploration by traversing energy barriers. Improvements are discovered through exploration in the high-temperature process and transferred to the low-temperature process, where they are permanently retained. This effective interplay between processes demonstrates the power of parallel tempering and lends credence to its design.