λEnter Calculus CompanionRegistered manuscripts, kept distinct

Manuscript Oai265-A@2 · Oai265-A.tex · section · c0a34a45

The separate algorithmic interface

Stage 3: PEPS existence, algorithms, and approximation budgets › The separate algorithmic interface · lines 910–929

Back to manuscript

An algorithmic theorem must fix at least:

  1. finite encodings and bit lengths for the local matrices;

  2. the gap and uniqueness promises and how they are supplied;

  3. the accuracy, normalization, and global phase convention;

  4. output tensor dimensions and entry precision;

  5. running time and success probability;

  6. which contraction, normalization, or verification tasks are included.

Existence of tensors with arbitrary real entries does not itself bound their bit complexity or give a method to find them.

Generic PEPS contraction has strong complexity obstructions SchuchEtAl. Those generic results do not, without a promise-preserving reduction, prove hardness of the particular unique, uniformly gapped ground-state class frozen here.

Nearby in this section