The Inverse Ising Problem and Planted Solutions

Abstract. Spin glasses are the archetypal native benchmark problem for any novel algorithm or computing architecture. The fact that a spin-glass-like Hamiltonian on a non-planar topology falls typically under the NP-hard complexity class is the main reason why these systems are of interest to the algorithm development and benchmarking community. In recent years, highly tunable spin-glass benchmarks have been developed to probe the efficiency of both classical and novel quantum architectures, like the D-Wave Inc. DW2X device. Because the number of qubits in quantum annealers is doubling every two years, soon it will be difficult to generate validation libraries of spin-glass problems that are also difficult to solve while being good benchmarks. As such, planting solutions – the process in which one first generates the solution to a problem and then builds the corresponding cost function around it – has gained much interest recently. Approaches based on the planting of random-constraint-satisfaction-problem formulas are straightforward, however the produced benchmark problems are too easy to challenge state-of-the-art algorithms and computing architectures. The generation of planted solutions is intimately related to the inverse Ising problem where, again, a model Hamiltonian is built around an existing data set. In this working group we attempt to tackle these difficult problems using novel approaches.