SAT Strikes Back: Parameter and Path Relations in Quantum Toolchains

In the foreseeable future, toolchains for quantumcomputing should offer automatic means of transforming a highlevel problem formulation down to a hardware executable form.Thereby, it is crucial to find (multiple) transformation paths thatare optimised for (hardware specific) metrics. We zoom into thispictured tree of transformations by focussing on k-SAT instancesas input and their transformation to QUBO, while consideringstructure and characteristic metrics of input, intermediate andoutput representations. Our results can be used to rate valid pathsof transformation in advance—also in automated (quantum)toolchains. We support the automation aspect by consideringstability and therefore predictability of free parameters andtransformation paths. Moreover, our findings can be used in themanifesting era of error correction (since considering structurein a high abstraction layer can benefit error correcting codes inlayers below). We also show that current research is closely linkedto quadratisation techniques and their mathematical foundation.