The Second Law of Quantum Complexity. (arXiv:1701.01107v2 [hep-th] UPDATED)
We give arguments for the existence of a thermodynamics of quantum complexity
that includes a "Second Law of Complexity". To guide us, we derive a
correspondence between the computational (circuit) complexity of a quantum
system of $K$ qubits, and the positional entropy of a related classical system
with $2^K$ degrees of freedom. We also argue that the kinetic entropy of the
classical system is equivalent to the Kolmogorov complexity of the quantum
Hamiltonian. We observe that the expected pattern of growth of the complexity
of the quantum system parallels the growth of entropy of the classical system.
We argue that the property of having less-than-maximal complexity
(uncomplexity) is a resource that can be expended to perform directed quantum
Although this paper is not primarily about black holes, we find a surprising
interpretation of the uncomplexity-resource as the accessible volume of
spacetime behind a black hole horizon.