Efficient contraction of physically restricted PEPS
For injective 2D PEPS specified by finite-precision tensors, establish checkable boundary-mixing and conditioning promises that allow normalized bounded-support expectation values to be computed to additive error in time polynomial in input length a
Problem statement
For injective 2D PEPS specified by finite-precision tensors, establish checkable boundary-mixing and conditioning promises that allow normalized bounded-support expectation values to be computed to additive error in time polynomial in input length and . State whether a uniform parent gap suffices within the chosen class.
Lean 4
No Lean statement or proof is attached yet. Have a formalization? Share its source to add it to this problem.
Background
Even when a state has a compact PEPS description, extracting expectation values requires contraction. Worst-case hardness results obstruct a general polynomial algorithm under the corresponding complexity assumptions. Exact contraction, relative approximation of a norm, and additive approximation of a normalized observable are different computational tasks; a hardness result must specify which one and its precision promises.
What is known: Numerical boundary-MPS and corner-transfer methods often perform well, but injectivity or finite correlation length alone is not an unconditional polynomial-time certificate. Schwarz, Buerschaper and Eisert give a quasi-polynomial local-observable algorithm under explicit injectivity, gap and conditioning assumptions. This is not a general polynomial contraction theorem.
The residual is to close the algorithmic gap in a named promise family, or exhibit an obstruction preserving those promises. Specify accessible boundary data, tensor conditioning and bond-dimension scaling; the phrase 'largest natural class' has no mathematical success criterion. Keep this task separate from existence of a representation (B2), certifying the parent gap (M7) and finding tensors from a Hamiltonian.
Progress & source assessment
Source catalogue review: 4 September 2026. Improved indicates partial progress, including qualified preprint claims.
- [1]Schuch, Wolf, Verstraete, Cirac, 'Computational complexity of PEPS', PRL 98, 140506 (2007) link
- [2]Cirac, Pérez-García, Schuch & Verstraete, 'Matrix product states and projected entangled pair states: Concepts, symmetries, and theorems', Rev. Mod. Phys. 93, 045003 (2021) link
- [3]Schwarz, Buerschaper & Eisert, local observables in PEPS and quasi-polynomial algorithms link
Recorded progress
Add yours →Nothing recorded yet. A pointer to a paper the entry is missing counts.
Machine attempts
0 recordedAttempts run against the statement below and are recorded in full, including the failures. The point is to stop the next model — and the next person — from re-walking a road that is already known to end. Each attempt costs 25 credits.
No machine attempts recorded.
Sign in to run an attempt. New accounts start with enough credits for ten.
Discussion
0 notesNotes are for clarifying the statement, flagging a missing reference, or recording why an approach fails. Claimed solutions belong in a submission, where they can be reviewed.
No notes yet.
Sign in to add a note.