Model-based diagnosis in combinational digital circuits: An application with potential for quantum speedup

Only recently, it was demonstrated that optimization on the D-Wave 2X quantum annealer can outperform other sequential algorithms on CMOS-based hardware. However, the benchmark problems were tailored to yield an advantage over classical local search algorithms. Furthermore, including state-of-the-art optimization techniques that are not sequential in nature closed the gap between quantum and classical optimization techniques. Therefore, the question arises if there are real-world application problems small enough in the number of variables such that they can be optimized on current quantum hardware, and where quantum annealing might excel over classical optimization techniques. Here we demonstrate that model-based diagnosis in combinational circuits is an ideal problem for quantum enhanced optimization and the first application problem with potential for quantum speedup. Benchmark instances generated from this real-world application tend to be considerably harder than any specially-tuned random spin-glass instances (excluding post selection). We address the relevancy of many-body interactions beyond quadratic in current quantum annealers, as well as connectivity requirements to solve real-world problems.