  We investigate the computational hardness of spin-glass instances on a square
lattice, generated via a recently introduced tunable and scalable approach for
planting solutions. The method relies on partitioning the problem graph into
edge-disjoint subgraphs, and planting frustrated, elementary subproblems that
share a common local ground state, which guarantees that the ground state of
the entire problem is known a priori. Using population annealing Monte Carlo,
we compare the typical hardness of problem classes over a large region of the
multi-dimensional tuning parameter space. Our results show that the problems
have a wide range of tunable hardness. Moreover, we observe multiple
transitions in the hardness phase space, which we further corroborate using
simulated annealing and simulated quantum annealing. By investigating
thermodynamic properties of these planted systems, we demonstrate that the
harder samples undergo magnetic ordering transitions which are also ultimately
responsible for the observed hardness transitions on changing the sample
composition.
