Complexity and Continuum Resource Costs

Complexity measures the minimum cost of a specified preparation or transformation. In QFT, reference states, allowed gates, penalties, tolerance, and regulator all affect that optimization, so a complexity value has meaning only with its task definition.

Enter this chapter

Begin with What Task Does Complexity Answer? to specify the target, controls, cost, and approximation tolerance.

Helpful background. Why Continuum QFT Does Not Factorize Naively explains why continuum subregions cannot automatically be treated as qubit registers. Direct Sums, Tensor Products, and Index Structure supplies the finite-regulator tensor language. Basis Dependence, Computational Complexity, and No Universal Cure shows how a change of representation can change an algorithmic cost, while Operator Spreading and Scrambling supplies the dynamics that Krylov measures summarize. These are useful entry routes, not conditions for reading the overview.

Topics

1. What Task Does Complexity Answer? — Supplies the comparison tuple and the four-way distinction among resource notions.
2. Circuit Complexity in Quantum Field Theory — Defines regulated approximation by admissible circuits.
3. Cost Geometry, Gate Sets, and Reference States — Develops Nielsen geometry and its normalization choices.
4. State, Unitary, Channel, and Operator Complexity — Derives the inequivalent quotient freedoms of four targets.
5. Gaussian-State Complexity — Turns covariance data into controlled solvable examples.
6. Mixed-State, Purification, and Formation Complexity — Compares optimizations over spectra, bases, and ancillas.
7. Interacting-Field Complexity — States what perturbative and variational estimates actually control.
8. Path-Integral and Euclidean Preparation Complexity — Separates Euclidean protocols from proposal-specific costs.
9. Krylov and Operator-Growth Complexity — Derives the Lanczos-chain probability distribution.
10. Complexity with Symmetry, Gauge, and Locality Constraints — Restricts admissible transformations before minimizing.
11. Regulator Dependence and Continuum Complexity — Tests divergent terms and finite remainders across matched schemes.
12. Operational Preparation Cost and Energy-Constrained Bounds — Connects abstract paths to bounded physical controls.
13. Complexity, Chaos, and Computational Claims — Gives a claim matrix and explicit nonimplications.

How the ideas fit together

Geometric circuit methods replace gate sequences by paths generated by allowed operators, with a chosen cost assigned to their directions Nielsen 2006, §§ 2–4, PDF. Gaussian fields provide tractable examples, but changing penalties or the reference changes the optimization problem.

Krylov growth and Euclidean preparation answer related but distinct questions; neither is automatically the minimum circuit cost. A continuum comparison must also specify how the entire task changes with the cutoff. Similar time dependence does not establish equality between complexity measures or prove quantum chaos.

The comparison below separates the assumptions and tests needed for these different conclusions.

Dictionary from objects to optimization problems

Complexity proposals compared by target task, admissible class, cost, reference, tolerance, regulator, continuum scaling, operational interpretation, and residual ambiguity.

Proposal	Target task	Admissible class and cost	Reference and tolerance	Regulator and continuum question	Operational or invariant content	Principal ambiguity
State circuit	Prepare ρtarget from ρreference	Declared local or Gaussian gates; size, depth, or path length	State reference; trace, fidelity, or covariance error	Fixed physical error as lattice spacing tends to zero	Preparation cost for the chosen gate model	Reference, stabilizer quotient, and gate penalties
Unitary circuit	Synthesize a unitary on a declared domain	Gates modulo permitted phases; size or depth	Identity or reference unitary; channel error	Energy-constrained domain and regulator matching	Implementation resource on that domain	Precision, generator normalization, and nonlocal gates
Channel complexity	Implement a completely positive channel	Allowed dilations, ancillas, and controls; circuit or control cost	Reference channel and channel distance	Energy constraint and environment model	Implementation resource after declared minimization	Dilation freedom and uncharged environment preparation
Krylov complexity	Evolve one seed operator in a Lanczos basis	Fixed Liouvillian and inner product; first Krylov-index moment	Seed and inner product fix the basis	Ultraviolet spectral tail and order of limits	Basis-relative operator spread	Seed, thermal inner product, and truncation
Computational complexity	Estimate or simulate an observable for an instance family	Algorithms satisfying a promise; time, queries, samples, or memory	Input encoding, error, and success probability	Family of regulated instances and scaling variable	Invariant only under stated reductions	Encoding and computational model
Sharp format and degree	Specify a definable set or function	Formulas in a fixed structure; filtration pair (F, D)	Presentation and reduction rules	Not a state-preparation continuum limit	Descriptive-geometric bounds	Choice of structure and presentation

Where to go next

Continue to Quantum Error Correction in Continuum Fields to define the logical observables, encoding, noise, and recovery criterion.

References

• Nielsen, Michael A. “A Geometric Approach to Quantum Circuit Lower Bounds.” Quantum Information & Computation 6 (2006): 213–262. Open PDF.