Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2609.40323

Computational Work Extraction: The Complexity of Catalysts

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

quant-phcs.CCSubmitted Sep 30, 2026• Announced Oct 1, 2026• 0 citations
arXivHTMLPDF

Abstract

We prove maximal separations: $n$-qubit systems can have $Θ(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 $λ$ catalysts; but (ii) cannot be solved by any algorithm with $cλ$ 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 $Θ(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.

Comments
70 pages, 3 Figures; See https://atulsingharora.github.io/cat for updates

Related papers

Quantum Catalytic Space

Harry Buhrman, Folkertsma, Marten, Ian Mertz +4 more

Space complexity is a key field of study in theoretical computer science. In the quantum setting there are clear motivations to understand the power of space-restricted computation, as qubits are an especially precious and limited resource. Recently, a new branch of space-bounded complexity called catalytic computing has shown that reusing space is a very powerful computational resource, especially for subroutines that incur little to no space overhead. While quantum catalysis in an information theoretic context, and the power of "dirty" qubits for quantum computation, has been studied over the years, these models are generally not suitable for use in quantum space-bounded algorithms, as they either rely on specific catalytic states or destroy the memory being borrowed. We define the notion of catalytic computing in the quantum setting and show a number of initial results about the model. First, we show that quantum catalytic logspace can always be computed quantumly in polynomial time; the classical analogue of this is the largest open question in catalytic computing. This also allows quantum catalytic space to be defined in an equivalent way with respect to circuits instead of Turing machines. We also prove that quantum catalytic logspace can simulate log-depth threshold circuits, a class which is known to contain (and believed to strictly contain) quantum logspace, thus showcasing the power of quantum catalytic space. Finally we show that both unitary quantum catalytic logspace and classical catalytic logspace can be simulated in the one-clean qubit model.

arXiv:2506.16324•Leibniz international proceedings in informatics•Jan 1, 2025•0 citations

Explicit Separations for One-Query Unitary Synthesis

Fangqi Dong, Alex Lombardi, Fermi Ma

The unitary synthesis problem (Aaronson-Kuperberg, CCC 2007) asks whether every $n$-qubit unitary $U$ is computable by efficient quantum circuits relative to some classical oracle $f = f_U$ depending on $U$. Recently, Lombardi-Ma-Wright (STOC 2024) proved that Haar-random unitaries cannot be efficiently synthesized by algorithms that make 1 query (or poly$(n)$ parallel queries) to an arbitrary classical oracle. In this work, we prove several results about the hardness (and easiness!) of variants of unitary synthesis. Our results include: (1) 1-query vs. 2-query unitary synthesis: we prove 1-query lower bounds for synthesizing random permutation unitaries $P\lvert x\rangle = \lvert π(x)\rangle$, as well as random alternating-basis phase unitaries $F_2 \cdot H^{\otimes n} \cdot F_1$. This gives 1-query lower bounds for "explicit" families of unitaries that have efficient (even 2-query) synthesis algorithms. (2) Upper bound for complex phase unitaries: we also consider complex phase unitaries $\lvert x\rangle\mapsto α_x \lvert x\rangle$, which have a clean 2-query synthesis algorithm with no obvious 1-query algorithm. In this case, we prove an upper bound: there are 1-query algorithms (relative to binary phase oracles) that constant-approximate these unitaries in diamond distance. In order to prove our lower bounds, we introduce and analyze two new cryptographic games: the oracle state search game and the oracle Choi state game. Compared to prior work, our framework is mathematically simple, more flexible in what it can prove, and more accurately captures the hardness of synthesizing unitaries that are not "fully random". Finally, we also use the search game to prove a new hardness-of-approximation result for quantum programs (synthesizing unitaries relative to quantum advice) for phase unitaries, giving a sharper separation between 1-query unitary synthesis and quantum programs.

quant-pharXiv:2607.26478•Jul 30, 2026•0 citations

Oracle separations of hybrid quantum-classical circuits

Atul Singh Arora, Alexandru Gheorghiu, Singh, Uttam

An important theoretical problem in the study of quantum computation, that is also practically relevant in the context of near-term quantum devices, is to understand the computational power of hybrid models, that combine poly-time classical computation with short-depth quantum computation. Here, we consider two such models: CQ_d which captures the scenario of a polynomial-time classical algorithm that queries a d-depth quantum computer many times; and QC_d which is more analogous to measurement-based quantum computation and captures the scenario of a d-depth quantum computer with the ability to change the sequence of gates being applied depending on measurement outcomes processed by a classical computation. Chia, Chung & Lai (STOC 2020) and Coudron & Menda (STOC 2020) showed that these models (with d=log^O(1) (n)) are strictly weaker than BQP (the class of problems solvable by poly-time quantum computation), relative to an oracle, disproving a conjecture of Jozsa in the relativised world. We show that, despite the similarities between CQ_d and QC_d, the two models are incomparable, i.e. CQ_d $\nsubseteq$ QC_d and QC_d $\nsubseteq$ CQ_d relative to an oracle. In other words, there exist problems that one model can solve but not the other and vice versa. We do this by considering new oracle problems that capture the distinctions between the two models and by introducing the notion of an intrinsically stochastic oracle, an oracle whose responses are inherently randomised, which is used for our second result. While we leave showing the second separation relative to a standard oracle as an open problem, we believe the notion of stochastic oracles could be of independent interest for studying complexity classes which have resisted separation in the standard oracle model. Our constructions also yield simpler oracle separations between the hybrid models and BQP, compared to earlier works.

arXiv:2201.01904•Jan 6, 2022•3 citations

Only uniform randomness can yield quantum advantages

Seok Hyung Lie, Hyunseok Jeong

Randomness can help one to implement quantum maps that cannot be realized in a deterministic fashion. Recently, it was discovered that explicitly treating a randomness source as a quantum system could double the efficiency as a catalyst for some tasks. In this work, we generalize this result to general randomness-utilizing processes and show that the gap between the efficiencies of classical and quantum catalytic randomness is generic. To explore the achievability of catalysis of quantum randomness, we first show that the second law of thermodynamics holds for general randomness-utilizing processes: the amount of randomness never decreases. Especially, for two important randomization processes, dephasing and erasure maps, randomness sources are forced to be used catalytically, i.e., in such a way that the randomness is preserved exactly. Second, we show that non-degenerate catalysts should be used classically, which leads to the fact that the quantum advantage of a catalytic process strictly comes from the uniformness of the randomness source. Finally, we discuss a method to circumvent the previous result that achieves quantum advantage with non-degenerate catalyst uniformized by employing extra work space.

•Oct 28, 2020•3 citations

Correlational Resource Theory of Catalytic Quantum Randomness under Conservation Law

Seok Hyung Lie, Hyunsek Jeong

Catalysts are substances that assist transformation of other resourceful objects without being consumed in the process. However, the fact that their `catalytic power' is limited and can be depleted is often overlooked, especially in the recently developing theories on catalysis of quantum randomness utilizing building correlation with catalyst. In this work, we establish a resource theory of one-shot catalytic randomness in which uncorrelatedness is consumed in catalysis of randomness. We do so by completely characterizing bipartite unitary operators that can be used to implement catalysis of randomness using partial transpose. By doing so, we find that every catalytic channel is factorizable, and therefore there exists a unital channel that is not catalytic. We define a family of catalytic entropies that quantifies catalytically extractable entropy within a quantum state and show how much degeneracy of quantum state can boost the catalytic entropy beyond its ordinary entropy. Based on this, we demonstrate that a randomness source can be actually exhausted after a certain amount of randomness is extracted. We apply this theory to systems under conservation law that forbids superposition of certain quantum states and find that non-maximally mixed states can yield the maximal catalytic entropy. We discuss implications of this theory to various topics including catalytic randomness absorption, the no-secret theorem and the possibility of multi-party infinite catalysis.

arXiv:2104.00300•Apr 1, 2021•1 citation

Empowering quantum computation with: measurements, catalysts, and guiding states

Marten Folkertsma

Despite rapid advances in quantum hardware and the appearance of the first devices with active error correction by 2025, fully fault-tolerant quantum computation remains a distant milestone. This thesis investigates how additional resources can enhance computational power across various stages of quantum device development. Part I examines computation before error correction, where only constant-depth circuits are feasible. We introduce LAQCC, which augments such circuits with intermediate measurement and classical computation, and show that this model enables far more powerful computations. In Part II, we study the early fault-tolerance regime, where the main limitation is the number of logical qubits. Inspired by the classical catalytic space model, we introduce a quantum analogue in which a space-bounded quantum machine has access to an auxiliary catalytic register that may be modified during the computation but must be restored at the end. We show that this catalytic resource increases the power of quantum space-bounded machines. In Part III, we study the full fault-tolerant regime and look at the problem of estimating the ground-state energy of a Local Hamiltonian which is central to quantum chemistry. Here, we study the BQP-hard Guided Local Hamiltonian problem (estimating ground-state energy given a guiding state), showing its hardness persists over a broader parameter range. Furthermore, by introducing the Guidable Local Hamiltonian problem, we provide complexity-theoretic evidence that classical guiding-state heuristics are as powerful as quantum ones, in this setting. Finally, this problem also provides restrictions on possible gap-amplification procedures, relevant for the quantum PCP conjecture.

•Jan 1, 2026•0 citations
We prove maximal separations: nnn-qubit systems can have Θ(n)Θ(n)Θ(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 λλλ catalysts; but (ii) cannot be solved by any algorithm with cλcλcλ catalysts, for any c<1c<1c<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 Θ(n)Θ(n)Θ(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.
Space complexity is a key field of study in theoretical computer science. In the quantum setting there are clear motivations to understand the power of space-restricted computation, as qubits are an especially precious and limited resource. Recently, a new branch of space-bounded complexity called catalytic computing has shown that reusing space is a very powerful computational resource, especially for subroutines that incur little to no space overhead. While quantum catalysis in an information theoretic context, and the power of "dirty" qubits for quantum computation, has been studied over the years, these models are generally not suitable for use in quantum space-bounded algorithms, as they either rely on specific catalytic states or destroy the memory being borrowed. We define the notion of catalytic computing in the quantum setting and show a number of initial results about the model. First, we show that quantum catalytic logspace can always be computed quantumly in polynomial time; the classical analogue of this is the largest open question in catalytic computing. This also allows quantum catalytic space to be defined in an equivalent way with respect to circuits instead of Turing machines. We also prove that quantum catalytic logspace can simulate log-depth threshold circuits, a class which is known to contain (and believed to strictly contain) quantum logspace, thus showcasing the power of quantum catalytic space. Finally we show that both unitary quantum catalytic logspace and classical catalytic logspace can be simulated in the one-clean qubit model.
The unitary synthesis problem (Aaronson-Kuperberg, CCC 2007) asks whether every nnn-qubit unitary UUU is computable by efficient quantum circuits relative to some classical oracle f=fUf = f_Uf=fU​ depending on UUU. Recently, Lombardi-Ma-Wright (STOC 2024) proved that Haar-random unitaries cannot be efficiently synthesized by algorithms that make 1 query (or poly(n)(n)(n) parallel queries) to an arbitrary classical oracle. In this work, we prove several results about the hardness (and easiness!) of variants of unitary synthesis. Our results include: (1) 1-query vs. 2-query unitary synthesis: we prove 1-query lower bounds for synthesizing random permutation unitaries P∣x⟩=∣π(x)⟩P\lvert x\rangle = \lvert π(x)\rangleP∣x⟩=∣π(x)⟩, as well as random alternating-basis phase unitaries F2⋅H⊗n⋅F1F_2 \cdot H^{\otimes n} \cdot F_1F2​⋅H⊗n⋅F1​. This gives 1-query lower bounds for "explicit" families of unitaries that have efficient (even 2-query) synthesis algorithms. (2) Upper bound for complex phase unitaries: we also consider complex phase unitaries ∣x⟩↦αx∣x⟩\lvert x\rangle\mapsto α_x \lvert x\rangle∣x⟩↦αx​∣x⟩, which have a clean 2-query synthesis algorithm with no obvious 1-query algorithm. In this case, we prove an upper bound: there are 1-query algorithms (relative to binary phase oracles) that constant-approximate these unitaries in diamond distance. In order to prove our lower bounds, we introduce and analyze two new cryptographic games: the oracle state search game and the oracle Choi state game. Compared to prior work, our framework is mathematically simple, more flexible in what it can prove, and more accurately captures the hardness of synthesizing unitaries that are not "fully random". Finally, we also use the search game to prove a new hardness-of-approximation result for quantum programs (synthesizing unitaries relative to quantum advice) for phase unitaries, giving a sharper separation between 1-query unitary synthesis and quantum programs.
An important theoretical problem in the study of quantum computation, that is also practically relevant in the context of near-term quantum devices, is to understand the computational power of hybrid models, that combine poly-time classical computation with short-depth quantum computation. Here, we consider two such models: CQ_d which captures the scenario of a polynomial-time classical algorithm that queries a d-depth quantum computer many times; and QC_d which is more analogous to measurement-based quantum computation and captures the scenario of a d-depth quantum computer with the ability to change the sequence of gates being applied depending on measurement outcomes processed by a classical computation. Chia, Chung & Lai (STOC 2020) and Coudron & Menda (STOC 2020) showed that these models (with d=log^O(1) (n)) are strictly weaker than BQP (the class of problems solvable by poly-time quantum computation), relative to an oracle, disproving a conjecture of Jozsa in the relativised world. We show that, despite the similarities between CQ_d and QC_d, the two models are incomparable, i.e. CQ_d ⊈\nsubseteq⊈ QC_d and QC_d ⊈\nsubseteq⊈ CQ_d relative to an oracle. In other words, there exist problems that one model can solve but not the other and vice versa. We do this by considering new oracle problems that capture the distinctions between the two models and by introducing the notion of an intrinsically stochastic oracle, an oracle whose responses are inherently randomised, which is used for our second result. While we leave showing the second separation relative to a standard oracle as an open problem, we believe the notion of stochastic oracles could be of independent interest for studying complexity classes which have resisted separation in the standard oracle model. Our constructions also yield simpler oracle separations between the hybrid models and BQP, compared to earlier works.
Randomness can help one to implement quantum maps that cannot be realized in a deterministic fashion. Recently, it was discovered that explicitly treating a randomness source as a quantum system could double the efficiency as a catalyst for some tasks. In this work, we generalize this result to general randomness-utilizing processes and show that the gap between the efficiencies of classical and quantum catalytic randomness is generic. To explore the achievability of catalysis of quantum randomness, we first show that the second law of thermodynamics holds for general randomness-utilizing processes: the amount of randomness never decreases. Especially, for two important randomization processes, dephasing and erasure maps, randomness sources are forced to be used catalytically, i.e., in such a way that the randomness is preserved exactly. Second, we show that non-degenerate catalysts should be used classically, which leads to the fact that the quantum advantage of a catalytic process strictly comes from the uniformness of the randomness source. Finally, we discuss a method to circumvent the previous result that achieves quantum advantage with non-degenerate catalyst uniformized by employing extra work space.
Catalysts are substances that assist transformation of other resourceful objects without being consumed in the process. However, the fact that their `catalytic power' is limited and can be depleted is often overlooked, especially in the recently developing theories on catalysis of quantum randomness utilizing building correlation with catalyst. In this work, we establish a resource theory of one-shot catalytic randomness in which uncorrelatedness is consumed in catalysis of randomness. We do so by completely characterizing bipartite unitary operators that can be used to implement catalysis of randomness using partial transpose. By doing so, we find that every catalytic channel is factorizable, and therefore there exists a unital channel that is not catalytic. We define a family of catalytic entropies that quantifies catalytically extractable entropy within a quantum state and show how much degeneracy of quantum state can boost the catalytic entropy beyond its ordinary entropy. Based on this, we demonstrate that a randomness source can be actually exhausted after a certain amount of randomness is extracted. We apply this theory to systems under conservation law that forbids superposition of certain quantum states and find that non-maximally mixed states can yield the maximal catalytic entropy. We discuss implications of this theory to various topics including catalytic randomness absorption, the no-secret theorem and the possibility of multi-party infinite catalysis.
Despite rapid advances in quantum hardware and the appearance of the first devices with active error correction by 2025, fully fault-tolerant quantum computation remains a distant milestone. This thesis investigates how additional resources can enhance computational power across various stages of quantum device development. Part I examines computation before error correction, where only constant-depth circuits are feasible. We introduce LAQCC, which augments such circuits with intermediate measurement and classical computation, and show that this model enables far more powerful computations. In Part II, we study the early fault-tolerance regime, where the main limitation is the number of logical qubits. Inspired by the classical catalytic space model, we introduce a quantum analogue in which a space-bounded quantum machine has access to an auxiliary catalytic register that may be modified during the computation but must be restored at the end. We show that this catalytic resource increases the power of quantum space-bounded machines. In Part III, we study the full fault-tolerant regime and look at the problem of estimating the ground-state energy of a Local Hamiltonian which is central to quantum chemistry. Here, we study the BQP-hard Guided Local Hamiltonian problem (estimating ground-state energy given a guiding state), showing its hardness persists over a broader parameter range. Furthermore, by introducing the Guidable Local Hamiltonian problem, we provide complexity-theoretic evidence that classical guiding-state heuristics are as powerful as quantum ones, in this setting. Finally, this problem also provides restrictions on possible gap-amplification procedures, relevant for the quantum PCP conjecture.