Resource theory of quantum uncomplexity

Quantum complexity is emerging as a key property of many-body systems, including black holes, topological materials, and early quantum computers. A state's complexity quantifies the number of computational gates required to prepare the state from a simple tensor product. The greater a state's distance from maximal complexity, or “uncomplexity,” the more useful the state is as input to a quantum computation. Separately, resource theories—simple models for agents subject to constraints—are burgeoning in quantum information theory. We unite the two domains, confirming Brown and Susskind's conjecture that a resource theory of uncomplexity can be defined. The allowed operations, fuzzy operations, are slightly random implementations of two-qubit gates chosen by an agent. We formalize two operational tasks, uncomplexity extraction and expenditure. Their optimal efficiencies depend on an entropy that we engineer to reflect complexity. We also present two monotones, uncomplexity measures that decline monotonically under fuzzy operations, in certain regimes. This work unleashes on many-body complexity the resource-theory toolkit from quantum information theory.

Figure 1

State complexity and its geometry. (a) A pure $n$-qubit state $|\psi \rangle$ has an exact circuit complexity $\mathcal{C}\left(\right|\psi \rangle )$ equal to the least number of gates required to prepare $|\psi \rangle$ from $|0^n\rangle$. The state's exact uncomplexity is the distance ${\mathcal{C}}_{\max }-\mathcal{C}\left(\right|\psi \rangle )$ to the maximal $n$-qubit state complexity, ${\mathcal{C}}_{\max }\sim e^n$. (b) In a revision of Nielsen's geometry [26, 27], complexity curves the state space negatively [28]. Applying a gate moves a state through a unit length along some direction. Most directions lead to higher-complexity states. To transform into a generic state $|{\psi }^{\prime }\rangle$, $|\psi \rangle$ likely must pass through $|0^n\rangle$; no significantly shorter path exists. Consequently, uncomplexity is desirable in quantum computation: Given a complex $|\psi \rangle$, to prepare a desired output $|{\psi }^{\prime }\rangle$, one must uncompute $|{\psi }^{\prime }\rangle$ to $|0^n\rangle$. Our resource theory slightly randomizes the gates (green shaded regions), leading them to realistically increase the state's complexity.

Figure 2

Operational tasks of uncomplexity extraction and expenditure in the resource theory. Since gates are fuzzy, the agent can perform only $\le r$ gates, lest the state grow too noisy to be useful. (a) Extracting uncomplexity from a state $\rho$, one applies $\le r$ fuzzy gates. The number of qubits left in the state $|0\rangle$ is the extractable uncomplexity, which equals the complexity entropy of $\rho$. (b) Given enough $|0\rangle$'s, an agent can “spend” uncomplexity to imitate $\rho$: The agent performs $r$ fuzzy gates, preparing a state believed, by a computationally bounded referee, to be $\rho$.

Figure 3

A brickwork circuit of the sort featured in Theorem t2. Periodic boundary conditions impose a gate (green boxes) on qubits $n$ and 1 in each even-indexed layer.