  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.
