Abstract
We demonstrate how a single heat exchange between a probe thermal qubit and multi-qubit thermal machine encoding a Boolean function, can determine whether the function is balanced or constant, thus providing a novel thermodynamic solution to the Deutsch-Jozsa problem. We introduce a thermodynamic model of quantum query complexity, showing how qubit thermal machines can act as oracles, queried via heat exchange with a probe. While the Deutsch-Jozsa problem requires an exponential encoding in the number of oracle bits, we also explore a restricted Bernstein-Vazirani problem, which admits a linear thermal oracle and a single thermal query solution. We establish bounds on the number of samples needed to determine the probe temperature encoding the solution for the Deutsch-Jozsa problem, showing that it remains constant with problem size. Additionally, we propose a proof-of-principle experimental implementation to solve the 3-bit Bernstein-Vazirani problem via thermal kickback. This work bridges thermodynamics and complexity theory, suggesting that quantum thermodynamics could provide an unconventional route to computing beyond classical computation.