well-defined architecture, which in turn determines the possible connectivity among the qubits. Due to the sparse connectivity of the hardware graph, it is clear that variables in dense or fully connected graphs cannot be mapped one-to-one to qubits in the device, resulting in an overhead of the number of qubits needed for the experimental realization. This overhead is necessary because some logical qubits in $\{q_i\}$ need to be replicated among several physical (hardware) qubits in order to fulfill the connectivity requirements in the original denser graph. The problem of finding this correspondence between logical and physical qubits is what we call *the embedding problem*. A more detailed description of this problem can be found elsewhere [@Choi2008; @Choi2011; @Klymko2013; @Cai-14]. For the purpose of our discussion, we use the embedding algorithm [@Cai-14] as implemented in D-wave’s Application Programming Interface, which allows us to obtain an assignment of the $n_{l}$ logical qubits to the $n_p$ physical (hardware) qubits as the final step before the processor can be programmed to solve the optimization problem of interest. Further details on how to set the parameters of the embedded Hamiltonian can be found in Ref. . To study the number of qubits required for the 