  A computational phase transition in a classical or quantum system is a
non-analytic change in behavior of an order parameter which can only be
observed with the assistance of a nontrivial classical computation. Such phase
transitions, and the computational observables which detect them, play a
crucial role in the optimal decoding of quantum error-correcting codes and in
the scalable detection of measurement-induced phenomena. In this work we show
that computational phase transitions and observables can also provide important
physical insight on the phase diagram of a classical statistical physics
system, specifically in the context of the dislocation-mediated melting of a
two-dimensional antiferromagnetic (AF) crystal. In the solid phase, elementary
dislocations disrupt the bipartiteness of the underlying square lattice, and as
a result, pairs of dislocations are linearly confined by string-like AF domain
walls. It has previously been argued that a novel AF tetratic phase can arise
when double dislocations proliferate while elementary dislocations remain
bound. However, since elementary dislocations carry AF Ising gauge flux, no
local order parameter can distinguish between AF and paramagnetic (PM) tetratic
regimes, and consequently there is no thermodynamic phase transition separating
the two regimes. Nonetheless, we demonstrate that it is possible to
algorithmically construct a staggered magnetization which distinguishes the AF
and PM tetratic regimes by "pairing" dislocations, which requires an
increasingly nontrivial classical computation as elementary dislocation pairs
increase in density and unbind. We discuss both algorithm-dependent and
"intrinsic" algorithm-independent computational phase transitions in this
setting, the latter of which includes a transition in one's ability to
consistently sort atoms into two sublattices to construct a well-defined
staggered magnetization.
