This work introduces an alternative paradigm: a thermodynamic proof of quantumness based on energy consumption, using the search problem of Yamakawa and Zhandry with a structureless uniformly random oracle to show that any classical machine solving the task with constant success probability must generate entropy that grows exponentially with the security parameter.
Abstract
Demonstrating that a machine performs genuinely quantum operations is a central challenge in quantum information processing. Existing proofs of quantumness typically rely on computational tasks that are infeasible for classical machines under assumptions such as computational hardness, or explicit bounds on classical runtime, memory, or oracle queries. Here we introduce an alternative paradigm: a thermodynamic proof of quantumness based on energy consumption. Using the search problem of Yamakawa and Zhandry with a structureless uniformly random oracle, we show that any classical machine solving the task with constant success probability must generate entropy that grows exponentially with the security parameter. By Landauer's principle, this implies an exponential lower bound on heat dissipation and hence on the energy consumption of any cyclic classical implementation. In contrast, the corresponding quantum prover solves the task with polynomial query and gate complexity, giving polynomial energy consumption under standard assumptions for quantum implementations. Thus, in the random-oracle setting, sufficiently low energy consumption in a successful implementation certifies quantumness through a macroscopic thermodynamic observation of energy consumption.
A central question in the theory of quantum advantage is whether there are quantum advantage protocols with similar resource requirements as random circuit sampling that are also verifiable just from the classical outputs of the quantum computation. Here, we develop the idea of simulation secrets for verifiable advanta...
M. Bläser, M. Gullans, D. Hangleiter et al.· arXiv.org· 1 citation
Computational self-testing gives a classical verifier command over the quantum register of a single computationally bounded prover. We use this framework to construct the first argument system for BQP with quasilinear total resource requirements in the circuit model. Our argument system is based on the learning with er...
Finn Holler, Anand Natarajan· arXiv.org· 0 citations
This paper gives a sampling problem that is solvable by shallow quantum circuits, hard for polynomial-time classical algorithms under lattice-based assumptions, and efficiently verifiable by a classical computer, and shows that shallow quantum circuits have sufficient structure to solve certain classically hard tasks w...
It is shown that security of the restricted model of computation, 1/2BQP_1, is built on not only classical hardness for factoring, but also conjectured circuit lowerbounds for rational reconstruction, which permits arbitrary circuits and system sizes.
S. A. Yadavalli, Joel Rajakumar, A. Schuckert et al.· 2 citations
In the quantum query model, it is shown that the honest sampler's ideal score acts as a Tsirelson bound for efficient devices and certified randomness and proves an earlier conjecture for Haar-random states and extends it to Fourier sampling.
Keshav Bhateja, Mehdi Esmaili, A. Mantri· 0 citations
Decoded quantum interferometry (DQI) is a polynomial-time quantum algorithm introduced by Jordan et al. (Nature 2025). For a natural optimization problem, known as optimal polynomial intersection (OPI), it achieves approximation guarantees in regimes where all known classical algorithms require exponential time. Beside...
Ke-Wen Wu, Guang-Xu Yang· 2 citations· ⚡1
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.