What a Planted Solution Gives Away: Known Energies, Hard Witnesses, and Planted Spin Glasses on the Cubic Lattice

Planted spin-glass instances, whose ground state is known by construction, are standard benchmarks for quantum annealers and Ising machines. We ask what a planted solution gives away, in terms of the cut polytope and computational complexity. Gauged to the planted state, frustrated-loop instances are exactly the conic combinations of cycle-inequality facet normals of the cut cone and ferromagnetic bonds, so the cycle relaxation is tight on them; for tile planting the energy is even known outright. What can remain hard is finding a ground state, and we show that it does. Deciding whether a three-dimensional tile instance is planted is NP-complete with four of its six cell classes, and finding a ground state then takes time 2^Θ(N^(2/3)) for N spins under the exponential time hypothesis; a recent preprint claims to refute that hypothesis, which would void only this lower bound. The decision remains NP-complete on the benchmark's own two-class mixture, and finding a ground state remains NP-hard for frustrated loops with ±1 couplings on the cubic torus. Cells with at most two ground-state pairs, by contrast, give a linear system over the two-element field. Finally, loop planting caps frustration at one over the girth, and the supremum of a graph's weighted frustration is its maximum over the facets of the cut cone.