Minimizing minor embedding energy: an application in quantum annealing

A significant challenge in quantum annealing is to map a real-world problem onto a hardware graph of limited connectivity. When the problem graph is not a subgraph of the hardware graph, one might employ minor embedding in which each logical qubit is mapped to a tree of physical qubits. Pairwise interactions between physical qubits in the tree are set to be ferromagnetic with some coupling strength $$F<0$$F<0 . Here we address the theoretical question of what the best valueFshould be in order to achieve unbroken trees in the pre-quantum-processing. The sum of |F| for each logical qubit is defined as minor embedding energy, and the best valueFis obtained when the minor embedding energy is minimized. We also show that our new analytical lower bound on |F| is a tighter bound than that previously derived by Choi (Quantum Inf Process 7:193–209, 2008). In contrast to Choi’s work, our new method depends more delicately on minor embedding parameters, which leads to a higher computational cost.