[initials=PhF,color=phfcc5]phf[initials=NT]nt[initials=AM,color=cyan]am[initials=AM,color=blue]amtwo
<EMAIL_ADDRESS>
# Complexity-constrained quantum thermodynamics

Anthony Munson  Joint Center for Quantum Information and Computer Science,
NIST and University of Maryland, College Park, MD 20742, USA  Department of
Physics, University of Maryland, College Park, MD 20742, USA  Naga Bhavya Teja
Kothakonda  Physics Department, Universitat Autònoma de Barcelona,08193
Bellaterra (Barcelona), Spain  Dahlem Center for Complex Quantum Systems,
Freie Universität Berlin, 14195 Berlin, Germany  Jonas Haferkamp  School of
Engineering and Applied Sciences, Harvard University, MA 02134, USA  Nicole
Yunger Halpern  Joint Center for Quantum Information and Computer Science,
NIST and University of Maryland, College Park, MD 20742, USA  Department of
Physics, University of Maryland, College Park, MD 20742, USA  Institute for
Physical Science and Technology, University of Maryland, College Park, MD
20742, USA  Jens Eisert  Dahlem Center for Complex Quantum Systems, Freie
Universität Berlin, 14195 Berlin, Germany  Philippe Faist  Dahlem Center for
Complex Quantum Systems, Freie Universität Berlin, 14195 Berlin, Germany

###### Abstract

Quantum complexity measures the difficulty of realizing a quantum process,
such as preparing a state or implementing a unitary.We present an approach to
quantifying the thermodynamic resources required to implement a process if the
process’s complexity is restricted.We focus on the prototypical task of
information erasure, or Landauer erasure, wherein an $n$-qubit memory is reset
to the all-zero state.We show that the minimum thermodynamic work required to
reset an arbitrary state, via a complexity-constrained process, is quantified
by the state’s _complexity entropy_.The complexity entropy therefore
quantifies a trade-off between the work cost and complexity cost of resetting
a state.If the qubits have a nontrivial (but product) Hamiltonian, the optimal
work cost is determined by the _complexity relative entropy_.The complexity
entropy quantifies the amount of randomness a system appears to have to a
computationally limited observer.Similarly, the complexity relative entropy
quantifies such an observer’s ability to distinguish two states.We prove
elementary properties of the complexity (relative) entropy and determine the
complexity entropy’s behavior under random circuits.Also, we identify
information-theoretic applications of the complexity entropy.The complexity
entropy quantifies the resources required for data compression if the
compression algorithm must use a restricted number of gates.We further
introduce a _complexity conditional entropy_ , which arises naturally in a
complexity-constrained variant of information-theoretic decoupling.Assuming
that this entropy obeys a conjectured chain rule, we show that the entropy
bounds the number of qubits that one can decouple from a reference system, as
judged by a computationally bounded referee.Overall, our framework extends the
resource-theoretic approach to thermodynamics to integrate a notion of _time_
, as quantified by _complexity_.

##  I Introduction

Quantum complexity is drawing increasing interest across physics, from many-
body physics to quantum gravity [1,
Caputa_22_QuantumComplexityAndTopologicalPhases, Brown_18_Second,
Susskind_18_Three].For the purposes of our work, the quantum complexity of a
unitary operation (respectively, a quantum state) is the minimum number of
operations required to implement the unitary (respectively, to prepare the
state).Each operation is chosen from a given set of elementary operations
(e.g., a universal set of two-qubit gates).In condensed-matter physics,
preparing a topologically ordered state requires a circuit of sufficient
complexity to spread information throughout a system [Chen_11_Classification,
1, 6, 7, 8, 9, 10, 11, Caputa_22_QuantumComplexityAndTopologicalPhases].Near-
term quantum devices aim to prepare states of sufficient complexities to offer
quantum advantages attributable, for example, to the hardness of sampling
classically from such states [Boixo, 13, 14, 15].Quantum complexity recently
gained significance in the context of the _anti–de Sitter–space/conformal-
field-theory_ (AdS/CFT) correspondence in high-energy physics: In a prominent
conjecture, the complexity of the field-theoretic state dual to a wormhole
connecting two black holes is proportional to the wormhole’s length [16,
Brandao_21_Models, Haferkamp_21_Linear, Li_22_ShortProofsOfLinearGrowth, 20,
Susskind_16_Computational, Stanford_14_Complexity, Brown_16_Complexity,
Brown_18_Second, Susskind_18_Three, Bouland_19_ComputationalPseudorandomness,
Brown_16_Holographic, 26, PhysRevLett.127.020501, PhysRevLett.128.081602, 29,
YungerHalpern_2022_Uncomplexity, 28].The relevance of quantum complexity to
AdS/CFT motivates connections to thermodynamics.Brown and Susskind posited
that the CFT state’s complexity should tend to increase, formulating a “second
law of complexity” [Brown_18_Second].Bai _et al._ extended the second law of
complexity by proving fluctuation relations mirroring Jarzynski’s equality in
statistical mechanics [Bai_22_Towards].A resource theory of _uncomplexity_ —a
state’s closeness to a simple tensor product—was furthermore established in
Ref. [YungerHalpern_2022_Uncomplexity].Quantum complexity also appears
connected to ergodicity and quantum chaos: complexity is believed to grow
linearly for long times under typical quantum chaotic dynamics;complexity
would thereby provide a universal measure for how long a chaotic system has
evolved [Susskind_18_Three, Brandao_21_Models, Haferkamp_21_Linear,
Li_22_ShortProofsOfLinearGrowth, 20].In contrast, standard correlation
functions and entanglement entropies typically reach their equilibrium values
after short times [Susskind_18_Three].Our main goal is to identify which state
transformations in quantum thermodynamics can be effected by processes, and
probed with measurement effects, utilizing limited computational resources,
hence of limited complexity.In particular, we seek to connect quantum
complexity and entropy as follows.In conventional thermodynamics, the minimum
amount of work needed to transform one equilibrium state into another, via
exchanges of heat at a fixed temperature, is determined by the energy and
entropy differences between the initial and final states.The complexity of a
many-body system’s evolution is upper-bounded by the evolution’s duration.An
observer with little computational power typically cannot distinguish a highly
complex pure state from a highly entropic mixed state.A phenomenological
description of possible state transformations under short-time evolutions,
from the viewpoint of such an observer, should not distinguish highly entropic
initial states from highly complex pure states.The states become
distinguishable if observed over sufficiently long timescales or through
sufficiently complex observables.This fact invites us to define thermodynamic
potentials for determining which state transformations can be effected under
complexity limitations.The roles of these potentials mirror the role of
entropy in standard thermodynamics.Using the potentials, we address our
general question: _how does one formulate thermodynamics at a given complexity
scale—for complexity-constrained processes and observers?_ Our analysis relies
on recent information-theoretic frameworks for quantum thermodynamics.The
relevance of an observer’s information, or knowledge, in thermodynamics was
significantly clarified by the pioneering works of Szilárd [32], Landauer
[33], and Bennett [34].Landauer argued that erasing a bit of information
dissipates an amount of heat $\geqslant k_{\mathrm{B}}T\log(2)$, where
$k_{\mathrm{B}}$ denotes Boltzmann’s constant and $T$ denotes an environment’s
temperature [33].This observation led to Bennett’s resolution of Maxwell’s
demon paradox [34, 35] and helped extend quantum thermodynamics to far-from-
equilibrium systems [36, 37, 38, 39].A common model for quantum thermodynamics
is the resource theory of thermal operations [40, 41, 42, 43, 36, 37]:one
assumes that energy-conserving interactions with a fixed-temperature heat bath
are the only operations performable without external resources, such as
thermodynamic work.Using this model, one can determine whether a state $\rho$
can transform into a state $\sigma$, for large classes of states.The answer
can be cast in terms of a family of entropy measures termed the Rényi-$\alpha$
relative entropies [43].A closely related model captures how many natural, or
spontaneous, dynamics have a particular fixed point.Using this model, one can
quantify, e.g., the thermodynamic work required to implement a general quantum
process [44, 45, 39].A key observation is that a process’s work cost is tied
fundamentally to its logical irreversibility: information erasure is costly,
but energy-conserving unitary operations can, in principle, be implemented at
zero work cost [33, 34, 35].We introduce a simple model that captures the main
features of the above models and that forms the basis for our analysis.Our
model centers on an $n$-qubit memory register governed by a completely
degenerate Hamiltonian.The following primitive operations are performable
(Fig. 1): (i) the reset of one qubit from any state to a standard state $\ket
0$, costing one unit of work; (ii) the preparation of one qubit in the
maximally mixed state from $\ket 0$, extracting one unit of work; and (iii)
the implementation of one two-qubit unitary gate, costing one unit of
complexity.(In our model, we neglect any complexity cost of single-qubit
erasure [Taranto2021arXiv_cooling].This choice enables us to attribute all
complexity costs to the unitary gates.)

Fig. 1: A simple model combining quantum-information thermodynamics and
complexity:An $n$-qubit memory register is governed by a completely degenerate
Hamiltonian.Processes consist of the primitive operations (i), (ii) and
(iii).Work and complexity costs are defined as the sums of the corresponding
costs over the operations.(a) A qubit can be reset from any state $\rho$ to a
standard state $\ket 0$.The resetting costs one unit of work ($W$), by
Landauer’s principle [33].This primitive has no complexity cost ($C$).(b) One
unit of work can be extracted from a qubit in the state $\ket 0$.The
extraction leaves the qubit maximally mixed [32].(c) Operations $\mathcal{E}$
are chosen from a set $\mathcal{T}$ of elementary computations.Each
$\mathcal{E}$ costs one unit of complexity but no work.A natural choice for
$\mathcal{T}$ is the set of two-qubit unitary operations, potentially subject
connectivity constraints.Choices of $\mathcal{T}$ natural to thermodynamic
applications preserve thermal states.

We first revisit the standard setting of _information erasure_ , or _Landauer
erasure_.Erasure has clarified information’s role in thermodynamics; we now
use erasure to clarify complexity’s role in quantum thermodynamics.We consider
an $n$-qubit system with a product Hamiltonian $H$ and a zero-energy ground
state.We prove that the minimum work required to reset an arbitrary state
$\rho$ to the ground state, using at most a fixed number of thermodynamic
processes in our model, is given by the _complexity relative entropy_ of
$\rho$ relative to a thermal state [YungerHalpern_2022_Uncomplexity].The
complexity relative entropy quantifies two states’ distinguishability, as
judged by an observer with limited computational power.If $H=0$, this quantity
reduces to the _complexity entropy_ [YungerHalpern_2022_Uncomplexity] and
quantifies how random a state appears to such an observer.A variant of the
complexity (relative) entropy appeared in our Ref.
[YungerHalpern_2022_Uncomplexity] to quantify the number of pure qubits
extractable from a state, in the resource theory of uncomplexity.The present
work further applies the complexity relative entropy to thermodynamics: we
extend the pure-qubit extraction protocol of Ref.
[YungerHalpern_2022_Uncomplexity] to general protocols for thermodynamic
information erasure under complexity limitations.Our result quantifies a
trade-off between the work and complexity costs of erasing an $n$-qubit state
$\rho$ (Fig. 2).

Fig. 2: An example trade-off between the work cost and complexity cost of
resetting an $n$-qubit memory register initiated to a highly complex pure
state $\ket\psi$.(a) A unitary operation resets the memory to the all-zero
state.In principle, the unitary costs no thermodynamic work.Many gates are
necessary to implement the unitary, incurring a high complexity cost.(b) To
reset the memory without gates, one can erase every qubit [via primitive (i)
in Fig. 1].This operation costs $n$ units of work total.The _complexity
entropy_ quantifies the work–complexity trade-off of erasing an arbitrary
state $\rho$.The complexity entropy was introduced in Ref.
[YungerHalpern_2022_Uncomplexity]; this work elucidates its properties and
applications.

Suppose that $H=0$, and consider a highly complex pure state $\ket\psi$.In
standard models for information thermodynamics, one can implement unitary
operations on an energy-degenerate memory register at zero work cost, since
such operations are logically reversible [47, 48, 42].Therefore, $\ket\psi$
can, in principle, be transformed into the all-zero state $\ket{0^{n}}$ at no
work cost.Yet, this transformation requires many gates, incurring a high
_complexity cost_.An alternative procedure would reset each memory qubit with
a thermodynamic reset operation.This procedure costs
$n\,k_{\mathrm{B}}T\log(2)$ units of work but no complexity.The complexity
entropy quantifies the trade-off between the work and complexity costs of
erasing $\ket\psi$.Bennett _et al._ analyzed a trade-off between complexity
and work in the context of classical bit erasure [49].Kolmogorov complexity,
rather than quantum complexity, is relevant to their problem.The connection
between Kolmogorov complexity and thermodynamics was further cemented in
Zurek’s work [50] and in Refs. [51, 52, 53].Kolmogorov complexity and quantum
complexity quantify the size of a state’s “smallest description” in different
ways.Kolmogorov complexity quantifies the size of the smallest program that
generates the state (regardless of the program’s runtime).In contrast, quantum
complexity measures the shortest runtime of a program that generates the state
(regardless of whether the program has a compact representation).The remainder
of this work is dedicated to the analysis of more-general thermodynamic
processes, including erasure in systems with nontrivial Hamiltonians, and to a
deeper study of the complexity entropy’s properties, uses, and extensions.We
study the work costs of general state transformations in quantum
thermodynamics where complexity limitations restrict which processes and
measurements one can implement.Furthermore, we evidence the complexity
entropy’s broad relevance to quantum information theory.First, we present
properties of the complexity entropy and bound it using well-known complexity
measures and an entanglement measure.Then, we characterize the complexity
entropy’s evolution under random circuits.Last, we apply our complexity-
entropy measures to information-theoretic tasks with complexity
constraints.What is the work cost of a general state transformation
$\rho\to\rho^{\prime}$, as in the model of Fig. 1?We consider the minimum work
cost of any process, of complexity at most $r\geqslant 0$, that maps $\rho$ to
a state indistinguishable from $\rho^{\prime}$.Here, distinguishability is
judged by an observer who possesses some bounded computational power
$R\geqslant 0$.This work cost extends the complexity relative entropy’s use to
general state transformations.Quantifying the work cost addresses our main
goal of establishing which state transformations are possible in quantum
thermodynamics for complexity-constrained agents.Considering regimes in which
$R$ is either extremely high or extremely low, we identify cases in which
bounding the work cost is sometimes possible.Our complexity-entropy measures
obey certain properties expected of entropies.For instance, the complexity
entropy achieves its maximum value on a maximally mixed state. Also, the
complexity relative entropy decreases monotonically under partial traces.Our
measures lack other common properties, such as invariance under unitaries and
monotonicity under completely positive, trace-preserving maps (a data-
processing inequality): by construction, the complexity (relative) entropy is
sensitive to a state’s complexity, which can change under arbitrary quantum
operations.Moreover, the complexity entropy obeys bounds involving known
complexity measures: one bound involves the _strong complexity_ of Ref. [17];
and the other, the _approximate circuit complexity_ (the minimum complexity of
any unitary that approximately prepares a target state).For a one-dimensional
(1D) chain of qubits, the complexity entropy obeys also a bound involving an
entanglement measure defined in terms of the quantum mutual information.We
argue that the complexity entropy can quantify chaotic behavior in a quantum
many-body system.Consider a suitably chaotic many-body system initialized in a
pure product state.The state’s complexity entropy should remain low until the
timescale matching an observer’s computational power.Beyond this timescale,
the complexity entropy should be close to maximal.We employ and extend the
results of Refs. [54, 17] to prove a corresponding statement about the output
of a random quantum circuit applied to $\ket{0^{n}}$, an $n$-qubit system’s
all-zero state.Suppose that an observer can measure only observables of
complexities $\leqslant r$.The complexity entropy, we show, transitions from
zero to $n-O(1)$ when the number of gates reaches $\approx r$ (Fig. 3).

Fig. 3: The complexity entropy of a state outputted by a random circuit,
relative to an observer who can implement only measurement effects of
complexities $\leqslant r$.We determine the complexity entropy’s evolution
using techniques from Refs. [54, 17, haferkamp2022random].After a time
$t\lesssim O(r)$, the state has a low enough complexity that the observer can
verify the state’s purity via measurement.After
$t\gtrsim\Omega\bm{(}\poly(r)\bm{)}$, the state is complex enough to be nearly
indistinguishable from a highly entropic state, according to any measurement
whose complexity is $\leqslant r$.We believe the $\poly(r)$ term to be an
artifact of our proof technique.We expect the transition from $0$ to $\approx
n$ to happen at the timescale $\sim r$.

For a random circuit of $\lesssim r$ gates, the observer can apply the inverse
circuit to recover the all-zero state and so to ascertain that the random
circuit’s output has a low entropy.For a random circuit of $\gtrsim
r^{5+o(1)}$ gates, Ref. [17] proves that the observer cannot distinguish the
circuit’s output from a maximally mixed state, using observables of
complexities $\leqslant r$.Accordingly, the output has a complexity entropy of
at least $n-O(1)$.Reference [17] quantifies a random circuit’s complexity by
applying a powerful tool in random-circuit analysis: a _unitary $k$-design_
[54, 56].The exponent in $r^{5+o(1)}$ comes from recently improved bounds for
the design order achieved by random circuits [haferkamp2022random].One might
expect that the exponent can be further improved from ${\sim}r^{5+o(1)}$ to
${\sim}r$, although a proof of this behavior is currently lacking.The term can
be brought to ${\sim}r$ for a system of qudits with a large local dimension
[17, 57].Very recent constructions of probability distributions over quantum
circuits improve the factor ${\sim}r^{5+o(1)}$ to ${\sim}r^{2}$ [58, 59].We
use our complexity-entropy measures to bound the optimal efficiencies of
information-theoretic tasks performed under complexity
limitations.Thermodynamic erasure is related to data compression, the storage
of information in the smallest possible register [60, 61, 62]:to erase a
memory register, one can first perform data compression to reduce the number
of qubits that need resetting.The complexity entropy quantifies the resources
required to compress a quantum state into the fewest qubits possible, via any
limited-complexity procedure.After addressing data compression, we study
_decoupling_ , or ensuring that an agent’s multiqubit system becomes maximally
mixed and uncorrelated with a referee’s system, $R$ [63, 64, 65, 66].Assuming
a conjecture about a chain rule for the complexity entropy, we lower-bound the
number of qubits that an agent must discard to obtain a state
indistinguishable, by a complexity-restricted referee, from a maximally mixed
state uncorrelated with $R$.The lower bound is given by a conditional variant
of the complexity entropy.One can interpret the variant as a _complexity-aware
conditional min-entropy_.Our paper is organized as follows.In II, we introduce
our framework, background information, and the complexity entropy.In III, we
bound the work cost of information erasure subject to complexity
restrictions.In IV, we generalize our analysis to arbitrary state
transformations.In V, we present the complexity entropy’s information-
theoretic properties and applications.We conclude in VI.

##  II Setting

In II.1, we introduce our setup and allowed operations.In II.2, we review
_one-shot information theory_ , which quantifies the efficiencies of
thermodynamic tasks performed on finite-size systems, with arbitrary success
probabilities.In II.3, we introduce the complexity entropy and complexity
relative entropy.

###  II.1 Thermodynamic framework

We consider a system of $n$ noninteracting qubits.Qubit $i$ evolves under a
Hamiltonian $H_{i}$, and the entire system under the Hamiltonian
$H=H_{1}+H_{2}+\cdots+H_{n}$.For simplicity, we suppose that
$H_{i}\ket{0}_{i}=0$ and $H_{i}\ket{1}_{i}=E_{i}^{(1)}\ket{1}_{i}$, with
$E_{i}^{(1)}\geqslant 0$.The all-zero bit string $\ket{0^{n}}$ labels the
zero-energy ground state.For a fixed inverse temperature
$\beta=1/k_{\mathrm{B}}T$, qubit $i$ has the thermal state

$\displaystyle\gamma_{i}=\Gamma_{i}/Z_{i}\ ,\
\text{where}\\\Gamma_{i}=e^{-\beta H_{i}}\
\text{and}\Z_{i}=\tr\left({\Gamma_{i}}\right)=1+e^{-\beta E_{i}^{(1)}}\ .$ (1)

The thermal qubit’s free energy isgiven by

$\displaystyle F_{i}=-k_{\mathrm{B}}T\log\left({Z_{i}}\right)\ .$ (2)

The _thermal operations_ model possible transformations in quantum
thermodynamics, for a system in controlled contact with a heat bath [41, 42,
37].Let $S$ denote a system with a Hamiltonian $H_{S}$.A thermal operation
$\Phi_{S}$ is defined as any operation of the form

$\displaystyle\rho\mapsto\Phi_{S}(\rho)=\tr_{B}\left({V_{SB}\,\left[{\rho\otimes\gamma_{B}}\right]\,V_{SB}^{\dagger}}\right)\
.$ (3)

$B$ denotes any auxiliary system with a Hamiltonian $H_{B}$.$V_{SB}$ denotes
any unitary that strictly conserves energy: $[V_{SB},H_{S}+H_{B}]=0$.For an
arbitrary system $X$ governed by a Hamiltonian $H_{X}$, the thermal state
$\gamma_{X}=e^{-\beta H_{X}}/\tr\left({e^{-\beta H_{X}}}\right)$ is defined
similarly to 1.Another general class of operations consists of the _Gibbs-
preserving maps_ [44].Let $S$ denote a system with a Hamiltonian $H_{S}$.A
Gibbs-preserving map $\mathcal{F}$ is any completely positive, trace-
preserving map that satisfies
$\mathcal{F}(\gamma_{S})=\gamma_{S^{\prime}}$.The Gibbs-preserving maps form a
larger class than the thermal operations [67].It remains unclear what resource
costs are necessary for implementing a general Gibbs-preserving map, using
other standard thermodynamic operations [68].When $H_{S}=0$, $\gamma_{S}$ is
proportional to the identity operator $\mathds{1}_{S}$, so every Gibbs-
preserving map $\mathcal{F}$ is a unital map
$\left[{\mathcal{F}(\mathds{1}_{S})=\mathds{1}_{S}}\right]$ and vice
versa.Inspired by the resource theory of thermodynamics, we use a model in
which all processes consist of primitive operations.A process is specified as
a sequence
$\mathcal{P}\coloneqq\left({\mathcal{E}_{1},\ldots,\mathcal{E}_{m}}\right)$ of
primitive operations.The sequence implements the operation
$\mathcal{E}_{\mathcal{P}}\coloneqq\mathcal{E}_{m}\cdots\mathcal{E}_{1}$.Each
process $\mathcal{P}$ has a complexity cost $C\left({\mathcal{P}}\right)$ and
a work cost $W\left({\mathcal{P}}\right)$.Both are sums

$\displaystyle
C\left({\mathcal{P}}\right)\coloneqq\sum_{i=1}^{m}C\left({\mathcal{E}_{i}}\right)\
,\;\;\text{and}\;\;W\left({\mathcal{P}}\right)\coloneqq\sum_{i=1}^{m}W\left({\mathcal{E}_{i}}\right)\$
(4)

of individual operations’ costs.One might refer to $C({\mathcal{P}})$ instead
as the _circuit size_ of $\mathcal{P}$.Suppose that $\mathcal{P}$ implements a
unitary operation $\mathcal{U}$.$C(\mathcal{P})$ might differ from the
complexity $C\left({\mathcal{U}}\right)$ of $\mathcal{U}$: there might exist a
process that also implements $\mathcal{U}$ but consists of fewer primitive
operations.The primitive operations on an $n$-qubit system, for a fixed
background inverse temperature $\beta=1/k_{\mathrm{B}}T$, are the following
(Fig. 1):

  1. (i)

The reset operation: qubit $i$ can be brought from an arbitrary state to the
ground state via an expenditure of work $\abs{F_{i}}$.This operation has the
work cost $W_{\textsc{reset},\,i}=-F_{i}=k_{\mathrm{B}}T\log(Z_{i})$ and no
complexity cost: $C_{\textsc{reset},\,i}=0$.

  2. (ii)

The extract operation: qubit $i$ can be brought from the state $\ket 0_{i}$ to
the thermal state $\gamma_{i}$ with an extraction of work $\abs{F_{i}}$.This
operation has the work cost
$W_{\textsc{extract},\,i}=F_{i}=-W_{\textsc{reset},i}$ and no complexity cost:
$C_{\textsc{extract},\,i}=0$.

  3. (iii)

Every operation $\mathcal{E}$ chosen from a fixed set $\mathcal{T}$ of
elementary computations costs one unit of complexity, $C(\mathcal{E})=1$, and
no work: $W(\mathcal{E})=0$.If $H_{i}=0$ for all $i$, then natural choices of
$\mathcal{T}$ include arbitrary two-qubit unitary gates with arbitrary
connectivities.In this case, $\mathcal{T}\simeq\bigcup_{(i,j)}\SU(4)_{i,j}$,
where each $(i,j)$ denotes a pair of qubits.If $H_{i}\neq 0$, natural choices
of $\mathcal{T}$ include the two-qubit thermal operations and the two-qubit
Gibbs-preserving maps, with arbitrary connectivities.

The work expended on the reset, and the work extracted via extract, naturally
generalize Landauer’s bound to noninteracting qubits.The reset and extract
operations’ ideal work costs are
$W_{\textsc{reset},\,i}=-W_{\textsc{extract},\,i}=F_{i}$ in standard
thermodynamic models, including the resource theory of thermal operations [42,
43, 69, 70, 71].If a qubit has a completely degenerate Hamiltonian, $H_{i}=0$,
these work costs reduce to Landauer’s bound:
$F_{i}=k_{\mathrm{B}}T\log(2)$.The set $\mathcal{T}$ of elementary
computations enables us to define a protocol’s complexity cost.$\mathcal{T}$
should contain only operations to which one can reasonably assign no work
costs.Typical models of information thermodynamics allow agents to extract
work from (multiple copies of) athermal states, so $\mathcal{T}$ should
contain only operations that map thermal states (from which no work can be
extracted) to thermal states.For energy-degenerate qubits ($H_{i}=0$ for all
$i$), a meaningful choice of $\mathcal{T}$ is a universal set of two-qubit
unitary gates: the primitive operation (iii) then enables quantum computation
with unitary circuits.If the qubits are not all energy-degenerate, some two-
qubit unitaries might map a thermal state to a athermal state; such gates
should be excluded from $\mathcal{T}$.A unitary operation that strictly
conserves energy may be included in $\mathcal{T}$.An operation that effects
transitions between energy levels may be included in $\mathcal{T}$ if the
operation preserves the set of thermal states.Examples include an operation
that always replaces its input with a thermal state.

###  II.2 One-shot entropy measures in quantum thermodynamics

A fundamental connection between thermodynamics and statistical mechanics is
the identification, under suitable conditions, of Clausius’ thermodynamic
entropy with the von Neumann entropy $\HH{\rho}$ of a quantum state $\rho$,

$\displaystyle\HH{\rho}\coloneqq-\tr({\rho\log\rho})\ .$ (5)

In the information-theoretic approach to thermodynamics, beyond the
traditional regime concerning many copies of a system, many thermodynamic
tasks have work costs inaccurately represented by the von Neumann entropy and
the standard free energy [61, 62, Dahlsten2013Non, 42,
lostaglio2015description, 74, 75, 76, vanderMeer2017Smoothed, 78, 79].Instead,
these work costs are quantified with _one-shot entropy measures_ , such as the
relative entropies [80, 81, 82] and Rényi-$\alpha$ entropies [43], including
the min- and max-entropies.We focus on the _hypothesis-testing relative
entropy_ , which interpolates between the min- and max-relative entropies [83,
Dupuis_13_Generalized, HypothesisEntropy, 86, 87, 88, 89].The hypothesis-
testing relative entropy is defined for a quantum state $\rho$, a positive-
semidefinite operator $\Gamma$, and an intolerance parameter $\eta\in(0,1]$:

$\displaystyle\DHyp[\eta]{\rho}{\Gamma}\coloneqq-\log\left({\min_{\begin{subarray}{c}0\leqslant
Q\leqslant\mathds{1}\\\
\tr({Q\rho})\geqslant\eta\end{subarray}}\left\\{{\frac{\tr\left({Q\Gamma}\right)}{\eta}}\right\\}}\right)\
.$ (6)

The _hypothesis-testing entropy_ of a quantum state $\rho$ is defined, for
$\eta\in(0,1]$, as

$\displaystyle\Hfnbase{\HSym}{\mathrm{H}}{\eta}\\{{-NoValue-}\\}(\rho)\coloneqq-\DHyp[\eta]{\rho}{\mathds{1}}\
.$ (7)

The entropy measures here have units of nats, rather than bits, because our
definitions have base-$e$, rather than base-2, logarithms.One can convert
between bits and nats via $\text{(\\# of bits)}=\text{(\\# of
nats)}/\log(2)$.Our convention introduces factors of $\log(2)$ in our results
for qubit systems.However, the convention yields familiar forms for
thermodynamic relations between entropy and quantities such as the free
energy.The hypothesis-testing entropy quantifies how well one can distinguish
between quantum states $\rho$ and $\sigma$ via a hypothesis test.Suppose that
we receive either $\rho$ or $\sigma$.We must guess which state we obtained,
based on the outcome of one measurement.We may choose the measurement,
specified by a two-outcome positive-operator-valued measure (POVM)
$\\{{Q,\mathds{1}-Q}\\}$.The outcome $Q$ implies that we should guess
“$\rho$”; and $\mathds{1}-Q$, that we should guess “$\sigma$.”Suppose that,
when $\rho$ is provided, the measurement must identify $\rho$ correctly with a
probability $\geqslant\eta$: $\tr({Q\rho})\geqslant\eta$.When $\sigma$ is
provided, the optimal probability $\tr({Q\sigma})$ of failing to identify
$\sigma$ is $\eta e^{-\DHyp[\eta]{\rho}{\sigma}}$.The interpretation of 6 as a
relative-entropy measure arises from certain properties.For example, 6 is non-
negative and obeys a data-processing inequality [84]; 6 approximates the min-
and max-relative entropies when $\eta\approx 0$ and $\eta\approx 1$ [84],
respectively; and 6 quantifies the resource costs of communication and
thermodynamic tasks [90].Appendix C contains a more detailed discussion of the
hypothesis-testing relative entropy and its properties.The hypothesis-testing
entropy and relative entropy have operational significances in quantum
thermodynamics [76, 91, 92].These quantities unify quantum-thermodynamic
results based on the min- and max- (relative) entropies [61, 93, 42, 45,
39]:Consider resetting a state $\rho$ on a memory register $S$ to a fixed
state $\ket{0}_{S}$.Suppose that $\rho$ evolves under a completely degenerate
Hamiltonian $H_{S}=0$ and that the resetting must fail with a probability at
most $\epsilon\geqslant 0$.Absent restrictions on the resetting’s complexity,
the resetting has a work cost [42, 84]

$\displaystyle
W^{\epsilon}\left({\rho_{S}\to\ket{0}_{S}}\right)\approx\Hfnbase{\HSym}{\mathrm{H}}{1-\epsilon}\\{{-NoValue-}\\}(\rho)\times
k_{\mathrm{B}}T\ .$ (8)

The approximation conceals technical details about how the failure probability
is measured.If $\rho_{S}=\mathds{1}_{2}/2$ is the single-qubit maximally mixed
state, we obtain the well-known formula for Landauer erasure [33]

$\displaystyle
W^{\epsilon}\left({\mathds{1}_{2}/2\to\ket{0}_{S}}\right)\approx
k_{\mathrm{B}}T\log(2)\ .$ (9)

###  II.3 Complexity (relative) entropy

The complexity entropy was introduced in the context of the resource theory of
uncomplexity [30].There, a state’s complexity entropy quantifies the qubits in
the state $\ket{0}$ extractable via a limited number of unitary gates.Here, we
apply the complexity entropy to quantum-information thermodynamics and detail
the entropy’s properties.We present a version of the complexity entropy that
is tailored to $n$-qubit quantum circuits wherein each gate is in the set
$\mathcal{T}$ of elementary computations.We introduce the complexity entropy’s
general form in Appendix D, where we prove general bounds and monotonicity
results.A key motivation for defining the complexity entropy is the
following.Consider a hypothesis test between states $\rho$ and $\sigma$.The
hypothesis-testing relative entropy quantifies the optimal probability of
wrongly rejecting $\sigma$ with any strategy that correctly accepts $\rho$
with a probability $\geqslant\eta$.However, an optimal measurement
$\\{{Q,\mathds{1}-Q}\\}$ might be too complex to be executed in a reasonable
time.Suppose, for instance, that $\rho=\proj{\psi}$ is a highly complex, pure
$n$-qubit state and that $\sigma=\mathds{1}_{2}^{\otimes n}/2^{n}$ is
maximally mixed.A measurement that distinguishes $\rho$ from $\sigma$ may
require a complex circuit implementable only in an exponentially long time
[94, 95].It is natural to restrict $Q$ to be implementable in a reasonable
time, with a circuit composed of $\leqslant r$ gates.The _complexity relative
entropy_ is defined similarly to the hypothesis-testing relative entropy. The
former, however, has a complexity restriction in the optimization over
measurement operators.To define the complexity entropy, we must specify the
set of POVM effects that a computationally limited observer can render.Define
$\mathsf{M}^{r}$ as the set of POVM effects that one can implement by
performing $\leqslant r$ gates and then applying certain single-qubit
projectors.All tensor products of those projectors constitute the set of
complexity-zero POVM effects

$\displaystyle\mathsf{M}^{0}\coloneqq\left\\{{\bigotimes_{i=1}^{n}Q_{i}\,:\;Q_{i}\in\left\\{{\proj
0,\mathds{1}_{2}}\right\\}}\right\\}\ .$ (10)

For each $i$, an effect in $\mathsf{M}^{0}$ projects qubit $i$ onto $\ket 0$
or does nothing.Fix any set $\mathcal{G}$ of elementary quantum operations
(completely positive, trace-nonincreasing maps).(We define complexity-
restricted POVM elements in terms of $\mathcal{G}$, as an information-
theoretic quantity independent of the thermodynamic framework in II.1.Hence
$\mathcal{G}$ is independent of the operations introduced there.If applying
the POVM elements in that framework, however, one can choose for $\mathcal{G}$
to consist of operations introduced in II.1.)For $r>0$, we define

$\displaystyle\mathsf{M}^{r}\coloneqq\left\\{{\mathcal{E}_{1}^{\dagger}\cdots\mathcal{E}_{r}^{\dagger}(P)\,:\;P\in\mathsf{M}^{0}\,,\;\mathcal{E}_{i}\in\mathcal{G}}\right\\}\
.$ (11)

One natural choice for $\mathcal{G}$ might be the set of two-qubit unitary
gates.Another choice, in the context of complexity and thermodynamics, is
$\mathcal{G}=\mathcal{T}$, where $\mathcal{T}$ is the set of elementary
computations defined in II.1.Even if a $Q$ belongs to $\mathsf{M}^{r}$, the
complementary effect $\mathds{1}-Q$ might not.Indeed, the definition of
$\mathsf{M}^{r}$ applies in settings where only one POVM effect is relevant in
a hypothetical measurement.For instance, suppose we wish to certify that some
process outputs a state close to some pure state $\ket\psi$.One may consider a
hypothetical measurement of the output state with a POVM containing the effect
$\proj\psi$, and ascertain that its outcome probability is close to unity.In
such a scenario, the POVM effect need not be implemented in practice, and
other effects that complete the POVM may be ignored.Having introduced
complexity-restricted POVM effects, we can define complexity-restricted
entropic quantities.Let $\rho$ denote any quantum state; and $\Gamma$, any
positive-semidefinite operator.The _complexity relative entropy_ of $\rho$
relative to $\Gamma$, at a complexity scale $r\geqslant 0$ with respect to
$\mathsf{M}^{r}$, and for $\eta\in(0,1]$, is

$\displaystyle\Dbase{\DSym}_{\mathrm{H}}^{{r},\,{\eta}}{\rho}{\Gamma}\coloneqq-\log\left({\inf_{\begin{subarray}{c}Q\in\mathsf{M}^{r}\\\
\tr(Q\rho)\geqslant\eta\end{subarray}}\left\\{{\frac{\tr(Q\Gamma)}{\tr(Q\rho)}}\right\\}}\right)\
.$ (12)

This definition extends the hypothesis-testing relative entropy 6 by
restricting the optimization to POVM effects implementable with $\leqslant r$
gates.(See D.1 for a more general definition and for details.)The definition
12 mirrors a construction, based on the trace norm, in Ref. [17].The
complexity relative entropy enjoys an operational interpretation similar to
that of the hypothesis-testing relative entropy 6.Consider a hypothesis test
between states $\rho$ and $\sigma$.We identify $\rho$ as the _null hypothesis_
and $\sigma$ as the _alternative hypothesis_.Suppose that one can measure only
a POVM $\left\\{{Q,\mathds{1}-Q}\right\\}$ for which $Q\in\mathsf{M}^{r}$.It
is useful to allow, apart from a measurement, one toss of a biased classical
coin.(We explain why below.)One can freely choose the coin’s probability
$q\in(0,1]$ of landing heads-up.Consider guessing “$\rho$” if the coin shows
“heads” and the POVM outcome is $Q$, guessing “$\sigma$” otherwise.This
strategy is equivalent to measuring the POVM
$\left\\{{qQ,\mathds{1}-qQ}\right\\}$.A type I error—incorrectly rejecting the
null hypothesis—occurs with a probability $1-\tr({qQ\rho})$.A type II
error—incorrectly rejecting the alternative hypothesis—occurs with a
probability $\tr({qQ\sigma})$.The following proposition shows how the
complexity relative entropy characterizes hypothesis testing with complexity
limitations:

######  Proposition I (Hypothesis testing with complexity limitations).

Let $\rho$ and $\sigma$ denote quantum states.Let $\eta\in(0,1]$ and
$\delta\in(0,1]$.There exists a $Q\in\mathsf{M}^{r}$ and $q\in(0,1]$ such that
$\tr\left({[qQ]\rho}\right)=\eta$ and
$\tr\left({[qQ]\sigma}\right)\leqslant\delta$ if and only if

$\displaystyle\Dbase{\DSym}_{\mathrm{H}}^{{r},\,{\eta}}{\rho}{\sigma}\geqslant-\log\left({\delta/\eta}\right)\
.$ (13)

The proposition guarantees that, if 13 holds, then, for any parameters
$\eta,\delta\in(0,1]$, some hypothesis test of the sort just described has two
properties:a type I error occurs with a probability $\leqslant 1-\eta$, and a
type II error occurs with a probability $\leqslant\delta$.One can satisfy 13
only if $\delta\leqslant\eta$, since the complexity relative entropy is non-
negative.The coin toss’s inclusion in the hypothesis test enables a precise
relationship between the complexity relative entropy and hypothesis testing,
for $\eta$ values far from 1.If $\eta\approx 1$, then $q\approx 1$, and the
agent need not toss the coin.We prove the proposition in D.3.Having introduced
the complexity relative entropy, we now define the complexity entropy.Let
$\rho$ denote any quantum state.The _complexity entropy_ of $\rho$, at a
complexity scale $r\geqslant 0$ with respect to $\mathsf{M}^{r}$, and for
$\eta\in(0,1]$, is

$\displaystyle\Hfnbase{\HSym}{\mathrm{H}}{{r},\,{\eta}}\\{{-NoValue-}\\}(\rho)\coloneqq-\Dbase{\DSym}_{\mathrm{H}}^{{r},\,{\eta}}{\rho}{\mathds{1}}\
.$ (14)

This definition mirrors 7.We follow a standard procedure for defining an
entropy using a relative entropy [96].The normalization factor $\tr(Q\rho)$ in
12 guarantees elementary properties of the complexity entropy, such as its
having the range $[0,n\log(2)]$ for all $\eta$.In Appendix D, we define an
alternative version of the complexity (relative) entropy without the
normalization factor.This alternative is technically more convenient, and we
bound one version in terms of the other.

##  III Thermodynamic information erasure with complexity constraints

We now turn to the erasure of the $n$-qubit memory register introduced in
II.What is the optimal work cost of resetting a state $\rho$ to $\ket{0^{n}}$,
using the primitive operations (i), (ii) and (iii)?

###  III.1 Erasure of qubits with a completely degenerate Hamiltonian

We first consider a simpler case: each memory qubit has a degenerate
Hamiltonian ($H_{i}=0$ for all $i$).Let the elementary computations
$\mathcal{T}$ be the two-qubit unitary gates with arbitrary connectivities:
$\mathcal{T}\simeq\bigcup_{(i,j)}\SU(4)_{i,j}$.The mixed-state fidelity
between states $\sigma$ and $\tau$ is defined as [BookNielsenChuang2000]

$F\left({\sigma,\tau}\right)\coloneqq\tr\left({\sqrt{\sigma^{1/2}\tau\sigma^{1/2}}}\right)\
.$ (15)

We define an erasure of $\rho$ as any composition of the operations (i), (ii)
and (iii) that transforms $\rho$ into a state $\rho^{\prime}$ satisfying
$F^{2}\left({\rho^{\prime},\proj{0^{n}}}\right)=\dmatrixel{0^{n}}{\rho^{\prime}}\geqslant\eta$,
for some fixed $\eta\in(0,1]$ [Fig. 4(a)].

Fig. 4: Protocols for thermodynamic information erasure with complexity
constraints.The process consists of reset gates (gray circuit elements),
extract gates (green), and computational gates (brown) [cf. primitives (i),
(ii) and (iii) of Fig. 1].(a) A general protocol interleaves the primitive
operations (i), (ii) and (iii), preparing a state close to $\ket{0^{n}}$.The
protocol’s complexity cost $C$ and work cost $W$ follow from summing the
primitive operations’ costs (Fig. 1).(b) In the simplified protocol, one
applies $\leqslant r$ computational gates [primitive (iii)].Then, one erases
any qubits far from $\ket 0$, using reset operations [primitive (i)].The
circuit compresses $\rho$ into fewer qubits, to be erased by reset
operations.Such protocols extract pure $\ket{0}$ qubits in the resource theory
of uncomplexity [30].

One can interpret $F^{2}\left({\rho^{\prime},\proj{0^{n}}}\right)$ as the
probability of preparing $\ket{0^{n}}$.We now quantify the trade-off between
the work cost and complexity cost of an erasure protocol $\mathcal{E}$.Being a
process, $\mathcal{E}$ is a sequence of primitive operations.Yet, we denote by
$\mathcal{E}$ also the operation implemented by the sequence, in a slight
abuse of notation.Suppose that $\mathcal{E}$ has a complexity at most
$r\geqslant 0$: $C(\mathcal{E})\leqslant r$.The optimal work cost for such a
protocol is

$\displaystyle
W_{r}\coloneqq\min_{\mathcal{E}}\left\\{{W(\mathcal{E})\,:\C(\mathcal{E})\leqslant
r\,,\;F^{2}\bm{(}\mathcal{E}(\rho),\proj{0^{n}}\bm{)}\geqslant\eta}\right\\}\
.$ (16)

####  III.1.1 Protocols whose reset operations happen at the end

As an initial step, we consider an erasure protocol divided into two parts
[Fig. 4(b)].First, the state undergoes $\leqslant r$ computational gates
[primitive (iii)].Then, reset operations [primitive (i)] are applied.Such a
protocol’s optimal work cost is

$\displaystyle W_{r}^{*}=$
$\displaystyle\min_{\mathcal{E}}\bigl{\\{}W(\mathcal{E})\,:\\\mathcal{E}=\left({\textstyle\prod_{i\in\mathcal{W}}\mathcal{E}_{\textsc{RESET},i}}\right)\mathcal{E}_{r}\cdots\mathcal{E}_{1}\,,\;$
$\displaystyle\hskip
11.38092pt\mathcal{W}\subset\\{{1,2,\ldots,n}\\}\,,\;F^{2}\bm{(}\mathcal{E}(\rho),\proj{0^{n}}\bm{)}\geqslant\eta\bigr{\\}}\
.$ (17)

$\mathcal{W}$ denotes the subset of the qubits that undergo reset
operations.We now identify how to erase $\rho$ using the least amount of work.
We should compress $\rho$ into as few qubits as possible, using $\leqslant r$
gates, to apply as few reset operations as possible.In other words, we should
perform data compression with $\leqslant r$ gates.This information-theoretic
interpretation of erasure mirrors two earlier interpretations of erasures: the
erasure of $n$ qubits without complexity restrictions [61] and the erasure of
a quantum system using a quantum memory [62].We analyzed a version of this
compression task in the context of extracting pure qubits in the resource
theory of uncomplexity [30].A variant of the complexity entropy, we showed,
quantifies the qubits that cannot be reset to $\ket{0}$ states with $\leqslant
r$ gates.In this subsection, we adapt that argument to thermodynamic
erasure.(We discuss further applications of the complexity entropy to
information-theoretic tasks in V.)Let $\mathcal{E}$ denote any protocol that
achieves the minimum in 17: $W(\mathcal{E})=W_{r}^{*}$.Assume that the work
cost $W(\mathcal{E})$ corresponds to $\beta
W(\mathcal{E})/\log(2)=\abs{\mathcal{W}}\eqqcolon w$ bits.Define the projector
$P\coloneqq\mathds{1}_{\mathcal{W}}\otimes\proj{0^{n-w}}_{\mathcal{W}^{\rm
c}}$, wherein $\mathcal{W}^{\rm c}$ denotes the complement of
$\mathcal{W}$.Define the POVM effect

$\displaystyle
Q\coloneqq\mathcal{E}_{1}^{\dagger}\cdots\mathcal{E}_{r}^{\dagger}({P})\ ,$
(18)

wherein each $\mathcal{E}_{i}^{\dagger}$ denotes the adjoint of the operation
$\mathcal{E}_{i}$ $\big{[}$defined via
$\tr\bm{(}\mathcal{E}_{i}^{\dagger}(A)\,B\bm{)}=\tr\bm{(}A\,\mathcal{E}_{i}(B)\bm{)}$
for all operators $A$ and $B$$\big{]}$.$P$ projects onto $\ket 0$ each qubit
not subject to any reset operation, leaving all other qubits untouched.We
choose for the set $\mathcal{G}$ of elementary operations, used to define
$\mathsf{M}^{r}$ in 11, to be the set $\mathcal{T}$ of elementary
computations, used to define our model in II.1.$Q$ belongs to
$\mathsf{M}^{r}$.Furthermore,

$\displaystyle\tr({Q\rho})$
$\displaystyle=\tr\left(P\,\mathcal{E}_{r}\cdots\mathcal{E}_{1}(\rho)\right)$
$\displaystyle=\tr\left\\{{\proj{0^{n-w}}\,\tr_{\mathcal{W}}\bm{(}\mathcal{E}_{r}\cdots\mathcal{E}_{1}(\rho)\bm{)}}\right\\}$
$\displaystyle=\tr\bm{(}\proj{0^{n}}\mathcal{E}(\rho)\bm{)}=F^{2}\bm{(}\mathcal{E}(\rho),\proj{0^{n}}\bm{)}\geqslant\eta\
,$ (19)

so $Q$ is a candidate for the optimization 12 defining the complexity entropy
$\Hfnbase{\HSym}{\mathrm{H}}{{r},\,{\eta}}\\{{-NoValue-}\\}(\rho)=-\Dbase{\DSym}_{\mathrm{H}}^{{r},\,{\eta}}{\rho}{\mathds{1}}$.Moreover,
since each $\mathcal{E}_{i}$ is unitary,
$\tr({Q})=\tr\bm{(}P\,\mathcal{E}_{r}\cdots\mathcal{E}_{1}(\mathds{1})\bm{)}=\tr({P})=2^{w}$.Hence,

$\displaystyle\Hfnbase{\HSym}{\mathrm{H}}{{r},\,{\eta}}\\{{-NoValue-}\\}(\rho)-\log\left({1/\eta}\right)\leqslant\log\bm{(}\tr(Q)/\tr(Q\rho)\bm{)}-\log\left({1/\eta}\right)$
$\displaystyle\leqslant\log\bm{(}\tr({Q})\bm{)}=w\log(2)=\beta
W(\mathcal{E})=\beta W_{r}^{*}\ .$ (20)

A similar inequality points in the opposite direction, as we show by reversing
the steps above.Consider any candidate $Q\in\mathsf{M}^{r}$ for the
optimization 12 defining
$\Hfnbase{\HSym}{\mathrm{H}}{{r},\,{\eta}}\\{{-NoValue-}\\}(\rho)=-\Dbase{\DSym}_{\mathrm{H}}^{{r},\,{\eta}}{\rho}{\mathds{1}}$.Let
$Q$ be optimal (or arbitrarily close to optimal).By the definition 11,
$Q=\mathcal{E}_{1}^{\dagger}\cdots\mathcal{E}_{r}^{\dagger}({P})$, wherein
each $\mathcal{E}_{i}\in\mathcal{G}$ and wherein $P$ projects onto $\ket 0$
each qubit in some subset $\mathcal{W}^{\rm c}$, leaving all other qubits
untouched.Let
$\mathcal{E}\coloneqq\left({\textstyle\prod_{i\in\mathcal{W}}\mathcal{E}_{\textsc{RESET},i}}\right)\mathcal{E}_{r}\cdots\mathcal{E}_{1}$.$\mathcal{E}$
erases $\rho$, since

$\displaystyle
F^{2}\bm{(}\mathcal{E}(\rho),\proj{0^{n}}\bm{)}=\tr\bm{(}\proj{0^{n}}\mathcal{E}(\rho)\bm{)}=\tr\left({Q\rho}\right)\geqslant\eta\
.$ (21)

Hence,

$\displaystyle\beta W_{r}^{*}\leqslant\beta
W(\mathcal{E})=\abs{\mathcal{W}}\,\log(2)$
$\displaystyle=\log\bm{(}\tr(Q)\bm{)}\leqslant\log\bm{(}\tr(Q)/\tr(Q\rho)\bm{)}=\Hfnbase{\HSym}{\mathrm{H}}{{r},\,{\eta}}\\{{-NoValue-}\\}(\rho)\
.$ (22)

The last equality holds if $Q$ is optimal.(If $Q$ is arbitrarily close to
optimal, then the last two quantities are arbitrarily close to each other.)We
have therefore proved the following theorem:

######  Theorem II (Complexity-limited erasure with restricted protocols).

Consider erasing an $n$-qubit system governed by a fully degenerate
Hamiltonian.Every optimal complexity-limited protocol that uses only primitive
(iii) (wherein $\mathcal{T}=\mathcal{G}$ consists of unitary operations)
followed by primitive (i), expends an amount $W_{r}^{*}$ of work that obeys

$\displaystyle\Hfnbase{\HSym}{\mathrm{H}}{{r},\,{\eta}}\\{{-NoValue-}\\}(\rho)-\log\left({1/\eta}\right)\leqslant\beta
W_{r}^{*}\leqslant\Hfnbase{\HSym}{\mathrm{H}}{{r},\,{\eta}}\\{{-NoValue-}\\}(\rho)\
.$ (23)

Two points merit mentioning.First, one might wonder whether the work cost
$\beta^{-1}\left[{\Hfnbase{\HSym}{\mathrm{H}}{{r},\,{\eta}}\\{{-NoValue-}\\}(\rho)-\log(1/\eta)}\right]$
is achievable.The answer depends on whether one can implement, with gates in
$\mathcal{G}$, a POVM effect $Q\in\mathsf{M}^{r}$ that satisfies
$\tr(Q\rho)=\eta$ and is arbitrarily close to optimal for
$\Hfnbase{\HSym}{\mathrm{H}}{{r},\,{\eta}}\\{{-NoValue-}\\}(\rho)$.In such a
case, the first inequality in 23 saturates:
$\Hfnbase{\HSym}{\mathrm{H}}{{r},\,{\eta}}\\{{-NoValue-}\\}(\rho)-\log(1/\eta)$
equals a variant of the complexity entropy, and that variant, we show, equals
$\beta W_{r}^{*}$.(See D.5 and E for details.)Considering the variant’s
definition, one can interpret the $\log(1/\eta)$ in 23 as a particularity of
how we defined the complexity entropy.Second, the $\log(1/\eta)$ is
proportional to the work won in a successful bet on an event that occurs with
a probability $\eta$ [98].We can understand this point through a simple
example.Consider resetting the single-qubit maximally mixed state
$\rho=\mathds{1}_{2}/2$ to $\ket 0$.Suppose that our target success
probability $\eta$ satisfies $\eta\leqslant 1/2$.One successful erasure
protocol does nothing: with the probability $1/2$, $\ket 0$ is prepared.Yet
standard measures of entropy (including the Rényi entropies of one-shot
information theory [80]) attribute to $\rho$ one bit of entropy.The zero work
cost of erasing a maximally mixed qubit with $\eta=1/2$ can be understood as a
sum of (i) one unit of work expended to reduce the entropy of $\rho$ and (ii)
one unit of work extracted by a successful bet with the success probability
$1/2$.We now present a few textbook quantum states and the work costs of
erasing them, in various regimes of $r$ and $\eta$.

##### Computational-basis states.

If $\rho=\proj{0^{n}}$, then
$\Hfnbase{\HSym}{\mathrm{H}}{{r},\,{\eta}}\\{{-NoValue-}\\}(\rho)=0$ for all
$r$ and $\eta$.An optimal protocol is to do nothing—apply no reset operations
and no work: $W_{r}^{*}=0$.If $\rho=\proj{1^{n}}$, then one resets $\rho$ to
$\ket{0^{n}}$ by flipping each qubit to $\ket{0}$, incurring a minor
complexity cost (minor compared to the exponential complexities expected of
most $n$-qubit unitaries [4]).Assume that $n$ is even, for simplicity.One can
flip all $n$ qubits with one layer of $n/2$ two-qubit gates.Therefore,
whenever $r\geqslant n/2$,
$\Hfnbase{\HSym}{\mathrm{H}}{{r},\,{\eta}}\\{{-NoValue-}\\}(\rho)=0$, and
$W_{r}^{*}=0$, for all $\eta$.If, however, $r<n/2$, then one can flip only
$2r<n$ qubits.One must apply reset operations to the other $n-2r$ qubits.In
this case,
$\Hfnbase{\HSym}{\mathrm{H}}{{r},\,{\eta}}\\{{-NoValue-}\\}(\rho)=(n-2r)\log(2)$,
and $W_{r}^{*}=({n-2r})\,k_{\mathrm{B}}T\log(2)$, for all $\eta$.

##### The maximally mixed state.

If $\rho$ is maximally mixed, then
$\Hfnbase{\HSym}{\mathrm{H}}{{r},\,{\eta}}\\{{-NoValue-}\\}(\rho)=n\log(2)$
for all $r$ and $\eta$.Suppose that the error tolerance is insignificant:
$\eta\approx 1$.An optimal protocol requires $n$ reset operations, costing the
maximum amount of work: $W_{r}^{*}=n\,k_{\mathrm{B}}T\log(2)$.

##### Greenberger-Horne-Zeilinger (GHZ) state.

Let

$\displaystyle\ket{\mathrm{GHZ}}$
$\displaystyle\coloneqq\frac{1}{\sqrt{2}}\left({\ket{0^{n}}+\ket{1^{n}}}\right)\
,$ (24)

and let $\rho=\proj{\mathrm{GHZ}}$.One can prepare the GHZ state with a
Hadamard gate followed by $n-1$ CNOT gates.Therefore,
$\Hfnbase{\HSym}{\mathrm{H}}{{r},\,{\eta}}\\{{-NoValue-}\\}(\rho)=0$ if
$r\geqslant n$.If $r<n$, then one can apply $r$ CNOT gates to disentangle $r$
qubits from the other $n-r$ qubits.The $n-r$ qubits require reset
operations.Absent any significant error tolerance (if $\eta\approx 1$),
$\Hfnbase{\HSym}{\mathrm{H}}{{r},\,{\eta}}\\{{-NoValue-}\\}(\rho)=(n-r)\log(2)$,
and $W_{r}^{*}=({n-r})\,k_{\mathrm{B}}T\log(2)$.

##### A Haar-random state.

Let $\ket\psi$ denote a state chosen randomly according to the Haar measure on
the pure $n$-qubit states.The state $\rho=\proj{\psi}$ is indistinguishable
from the maximally mixed state, according to $\poly(n)$-complex observables
[94, 95].Therefore, if $r\lesssim\poly(n)$, one cannot distinguish $\rho$ from
the maximally mixed state using $\leqslant r$ gates.All $n$ qubits must
undergo reset operations.Absent any significant error tolerance (if
$\eta\approx 1$),
$\Hfnbase{\HSym}{\mathrm{H}}{{r},\,{\eta}}\\{{-NoValue-}\\}(\rho)=n\log(2)$,
and $W_{r}^{*}=n\,k_{\mathrm{B}}T\log(2)$.This example constitutes a special
case of V.4 in V.4.There, we prove a lower bound on the complexity entropy of
a state generated by a random circuit.Random circuits effect Haar-random
unitaries in the large-circuit-depth limit.

##### Mixture of different-complexity states.

Let $\rho$ denote a convex mixture of $\proj{0^{n}}$ and a high-complexity
state $\proj{\psi}$: $\rho=(1-\epsilon)\proj{0^{n}}+\epsilon\proj{\psi}$,
wherein $\epsilon\in[0,1-\eta]$.The POVM effect $Q=\proj{0^{n}}$ is a
candidate for the optimization 12 defining
$\Hfnbase{\HSym}{\mathrm{H}}{{r},\,{\eta}}\\{{-NoValue-}\\}(\rho)=-\Dbase{\DSym}_{\mathrm{H}}^{{r},\,{\eta}}{\rho}{\mathds{1}}$.
Therefore,
$\Hfnbase{\HSym}{\mathrm{H}}{{r},\,{\eta}}\\{{-NoValue-}\\}(\rho)\leqslant-\log(1-\epsilon)$,
and $W_{r}^{*}\leqslant-
k_{\mathrm{B}}T\log(1-\epsilon)\approx\epsilon\,k_{\mathrm{B}}T$ (the
approximation holds for small $\epsilon$).

####  III.1.2 General protocols with midcircuit reset and extract operations

Suppose that each qubit’s Hamiltonian is degenerate.Suppose further that a
process can be any sequence of the primitives (i), (ii) and (iii) [Fig.
4(a)].A process may interleave elementary computations with reset and extract
operations on the same qubit.These midcircuit nonunitary operations can reduce
the complexity of information erasure.The significance of midcircuit
measurements in _monitored circuits_ has only recently been appreciated, both
in quantum information and in condensed-matter theory.Experimentalists have
recently used midcircuit measurements in quantum error correction and in
_monitored circuits_ [99, 100, 101].Along similar lines, quantum phases of
matter driven by measurements have been explored [102, 103, 104, 105, 106].We
seek to bound $W_{r}$, defined in 16.Our strategy is to map a general erasure
protocol to a different protocol involving additional auxiliary systems and
whose reset operations all happen at the end.The work cost of the general
protocol is then bounded using an argument adapted from the one in III.1.1.We
must transform a protocol $\mathcal{E}$ into a POVM effect.Our strategy
involves ancillary qubits, each initialized to $\ket 0$.Every midcircuit reset
operation on qubit $i$ is performable with a final reset operation: we swap
qubit $i$ with an ancilla, then reset the ancilla.Similarly, every midcircuit
extract operation on qubit $i$ is performable with an initial extract
operation: we perform an extract operation on an ancilla, then swap the
ancilla with qubit $i$.In both processes, every ancilla begins and ends in
$\ket 0$ (recall that the extract operation is performable only on a qubit in
$\ket 0$).We assume that the swap gate belongs to $\mathcal{T}$.

Consider any candidate protocol $\mathcal{E}$ for the optimization 16.Suppose
that $\mathcal{E}$ consists of $m_{1}$ reset operations, $m_{2}$ extract
operations, and $\leqslant r$ gates.$\mathcal{E}$ has the complexity cost
$C(\mathcal{E})\leqslant r$ and the work cost
$W(\mathcal{E})=(m_{1}-m_{2})\,k_{\mathrm{B}}T\log(2)$.Let us transfer all the
reset and extract operations in $\mathcal{E}$ to ancillas.We obtain a protocol
$\mathcal{E}^{\prime}$ of $\leqslant r+m_{1}+m_{2}$ gates (each swap
contributes one gate), preceded by extract operations and followed by reset
operations.$\mathcal{E}^{\prime}$ acts on $n+m_{1}+m_{2}$ qubits and has the
complexity cost $C(\mathcal{E}^{\prime})\leqslant r+m_{1}+m_{2}$.Immediately
after the initial extract operations, the input state is

$\displaystyle\tilde{\rho}_{m_{1},m_{2}}\coloneqq\rho\otimes\proj{0^{m_{1}}}\otimes\mathds{1}_{2}^{\otimes
m_{2}}/2^{m_{2}}\ .$ (25)

Subsequently, $\mathcal{E}^{\prime}$ outputs a state
$\mathcal{E}^{\prime}(\tilde{\rho})\eqqcolon\tilde{\rho}^{\prime}$ satisfying

$\displaystyle
F^{2}\bm{(}\tr_{m_{1}}({\tilde{\rho}^{\prime}}),\proj{0^{n+m_{2}}}\bm{)}\geqslant\eta\
.$ (26)

We now adapt the argument used for protocols whose reset operations happen at
the end.Suppose the set $\mathcal{G}$ of elementary operations, used to define
$\mathsf{M}^{r}$ in 11, equals the set of elementary computations:
$\mathcal{G}=\mathcal{T}$.Define the POVM effect

$\displaystyle
Q\coloneqq\mathcal{E}^{\prime\dagger}\left({\proj{0^{n}}\otimes\mathds{1}_{2}^{\otimes
m_{1}}\otimes\proj{0^{m_{2}}}}\right)\ .$ (27)

Then

$\displaystyle\tr\left({Q\tilde{\rho}}\right)$
$\displaystyle=\tr\bm{(}\proj{0^{n+m_{2}}}\,\tr_{m_{1}}({\tilde{\rho}^{\prime}})\bm{)}\geqslant\eta\
.$ (28)

Hence, $Q$ is a candidate for the optimization 12 defining
$\Hfnbase{\HSym}{\mathrm{H}}{{r+m_{1}+m_{2}},\,{\eta}}\\{{-NoValue-}\\}(\tilde{\rho})=-\Dbase{\DSym}_{\mathrm{H}}^{{r+m_{1}+m_{2}},\,{\eta}}{\tilde{\rho}}{\mathds{1}}$.Therefore,

$\displaystyle\Hfnbase{\HSym}{\mathrm{H}}{{r+m_{1}+m_{2}},\,{\eta}}\\{{-NoValue-}\\}(\tilde{\rho})$
$\displaystyle\leqslant\log\bm{(}\tr(Q)/\tr(Q\tilde{\rho})\bm{)}$
$\displaystyle\leqslant m_{1}\log(2)+\log\left({1/\eta}\right)\ ,$ (29)

so

$\displaystyle\beta
W\left({\mathcal{E}}\right)\geqslant\Hfnbase{\HSym}{\mathrm{H}}{{r+m_{1}+m_{2}},\,{\eta}}\\{{-NoValue-}\\}(\tilde{\rho})-m_{2}\log(2)-\log\left({1/\eta}\right)\
.$ (30)

We use the shorthand notation

$\displaystyle g^{r,\eta}(\rho)\coloneqq\inf_{m_{1},m_{2}\geqslant
0}\left\\{{\Hfnbase{\HSym}{\mathrm{H}}{{r+m_{1}+m_{2}},\,{\eta}}\\{{-NoValue-}\\}(\tilde{\rho}_{m_{1},m_{2}})-m_{2}\log(2)}\right\\}$
(31)

and take the infimum of 30 over all protocols $\mathcal{E}$.Combining the
previous two equations yields

$\displaystyle\beta W_{r}\geqslant g^{r,\eta}(\rho)-\log\left({1/\eta}\right)\
.$ (32)

The reverse direction might not hold, generally.For any $m_{1},m_{2}\geqslant
0$, 23 guarantees the existence of a protocol $\mathcal{E}$ that has two
properties.First, $\mathcal{E}$ consists of $\leqslant r+m_{1}+m_{2}$
computational gates followed by $w$ reset operations.Second, $\mathcal{E}$
maps $\tilde{\rho}$ approximately to $\ket{0^{n+m_{1}+m_{2}}}$, at the work
cost
$w\,\log(2)\leqslant\Hfnbase{\HSym}{\mathrm{H}}{{r+m_{1}+m_{2}},\,{\eta}}\\{{-NoValue-}\\}(\tilde{\rho})$.Yet,
such a protocol may involve the $m_{1}+m_{2}$ ancillas in a computation
inequivalent to any computation on $n$ qubits, even if the latter computation
includes midcircuit reset and extract operations.Overall, we have bounded the
optimal work cost $W_{r}$ of erasing $\rho$ using $\leqslant r$ computational
gates.

######  Theorem III (Bound of optimal work cost).

$W_{r}$ obeys

$\displaystyle g^{r,\eta}(\rho)-\log\left({1/\eta}\right)\leqslant\beta
W_{r}\leqslant\beta
W_{r}^{*}\leqslant\Hfnbase{\HSym}{\mathrm{H}}{{r},\,{\eta}}\\{{-NoValue-}\\}(\rho)\
.$ (33)

A large gap may separate $W_{r}$ and $W_{r}^{*}$ if, with few pure ancillas,
one can uncompute a pure state $\ket\chi$ to $\ket{0^{n}}$, using a circuit
much shorter than is possible without ancillas.In other words, an erasure
protocol may benefit from early reset operations: the resulting pure qubits
may be used as ancillas for uncomputing the remaining state.For instance,
there might exist an $n$-qubit state $\ket\chi$, and an $\ell\ll n$, with the
following two properties.First, $\ket{\chi}\otimes\ket{0^{\ell}}$ is much less
complex than$\ket\chi$: $C\left({\ket\chi\otimes\ket{0^{\ell}}}\right)\ll
C\left({\ket\chi}\right)$.Second, in the absence of ancillas, $r$ gates fail
to extract any $\ket{0}$’s from $\ket\chi$, if
$r=C\left({\ket\chi\otimes\ket{0^{\ell}}}\right)$.Midcircuit reset operations
would be able to lower the work cost of erasing
$\proj\chi\otimes\left({\mathds{1}_{2}^{\otimes\ell}/2^{\ell}}\right)$ with at
most $r=C\left({\ket\chi\otimes\ket{0^{\ell}}}\right)$ gates, we now show.The
following protocol would employ midcircuit reset operations and cost work
$k_{\rm B}T\ell\log(2)$: reset the $\ell$ mixed qubits, paying $\ell$ units of
work.Then, uncompute the remaining state, $\ket\chi\otimes\ket{0^{\ell}}$, to
$\ket{0^{n+\ell}}$, using $r$ gates.The total work cost would be
$\beta^{-1}\ell\log(2)$.In contrast, consider a protocol whose reset
operations happen at the end.$r$ operations would not extract any
$\ket{0}$’s.Such a protocol would require $n+\ell$ units of work: $\beta
W_{r}^{*}=(n+\ell)\log(2)\gg\beta W_{r}$.

###  III.2 Erasure of qubits with a general product Hamiltonian

We now consider a more general setup: each qubit has a not-necessarily-
degenerate Hamiltonian $H_{i}$, as per II.The set $\mathcal{T}$ of elementary
computations can no longer be the set of all two-qubit unitary gates: some
gates would require work.We require that $\mathcal{T}$ contain only completely
positive, trace-preserving maps $\mathcal{E}$ that satisfy thetechnical
property

$\displaystyle\mathcal{E}(\Gamma)=\Gamma\
,\;\;\text{wherein}\;\;\Gamma=e^{-\beta\sum_{i}H_{i}}=\bigotimes_{i=1}^{n}\Gamma_{i}\
.$ (34)

The operators $\Gamma_{i}$ are defined in 1.Examples of such operations
include the two-qubit thermal operations and the two-qubit Gibbs-preserving
maps (II).We assume 34 to ensure a thermodynamically consistent accounting of
work costs: elementary computations should cost no work.For concreteness, we
describe another class of operations that satisfy condition 34.These
operations can model computations on systems governed by product Hamiltonians,
as well as crude control over interactions with a heat bath.Consider an
operation, on qubits $i$ and $j$, of the form

$\displaystyle\rho\mapsto\mathcal{E}(\rho)$
$\displaystyle=(1-q)U_{i,j}\,\rho\,U_{i,j}^{\dagger}+q\,\gamma_{i}\otimes\gamma_{j}\
.$ (35)

$q$ denotes a probability.$U_{i,j}$ denotes an energy-conserving unitary:
$\left[{U_{i,j},H_{i}+H_{j}}\right]=0$.$\gamma_{i}$
$\left({\gamma_{j}}\right)$ denotes the thermal state of qubit $i$
$\left({j}\right)$, defined in 1.With a probability $q$, $\mathcal{E}$
replaces its input with a thermal state. Otherwise, $\mathcal{E}$ effects an
energy-conserving unitary.$\mathcal{E}$ can model an interaction between
qubits and a heat bath over short times, during which the bath partially
thermalizes the qubits.This interaction may be exploited to implement
operations that do not strictly conserve energy, i.e., that do not commute
with the total Hamiltonian.Subjecting $\gamma_{i}\otimes\gamma_{j}$ to any
operation 35 shows directly that the operation obeys the condition 34.Consider
any protocol $\mathcal{E}$ in $\mathcal{T}$ that has two properties: first,
$\mathcal{E}$ consists of $\leqslant r$ computational gates followed by reset
operations.Second, $\mathcal{E}$ satisfies
$F^{2}\bm{(}\mathcal{E}(\rho),\proj{0^{n}}\bm{)}\geqslant\eta$.What is the
optimal work cost $W_{r}^{*}$ of such a protocol?The following theorem bounds
$W_{r}^{*}$ in terms of the complexity relative entropy, generalizing 23 to
product Hamiltonians.

######  Theorem IV (Optimal work cost for product Hamiltonians).

The optimal work cost $W_{r}^{*}$ is quantified by the complexity relative
entropy as

$\displaystyle-\Dbase{\DSym}_{\mathrm{H},\,\mathcal{T}}^{{r},\,{\eta}}{\rho}{\Gamma}-\log\left({1/\eta}\right)\leqslant
W_{r}^{*}\leqslant-\Dbase{\DSym}_{\mathrm{H},\,\mathcal{T}}^{{r},\,{\eta}}{\rho}{\Gamma}\
.$ (36)

The subscript $\mathcal{T}$ signifies that the set $\mathsf{M}^{r}$ in 11 is
defined in terms of the gate set $\mathcal{G}=\mathcal{T}$.

The proof, provided in Appendix E, resembles the proof for degenerate
Hamiltonians.

##  IV Work costs of general state transformations

We now turn to our paper’s motivating problem.Consider a system that begins in
a state $\rho$ and then undergoes any evolution of complexity at most
$r\geqslant 0$.$\rho$ will transform into a possibly different state.Which
transformations appear possible, according to an observer who can distinguish
states using only some computational power $R\geqslant 0$?Alternatively, how
much work must one invest to effect an evolution whose complexity is
$\leqslant r$ and whose output the observer cannot distinguish from a given
state $\rho^{\prime}$?

##### Setting.

To formalize the questions above, we consider an $n$-qubit system initialized
in a state $\rho$. The state undergoes an evolution $\mathcal{E}$ composed of
primitive operations (II).$C(\mathcal{E})$ and $W(\mathcal{E})$ quantify the
complexity cost and work cost of $\mathcal{E}$, respectively.To establish
whether a transformation $\rho\to\rho^{\prime}$ appears to result from
$\mathcal{E}$, imagine a referee who must distinguish the output
$\mathcal{E}(\rho)$ from the reference $\rho^{\prime}$.The referee can effect
only operations of complexities $\leqslant R$.Using a measurement operator of
complexity $\leqslant R$, the referee performs a hypothesis test of the form
described in II.3, subject to the type I and type II error constraints
specified with $\eta\in(0,1]$ and $\delta\in(0,1]$, respectively.According to
the referee, $\rho\to\rho^{\prime}$ may result from $\mathcal{E}$ precisely if
there exists no hypothesis test by which the referee can correctly accept
$\mathcal{E}(\rho)$ with a probability $\geqslant\eta$ and incorrectly accept
$\rho^{\prime}$ with a probability $\leqslant\delta$.Equivalently, by II.3,
$\rho\to\rho^{\prime}$ may result from $\mathcal{E}$ precisely if

$\displaystyle\Dbase{\DSym}_{\mathrm{H}}^{{R},\,{\eta}}\left\\{{\mathcal{E}(\rho)}\right\\}{\rho^{\prime}}\leqslant-\log\left({\delta/\eta}\right)\
.$ (37)

Condition 37 can simplify, evoking the previous section’s fidelity condition,
if the referee lacks computational restrictions.Depending on the POVMs
performable, the referee could perform the optimal measurement for
distinguishing between $\rho$ and $\rho^{\prime}$.The measurement’s success
probability is given by the trace distance
$\frac{1}{2}\lVert{\rho-\rho^{\prime}}\rVert_{1}$, which is small when the
fidelity is large [97].Hence condition 37 effectively reduces to a constraint,
as in the previous section, on $F$.Let $\mathcal{E}$ denote any evolution that
transforms $\rho$ into any state $\mathcal{E}(\rho)$ indistinguishable from
$\rho^{\prime}$ by the referee.The minimum work cost of any such evolution is

$\mathcal{W}^{r,\,R,\,\eta,\,\delta}\left[{\rho\to\rho^{\prime}}\right]\coloneqq\\\
\inf\left\\{{W\left({\mathcal{E}}\right)\,:\;C\left({\mathcal{E}}\right)\leqslant
r\,,\;\Dbase{\DSym}_{\mathrm{H}}^{{R},\,{\eta}}\left\\{{\mathcal{E}(\rho)}\right\\}{\rho^{\prime}}\leqslant-\log\left({\delta/\eta}\right)}\right\\}\
.$ (38)

This quantity, in its general form, does not appear amenable to simple
analysis.In the following, we specialize to situations where the referee’s
computational power is extremely high or low.In these situations, we find
examples where one of the conditions in 38 is expected to be tractable, as is
needed to upper-bound the work cost.

##### Referee with extremely high computational power.

First, suppose that $R$ is extremely large.The first condition in 38 can be
tractable:under certain conditions (see Appendix J),
$\Dbase{\DSym}_{\mathrm{H}}^{{R},\,{\eta}}\left\\{{\mathcal{E}(\rho)}\right\\}{\rho^{\prime}}$
can approximate the hypothesis-testing relative entropy
$\DHyp[\eta]\left\\{{\mathcal{E}(\rho)}\right\\}{\rho^{\prime}}$ [defined in
6].The latter can be evaluated via a semidefinite program (SDP), in principle
[84].Hence one can, in principle, evaluate each side of condition 37, as is
necessary to calculate the work cost 38.(As a caveat, the SDP calculation’s
time and memory grow exponentially in $n$.)

##### Referee with extremely low computational power.

Now, suppose that $R$ is extremely small.The referee may have great difficulty
distinguishing the output $\mathcal{E}(\rho)$ from the reference
$\rho^{\prime}$.Consider the extreme case where $R=0$: the referee may perform
only the local projective measurements in 10.We can apply a general upper
bound: denote by $\sigma$ and $\tau$ any $n$-qubit states; and, by
$\sigma_{j}$ and $\tau_{j}$, the respective reduced states of qubit $j$.The
complexity relative entropy obeys

$\displaystyle\Dbase{\DSym}_{\mathrm{H}}^{{R=0},\,{\eta}}\left\\{{\sigma}\right\\}{\tau}\lesssim\sum_{j=1}^{n}\DHyp[\eta]\left\\{{\sigma_{j}}\right\\}{\tau_{j}}\
.$ (39)

The approximation hides error terms that vanish in the limit as $\eta\to
1$.Inequality 39 follows from D.2 in Appendix D.One can apply this inequality
to evaluate 37 and thereby certify that $\mathcal{E}(\rho)$ is
indistinguishable from $\rho^{\prime}$ to a referee who lacks computational
power and tolerates little error.

##### Simple transformation.

Suppose that the transformation $\mathscr{E}$ involves few primitive
operations: $r<O(n)$.Also, suppose that the system is 1D. The system’s
entanglement, as quantified in V.3, can change.$\mathscr{E}$ can change the
entanglement only by an amount proportional to $r$, by V.3.Furthermore, our
entanglement measure is related to the complexity entropy at small $r$ (see
V.3).Hence we expect the first condition in 38 to relax to a constraint on
entanglement, which we expect to be more tractable.

##  V Information-theoretic features of the complexity entropy

The complexity relative entropy 12 and the complexity entropy 14 are additions
to a large cast of information-theoretic entropy measures [96,
107].Intuitively, the complexity entropy quantifies a state’s apparent
randomness to an agent who can implement only limited-complexity measurement
effects.Unlike common entropies, the complexity entropy lacks unitary
invariance.Indeed, a computationally limited agent may need more work to erase
a state after it has evolved under a complex unitary (cf. examples in
III.1).In this section, we present the complexity entropy’s properties, as
well as its applications to information-theoretic tasks.Most generally, the
complexity (relative) entropy is defined for an abstract family
$\\{\mathsf{M}^{r}\\}$ of sets.Each $\mathsf{M}^{r}$ denotes the set of POVM
effects of complexities at most $r\geqslant 0$.This formalism generalizes the
above, $n$-qubit constructions to arbitrary discrete quantum systems.In
Appendix D, we present the general definition of the complexity (relative)
entropy and prove the properties stated below.Here, to achieve a simpler and
more concrete presentation, we focus on an $n$-qubit system and on the family
$\\{{\mathsf{M}^{r}}\\}$ defined by 11.For information-theoretic applications,
it is convenient to measure entropy in units of bits, rather than in nats $[1\
\text{bit}=\log(2)\ \text{nats}]$.In this section, we denote with an overbar
entropies expressed in units of bits; these entropies are related to their
counterparts by the factor $\log(2)$:

$\displaystyle\begin{split}\overline{H}(\rho)&=H(\rho)/\log(2)\ ,\\\
\Dbase{\overline{\DSym}}_{\mathrm{H}}^{\eta}{\rho}{\sigma}&=\DHyp[\eta]{\rho}{\sigma}/\log(2)\
,\\\
\Hfnbase{\overline{\HSym}}{\mathrm{H}}{\eta}\\{{-NoValue-}\\}(\rho)&=\Hfnbase{\HSym}{\mathrm{H}}{\eta}\\{{-NoValue-}\\}(\rho)/\log(2)\
,\\\
\Dbase{\overline{\DSym}}_{\mathrm{H}}^{{r},\,{\eta}}{\rho}{\sigma}&=\Dbase{\DSym}_{\mathrm{H}}^{{r},\,{\eta}}{\rho}{\sigma}/\log(2)\
,\;\;\text{etc.}\end{split}$ (40)

The factor $[\log(2)]^{-1}$ changes natural logarithms to base-2 logarithms in
the entropies’ definitions.For instance, the von Neumann entropy
$H(\rho)=-\tr\left({\rho\log\rho}\right)$, expressed in units of bits, is
$\overline{H}(\rho)=-\tr\left({\rho\log_{2}\rho}\right)$.

###  V.1 Overview of elementary properties

In this subsection, $\rho$ denotes any quantum state, and $\Gamma$ any
positive-semidefinite operator, defined on the $n$-qubit Hilbert space.Let
$r\geqslant 0$ and $\eta\in(0,1]$.The complexity relative entropy inherits
some properties from the hypothesis-testing relative entropy 6.For example,
$\Dbase{\overline{\DSym}}_{\mathrm{H}}^{{r},\,{\eta}}{\rho}{\Gamma}$, like
$\Dbase{\overline{\DSym}}_{\mathrm{H}}^{\eta}{\rho}{\Gamma}$, monotonically
decreases as $\eta$ increases.The greater an agent’s error intolerance (the
greater the $\eta$), the more mixed $\rho$ appears $[$the greater
$\Hfnbase{\HSym}{\mathrm{H}}{{r},\,{\eta}}\\{{-NoValue-}\\}(\rho)$ is$]$.The
complexity (relative) entropy also has properties that reflect its sensitivity
to state complexity.For example,
$\Dbase{\overline{\DSym}}_{\mathrm{H}}^{{r},\,{\eta}}{\rho}{\Gamma}$
monotonically increases as $r$ increases.The greater an agent’s computational
power (the greater the $r$), the less mixed $\rho$ appears $[$the less
$\Hfnbase{\HSym}{\mathrm{H}}{{r},\,{\eta}}\\{{-NoValue-}\\}(\rho)$ is$]$.These
monotonicity properties imply that $\rho$ is more distinguishable from
$\Gamma$ to an observer who has greater computational power and has a higher
tolerance for guessing $\Gamma$ when given $\rho$.Furthermore, the complexity
(relative) entropy has the same range as the hypothesis-testing (relative)
entropy:

$\displaystyle\Dbase{\overline{\DSym}}_{\mathrm{H}}^{{r},\,{\eta}}{\rho}{\Gamma}$
$\displaystyle\in\left[{-\log_{2}\bm{(}\tr(\Gamma)\bm{)}\,,\;-\log_{2}\left({\norm{\Gamma}}\right)}\right]\
,\;\;$
$\displaystyle\Hfnbase{\overline{\HSym}}{\mathrm{H}}{{r},\,{\eta}}\\{{-NoValue-}\\}(\rho)$
$\displaystyle\in[0\,,\;n]\ .$ (41a)

The complexity relative entropy, like standard relative entropies, enjoys a
scaling property in its second argument: for all $\lambda>0$,
$\Dbase{\overline{\DSym}}_{\mathrm{H}}^{{r},\,{\eta}}{\rho}{\lambda\Gamma}=\Dbase{\overline{\DSym}}_{\mathrm{H}}^{{r},\,{\eta}}{\rho}{\Gamma}-\log_{2}(\lambda)$.By
construction, the complexity (relative) entropy is not unitarily invariant.On
similar grounds, it does not satisfy a data-processing inequality.Indeed,
unitary evolution is a special case of data processing. Furthermore, a unitary
can increase or decrease a pure state’s complexity.Therefore, a unitary can
increase or decrease a state’s complexity entropy.Nevertheless, the complexity
(relative) entropy monotonically increases (decreases) under partial
traces.Tracing out $k$ qubits from $\rho$ yields

$\displaystyle\Dbase{\overline{\DSym}}_{\mathrm{H}}^{{r},\,{\eta}}{\rho}{\Gamma}$
$\displaystyle\geqslant\Dbase{\overline{\DSym}}_{\mathrm{H}}^{{r},\,{\eta}}\big{\\{}{\tr_{k}({\rho})}\big{\\}}{\tr_{k}({\Gamma})}\
,$ (41apa)
$\displaystyle\Hfnbase{\overline{\HSym}}{\mathrm{H}}{{r},\,{\eta}}\\{{-NoValue-}\\}(\rho)$
$\displaystyle\leqslant\Hfnbase{\overline{\HSym}}{\mathrm{H}}{{r},\,{\eta}}\\{{\big{}}\\}(\tr_{k}({\rho}))+k\
.$ (41apb)

The complexity (relative) entropy is greater (less) than or equal to the
hypothesis-testing (relative) entropy:
$\Hfnbase{\overline{\HSym}}{\mathrm{H}}{{r},\,{\eta}}\\{{-NoValue-}\\}(\rho)\geqslant\Hfnbase{\overline{\HSym}}{\mathrm{H}}{\eta}\\{{-NoValue-}\\}(\rho)$
and
$\Dbase{\overline{\DSym}}_{\mathrm{H}}^{{r},\,{\eta}}{\rho}{\Gamma}\leqslant\Dbase{\overline{\DSym}}_{\mathrm{H}}^{\eta}{\rho}{\Gamma}$.In
the large-$r$ limit, one would expect the complexity (relative) entropy to
converge to the hypothesis-testing (relative) entropy.Yet, an exact
convergence might not occur: some POVM effects might not be well-approximated
by any effect in $\mathsf{M}^{r}$.This is due to our choice of
$\mathsf{M}^{r}$ and to the lack of ancillas in our computational
model.Nevertheless, we show in Appendix J that, under certain conditions, the
complexity (relative) entropy approximates the hypothesis-testing (relative)
entropy up to constant error terms.Alternatively, one might hope to ensure
convergence to the hypothesis-testing (relative) entropy by allowing the use
of one ancillary qubit in implementations of measurement effects, as
introduced in Ref. [Brandao_21_Models].

###  V.2 Bounds from well-known complexity measures

To what extent does the complexity entropy
$\Hfnbase{\overline{\HSym}}{\mathrm{H}}{{r},\,{\eta}}\\{{-NoValue-}\\}(\psi)$
quantify the complexity of a pure state $\psi\equiv\proj{\psi}$?We bound the
complexity entropy in terms of two complexity measures: the _strong
complexity_ of Ref. [17] and the _approximate circuit complexity_ (B.2 in
Appendix B).We describe the bounds qualitatively here, deferring rigorous
statements, and proofs thereof, to D.4.The complexity entropy reflects
approximate circuit complexity as follows.Assume that the set $\mathcal{G}$,
used in the definition 11, contains only unitary gates.Consider beginning with
some reference state, then applying gates in $\mathcal{G}$ to prepare any
state $\epsilon$-close to $\ket{\psi}$ in trace distance.Let
$C^{\epsilon}\left({\ket\psi}\right)$ denote the least number of gates in any
such process.$C^{\epsilon}\left({\ket\psi}\right)$ is the
$\epsilon$-approximate circuit complexity of $\ket\psi$.For all $r\geqslant
C^{\epsilon}\left({\ket\psi}\right)$,
$\Hfnbase{\overline{\HSym}}{\mathrm{H}}{{r},\,{1-\epsilon^{2}}}\\{{-NoValue-}\\}(\psi)\approx
0$.Furthermore,
$\Hfnbase{\overline{\HSym}}{\mathrm{H}}{{r},\,{1-\epsilon^{2}}}\\{{-NoValue-}\\}(\psi)\not\approx
0$ for all $r<C^{2\epsilon}\left({\ket\psi}\right)$ (see D.4).The complexity
relative entropy also obeys an upper bound involving the _strong complexity_
of Ref. [17] (see D.4).

###  V.3 Bounds from entanglement

We lower-bound an $n$-qubit state’s complexity entropy using a measure of the
state’s entanglement.Consider a 1D chain $S$ of $n\geqslant 2$ qubits:
$S=S_{1}S_{2}\ldots S_{n}$.Let $\rho$ denote any state of $S$.We define the
following entanglement measure:

$\displaystyle
E(\rho)\coloneqq\frac{1}{n-1}\sum_{j=1}^{n-1}\II[\rho]{S_{1}\ldots
S_{j}}{S_{j+1}\ldots S_{n}}\ .$ (41aq)

$\II[\rho]{A}{B}\coloneqq\HH[\rho]{A}+\HH[\rho]{B}-\HH[\rho]{AB}$ denotes the
quantum mutual information defined in terms of the von Neumann entropy
$\HH[\rho]{X}\coloneqq-\tr\left({\rho\log\rho}\right)$.The mutual information
quantifies all correlations—classical and quantum—including correlations due
to entanglement.Assume that the operations $\mathcal{G}$ in 11 are unitary
gates that can act nontrivially only on two neighboring qubits (the gates are
_geometrically local_).We upper-bound the change in $E(\rho)$ under one gate
in $\mathcal{G}$.

######  Proposition V (Change in $E(\rho)$ under a two-qubit unitary).

Let $\rho$ denote any quantum state of a 1D chain $S$ of $n\geqslant 2$
qubits.Let $U$ denote any unitary that can act nontrivially only on two
neighboring qubits in $S$.Then

$\displaystyle\abs\left\\{{E\left({U\rho
U^{\dagger}}\right)-E\left({\rho}\right)}\right\\}\leqslant\frac{8\log(2)}{n-1}\
.$ (41ar)

To prove V.3, one observes that $U$ can alter only one mutual information in
41aq—the mutual information associated with (the bipartition that separates)
the qubits on which $U$ can act nontrivially.In Appendix G, we generalize 41ar
to account for the _potential entangling power_ [27] of $\mathcal{G}$.This
power quantifies the entanglement generable by one gate in $\mathcal{G}$.By
repeatedly applying 41ar, we upper-bound the change in $E(\rho)$ under
$\leqslant r$ gates in $\mathcal{G}$.We then lower-bound the complexity
entropy $\Hfnbase{\HSym}{\mathrm{H}}{{r},\,{\eta}}\\{{-NoValue-}\\}(\rho)$ in
terms of $E(\rho)$ as

$\displaystyle\Hfnbase{\HSym}{\mathrm{H}}{{r},\,{\eta}}\\{{-NoValue-}\\}(\rho)\geqslant\frac{1}{\eta}\left[{E(\rho)-r\,\frac{8\log(2)}{n-1}+H(\rho)+\text{error
terms}}\right]\ .$ (41as)

The error terms depend on $\eta$ and $n$ and vanish in the limit as $\eta\to
1$.See Appendix G for details.In Appendix H, we also investigate similar
bounds that arise from natural dynamics under local Hamiltonians.This setting
is particularly relevant to locally interacting systems.

###  V.4 Evolution of the complexity entropy under random circuits

Consider an $n$-qubit circuit generated with gates sampled Haar-randomly from
all two-qubit gates.The circuit effects a unitary.As the circuit depth grows,
the unitary’s complexity grows, until saturating at a value exponential in
$n$.The complexity growth is at least sublinear [17] and, for some nonrobust
complexity measures [18, 19, 108], is linear.We ask how well the complexity
entropy tracks the complexity of a pure state evolving under a random
circuit.We consider _brickwork circuits_ [Haferkamp_21_Linear, 55].A brickwork
circuit consists of staggered layers of nearest-neighbor two-qubit gates.The
following proposition reveals the behaviors of the complexity entropy at a
fixed complexity scale $r$: under short circuits, the complexity entropy
vanishes.Around a circuit depth $t$ commensurate with $r$, the complexity
entropy transitions to a near-maximal value (Fig. 3).We bound the interval of
$t$-values in which the transition happens to values satisfying $r\lesssim
t\lesssim r^{5+o(1)}$.Furthermore, we conjecture that the complexity entropy
reaches a near-maximal value by $t\gtrsim r$.We prove the proposition using a
strategy borrowed from Ref. [17], which contains a similar proposition about
the strong complexity.

######  Proposition VI (Transition of the complexity entropy under random
circuits).

Consider a depth-$t$, random $n$-qubit circuit $V$ whose gates act in a
brickwork layout.Let $\ket\psi\coloneqq V\ket{0^{n}}$, $r\geqslant 0$, and
$\eta\in(0,1]$.If the circuit is short, such that $t\leqslant O(r)$, then

$\displaystyle\Hfnbase{\overline{\HSym}}{\mathrm{H}}{{r},\,{\eta}}\\{{*}\\}(\proj{\psi})=0\
.$ (41at)

If the circuit is long, such that
$t\geqslant\Omega\big{(}{r^{5+o(1)}}\big{)}$, then

$\displaystyle\Hfnbase{\overline{\HSym}}{\mathrm{H}}{{r},\,{\eta}}\\{{*}\\}(\proj{\psi})\geqslant
n-\log_{2}\left({2/\eta}\right)\ ,$ (41au)

except with a probability $e^{-\Omega(n)}$ over the sampling of $V$.

The proof of 41at is immediate: one can use the circuit $V$ to construct a
candidate $Q=V^{\dagger}\proj{0^{n}}V\in\mathsf{M}^{r}$ for the optimization
12 that defines
$\Hfnbase{\overline{\HSym}}{\mathrm{H}}{{r},\,{\eta}}\\{{*}\\}(\proj{\psi})$.The
proof of 41au is presented in Appendix F.

###  V.5 Data compression under complexity limitations

The complexity entropy naturally quantifies the optimal efficiency of data
compression under computational limitations.Let $\rho$ denote any $n$-qubit
state; $m$, a number of qubits; and $\epsilon\in[0,1]$, an error parameter.To
perform _data compression under complexity limitations_ , one seeks a unitary
$U$, composed from $\leqslant r$ two-qubit gates, such that some subset
$\mathcal{W}\subset\\{{1,2,\ldots,n}\\}$ of $\abs{\mathcal{W}}=m$ qubits
satisfies

$\displaystyle F^{2}\bm{(}\tr_{\mathcal{W}}(U\rho
U^{\dagger}),\proj{0^{n-m}}\bm{)}\geqslant 1-\epsilon\ .$ (41av)

One _compresses_ $\rho$ onto the qubits of $\mathcal{W}$, with an accuracy
$1-\epsilon$ and using $\leqslant r$ gates.For background, consider an agent
who lacks complexity limitations (who operates in the limit as
$r\to\infty$).The hypothesis-testing entropy quantifies the optimal one-shot
data-compression size of $\rho$ [84]

$\displaystyle
m_{\mathrm{optimal}}\approx\Hfnbase{\overline{\HSym}}{\mathrm{H}}{1-\epsilon}\\{{-NoValue-}\\}(\rho)\
.$ (41aw)

Every protocol for data compression under complexity limitations can be mapped
to a “simple” protocol for erasure.The erasure protocol consists of
computational gates followed by reset operations [see Fig. 4(b)].The least
number $m_{\mathrm{optimal},r}$ of qubits onto which $\rho$ can be compressed,
with an accuracy $1-\epsilon$ and using $\leqslant r$ gates, satisfies

$\displaystyle\Hfnbase{\overline{\HSym}}{\mathrm{H}}{{r},\,{1-\epsilon}}\\{{-NoValue-}\\}(\rho)-\log_{2}\left({1/\left[{1-\epsilon}\right]}\right)$
$\displaystyle\leqslant
m_{\mathrm{optimal},r}\leqslant\Hfnbase{\overline{\HSym}}{\mathrm{H}}{{r},\,{1-\epsilon}}\\{{-NoValue-}\\}(\rho)\
.$ (41ax)

The complexity entropy
$\Hfnbase{\overline{\HSym}}{\mathrm{H}}{{r},\,{1-\epsilon}}\\{{-NoValue-}\\}(\rho)$
is defined with respect to the set $\mathcal{G}$ of all two-qubit gates.In
Appendix K, we prove 41ax.

###  V.6 Complexity conditional entropy

In information theory, conditional-entropy measures quantify the randomness of
a system $A$, as apparent to an observer given access to a system $B$ that may
share correlations with $A$.The conditional entropy appears throughout
classical and quantum information theory.Applications include communication
[109, 64, 65], thermodynamic erasure with side information [62], and quantum
entropic uncertainty relations [110].Consider defining a conditional entropy
$\Hbase{\overline{\HSym}}{*}[\rho]{A}[B]$ of a state $\rho_{AB}$.A standard
technique is to identify an appropriate relative entropy
$\Dbase{\overline{\DSym}}_{*}{}{}$ and to set
$\Hbase{\overline{\HSym}}{*}[\rho]{A}[B]\coloneqq-\Dbase{\overline{\DSym}}_{*}{\rho_{AB}}{\mathds{1}_{A}\otimes\rho_{B}}$.Here,
$\rho_{B}\coloneqq\tr_{A}({\rho_{AB}})$ is the reduced state of $\rho$ on $B$
[96].$\Hbase{\overline{\HSym}}{*}[\rho]{A}[B]$ reflects one’s ability to
distinguish $\rho_{AB}$ from a state that provides the same knowledge about
$B$ ($B$ is in state $\rho_{B}$) but minimal knowledge about $A$ ($A$ is
maximally mixed and uncorrelated with $B$).In this interpretation,
$\Dbase{\overline{\DSym}}_{*}{}{}$ quantifies the notion of
distinguishability.Conditional entropies defined as above include the
conditional min- and max-entropies and the conditional Rényi-$\alpha$
entropies [96].We employ the complexity relative entropy 12 to define the
complexity conditional entropy.Denote any arbitrary bipartite state by
$\rho_{AB}$.For all $r\geqslant 0$ and $\eta\in(0,1]$, the _complexity
conditional entropy_ of $\rho_{AB}$ is

$\displaystyle\Hbase{\overline{\HSym}}{\mathrm{H}}[\rho][{{r},\,{\eta}}]{A}[B]\coloneqq-\Dbase{\overline{\DSym}}_{\mathrm{H}}^{{r},\,{\eta}}{\rho_{AB}}{\mathds{1}_{A}\otimes\rho_{B}}\
.$ (41ay)

We prove the following properties of the complexity conditional entropy.It,
like the complexity entropy, decreases monotonically as $r$ increases and
increases monotonically as $\eta$ increases.Furthermore, the complexity
conditional entropy is bounded in terms of the Hilbert-space dimensionality of
$A$, $d_{A}$, as

$\displaystyle-\log_{2}(d_{A})\leqslant\Hbase{\overline{\HSym}}{\mathrm{H}}[\rho][{{r},\,{\eta}}]{A}[B]\leqslant\log_{2}(d_{A})\
.$ (41az)

The complexity conditional entropy also exhibits strong subadditivity: for
every tripartite state $\rho_{ABC}$,

$\displaystyle\Hbase{\overline{\HSym}}{\mathrm{H}}[\rho][{{r},\,{\eta}}]{A}[BC]\leqslant\Hbase{\overline{\HSym}}{\mathrm{H}}[\rho][{{r},\,{\eta}}]{A}[B]\
.$ (41ba)

The strong subadditivity follows from the complexity relative entropy’s
monotonicity under partial traces.We prove 41az and 41ba in D.6.The complexity
conditional entropy has operational significance in a variant of the
information-theoretic task of _decoupling_ , we show next.

###  V.7 Decoupling from a reference system

First, we define the decoupling of a system $A$ from a system $R$.Define
$d_{A}$ as the Hilbert-space dimensionality of $A$ and
$\pi_{A}\coloneqq\mathds{1}_{A}/d_{A}$ as a maximally mixed state.We say that
$A$ is maximally mixed and decoupled from $R$ if the joint state $\rho_{AR}$
is the product $\pi_{A}\otimes\rho_{R}$ [111]._Decoupling $A$ from $R$_ means
transforming a general $\rho_{AR}$ into a state $\rho^{\prime}_{AR}$ close to
a state in which $A$ is maximally mixed and decoupled from $R$ [64,
65].Decoupling is an information-theoretic primitive applied in randomness
extraction [80, 112], quantum communication [64], and thermodynamic erasure
with side information [62].The standard information-theoretic task of
decoupling can be defined as follows.Alice possesses an $n$-qubit system $A$
that might be correlated with a reference $R$.The joint system begins in a
state $\rho_{AR}$.First, Alice applies to $A$ a unitary $U_{0}$, preparing
$\left({U_{0}\otimes\mathds{1}_{R}}\right)\rho_{AR}\left({U_{0}\otimes\mathds{1}_{R}}\right)^{\dagger}\eqqcolon\rho_{AR}^{\prime}$.Then,
Alice discards a subsystem $A_{1}$ formed from $k\geqslant 0$ qubits of $A$. A
subsystem $A_{2}$, formed from $n-k$ qubits, remains.Alice sends $A_{2}$ to a
referee, who possesses $R$.The referee attempts to distinguish the reduced
state $\rho^{\prime}_{A_{2}R}$ from $\pi_{A_{2}}\otimes\rho_{R}$.Alice
succeeds if the referee cannot distinguish the states to within some error
tolerance.Alice can ensure that $\rho_{A_{2}R}^{\prime}$ approximates
$\rho_{A_{2}}^{\prime}\otimes\rho_{R}$ if [65]

$\displaystyle
k\gtrsim\frac{1}{2}\left[{n-\Hbase{\overline{\HSym}}{\mathrm{min}}[\rho][\epsilon]{A}[R]}\right]\
.$ (41bb)

$\epsilon>0$ denotes a tolerance
parameter.$\Hbase{\overline{\HSym}}{\mathrm{min}}[\rho][\epsilon]{A}[R]$
denotes the _smooth conditional min-entropy_ of $\rho$ [65, 96].Here, we
introduce a complexity-constrained variant of decoupling.Assume that $R$
consists of qubits.Assume further that both Alice and the referee can
implement two-qubit gates that form a set universal for quantum computation.We
define our decoupling task as the task above, except we impose two complexity
constraints.First, we constrain Alice’s computational power, requiring that
$U_{0}$ be implementable with at most $r_{0}\geqslant 0$ gates.Second, we
constrain the referee’s computational power.Using at most $r_{1}\geqslant 0$
gates, the referee performs a hypothesis test of the form described in II.3,
subject to type I and type II error constraints specified with $\eta\in(0,1]$
and $\delta\in(0,1]$, respectively.Alice succeeds in our decoupling task if
there exists no hypothesis test by which the referee can correctly accept
$\rho_{A_{2}R}^{\prime}$ with a probability $\geqslant\eta$ and incorrectly
accept $\pi_{A_{2}}\otimes\rho_{R}$ with a probability
$\leqslant\delta$.Equivalently, by II.3, Alice is successful if

$\displaystyle\Dbase{\overline{\DSym}}_{\mathrm{H}}^{{r_{1}},\,{\eta}}\left\\{{\rho^{\prime}_{A_{2}R}}\right\\}{\pi_{A_{2}}\otimes\rho_{R}}\leqslant-\log_{2}\left({\delta/\eta}\right)\
.$ (41bc)

In terms of the complexity conditional entropy
$\Hbase{\overline{\HSym}}{\mathrm{H}}[\rho^{\prime}][{{r_{1}},\,{\eta}}]{A_{2}}[R]$,
the condition 41bc is

$\displaystyle
n-k-\Hbase{\overline{\HSym}}{\mathrm{H}}[\rho^{\prime}][{{r_{1}},\,{\eta}}]{A_{2}}[R]\leqslant-\log_{2}\left({\delta/\eta}\right)\
.$ (41bd)

Thus, Alice succeeds if
$\Hbase{\overline{\HSym}}{\mathrm{H}}[\rho^{\prime}][{{r_{1}},\,{\eta}}]{A_{2}}[R]$
is sufficiently close to its maximum value, $n-k$.

Fig. 5: Decoupling with respect to a computationally bounded referee.Alice’s
system $A$ might be correlated with a reference system $R$.Alice applies to
$A$ a unitary $U_{0}$, then discards $k$ qubits of $A$.Alice retains an
$(n-k)$-qubit system $A_{2}$.Alice succeeds in our decoupling task if a
referee cannot, using a circuit of $\leqslant r_{1}$ gates, distinguish the
final state of $A_{2}R$ from $\pi_{A_{2}}\otimes\rho_{R}$.The success
condition depends on the conditional complexity entropy
$\Hbase{\overline{\HSym}}{\mathrm{H}}[\rho^{\prime}][{{r_{1}},\,{\eta}}]{A_{2}}[R]$.Conjecturing
a property of that entropy, we bound, in terms of
$\Hbase{\overline{\HSym}}{\mathrm{H}}[\rho][{{r},\,{\eta}}]{A}[R]$, the number
of qubits that Alice can decouple from $R$.Our bound mirrors the bound 41bb,
which holds in the absence of complexity constraints.

Before quantifying Alice’s decoupling capabilities, we posit two
expectations.First, we do not expect Alice’s complexity constraint to
meaningfully change the number of qubits that she can decouple from $R$
(unless $r_{0}$ is very small).Indeed, one may achieve near-optimal decoupling
by choosing for $U_{0}$ to be a random circuit of only
$O\bm{(}n\log^{2}(n)\bm{)}$ gates, in an all-to-all-coupling model [113].In
contrast, we expect the referee’s complexity constraint to substantially
increase the number of qubits that Alice can decouple from $R$, by enabling
Alice to succeed with strategies that would fail at standard decoupling.For
instance, consider a highly complex, maximally entangled state $\rho_{AR}$.In
the standard scenario, Alice cannot decouple any qubits from $R$.[We can check
this claim by substituting
$\Hbase{\overline{\HSym}}{\mathrm{min}}[\rho][\epsilon]{A}[R]=-n$ in
41bb.]Now, suppose that the referee is computationally limited.Alice’s system
is apparently decoupled from $R$ already: a complex state can be
indistinguishable from a maximally mixed state, so the referee cannot
distinguish $\rho_{AB}$ from a decoupled state.More precisely, suppose that
$\rho_{AR}$ is maximally entangled, that $\eta=1$, and that the referee has
unlimited computational power.Alice cannot decouple $n-k$ qubits from $R$, if
$\delta\leqslant 2^{-2(n-k)}$.$[$If Alice discards $k$ qubits, then
$\rho_{A_{2}R}^{\prime}$ is a uniform mixture of $2^{k}$ pure states.In an
optimal strategy, the referee transforms $\rho_{A_{2}R}^{\prime}$ into
$\rho_{A_{2}R}^{\prime\prime}\coloneqq\proj{0^{2(n-k)}}\otimes\left({\mathds{1}_{2}^{\otimes
k}/2^{k}}\right)$, before implementing the measurement effect

$Q\coloneqq\proj{0^{2(n-k)}}\otimes\mathds{1}_{2}^{\otimes k}\ .$ (41be)

Consequently, the referee can distinguish $\rho_{A_{2}R}^{\prime}$ from
$\pi_{A_{2}}\otimes\rho_{R}=\pi_{A_{2}R}$:
$\Dbase{\overline{\DSym}}_{\mathrm{H}}^{{r_{1}},\,{\eta}}{\rho^{\prime}_{A_{2}R}}{\pi_{A_{2}}\otimes\rho_{R}}=-\log_{2}\bm{(}\tr({Q\pi_{A_{2}R}})/\tr({Q\rho_{A_{2}R}^{\prime\prime}})\bm{)}=2(n-k)\leqslant-\log_{2}\left({\delta/\eta}\right)$.$]$Now,
however, suppose that the referee’s computational power is substantially
limited and that $\rho_{AR}$ is highly complex.Alice may be able to decouple
$n-k$ (or more) qubits even if $\delta\leqslant 2^{-2(n-k)}$: the referee may
require more computational power to perform a unitary necessary for
distinguishing $\rho^{\prime}_{A_{2}R}$ from $\pi_{A_{2}}\otimes\rho_{R}$.How
many qubits $k$ must Alice discard to convince the referee that a maximally
mixed, decoupled state was prepared?We present a bound that generalizes 41bb
to our decoupling task.The bound holds if one assumes that the complexity
conditional entropy obeys an inequality reminiscent of the Rényi-entropy chain
rule [114, 115].

######  Conjecture VII (Chain rule for the complexity conditional entropy).

Let $\rho_{ABR}$ denote a quantum state of systems $A$, $B$, and $R$ of
$n_{A}$, $n_{B}$, and $n_{R}$ qubits.Let $r\geqslant 0$ and $\eta\in(0,1]$.We
conjecture that

$\displaystyle\Hbase{\overline{\HSym}}{\mathrm{H}}[\rho][{{r},\,{\eta}}]{B}[R]\leqslant\Hbase{\overline{\HSym}}{\mathrm{H}}[\rho][{{r},\,{\eta}}]{AB}[R]+n_{A}\
.$ (41bf)

In words, introducing a system $A$ can decrease the complexity conditional
entropy by, at most, the size $n_{A}$ of $A$.The von Neumann conditional
entropy $\Hbase{\overline{\HSym}}{}{B}[R]$ obeys an analogous bound, due to a
chain rule and the lower bound $\Hbase{\overline{\HSym}}{}{A}[BR]\geqslant-
n_{A}$:
$\Hbase{\overline{\HSym}}{}{B}[R]=\Hbase{\overline{\HSym}}{}{AB}[R]-\Hbase{\overline{\HSym}}{}{A}[BR]\leqslant\Hbase{\overline{\HSym}}{}{AB}[R]+n_{A}$.This
$\Hbase{\overline{\HSym}}{}{B}[R]$ bound reflects how introducing $A$ can
resolve only as much randomness as $A$ can store.Indeed, the bound saturates
whenever $A$ is maximally entangled with $B$ ($R$).In such a case, $B$ and $R$
are uncorrelated, and $A$ purifies a maximally mixed state of $B$ ($R$). Hence
$A$ resolves $n_{A}$ maximally mixed qubits’ randomness.Similar bounds follow
from chain rules for Rényi entropies [114, 115].Using V.7, we prove a bound on
the number of qubits that Alice can decouple from $R$.

######  Theorem VIII (Upper bound on the number of qubits that Alice can
decouple).

Consider the complexity-restricted decoupling described above and depicted in
Fig. 5.Suppose $r_{1}\geqslant r_{0}$.Assume V.7.Under the condition 41bc (if
Alice is successful),

$\displaystyle
k\geqslant\frac{1}{2}\left[{n-\Hbase{\overline{\HSym}}{\mathrm{H}}[\rho][{{r_{1}-r_{0}},\,{\eta}}]{A}[R]+\log_{2}\left({\delta/\eta}\right)}\right]\
.$ (41bg)

We prove V.7 in Appendix L.The bound 41bg mirrors the bound 41bb, which
governs decoupling without complexity restrictions.Indeed, if $\eta\approx 0$,
the conditional hypothesis-testing entropy approximates the smooth conditional
min-entropy [84].As such, one can interpret the conditional complexity
entropy, when $\eta\approx 0$, as a _complexity-aware version of the
conditional min-entropy_.The general achievability of the bound 41bg is
unknown.A standard technique for proving standard decoupling’s achievability
involves the trace distance between a protocol’s output and a decoupled target
[64, 116, 65].One cannot readily extend this technique to V.7: the trace
distance is expressible as an optimization over all POVM effects but not over
complexity-limited effects.V.7 appears to preclude a kind of pseudorandom
quantum state that we call a _pseudomixed state_.Let $A$ and $B$ denote
systems of $n_{A}$ and $n_{B}$ qubits, respectively.Let $\ket\chi_{AB}$ denote
a pure state of $AB$.Let $r\geqslant 0$ and $\eta\in(0,1]$.$\ket\chi_{AB}$ is
an _efficiently preparable pseudomixed state_ on $B$ if the complexity entropy
of $\ket\chi$ is low,
$\Hfnbase{\overline{\HSym}}{\mathrm{H}}{{r},\,{\eta}}\\{{-NoValue-}\\}(\proj\chi)\approx
0$, while the complexity entropy of the reduced state
$\chi_{B}\coloneqq\tr_{A}\left({\proj\chi}\right)$ is high:

$\displaystyle\Hfnbase{\overline{\HSym}}{\mathrm{H}}{{r},\,{\eta}}\\{{-NoValue-}\\}(\chi_{B})\geqslant\Omega\bm{(}\exp(n_{A})\bm{)}\
.$ (41bh)

In other words, $B$ appears exponentially more mixed without the purifying
$A$.The condition 41bh directly contradicts the conjecture 41bf.Therefore, any
efficiently preparable pseudomixed state would disprove V.7.We can therefore
interpret V.7 as a _no-efficient-pseudomixedness conjecture_.A naïve approach
to constructing a pseudomixed state from pseudorandom states [117, 118] may
fail.The approach begins with a seed: a short, random bit string $\kappa$.The
construction efficiently produces a state $\ket{\phi_{\kappa}}$ that has the
following property: no efficient quantum algorithm can distinguish $\poly(n)$
copies of $\ket{\phi_{\kappa}}$ from the same number of copies of a Haar-
random state.Consider an $n$-qubit system formed from two subsystems: an
$O\bm{(}\log(n)\bm{)}$-qubit subsystem $A$ and an $O(n)$-subsystem $B$.Suppose
that

$\ket\psi_{AB}\coloneqq\sum_{\kappa}\ket{\kappa}_{A}\otimes\ket{\phi_{\kappa}}_{B}$
(41bi)

can be generated from $\ket{0^{n}}$ with at most $r_{\mathrm{gen}}\geqslant 0$
gates.$($One can generate $\ket\psi_{AB}$ by first preparing $A$ in
$\sum_{\kappa}\ket{\kappa}_{A}$, by applying Hadamard gates.Then, one
implements a controlled unitary $\sum_{\kappa}\proj{\kappa}_{A}\otimes
U_{\kappa}$.$U_{\kappa}$ denotes a unitary that prepares
$\ket{\phi_{\kappa}}$.$)$For all $\eta$,
$\Hfnbase{\overline{\HSym}}{\mathrm{H}}{{r_{\mathrm{gen}}},\,{\eta}}\\{{-NoValue-}\\}(\proj\psi)=0$.Denote
by $\psi_{B}\coloneqq\tr_{A}(\ketbra{\psi}{\psi})$ the reduced state of $B$.By
discarding $A$, one forgets the seed $\kappa$ used to construct the
pseudorandom state $\ket{\phi_{\kappa}}_{B}$.Therefore, no efficient algorithm
can distinguish $\psi_{B}$ from a Haar-random state.Nevertheless, $\psi_{B}$
may have a low complexity entropy, so $\ket\psi$ may not constitute a
counterexample to V.7.$\psi_{B}$ may have pseudorandomness properties because
a preparation circuit is hard to find, rather than because every preparation
circuit is large.

##  VI Discussion

Our framework highlights quantum complexity in thermodynamics.Thermodynamics
is operational: it concerns how efficiently an agent, given certain resources,
can accomplish certain tasks.We incorporate into the theory complexity
restrictions on (i) the agent’s operations and (ii) the evaluation of the
agent’s output.This “agent” could be human, could consist of a system’s
natural dynamics, etc.Our framework introduces a new role for time in
thermodynamics: a complex process requires a long time.Conventional
thermodynamics distinguishes only what is possible and impossible.When
augmented with complexity, thermodynamics dictates what is practical and
impractical.A spin glass illustrates the need to incorporate complexity
restrictions into thermodynamics: according to the conventional thermodynamic
laws, a spin glass can cool to low-temperature states.However, this cooling
process would require a very long time, or a highly complex process.We
illustrated the interplay between complexity and conventional thermodynamics
through Landauer erasure.Consider aiming to erase a highly complex pure
state.One could “uncompute” the state, paying in complexity.Alternatively, one
could erase every qubit, paying work.More generally, consider resetting an
arbitrary state $\rho$ with a success probability $\eta$.The complexity
entropy $\Hfnbase{\HSym}{\mathrm{H}}{{r},\,{\eta}}\\{{-NoValue-}\\}(\rho)$
quantifies the trade-off between the complexity and work costs.Landauer
erasure is one of many thermodynamic and information-processing tasks.We
analyzed data compression and decoupling, as well.Many tasks merit analysis in
the presence of complexity constraints.We expect complexity-restricted
entropies to quantify these tasks’ optimal efficiencies.Our entropies quantify
how mixed a state appears to a computationally limited agent.For instance,
even a pure state can have a high complexity entropy, if uncomputable by an
agent.Hence the complexity entropy quantifies a variation on
pseudorandomness—more specifically, pseudomixedness: randomness apparent in
determinstic phenomena, due to the observer’s computational limitations.Unlike
the standard hypothesis-testing entropy, the complexity entropy cannot be
approximated via convex optimization.We expect that computing the complexity
entropy is typically hard, given strong evidence that computing the state
complexity is hard [119, 120].Yet it might be possible to derive more-
tractable bounds for the complexity entropy in specific settings.Examples
include low-complexity regimes as well as settings featuring random
dynamics.We derived such a bound for pure states evolving under random
circuits (V.4).Other measures have been defined to quantify complexity or
apparent randomness: the computational min-entropy [121], the coarse-grained
entropy [122], the observational entropy [123], the logical depth [124], and
the quantum Kolmogorov complexity [125, 52].These measures reflect different
approaches to quantifying complexity, as illustrated in the
introduction.Rigorous comparisons between these quantities and the complexity
entropies merit future work.The main text illustrates the complexity
entropies’ properties and usefulness; but generalizations are possible, and
many are provided in Appendix D.For example, systems can be generalized beyond
qubits to qudits.We expect extensions to continuous-variable systems to be
achievable.Also, the complexity measure used can be replaced, as with
Nielsen’s complexity [126, Nielsen_06_Quantum, 128, 129].One could even
replace $r$ with a matrix-product-state bond dimension—anything that
constrains the POVM effects implementable.One need only specify those POVM
effects to construct general complexity entropies.Another opportunity for
future research is to literally analyze—break apart—our reset and extract
operations.We have presented these operations as the basic units of a
computation.Yet each operation may consist of multiple steps, entailing extra
costs.To incorporate these costs into our proofs, one could apply results from
Ref. [46].Furthermore, we attributed to the reset the ideal work cost of
$k_{\rm B}T\ln(2)$.Any realistic reset will cost more work.Such extra costs
can be absorbed straightforwardly into our assumptions.Complexity was recently
incorporated into thermodynamics alternatively, in a resource theory [30].In
the resource theory of uncomplexity, an agent can perform arbitrarily many
free operations.Each operation is slightly noisy, and the agent will have a
natural noise tolerance.Hence the agent will naturally limit the number of
operations they perform.In the present paper, the agent’s complexity
restriction is a hard, external constraint.Just as complexity has recently
emerged in resource theories, pseudorandomness has emerged in studies of
quantum gravity [130, 24, 131].We therefore anticipate the complexity
entropy’s utility in understanding black holes in the context of the AdS/CFT
correspondence, uniting tools of quantum information theory, high-energy
physics, and statistical physics.

###### Acknowledgements.

The authors thank Matthew Coudron, Richard Kueng, Lorenzo Leone, Yi-Kai Liu,
Carl Miller, Ralph Silva, and Twesh Upadhyaya for valuable discussions.This
research has been supported by the National Institute of Standards and
Technology and the Joint Center for Quantum Information and Computer Science
under NIST grant 70NANB21H055_0, as well as by the Ford Foundation and by the
National Science Foundation (QLCI grant OMA-2120757).A. M. thanks Freie
Universität Berlin for its hospitality.The Berlin team has been funded by the
DFG (FOR 2724 and CRC 183), the FQXi, and theERC (DebuQC).J. H. was funded by
the Harvard Quantum Initiative.

## APPENDICES

##  Appendix A Preliminaries, notation, and useful lemmas

Throughout these appendices, we use the following definitions and
conventions.We denote the set of non-negative reals by
$\mathbb{R}_{+}\coloneqq\\{{x\in\mathbb{R}:x\geqslant 0}\\}$.We consider a
system $S$ equipped with a Hilbert space $\mathscr{H}_{S}$ of a finite
dimensionality $d_{S}$.For any system $R$ distinct from $S$, we denote the
composition of $S$ and $R$ by $SR$.$\mathscr{H}_{S}$, as well as spaces of
operators and of superoperators on $\mathscr{H}_{S}$,are equipped with the
standard topology of $\mathbb{C}^{d_{S}}$.We denote the identity operator on
$\mathscr{H}_{S}$ by $\mathds{1}_{S}$.We denote the identity superoperator on
$\mathscr{H}_{S}$ by<EMAIL_ADDRESS>denote the
single-qubit identity operator by $\mathds{1}_{2}$.For any Hermitian operators
$A$ and $B$, we write $A\leqslant B$ if $B-A$ is positive-semidefinite.A
subnormalized quantum state $\rho_{S}$ is a positive-semidefinite operator
that satisfies $\tr(\rho_{S})\leqslant 1$.If $\tr(\rho_{S})=1$, then
$\rho_{S}$ is normalized and represents a physical quantum state.In the
absence of ambiguity, we omit system subscripts from operators.We denote the
projector onto a pure state $\ket\psi$ by $\psi\coloneqq\proj{\psi}$.We denote
by $\pi_{S}\coloneqq\mathds{1}_{S}/d_{S}$ the maximally mixed state of $S$.For
any sets $X$ and $Y$ of operators, we define $X\otimes Y\coloneqq\\{A\otimes
B:\,A\in X,\,B\in Y\\}$.An operator $A$ has the operator norm
$\lVert{A}\rVert$, defined as the greatest singular value of $A$.The trace
norm $\lVert{A}\rVert_{1}$ is the sum of the singular values of $A$.We denote
by $\ket{0}$ the eigenvalue-1 eigenvector of the Pauli-$z$ operator.Tensor
products are notated as $\ket{0^{k}}\coloneqq\ket{0}^{\otimes k}$.A _POVM
effect_ $Q$ on a system $S$ is a (Hermitian) positive-semidefinite operator
satisfying $0\leqslant Q\leqslant\mathds{1}_{S}$.Finally, all logarithms are
base-$e$, unless otherwise indicated.The _diamond norm_ of a superoperator
$\mathcal{X}$ on $\mathscr{H}_{S}$ is defined as

$\displaystyle\lVert{\mathcal{X}}\rVert_{\diamond}\coloneqq\max_{\rho_{SR}}\left\\{{\lVert{(\mathcal{X}\otimes\phfqit@parsesizearg\operatorname{id}_{R})(\rho_{SR})}\rVert_{1}}\right\\}\
,$ (41bj)

where $R$ denotes any system isomorphic to $S$, and the maximization is
defined with respect to all subnormalized states $\rho_{SR}$.For any
subnormalized state $\rho$ on $S$, the diamond norm
$\lVert{\mathcal{X}}\rVert_{\diamond}$ upper-bounds the trace norm
$\lVert{\mathcal{X}(\rho)}\rVert_{1}$ as

$\displaystyle\lVert{\mathcal{X}(\rho)}\rVert_{1}=\lVert{(\mathcal{X}\otimes\phfqit@parsesizearg\operatorname{id}_{R})(\rho_{S}\otimes\rho_{R})}\rVert_{1}\leqslant\lVert{\mathcal{X}}\rVert_{\diamond}\
.$ (41bk)

For any completely positive, trace-preserving maps $\mathcal{E}$ and
$\mathcal{F}$, the diamond distance
$\frac{1}{2}\lVert{\mathcal{E}-\mathcal{F}}\rVert_{\diamond}$ quantifies the
one-shot distinguishability of $\mathcal{E}$ and $\mathcal{F}$ [111].For any
state $\rho$ of $S$, the von Neumann entropy of $\rho$ is
$\HH{\rho}\equiv\HH[\rho]{S}\coloneqq-\tr\bm{(}\rho\log(\rho)\bm{)}$.For any
positive-semidefinite operator $\Gamma$ on $\mathscr{H}_{S}$, the (Umegaki)
quantum relative entropy of $\rho$ with respect to $\Gamma$ is
$\DD{\rho}{\Gamma}\coloneqq\tr\bm{(}\rho[\log(\rho)-\log(\Gamma)]\bm{)}$.If
$S$ is a joint system, $S=XY$, the conditional quantum entropy
$\HH[\rho]{X}[Y]$ is $\HH[\rho]{X}[Y]\coloneqq\HH[\rho]{XY}-\HH[\rho]{Y}$.The
following inequality is used often in quantum information theory. The
inequality is equivalent to a general lower bound on a version of the
conditional min-entropy [80, 96].

######  Lemma 1 (Partial order for joint states).

††margin:

Let $X$ and $Y$ denote distinct quantum systems.If $\rho_{XY}$ denotes any
subnormalized state on $XY$, then

$\displaystyle\frac{1}{d_{X}}\,\rho_{XY}\leqslant\mathds{1}_{X}\otimes\rho_{Y}\
.$ (41bl)

  * Proof. Let $C$ denote a system isomorphic to $X$. Let $\\{{\ket{j}_{X}}\\}$ and $\\{{\ket{j}_{C}}\\}$ denote bases for the eigenspaces of $X$ and $C$.If $\ket{\chi}_{C}\coloneqq\sum_{j}\ket{j}_{C}/\sqrt{d_{X}}$, then $\rho_{XY}\otimes\chi_{C}\leqslant\rho_{XY}\otimes\mathds{1}_{C}$, since $\chi_{C}\leqslant\mathds{1}_{C}$.Every positive map preserves the partial order on operators.[If $\mathcal{N}$ is a positive (linear) map acting on operators $A$ and $B\geqslant A$, then $\mathcal{N}(B)\geqslant\mathcal{N}(A)$: $\mathcal{N}(B-A)=\mathcal{N}(B)-\mathcal{N}(A)$ is positive-semidefinite, since $B-A$ is positive-semidefinite.]Hence, conjugating both sides of $\rho_{XY}\otimes\chi_{C}\leqslant\rho_{XY}\otimes\mathds{1}_{C}$ by $\sum_{j}\proj{j}_{X}\otimes\bra{j}_{C}$ yields the pinching inequality

$\displaystyle\rho_{XY}=d_{X}\left({\sum_{j}\proj{j}_{X}\otimes\bra{j}_{C}}\right)(\rho_{XY}\otimes\chi_{C})\left({\sum_{k}\proj{k}_{X}\otimes\ket{k}_{C}}\right)\leqslant
d_{X}\sum_{j}\proj{j}_{X}\,\bra{j}_{X}\rho_{XY}\ket{j}_{X}\ .$ (41bm)

In terms of the Fourier-transformed states
$\ket{\tilde{l}}_{X}\coloneqq\sum_{j}e^{i2\pi
lj/d_{X}}\ket{j}_{X}/\sqrt{d_{X}}$, the pinching inequality is

$\displaystyle\rho_{XY}\leqslant
d_{X}\sum_{l}\proj{\tilde{l}}_{X}\,\bra{\tilde{l}}_{X}\rho_{XY}\ket{\tilde{l}}_{X}\
.$ (41bn)

Applying the positive map
$d_{X}\sum_{j}\proj{j}_{X}\,\bra{j}_{X}(\cdot)\ket{j}_{X}$ to both sides of
41bn yieldsWe have used
$\abs\left\\{{\braket{j}{\tilde{l}}_{X}}\right\\}^{2}=1/d_{X}$.Chaining
together 41bm and LABEL:eq:positive-map-on-pinching-inequality proves the
lemma.∎

The following lemma provides a useful expression for, and bound on, the
diamond distance between a unitary operation and the identity process.

######  Lemma 2 (Diamond distance between a unitary operation and the identity
process).

††margin:

Let $U$ denote any unitary operator, and let $\mathcal{U}(\cdot)\coloneqq
U({\cdot})U^{\dagger}$.It holds that

$\displaystyle\frac{1}{2}\lVert{\mathcal{U}-\phfqit@parsesizearg\operatorname{id}}\rVert_{\diamond}$
$\displaystyle=\sin\left({\min\left\\{{e(U),\frac{\pi}{2}}\right\\}}\right),$
(41bo)

where

$\displaystyle e(U)$
$\displaystyle\coloneqq\min\left\\{{\lVert{H}\rVert\,:\;H=H^{\dagger},\;\exists\chi\in\mathbb{R}\text{
such that }e^{-iH}=e^{-i\chi}U}\right\\}\ .$ (41bp)

Furthermore,

$\displaystyle\frac{1}{2}\lVert{\mathcal{U}-\phfqit@parsesizearg\operatorname{id}}\rVert_{\diamond}\leqslant\lVert{U-\mathds{1}}\rVert\
.$ (41bq)

The quantity $e(U)$ is called the potential entangling power of $U$; a similar
quantity is defined in Ref. [27].$e(U)$ is insensitive to global phases: for
all $\chi\in\mathbb{R}$, $e(e^{i\chi}U)=e(U)$.Inequality 41bq automatically
yields an upper bound on the diamond distance between arbitrary unitary
operations.For all unitaries $U$ and $V$ acting on the same Hilbert space, the
operations $\mathcal{U}(\cdot)\coloneqq U({\cdot})U^{\dagger}$ and
$\mathcal{V}(\cdot)\coloneqq V({\cdot})V^{\dagger}$ obey

$\displaystyle\frac{1}{2}\lVert{\mathcal{U}-\mathcal{V}}\rVert_{\diamond}=\frac{1}{2}\lVert{\mathcal{V}^{\dagger}\mathcal{U}-\phfqit@parsesizearg\operatorname{id}}\rVert_{\diamond}\leqslant\lVert{V^{\dagger}U-\mathds{1}}\rVert=\lVert{U-V}\rVert\
.$ (41br)

The first (second) equality follows from the diamond (operator) norm’s
invariance under unitary operations (operators).

  * Proof of Appendix A. By Proposition 18 of Ref. [132], $\frac{1}{2}\lVert{\mathcal{U}-\phfqit@parsesizearg\operatorname{id}}\rVert_{\diamond}=\sin\left({\min\\{{\alpha,\pi/2}\\}}\right)$, where $\alpha$ is half the angle of the shortest arc $A$, on the unit circle, that contains every eigenvalue (eigenphase) of $U$.Let $\chi_{*}\in\mathbb{R}$ such that $e^{i\chi_{*}}$ is the midpoint of $A$.(Since $U$ has only finitely many eigenphases, $A$ does not encompass the unit circle, so $A$ has endpoints and a midpoint.)By definition, $A=\left\\{{e^{i\chi_{*}}e^{i\varphi}\,:\;\varphi\in[-\alpha,\alpha]}\right\\}$.$A$ has the endpoints $\theta_{\pm}\coloneqq e^{i\chi_{*}}e^{\pm i\alpha}$.$\theta_{\pm}$ are eigenphases of $U$.Otherwise, one could obtain an arc shorter than $A$ that contains every eigenphase of $U$.To prove 41bo, we show that $e(U)=\alpha$.Let $-iH_{*}$ denote the unique logarithm of $e^{-i\chi_{*}}U$ such that every eigenvalue of $H_{*}$ lies in $(-\pi,\pi]$.Since $H_{*}$ is Hermitian and $e^{-iH_{*}}=e^{-i\chi_{*}}U$, $e(U)\leqslant\lVert{H_{*}}\rVert$.Because every eigenvalue of $U$ lies in $A$, every eigenvalue of $e^{-iH_{*}}$ lies in the arc $A_{*}\coloneqq\left\\{{e^{i\varphi}\,:\;\varphi\in[-\alpha,\alpha]}\right\\}$, which one obtains by multiplying every point in $A$ by $e^{-i\chi_{*}}$.Consequently, every eigenvalue of $H_{*}$ lies in $[-\alpha,\alpha]$, so $\lVert{H_{*}}\rVert\leqslant\alpha$.Hence, $e(U)\leqslant\alpha$.For the sake of contradiction, suppose $e(U)<\alpha$.Let $H$ denote any Hermitian operator that achieves the minimum in 41bp.$e^{-iH}=e^{-i\chi}U$ for some $\chi\in\mathbb{R}$, and $\lVert{H}\rVert=e(U)<\alpha$.Since every eigenvalue of $H$ lies in $\left[{-\lVert{H}\rVert,\lVert{H}\rVert}\right]$, the arc $A_{H}\coloneqq\left\\{{e^{i\chi_{*}}e^{i\varphi}\,:\;\varphi\in\left[{-\lVert{H}\rVert,\lVert{H}\rVert}\right]}\right\\}$ contains every eigenvalue of $e^{i\chi}e^{-iH}=U$.Having the half-angle $\lVert{H}\rVert<\alpha$, $A_{H}$ is shorter than $A$, a contradiction.Therefore, $e(U)=\alpha$.We now prove 41bq.Suppose $\alpha\geqslant\pi/2$.Then $A$ contains a half-circle and thus has an endpoint $\theta\in\left\\{{\theta_{\pm}}\right\\}$ whose real part is nonpositive: $\Re(\theta)\leqslant 0$.$\theta$ is an eigenphase of $U$, so $\theta-1$ is an eigenvalue of $U-\mathds{1}$.Hence,

$\displaystyle\frac{1}{2}\lVert{\mathcal{U}-\phfqit@parsesizearg\operatorname{id}}\rVert_{\diamond}=\sin\left({\min\left\\{{\alpha,\frac{\pi}{2}}\right\\}}\right)=1\leqslant\abs\left\\{{\Re(\theta)-1}\right\\}=\abs\left\\{{\Re(\theta-1)}\right\\}\leqslant\abs\left\\{{\theta-1}\right\\}\leqslant\lVert{U-\mathds{1}}\rVert\
.$

Now, suppose $\alpha<\pi/2$.Then

$\displaystyle\frac{1}{2}\lVert{\mathcal{U}-\phfqit@parsesizearg\operatorname{id}}\rVert_{\diamond}$
$\displaystyle=\sin\left({\min\left\\{{\alpha,\frac{\pi}{2}}\right\\}}\right)=\sin\left({\alpha}\right)=\abs\left\\{{e^{i\chi_{*}}\sin\left({\alpha}\right)}\right\\}$
$\displaystyle=\frac{1}{2}\abs\left\\{{e^{i\chi_{*}}\left({e^{i\alpha}-e^{-i\alpha}}\right)}\right\\}=\frac{1}{2}\abs\left\\{{\theta_{+}-\theta_{-}}\right\\}=\frac{1}{2}\abs\left\\{{(\theta_{+}-1)-(\theta_{-}-1)}\right\\}$
$\displaystyle\leqslant\frac{1}{2}\abs\left\\{{\theta_{+}-1}\right\\}+\frac{1}{2}\abs\left\\{{\theta_{-}-1}\right\\}$
$\displaystyle\leqslant\lVert{U-\mathds{1}}\rVert\ .$ (41bs)

The second inequality follows because $U-\mathds{1}$ has the eigenvalues
$\theta_{\pm}-1$.∎

##  Appendix B Measures of complexity and POVM-effect complexity

We define the complexity (relative) entropy in terms of POVM-effect
complexity.This section’s main purpose is to introduce general assumptions
that define POVM-effect complexity.Our setting’s generality enables one to
define the complexity (relative) entropy for a range of physical systems,
including qubits, qudits, and continuous-variable systems.

###  B.1 Complexity of superoperators and unitaries

Using conservative assumptions, we define complexity measures for
superoperators and unitaries.We later use these measures to construct measures
of POVM-effect complexity.

######  Definition 3 (Superoperator-complexity measure).

Let $S$ denote a composition of $N$ quantum subsystems: $S=S_{1}S_{2}\ldots
S_{N}$.For every subset $I\subset\\{{1,2,\ldots,N}\\}$, let $S_{I}$ denote the
composition of the subsystems in $\\{{S_{i}}\\}_{i\in I}$.A superoperator-
complexity measure on $S$ is a family of functions $C_{S_{I}}$ that map
completely positive, trace-nonincreasing maps to
$\mathbb{R}_{+}\cup\\{{\infty}\\}$, for all $I\subset\\{{1,2,\ldots,N}\\}$.The
functions must have the following properties, for every
$I\subset\\{{1,2,\ldots,N}\\}$:

  1. ()

The identity operation has zero complexity:
$C_{S_{I}}(\phfqit@parsesizearg\operatorname{id}_{S_{I}})=0$.

  2. ()

No sequential composition of operations has a complexity that exceeds the sum
of the individual operations’ complexities:for any operations
$\mathcal{E}_{1}$ and $\mathcal{E}_{2}$ on $S_{I}$,
$C_{S_{I}}(\mathcal{E}_{2}\mathcal{E}_{1})\leqslant
C_{S_{I}}(\mathcal{E}_{1})+C_{S_{I}}(\mathcal{E}_{2})$.

  3. ()

No parallel composition of operations has a complexity that exceeds the sum of
the individual operations’ complexities:for any $J$ disjoint from $I$, for any
operation $\mathcal{E}_{1}$ on $S_{I}$, and for any operation
$\mathcal{E}_{2}$ on $S_{J}$,
$C_{S_{I}S_{J}}(\mathcal{E}_{1}\otimes\mathcal{E}_{2})\leqslant
C_{S_{I}}(\mathcal{E}_{1})+C_{S_{J}}(\mathcal{E}_{2})$.

For every operation $\mathcal{E}$ on any $S_{I}$, we employ the shorthand
notation $C_{S}(\mathcal{E})\coloneqq C_{S_{I}}(\mathcal{E})$.Accordingly, we
denote a superoperator-complexity measure by its function $C_{S}$, for
convenience.The following is a natural way to construct a superoperator-
complexity measure:Choose a set $\mathcal{G}$ of elementary operations.Define
the complexity of an arbitrary operation $\mathcal{E}$ as the minimum number
of operations in $\mathcal{G}$ that, under composition, effect $\mathcal{E}$.

######  Definition 4 (Circuit-superoperator-complexity measure).

Let $S=S_{1}S_{2}\ldots S_{N}$ denote a quantum system.We employ the notation
of B.1.For every subset $I\subset\\{{1,2,\ldots,N}\\}$, let
$\mathcal{G}_{S_{I}}$ denote an (arbitrary) set of completely positive, trace-
nonincreasing maps such that
$\phfqit@parsesizearg\operatorname{id}_{S_{I}}\in\mathcal{G}_{S_{I}}$ and
$\mathcal{G}_{S_{I}}\subset\mathcal{G}_{S_{J}}$ for all $J\supset I$.Denote
the set $\mathcal{G}_{S}$ by $\mathcal{G}$.A _circuit-superoperator-complexity
measure_ on $S$ associated with $\mathcal{G}$ is a family of functions
$C_{\mathcal{G},S_{I}}$, for any $I\subset\\{{1,2,\ldots,N}\\}$, defined as

$\displaystyle
C_{\mathcal{G},S_{I}}(\mathcal{E})\coloneqq\min\left\\{{r\in\mathbb{N}:\mathcal{E}_{r}\cdots\mathcal{E}_{2}\mathcal{E}_{1}=\mathcal{E}\,,\;\mathcal{E}_{i}\in\mathcal{G}_{S_{I}}\>\,\forall
i\in\left\\{{1,2,\ldots,r}\right\\}}\right\\}\ .$ (41bt)

We introduce three conventions.First, we denote a circuit-superoperator-
complexity measure by its function $C_{\mathcal{G},S}$.Second, we designate
the composition of a zero number of operations on $S_{I}$ as the identity
operation<EMAIL_ADDRESS>we set
$C_{S_{I}}(\mathcal{E})=\infty$ whenever no finite sequence of operations from
$\mathcal{G}_{S_{I}}$ implements an operation $\mathcal{E}$ exactly.The
following proposition confirms that every circuit-complexity measure (B.1) is
a superoperator-complexity measure (B.1).

######  Proposition 5 (Compatibility of circuit-superoperator complexity and
general-superoperator complexity).

††margin:

Define $S$ and the gate set $\mathcal{G}$ as in B.1.Every circuit-
superoperator-complexity measure on $S$ associated with $\mathcal{G}$ is a
superoperator-complexity measure.

  * Proof. We verify that every circuit-superoperator-complexity measure $C_{\mathcal{G},S}$ has the three properties in B.1.Property 1 holds because, by definition, $\phfqit@parsesizearg\operatorname{id}_{S_{I}}\in\mathcal{G}_{S_{I}}$; and, by convention, $\phfqit@parsesizearg\operatorname{id}_{S_{I}}$ is the sequential composition of zero operations.Property 2 automatically characterizes every sequential composition that involves an infinite-complexity operation.Now, we prove that property 2 characterizes finite-complexity operations $\mathcal{E}$ and $\mathcal{E}^{\prime}$ on $S_{I}$.If the operations’ complexities are $C_{S_{I}}(\mathcal{E})=r$ and $C_{S_{I}}(\mathcal{E}^{\prime})=r^{\prime}$, we can decompose $\mathcal{E}$ and $\mathcal{E}^{\prime}$ as sequences of $r$ and $r^{\prime}$ operations in $\mathcal{G}_{S_{I}}$, respectively.Therefore, we can decompose $\mathcal{E^{\prime}}\mathcal{E}$ as a sequence of $r+r^{\prime}$ operations in $\mathcal{G}_{S_{I}}$.Hence $C_{S_{I}}(\mathcal{E^{\prime}}\mathcal{E})\leqslant r+r^{\prime}=C_{S_{I}}(\mathcal{E})+C_{S_{I}}(\mathcal{E}^{\prime})$.Property 3 follows as a special case of Property 2: one can express every operation $\mathcal{E}$ on $S_{I}$ as the operation $\mathcal{E}\otimes\phfqit@parsesizearg\operatorname{id}_{S_{J}}$ on $S_{I}S_{J}$ and vice versa.∎

Many complexity measures in the literature are defined only for unitary
operations.The following definition specializes B.1 to such situations.

######  Definition 6 (Unitary-complexity measure).

A _unitary-complexity measure_ isa superoperator-complexity measure that
assigns finite values only to unitary operations.A unitary-complexity measure
$C_{S}$ is called _adjoint-invariant_ if
$C_{S}(\mathcal{U})=C_{S}(\mathcal{U}^{\dagger})$ for every unitary operation
$\mathcal{U}$ on $S$.

Let $U$ denote any unitary operator on $\mathscr{H}_{S}$, and let
$\mathcal{U}(\cdot)\coloneqq U(\cdot)U^{\dagger}$.We write $C_{S}(U)$ as a
shorthand for $C_{S}(\mathcal{U})$, for convenience.Correspondingly, a
_unitary-circuit-complexity measure_ is a unitary-complexity measure that is
also a circuit-complexity measure.Equivalently, a unitary-circuit-complexity
measure is a circuit-complexity measure associated with a set of unitary
gates.

###  B.2 Quantum-state complexity

Here, we introduce state-complexity measures in general, for completeness and
for use in later appendices.

######  Definition 7 (Exact-state-complexity measure).

Let $S$ denote a quantum system.Let $C_{S}$ denote any superoperator-
complexity measure; and $\rho_{0}$, any state of $S$.The _exact-state-
complexity measure_ with respect to $C_{S}$ and $\rho_{0}$ is

$\displaystyle
C_{S}^{\rho_{0}}(\rho)\coloneqq\inf\left\\{{C_{S}(\mathcal{E}):\mathcal{E}(\rho_{0})=\rho}\right\\}\
.$ (41bu)

An exact-state-complexity measure $C_{S}^{\rho_{0}}$ is called an _exact-pure-
state-complexity measure_ if $\rho_{0}$ is pure and if $C_{S}^{\rho_{0}}$
assigns finite values only to pure states.$C_{S}^{\rho_{0}}$ is such a measure
if, for instance, $\rho_{0}$ is pure and $C_{S}$ is a unitary-complexity
measure.

######  Definition 8 (Approximate-state-complexity measure).

Let $S$ denote a quantum system.Let $C_{S}$ denote any superoperator-
complexity measure; and $\rho_{0}$, any state of $S$.Let $\delta\geqslant
0$.The _$\delta$ -approximate-state-complexity measure_ with respect to
$C_{S}$ and $\rho_{0}$ is

$\displaystyle C_{S}^{\rho_{0},\,\delta}(\rho)\coloneqq\lim_{\zeta\to
0^{+}}\inf\left\\{{C_{S}(\mathcal{E})\,:\;\frac{1}{2}\lVert{\mathcal{E}(\rho_{0})-\rho}\rVert_{1}\leqslant\delta+\zeta}\right\\}\
.$ (41bv)

The stabilization $\lim_{\zeta\to 0^{+}}$ in 41bv helps smooth
$C_{S}^{\rho_{0},\,\delta}$ at unusual discontinuities in superoperator-
complexity measures.For instance, consider any set $\mathcal{G}_{0}$ of two-
qubit unitary gates that is universal for quantum computation.Let
$\mathcal{G}$ denote the set of $n$-qubit unitaries realizable as finite
sequences of gates in $\mathcal{G}_{0}$.$\mathcal{G}$ is closed under
composition.Let $C_{\mathcal{G}}$ denote the unitary-circuit-complexity
measure associated with $\mathcal{G}$ (B.1).By construction, the identity
$\mathds{1}_{2}^{\otimes n}$ has zero complexity, and every unitary
$U\in\mathcal{G}$ has unit complexity: $C_{\mathcal{G}}(U)=1$.Any other
unitary has infinite complexity, since it can only be approximated by a
sequence of gates in $\mathcal{G}_{0}$—and thus by a unitary in $\mathcal{G}$
[BookNielsenChuang2000].Let $\ket{\psi_{0}}$ denote any pure $n$-qubit
state.The stabilization ensures that $C_{S}^{\psi_{0},\,0}(\psi)=1$ for all
pure states $\ket{\psi}\neq\ket{\psi_{0}}$.Without the stabilization, every
state $\ket\psi$ inaccessible from $\ket{\psi_{0}}$ by any unitary in
$\mathcal{G}$ would have an infinite complexity:
$C_{S}^{\psi_{0},\,0}(\psi)=\infty$.As an immediate consequence of 41bv,
$C_{S}^{\rho_{0},\delta}$ is right-continuous in $\delta$:

$\displaystyle\lim_{\zeta\to
0^{+}}C_{S}^{\rho_{0},\delta+\zeta}(\rho)=C_{S}^{\rho_{0},\delta}(\rho)\ .$
(41bw)

An approximate-state-complexity measure $C_{S}^{\rho_{0},\,\delta}$ is called
an _approximate-pure-state-complexity measure_ if $\rho_{0}$ is pure and if
$C_{S}^{\rho_{0},\,0}$ assigns finite values only to pure
states.$C_{S}^{\rho_{0},\,\delta}$ is such a measure if, for instance,
$\rho_{0}$ is pure and $C_{S}$ is a unitary-complexity measure.The following
proposition provides an alternative expression for 41bv.From this expression,
we derive a condition under which the stabilization in 41bv becomes
inconsequential.

######  Proposition 9 (Alternative expression for approximate-state-complexity
measure).

††margin:

Let $S$ denote a quantum system.Let $C_{S}$ denote any superoperator-
complexity measure; and $\rho_{0}$, any state of $S$.Let $\delta\geqslant
0$.It holds that

$\displaystyle C_{S}^{\rho_{0},\delta}(\rho)$
$\displaystyle=\inf\left\\{{r\,:\;\operatorname{dist}_{1}(\rho,\mathfrak{G}_{r}[\rho_{0}])\leqslant\delta}\right\\}\
,$ (41bx)

where

$\displaystyle\mathfrak{G}_{r}[\rho_{0}]\coloneqq\left\\{{\mathcal{E}(\rho_{0})\,:\;C_{S}(\mathcal{E})\leqslant
r}\right\\}\\\;\;\text{and}\;\;\operatorname{dist}_{1}(\rho,T)$
$\displaystyle\coloneqq\inf_{\rho^{\prime}\in
T}\left\\{{\frac{1}{2}\big{\lVert}{\rho-\rho^{\prime}}\big{\rVert}_{1}}\right\\}\
,$ (41by)

and where $T$ is any set of states.

We now show that, under simple conditions, we can forgo the stabilization in
the definition of the approximate-state-complexity measure.