The Perils of Embedding for Sampling Problems*

Current quantum annealers impose constraints on the structure of the cost Hamiltonian due to the connectivity of the qubits. This means that in order to solve many problems of interest, one is required to embed the native graph into the hardware graph. The effect of embedding for sampling is more pronounced than for optimization, since one needs to consider states at all energies, and not just the ground states. We argue that as the problem size grows, the chance of a sample being in the logical subspace is exponentially suppressed. It is therefore necessary to construct post-processing techniques to evade this exponential sampling overhead, to project from the embedded distribution one is physically sampling from, back to the logical space. We observe that the simplest projection technique, majority vote, can fail quite spectacularly at preserving distribution properties. Furthermore, we show that even with care, one cannot avoid biasing the statistics. On the positive side, we demonstrate a new projection technique which substantially out-performs majority vote.