PaperlayerView exact revision on arXiv

Source-linked AI summary

Computational Work Extraction: The Complexity of Catalysts

Atul Singh Arora, Shantanav Chakraborty, Alexandru Cojocaru, Sreyas Saminathan, Uttam Singh

arXiv:2609.40323v1quant-phcs.CC

TL;DR

Because implementing the unrestricted unitary optimum may be costly, the paper formalizes efficient extraction for growing families. It proves that ergotropy can be inaccessible to efficient processes, while catalysts can make computational extraction maximal.

  • Problem

    Ordinary ergotropy optimizes over all unitaries, but implementing the optimum may be costly; efficiency therefore requires an asymptotic notion over growing state and Hamiltonian families.

    Source: §1 · pp. 4–5

  • Method

    The paper formalizes efficient extraction over growing families, granting polynomially many state copies and an efficient Hamiltonian description, and proves an unconditional separation using Haar-random states, concentration, and counting.

    Source: §1 · p. 5, §1.1 · p. 9

  • Results

    Pure states can store nearly all their energy as ergotropy while efficient extraction is negligible even with single-qubit Hamiltonians; catalysts enable maximal computational extraction despite cλ-space lower bounds.

    Source: §1 · pp. 5, 7

  • Takeaways & Limitations

    The work ties computational ergotropy to catalytic computation: quantum-space limits can remain decisive even when auxiliary registers need not be restored.

    Source: §1 · p. 7

    Allowing catalysts to remain correlated is too permissive: arbitrary-accuracy reachability expands to states with at least the same entropy, and creating correlations carries thermodynamic cost.

    Source: §1 · pp. 5–6

Abstract

from arXiv · show

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.

1 Introduction

The introduction examines how computational efficiency and exact-return catalysts shape work extraction, relating computational and information-theoretic ergotropy. It presents a criterion for catalytic work potential and constructions involving catalytic pseudoergotropy and classical–quantum separation, in the context of computational extraction and unrestricted ergotropy.

1 Introduction

  • Efficient extraction is defined asymptotically over growing families, giving the process polynomially many state copies and an efficient Hamiltonian description from which to produce its circuit.Computational ergotropy is the largest work such efficient processes extract.Source: §1 · p. 5
  • With λ catalysts, computational catalytic ergotropy can be maximal, while algorithms with cλ quantum space for c < 1 extract no non-negligible work.By contrast, catalysts do not increase information-theoretic ergotropy, even when restoration is approximate and the final joint state is close to a product.Source: §1 · pp. 6–7, §1.1 · p. 10
  • Any efficiently describable Hamiltonian with an efficiently preparable ground state meets the paper’s sufficient criterion for maximal catalytic work-potential.Catalytic work-potential is the difference between work efficiently extractable with catalysts and without them.Source: §1 · p. 7
  • Catalysts enable pseudoergotropy: keyed state-and-Hamiltonian families are computationally indistinguishable without the key but have low versus high catalytic ergotropy when keyed.The work-extraction property plays a role analogous to entropy in pseudorandomness.Source: §1 · pp. 7–8
  • For a family under cryptographic assumptions, classical catalytic ergotropy is negligible while quantum catalytic ergotropy is constant, although their information-theoretic ergotropies coincide.Most constructions and maximal-work extraction processes in the paper use classical states, diagonal Hamiltonians, and permutations, yielding analogous classical results.Source: §1 · p. 8

1.1 Main results

  • An unconditional family has ergotropy n−o(n), yet every efficient process extracts only negligible work, even with a single-qubit-term Hamiltonian.The separation also persists for explicit, efficiently preparable states in the random oracle model and, assuming quantum-secure pseudorandom functions, in the plain model.Source: §1 · p. 5, §1.1 · pp. 8–9
  • Information-theoretic catalytic operations that restore a pure catalyst exactly or approximately as a product are essentially equivalent to unitaries on the system alone.Thus catalysts do not substantially alter information-theoretic ergotropy; the computational setting is where their effect changes the theory.Source: §1 · p. 7, §1.1 · pp. 9–10
  • In the random oracle model, a decision problem is solvable with λ catalysts but not with cλ catalysts for any c < 1.The related query lower bound is exponential for algorithms with at most cλ auxiliary qubits, even when they need not restore those qubits.Source: §1 · p. 7, §1.1 · p. 10

Catalytic Work-Potential

  • For efficient extensive Hamiltonians on 2λ qubits, a polynomial-catalyst algorithm with tr[Hλσλ] = non-negl(λ) suffices to establish catalytic work potential.This is the criterion stated for Hamiltonians acting on n(λ) = 2λ qubits.Source: Catalytic Work-Potential · p. 11
  • Quantum-secure pseudorandom permutations yield an efficiently sampleable keyed distribution with (0, 4λ)-catalytic-pseudoergotropy using polynomially many catalysts.The number of catalysts depends on the pseudorandom permutation used.Source: Catalytic Work-Potential · p. 12
  • Under classical factoring hardness, Theorem 9 gives a classical-versus-quantum catalytic ergotropy separation in the common-reference string model.The result can be instantiated with a two-message, public-coin proof-of-quantumness protocol whose completeness and soundness can be made almost perfect; the setup allows negligible error in catalytic restoration.Source: Catalytic Work-Potential · p. 12

1.2 Prior Work

  • Approximate catalyst restoration increases maximum extractable work by at most ε^2∥H∥∞, while exact uncorrelated catalysts leave unrestricted ergotropy unchanged [LBWN24b].The bound applies when the joint unitary maps every pure system state with a fixed pure catalyst to within trace distance ε of a product state whose catalyst factor is the initial state.Source: §1.2 · pp. 12–13
  • In the random oracle model, reusable workspace creates an exponential separation in unitary computation with only a constant-factor increase in total space, despite leaving information-theoretic ergotropy unchanged.The paper’s catalysts are known fixed states, and its algorithms assume auxiliary qubits initialized to zero and returned exactly and uncorrelated.Source: §1.2 · p. 13
  • With a permutation key, classical reversible extraction recovers full ergotropy using exactly restored auxiliary qubits; without it, efficient quantum protocols extract negligible expected work.The construction uses reduced states from and a public, key-independent Hamiltonian of single-qubit terms; the reference ensemble has zero ergotropy, while the other has extensive ergotropy on average over the key.Source: §1.2 · p. 13
  • With quantum-secure pseudorandom permutations, the same ensembles at zero Hamiltonian have free-energy excesses of 0 and Θ(n) and remain computationally indistinguishable given polynomially many copies.This gives a counterexample to the conjectured nonexistence of pseudo-nonequilibrium states [WT26].Source: §1.2 · p. 13

2 Technical Overview

The overview develops separations between unrestricted and efficient work extraction, then connects computational ergotropy to catalytic computation. It also shows how catalysts affect computational extraction and pseudoergotropy, while preserving the information-theoretic ergotropy.

2.1 Separating ergotropy from computational ergotropy

  • For H_n = sum_i X_i and a Haar-random pure state, ergotropy is nearly n, while every circuit with at most 2^n/4 gates extracts at most 2^n·2^-n/3 work.The state’s energy concentrates near zero, and a union bound controls all such circuits simultaneously.Source: §2.1 · p. 13
  • The random-oracle construction has expected ergotropy n/2 but negligible efficient extraction, and a quantum-secure PRF extends the separation to the plain model.The random-oracle state is computationally indistinguishable from maximally mixed even to distinguishers querying the oracle.Source: §2.1 · p. 14
  • Exact restoration of a fixed pure catalyst leaves information-theoretic ergotropy unchanged; ε-close restoration changes it by at most roughly a factor ε^2.The approximate-restoration argument bounds additional work by a quadratic error times the spectral width of H.Source: §2.1 · p. 14

2.2 Query separations for catalytic computation

  • Relational and decision problems resist polynomial-query quantum algorithms with ⌊cλ⌋ auxiliary qubits for any fixed c < 1, even without requiring register restoration.The relational and decision lower bounds reduce success or distinguishing advantage to random-function inversion.Source: §2.2 · pp. 14–15

2.3 Catalytic Work Extraction and Catalytic Work Potential

  • With λ catalysts, a three-query circuit clears the second register and restores its workspace, enabling near-maximal extraction; without auxiliaries, efficient extraction is negligible.For public oracle-independent local Hamiltonians, exactly catalytic reachability of a state below the initial expected energy yields catalytic work potential.Source: §2.3 · pp. 15–16

2.4 Pseudoergotropy

  • Haar-random states are low-ergotropy, so pseudorandom states do not suffice; a keyed PRP construction makes ρ and σ indistinguishable without the key, while keyed extraction works on ρ but not σ.The construction uses contracting and expanding functions derived from the PRP.Source: §2.4 · p. 16

2.5 Separating classical and quantum ergotropy

  • A pseudo-deterministic proof of quantumness lets a quantum extractor compute-copy-uncompute its workspace, extracting 1 − negl(λ) work while efficient classical extraction yields no non-negligible work.The construction uses classical states and Hamiltonians; classical work extraction is bounded by the probability of producing a ground state.Source: §2.5 · p. 16

3 Preliminaries and Notation

This section establishes notation and preliminaries for Hamiltonians, ergotropy, Haar sampling, quantum oracles, and cryptographic constructions, including the definition of h(x) as the n-bit prefix of F(k_h, x).

Quantum Notation

  • The notation fixes n as the system’s qubit count and q as a typical query count, alongside conventions for registers, operators, and quantum algorithms.The authors also define trace distance, negligible functions, and canonical circuit descriptions.Source: Quantum Notation · p. 18

Hamiltonians

  • A k-local Hamiltonian is a sum of terms acting nontrivially on at most k qubits; the Hamming-weight Hamiltonian models independent spins in a fixed magnetic field.A family is called local when k does not depend on n.Source: Hamiltonians · p. 19

3.2 Ergotropy

  • Ergotropy is the maximum work extractable under unitary operations, and passive states are precisely the states with zero ergotropy.The section also states a characterization of passive states and a fact about pure-state ergotropy, but the supplied passages omit their full statements.Source: §3.2 · p. 20

3.3 Haar measure

  • Haar-random pure states are defined by applying a Haar-random unitary to |0⟩^⊗n, and the section recalls Levy’s lemma for observable expectation values.The authors use Haar measure to establish an existential separation between ergotropy and computational ergotropy.Source: §3.3 · pp. 20–21

3.4 Oracles

  • The O2H lemma addresses quantum algorithms distinguishing random oracles that agree outside a random subset, including when their input string is correlated with the oracles.The section also defines quantum oracle algorithms by their query count.Source: §3.4 · p. 21

3.5 Cryptography

  • Quantum-secure pseudorandom functions support a plain-model separation, while pseudorandom permutations are used for pseudoergotropy and other plain-model separations.The section also gives a PRP result relating permutations to expansion followed by contraction.Source: §3.5 · pp. 22–23
  • In the cryptography preliminaries, h(x) is the n-bit prefix of F(k_h, x), and its proof is deferred to Section A.The excerpt begins a claim about polynomial-time quantum algorithms with binary output but does not include the claim itself.Source: §3.5 · p. 23

4 Computational work extraction

The section studies computationally bounded work extraction and how computational ergotropy can differ from information-theoretic ergotropy. It establishes a maximal separation in the random oracle model and extends it to the plain model assuming quantum-secure pseudorandom functions.

4.1 Defining computational ergotropy c

  • Computational ergotropy is defined over asymptotic state–Hamiltonian families and algorithm classes; unbounded halting quantum machines recover information-theoretic ergotropy within any positive epsilon.The framework uses a security parameter to index the families and considers how algorithms access them.Source: §4.1 · pp. 24–26

4.2 Unconditional existential separation between erg and c

  • The section establishes that near-maximal separation is possible and notes that its proof techniques generalize to most physically relevant extensive Hamiltonians.Source: §4.2 · p. 26

4.2.1 Unconditional Existential Separation

  • A counting argument with Haar-random states yields states with high unrestricted ergotropy but negligible work extraction by circuits of bounded size.The proof bounds the number of small circuits and uses a union bound to show that bounded-size unitaries fail on typical Haar-random states.Source: §4.2.1 · pp. 26–28

4.3 Defining computational ergotropy for distributions c

  • For distributions over state–Hamiltonian families, computational ergotropy is called negligible when no algorithm extracts a non-negligible amount of work.Requiring one shared negligible upper bound for every algorithm would be too strong in many cases.Source: §4.3 · p. 29

4.4 Constructive separation between ergD from c

  • The section begins a constructive separation by leveraging computational hardness assumptions to specify states and Hamiltonians with near-maximal separation.Source: §4.4 · p. 30

4.4.1 Constructive Separation in the random oracle model

  • In the random oracle model, unbounded ergotropy is at least n/2 asymptotically, while computational ergotropy is negligible.The proof uses O2H-based indistinguishability of the constructed states to bound work extracted by efficient processes.Source: §4.4.1 · pp. 31, 33, 34

4.4.2 Constructive Separation in the plain model

  • Assuming quantum-secure PRFs, the plain model has the same separation: unbounded ergotropy is at least n/2, while computational ergotropy is negligible.An unbounded algorithm can enumerate the PRF outputs using the state-generation oracle; the proof bounds efficient extraction even when algorithms are given PRF access.Source: §4.4.2 · pp. 35–36

5 Catalytic Computation

The section studies catalytic computation, where auxiliary qubits are restored to their initial state, and establishes random-oracle separations based on catalyst count. It considers relational and decision problems, as well as inversion success with fewer catalysts.

5 Catalytic Computation

  • Unconstrained fresh ancillas let a unitary extract n/2 work from a maximally mixed n-qubit state, motivating catalysts that must be restored exactly.The proposed constraint avoids this pathology while retaining auxiliary qubits for computation.Source: §5 · p. 37

5.1 Catalytic Unitaries

  • Exact catalysts do not expand information-theoretic unitary channels, and approximate catalysts yield channels within ε^2 of ordinary unitary channels.The approximate result allows the catalyst to be correlated with the system, subject to the stated approximation condition.Source: §5.1 · pp. 38, 40, 41

5.2 Computational Catalytic setting

  • The computational model uses PPT-generated catalytic unitaries that restore a fixed |0^ℓ⟩ catalyst exactly, while the stated impossibility results allow arbitrary errors.This defines the setting for computationally bounded catalytic computation without permitting unconstrained advice states.Source: §5.2 · pp. 41–42

5.2.1 Computational catalytic computation with oracles

  • In the oracle setting, the section states a relational separation: (2λ, cλ)-Fc cat ⊊ (2λ, λ)-Fc cat for c < 1.The announced construction uses oracles for length-preserving random functions f and g.Source: §5.2.1 · p. 43
  • With λ catalysts the relation is efficiently solvable, but with cλ catalysts for any c < 1 it has negligible success, yielding a strict class separation.The efficient construction uses three oracle gates and O(λ) SWAP gates; the lower bound follows via random-function inversion and remains negligible for polynomially many queries.Source: §5.2.1 · pp. 44, 45, 48, 49
  • Even with 2λ + cλ qubits for c < 1, the relation remains intractable, preserving the separation when arbitrary errors are allowed.The stronger lower bound is stated for the relational problem P and follows from the proof of Lemma 76.Source: §5.2.1 · pp. 45, 49
  • For the decision variant, distinguishing (x, f(g(x))) from (x, r) is negligible with cλ catalysts for c < 1.The decision analogue uses an inversion argument, although the search proof does not transfer directly because the decision acceptance projector need not have rank one.Source: §5.2.1 · p. 50
  • For polynomially bounded q and q_g, inversion is negligible when λ − ℓ(λ) = ω(log λ), including ℓ(λ) = ⌊cλ⌋ for any fixed 0 ≤ c < 1.This bound does not require the catalytic register to be restored.Source: §5.2.1 · p. 53
  • In the random oracle model, for n = 2λ, ℓ′(λ) = λ, and ℓ(λ) = cλ with c < 1, decision problem P is not in (2λ, cλ)-c-cat.The separation follows from indistinguishability of (x, r) and (x, f(g(x))) with fewer than λ catalysts.Source: §5.2.1 · p. 53

6 Catalytic Work Extraction

The section extends work extraction to catalytic processes, then distinguishes information-theoretic invariance from computational gains. It establishes computational separations and catalytic work potential relative to a random oracle.

6 Catalytic Work Extraction

  • Even when catalysts are restored exactly, they do not change information-theoretic ergotropy: cat-erg equals erg for every state, Hamiltonian, and system size.Source: §6 · p. 54

6.1 Computational Catalytic Work Extraction

  • In the random-oracle construction, noncatalytic computational extraction is negligible, whereas an oracle PPT catalytic algorithm extracts Ω(n) work.The construction gives explicit state and Hamiltonian distributions for this separation.Source: §6.1 · pp. 55, 57, 58

6.3 Catalytic work potential

  • For efficient extensive Hamiltonians on 2λ qubits, polynomially many catalysts yield work potential ∆=E−Ē relative to a random oracle; the Hamming-weight Hamiltonian has a near-maximal gap.Source: §6.3 · pp. 58–59

7 Pseudoergotropy

The paper defines catalytic pseudoergotropy as a computational indistinguishability between efficiently generated low- and high-ergotropy state–Hamiltonian families. It gives an explicit construction under a quantum-secure pseudorandom-permutation assumption, with a linear nonequilibrium free-energy gap.

7 Pseudoergotropy

  • Catalytic pseudoergotropy captures when efficiently generated low-ergotropy states are computationally indistinguishable from high-ergotropy states, limiting an adversary’s ability to extract work.The paper compares distributions over state–Hamiltonian pairs and relates the notion to pseudorandomness.Source: §7 · p. 59

7.1 Construction for Catalytic Pseudoergotropy

  • The paper constructs explicit catalytic-pseudoergotropy distributions and states that the construction is a counterexample to Watanabe and Takagi’s conjecture [WT26].The construction uses a padded Hamming-weight Hamiltonian and keyed distributions that differ in their state families.Source: §7 · p. 59, §7.1 · pp. 60–62

7 Pseudoergotropy

  • The section formalizes catalytic pseudoergotropy for keyed distributions and introduces efficiency and indistinguishability conditions.The distributions include states, Hamiltonians, and keys; the construction section specifies the family sizes and key setting.Source: §7 · pp. 59–60

7.1 Construction for Catalytic Pseudoergotropy

  • Assuming quantum-secure pseudorandom permutations and setting m = 2n, the construction gives catalytic pseudoergotropy with a linear free-energy gap.The states have entropies n ln 2 and m ln 2, respectively; the free-energy gap is β^-1(m − n) ln 2, while computational indistinguishability given polynomially many copies is unchanged.Source: §7.1 · pp. 61–62
  • The construction’s two distributions differ only in their state families: one uses maximally mixed states, while catalysts permit converting the less-mixed state to the Hamiltonian’s ground state by inverting a keyed permutation.The maximally mixed family has negligible catalytic ergotropy, and the distribution is efficiently sampleable.Source: §7.1 · pp. 61–62

8 Classical vs Quantum Computational Ergotropy

The section compares classical and quantum computational ergotropy and develops a catalyst-assisted separation using pseudo-deterministic computation and circuit-to-Hamiltonian encoding. Under a proof-of-quantumness setting, classical catalytic ergotropy is negligible while quantum catalytic ergotropy is constant.

8 Classical vs Quantum Computational Ergotropy

  • Classical states and Hamiltonians can yield non-negligible work with efficient catalytic unitaries, even when efficient reversible classical permutations cannot extract non-negligible work.The section assumes BPP ⊊ BQP and allows negligible error when restoring catalysts.Source: §8 · pp. 62–63

8.1 Pseudo-deterministic to catalytic circuits

  • A pseudo-deterministic circuit, which produces a fixed answer with probability 1 − negl, can be transformed into a catalytic circuit with negligible catalyst-restoration error.For a unique-solution relation, the construction uses n + m + s catalyst qubits for input, output, and workspace sizes n, m, and s.Source: §8.1 · p. 64

8.2 Classical circuit to classical Hamiltonian

  • The circuit-to-Hamiltonian construction makes accepting inputs correspond to efficiently constructible classical ground states, and ground states yield accepting inputs.The Hamiltonian penalizes inconsistent computation transcripts and a rejecting decision bit.Source: §8.2 · pp. 64–66

8.3 Putting everything together—the separation

  • For a public-coin proof of quantumness in the common-reference-string model, the section constructs extensive 4-local classical Hamiltonians and corresponding states with negligible classical but constant quantum catalytic ergotropy.The construction encodes the verifier’s reversible computation as a Hamiltonian and uses its transcript as the state.Source: §8.3 · pp. 66–67
  • The constructed state has energy 1 − negl, and a quantum catalytic procedure can reverse the verifier computation and produce an accepting response using pseudo-deterministic computation.The proof-of-quantumness protocol supplies the high-completeness response; the transcript can be reversed because the verifier circuit is reversible.Source: §8.3 · p. 67
  • A classical efficient extractor cannot reach the ground state without producing an accepting response, which proof-of-quantumness soundness rules out with more than negligible probability.The section states the classical catalytic ergotropy is negligible for this family, while the quantum catalytic ergotropy is constant.Source: §8.3 · p. 67
  • For this family, information-theoretic and computational ergotropy are identical across classical and quantum settings, while the catalytic classical and quantum values differ.The stated catalytic values are negligible classically and constant quantumly.Source: §8.3 · p. 67

A Deferred Proofs

The deferred proofs establish indistinguishability claims by replacing keyed pseudorandom permutations with random functions through hybrids. They also compare oracle experiments using a query argument showing that a polynomial-query quantum algorithm is unlikely to find the changed point.

Deferred proofs

  • The proof replaces keyed functions with random permutations and then random functions through successive hybrids, bounding each change using pseudorandomness and query lower bounds.It later replaces a random function with a random permutation and returns to the keyed permutation using the corresponding indistinguishability arguments.Source: A Deferred Proofs · p. 68
  • The proof also simulates random-oracle queries by routing queries on the specified input domain to the function oracle and answering other queries independently.This gives identical output distributions for inputs depending only on the restricted oracle.Source: A Deferred Proofs · pp. 68–69
  • The oracle-query proof changes one oracle point between experiments; an algorithm’s outputs can differ only if it queries that point, which a polynomial-query quantum algorithm does with negligible probability.The proof measures a query register to bound the chance of guessing the uniformly random point, then applies a union bound over polynomially many queries.Source: A Deferred Proofs · p. 69
Loading 2609.40323v1…