What Task Does Complexity Answer?

A complexity claim answers a minimization or resource question only after its task is fully specified. In QFT this is especially important because the target may live in a regulated Hilbert space, the continuum theory may not factorize into spatial tensor factors, and different notions called “complexity” minimize over different mathematical objects. The transferable result is therefore the task tuple, not a bare number.

Required background. Why Continuum QFT Does Not Factorize Naively supplies the algebraic alternative to an assumed continuum qubit register. Direct Sums, Tensor Products, and Index Structure supplies the regulated product structure used by circuits.

Helpful background. Information-Measure Domain and Comparison Atlas models the same discipline of attaching domains and operational meanings to formulas.

The eight fields of a resource question

For an object $X$, define

$$\mathcal T=(X_{\rm ref},X_{\rm tar},\mathcal A,d,\epsilon,F,\Lambda,\mathcal R), \qquad \mathfrak C_{\mathcal T}=\inf_{P\in\mathcal P_{\mathcal T}}F[P].$$

The fields have distinct jobs:

1. $X_{\rm ref}$ and $X_{\rm tar}$ identify the object type and the boundary data.
2. $\mathcal A$ lists admissible gates, controls, algorithms, bases, formulas, or dilations.
3. $d(X(P),X_{\rm tar})\leq\epsilon$ defines successful approximation on a stated domain.
4. $F$ assigns cost and fixes generator normalization, penalties, and aggregation rule.
5. $\Lambda$ specifies the regulator, physical volume, and order of limits.
6. $\mathcal R$ names what is counted: gates, depth, duration, work, queries, samples, memory, Krylov index, or descriptive format and degree.

An infimum may fail to be attained; an extremal path may be only locally minimal; and the admissible class may be empty. These are mathematical outcomes, not nuisances to be hidden by calling the answer infinite or universal.

For state preparation, stabilizers of the target can make many unitary paths equivalent. For a channel, different Stinespring dilations implement the same map. For an operator, the Lanczos basis is determined by an inner product and Liouvillian rather than an allowed gate set. The quotient freedom therefore belongs in $\mathcal A$, not in a footnote after the minimization.

Four inequivalent meanings

Circuit or physical-resource complexity. A circuit count minimizes over products of allowed transformations. A physical-resource cost instead integrates declared controls, time, energy, bandwidth, or work. They coincide only if an implementation theorem relates each gate and its penalty to the laboratory control model. The geometric circuit formulation and its explicit penalty dependence are developed by Nielsen 2006, §§2–4.

Krylov complexity. Given a seed $O_0$, inner product $(\cdot,\cdot)$, and generator $\mathcal L$, Lanczos recursion produces $O_n$ and amplitudes $\varphi_n(t)$. The moment $K(t)=\sum_n n\lvert\varphi_n(t)\rvert^2$ measures spreading along that basis. It is not obtained by minimizing a circuit.

Computational complexity. An algorithmic statement concerns a family of encoded instances, a promise, an accuracy and success probability, and a resource such as queries or runtime. “Hard to simulate” is meaningless without the input size and computational model. A large circuit-geometric length neither proves nor is proved by membership in a complexity class.

Format and degree. In a sharply o-minimal structure, a definable set is assigned a filtration by format and degree whose behavior under logical and geometric operations is controlled Binyamini, Novikov, and Zack 2022, §§1–3. This is specification complexity: it can bound numbers of cells or Betti numbers. It does not measure Euclidean evolution time, path-integral action, or the work required to prepare a QFT state.

Four worked task tuples

Question	Essential tuple data	Legitimate output
Prepare a regulated scalar vacuum	product reference at frequency $\omega_0$; quadratic nearest-neighbor gates; covariance error $\epsilon$; $F_2$ cost; lattice spacing $a$	gate-geometric scaling at fixed $\omega_0$, $a$, and $\epsilon$
Track an operator	thermal Kubo inner product; seed $O$; Liouvillian $[H,\cdot]$; Krylov cutoff	$b_n$, $\varphi_n(t)$, and $K(t)$ with truncation error
Estimate a correlator	encoded Hamiltonian family; oracle or gate model; additive error; failure probability	query, sample, or runtime bound as a function of instance size
Specify a definable parameter domain	chosen o-minimal structure; formula; filtration and reduction convention	bounds controlled by format $F$ and degree $D$

Holding the target symbol fixed while swapping rows changes the question. There is no paradox if the rankings reverse.

Comparison and falsification protocol

To compare two proposals, first align object type, quotient freedoms, admissible transformations, tolerance, and resource. Then give an explicit translation map. If one cost satisfies

$$c_- F_1[P]\leq F_2[\Phi(P)]\leq c_+ F_1[P]$$

for all admissible paths in a common regulated family, the minima can be bounded. Without uniform $c_\pm$, only example-by-example comparison is licensed. A continuum comparison additionally requires $c_\pm$ to be controlled as the cutoff is removed at fixed physical tolerance.

A useful adversarial test keeps $X_{\rm tar}$ fixed and changes one field at a time: allow a nonlocal gate, rescale a generator, enlarge the channel environment, choose another seed, or re-encode the input. If the conclusion changes, report the dependence rather than averaging it away.

Exercises

Hidden resource. A protocol claims constant-time preparation because every unitary is counted as one gate. Diagnose the task.

Solution

The gate alphabet contains operations of unbounded physical or descriptive complexity. The constant count is correct only for that oracle model. A physical conclusion requires decomposing the unitary into bounded, local controls and charging their duration, amplitude, bandwidth, and synthesis error.

Incomparable values. One Gaussian-state calculation uses $F_1=\int ds\sum_I\lvert Y^I\rvert$ and another uses $F_2=(\int ds\sum_I\lvert Y^I\rvert^2)^{1/2}$. Can their numerical results be equated?

Solution

No. They are different path norms. In a fixed finite generator dimension one may derive norm-equivalence bounds, but the constants can scale with the number of modes and need not survive the continuum limit. Equality requires an additional result about the optimizing path and normalization.

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

• Binyamini, Gal, Dmitri Novikov, and Benny Zack. “Sharply o-Minimal Structures and Sharp Cellular Decomposition.” arXiv:2209.10972 (2022; revised 2024). Preprint.
• Nielsen, Michael A. “A Geometric Approach to Quantum Circuit Lower Bounds.” Quantum Information & Computation 6 (2006): 213–262. Open PDF.