Imagine you're moving apartments with a friend's truck. The deal: you can use the truck all day, but it must come back with the same gas level, same mileage reading, same everything. Sounds impossible — you can't haul furniture without burning fuel. But what if, by routing cleverly through downhill streets, you could exploit the landscape to move everything AND return the truck in its exact original state? That's a catalyst in quantum thermodynamics: auxiliary qubits you borrow, use, and must restore perfectly. This paper proves that access to these catalysts creates an exponential computational separation in how much useful work (ergotropy) you can extract from a quantum system. The committed claim: there exist n-qubit quantum states with Θ(n) extractable work (ergotropy), but every efficient algorithm WITHOUT catalysts extracts negligibly close to zero. Hand the same algorithm catalytic scratch space, and it pulls out the full Θ(n). This is maximal — not a constant-factor gap, but an exponential one. The authors establish this unconditionally via a random oracle construction, and conditionally (assuming quantum-secure pseudorandom functions exist) in the plain model. The mechanism connects two previously separate literatures. In quantum thermodynamics, ergotropy measures the maximum work extractable from a state via unitary operations. In complexity theory, catalytic computation — where auxiliary space must be returned to its initial state — has been studied since Buhrman et al. (2014) showed catalytic logspace is surprisingly powerful. This paper bridges the gap: it proves that catalytic computation's power directly translates into thermodynamic work extraction. The key technical engine is query lower bounds for quantum-space-bounded algorithms, which force non-catalytic processes into an exponential wall. The integrity story is strong for a theory paper. Results are proved, not simulated. The unconditional separation uses a random oracle — standard in complexity theory but always carries the caveat that random oracle separations don't automatically transfer to the real world. The conditional result relies on quantum-secure PRFs, a standard and well-studied cryptographic assumption. There's no cherry-picking risk because these are mathematical proofs, but the real-world thermodynamic relevance depends on whether the Hamiltonians constructed (sums of single-qubit terms) are physically natural or engineered for the proof. A bonus result introduces "pseudoergotropy" — states that LOOK like they have no extractable work to any efficient observer, but actually have Θ(n) ergotropy unlockable with catalysts. This is a direct thermodynamic analog of pseudorandomness, and it's a genuinely new concept. The authors also show that catalysts don't change information-theoretic ergotropy (when you have unlimited computation), so the separation is purely computational. Finally, they connect to proof-of-quantumness protocols, showing these can separate classical and quantum catalytic ergotropy. The classical implications deserve attention. Most constructions use classical states and classical Hamiltonians, meaning the catalytic separation isn't a quantum phenomenon per se — it's a computational phenomenon that happens to have thermodynamic consequences. This makes the results potentially relevant to classical thermodynamic engines with computational constraints, not just quantum devices. At 70 pages, this is a dense theory contribution that advances the interface between quantum complexity and quantum thermodynamics. The next question the field will ask: can these separations be demonstrated on near-term quantum hardware, or are they asymptotic results that live purely in the proof world? The constructed Hamiltonians are sums of single-qubit terms — simple enough to be physically plausible — but the state preparations and catalytic circuits may require resources beyond current devices.
