State, Unitary, Channel, and Operator Complexity

State preparation, unitary synthesis, channel implementation, and operator growth are inequivalent complexity tasks because they identify different targets and optimize over different freedoms. Even when one Gaussian transformation appears in all four descriptions, the relevant equivalence classes and error metrics differ. A numerical equality in a special gate model should not be promoted to an identity of notions.

Required background. What Task Does Complexity Answer? supplies the task tuple and the resource distinctions. Helpful background. Channel–State Correspondence in Infinite Dimensions explains why a formal maximally entangled Choi vector is insufficient for an unrestricted field channel.

Four targets and four quotient freedoms

For a reference state $\rho_0$ and target $\rho_1$, state complexity minimizes over implementations whose output is close to $\rho_1$:

$$C_{\rm state}(\rho_1;\rho_0) =\inf_{U:\,d(U\rho_0U^\dagger,\rho_1)\leq\epsilon}F[U].$$

Any two unitaries that agree on $\rho_0$ are equivalent for this task. If $V\rho_0V^\dagger=\rho_0$, then $UV$ prepares the same state, so the stabilizer may lower the optimum.

Unitary complexity instead approximates $U_1$ on a declared domain:

$$C_{\rm unitary}(U_1) =\inf_{V:\,d_{\mathcal D}(V,U_1)\leq\epsilon}F[V].$$

The domain $\mathcal D$ matters in QFT. Uniform operator-norm approximation on an unbounded Hilbert space is much stronger than agreement on a finite-energy subspace. A global phase may be quotiented; arbitrary right multiplication by a state stabilizer may not.

For a channel $\mathcal N$, one can minimize over allowed implementations or dilations,

$$C_{\rm channel}(\mathcal N) =\inf_{W,E,\sigma_E:\,d_E(\mathcal N_{W,\sigma_E},\mathcal N)\leq\epsilon} F[W,E,\sigma_E].$$

The environment dimension, initial state, discarded algebra, and whether environment preparation is charged must be fixed. Stinespring dilations related by environment isometries implement the same channel but need not have the same raw circuit cost.

Continuity of Stinespring representations controls how channel distance constrains dilation distance, under its stated channel-norm and representation hypotheses Kretschmann, Schlingemann, and Werner 2008, Theorem 1. It does not assign a cost to preparing the environment or implementing the isometry.

Operator complexity may mean synthesizing an operator as a unitary, expanding it in a gate algebra, or tracking its Krylov growth. The last is a basis moment and involves no minimization over implementing circuits. The page on Krylov Complexity and Operator Growth develops that distinct construction.

One Gaussian map viewed four ways

Consider one bosonic mode with a squeeze $S(r)$:

$$S(r)^\dagger qS(r)=e^{-r}q, \qquad S(r)^\dagger pS(r)=e^{r}p.$$

• As a state task, preparing $S(r)|0\rangle$ allows any final phase rotation that stabilizes the squeezed covariance.
• As a unitary task, the action on every state in the energy domain must match $S(r)$, so the stabilizer freedom is reduced.
• As a channel task, $\rho\mapsto S(r)\rho S(r)^\dagger$ can be implemented directly or as part of a larger dilation; the declared resource decides whether those are equivalent.
• As an operator-growth task, one may evolve $q$ under the squeeze generator and ask how its expansion changes. That coefficient growth does not equal the synthesis cost of $S(r)$.

With a one-generator $F_1$ geometry, all first three minimal values may reduce to $|r|$ in an idealized model. Add bounded controls, a noisy environment, or a penalty for the squeeze generator and the equality disappears while the physical transformation is unchanged.

Composition laws are task dependent

An explicit concatenation gives an upper bound, consistent with the path-length construction in Nielsen geometry Nielsen 2006, §§2–3,

$$C(U_2U_1)\leq C(U_2)+C(U_1)$$

when the same gate set, cost, domain, and tolerance allocation apply. State complexity can be strictly smaller because the composite unitary may differ from a shortest state-preparation representative. Channel composition also requires distributing the error budget and charging reset or memory resources. Krylov complexity is generally not subadditive under operator multiplication because the Lanczos bases differ.

These distinctions prevent a common error: using a circuit upper bound for one state to claim a lower bound for implementing a unitary or channel.

Exercises

Stabilizer shortcut. If $V|\psi_0\rangle=|\psi_0\rangle$, compare the state-preparation roles of $U$ and $UV$.

Solution

They prepare the same target from $|\psi_0\rangle$, so state complexity minimizes over both representatives. They need not implement the same unitary on other inputs, so unitary complexity cannot quotient by $V$ unless the task explicitly does so.

Free environment. Why can uncharged ancillas artificially lower channel complexity?

Solution

A complicated state or transformation can be moved into the environment preparation and then coupled by a simple swap or interaction. If the ancilla resource is free, the reported cost omits part of the implementation. The task must charge or constrain environment dimension, state, and controls.

Task and validity maps

The first diagram distinguishes target objects and their admissible resource models; inspect which equivalence class is being minimized over. The second shows the definition changes and physical controls that must be held fixed before two complexity values or growth laws are compared.

A complexity value is defined only after the target object selects an admissible family of paths or descriptions. Circuit length, physical control cost, Krylov spread, algorithmic resources, and sharp o-minimal format or degree answer different questions. The diagram is schematic and not to scale.

Reference sensitivity, gate nonuniqueness, regulator dependence, symmetry constraints, and unbounded controls are distinct failure modes. A link from complexity growth to chaos or computational hardness requires separate evidence after those controls. The diagram is schematic.

References

• Kretschmann, Dennis, Dirk Schlingemann, and Reinhard F. Werner. “The Information-Disturbance Tradeoff and the Continuity of Stinespring’s Representation.” IEEE Transactions on Information Theory 54 (2008): 1708–1717. DOI. Open PDF.
• Nielsen, Michael A. “A Geometric Approach to Quantum Circuit Lower Bounds.” Quantum Information & Computation 6 (2006): 213–262. Open PDF.