Quantum Annealers Chain Strengths: A Simple Heuristic to Set Them All

Quantum annealers (QA), such as D-Wave systems, become increasingly efficient and competitive at approximating combinatorial optimization problems. However, solving problems that do not directly map the chip topology remains challenging for this type of quantum computer. The creation of logical qubits as sets of interconnected physical qubits overcomes limitations imposed by the sparsity of the chip at the expense of increasing the problem size and adding new parameters to optimize. This paper explores the advantages and drawbacks provided by the structure of the logical qubits and the impact of the rescaling of coupler strengths on the minimum spectral gap of Ising models. We show that logical qubits encoded over densely connected physical qubits require a lower chain strength to maintain the ferromagnetic coupling. We also analyze the optimal chain strength variations considering different minor embeddings of the same instance. This experimental study suggests that the chain strength can be optimized for each instance. We design a heuristic that optimizes the chain strength using a very low number of shots during the preprocessing step. This heuristic outperforms the default method used to initialize the chain strength on D-Wave systems, increasing the quality of the best solution by up to \(17.2\%\) for tested instances on the max-cut problem.