Benchmarking Hard Ising Instances with Energy Scrambling*

Optimization problems with planted solutions have served as a testbed for the development of quantum computers and quantum-inspired devices tailored for combinatorial optimization. We propose benchmarks of a class of instances produced by random energy scrambling, inspired by the McEliece and Niederreiter post-quantum cryptographic protocols, which allow for both solution planting and computational hardness guarantees in general. We evaluate the performance of Markov Chain Monte Carlo as well as information set decoding algorithms originally developed to attack the cryptosystem and discuss the role of these instances in quantum and Ising device benchmarking.