A Temperature Change can Solve the Deutsch-Jozsa Problem : An Exploration of Thermodynamic Query Complexity

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.

v3: 5 + 6 pgs, 7 figures, overhauled presentation, new appendix, nicer inequalities, comments welcome!

References in corpus (22)

• Spins in few-electron quantum dots
• Circuit Quantum Electrodynamics
• Electron transport through double quantum dots
• Silicon Quantum Electronics
• Quantum Thermodynamics
• The role of quantum information in thermodynamics --- a topical review
• On the Power of One Bit of Quantum Information
• How small can thermal machines be? The smallest possible refrigerator
• Entanglement Generation is Not Necessary for Optimal Work Extraction
• The Quantum Absorption Refrigerator
• Virtual qubits, virtual temperatures, and the foundations of thermodynamics
• Thermometry in the quantum regime: Recent theoretical progress
• Quantum thermal absorption machines: refrigerators, engines and clocks
• Quantum Thermal Machine as a Thermometer
• Landauer vs. Nernst: What is the True Cost of Cooling a Quantum System?
• Exponential speed-up with a single bit of quantum information: Testing the quantum butterfly effect
• Performance of autonomous quantum thermal machines: Hilbert space dimension as a thermodynamic resource
• Unifying paradigms of quantum refrigeration: A universal and attainable bound on cooling
• Thermally driven quantum refrigerator autonomously resets superconducting qubit
• Testing integrability with a single bit of quantum information
• Power of one non-clean qubit
• Certifying quantum enhancements in thermal machines beyond the Thermodynamic Uncertainty Relation