Metraipolis › archive › dc_3a087726612e

Computational Work Extraction: The Complexity of Catalysts — arXiv:2609.40323

Source
arXiv (en)
Original
https://arxiv.org/abs/2609.40323
License (as archived)
CC0-1.0
Archived
2026-10-07T15:18:05.996Z
SHA-256 of the archived text
f72064db4e539edf69743a06d4d1b1519455b6b270901dff89b5b753e3d5b7bb
Stable URL of this page
https://metraipolis.com/documento/dc_3a087726612e

How to cite

Computational Work Extraction: The Complexity of Catalysts — arXiv:2609.40323 — arXiv (en), https://arxiv.org/abs/2609.40323 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_3a087726612e (Metraipolis archive dc_3a087726612e, sha256 f72064db4e539edf69743a06d4d1b1519455b6b270901dff89b5b753e3d5b7bb)
BibTeX
@misc{dc3a087726612e,
  title = {Computational Work Extraction: The Complexity of Catalysts — arXiv:2609.40323},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.40323},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_3a087726612e; sha256 f72064db4e539edf69743a06d4d1b1519455b6b270901dff89b5b753e3d5b7bb},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.40323. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

We prove maximal separations: $n$-qubit systems can have $\Theta(n)$ ergotropy, while every efficient process extracts negligible work, even for Hamiltonians consisting of single-qubit terms. We establish an unconditional existential separation and give an explicit construction in the random oracle model. Assuming the existence of quantum-secure pseudorandom functions, this separation extends to the plain model. This work uncovers an important connection between ergotropy and the complexity of catalytic computation---computation where auxiliary qubits must be finally restored to their initial state. Relative to a random oracle, we establish relational and decision problems that: (i) can be solved efficiently with $\lambda$ catalysts; but (ii) cannot be solved by any algorithm with $c\lambda$ catalysts, for any $c<1$. We show this by proving query lower bounds for quantum-space bounded algorithms. As a consequence, for computational ergotropy, catalysts prove to be surprisingly powerful---there is a family of Hamiltonians and states for which catalysts enable efficient extraction of the full $\Theta(n)$ ergotropy, while every efficient non-catalytic process extracts negligible work. Furthermore, catalysts also allow us to introduce and instantiate the notion of pseudoergotropy---analogous to pseudorandomness. On the other hand, we show catalysts do not change (information-theoretic) ergotropy. Finally, our work also sheds light on the classical aspect of the problem. First, most of our constructions rely on classical states and Hamiltonians and therefore imply analogous results for classical ergotropy. Second, we show that certain proof of quantumness protocols can be used to generically separate classical and quantum catalytic ergotropy.

Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-10-01 in cs.CC).
Categorie arXiv: Quantum Physics (quant-ph) ; Computational Complexity (cs.CC).
Pagina del lavoro: https://arxiv.org/abs/2609.40323 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-07T14:51:27.492Z dalla pagina https://arxiv.org/catchup/cs.CC/2026-10-01?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).