A problem graph having one or more odd cycles is embedded in a quantum processor. The quantum processor includes a plurality of qubits and coupling devices, each coupling device operable to provide controllable communicative coupling between a respective pair of the plurality of qubits to form an interconnected topology. Embedding may, for example, be realized by mapping each vertex of the problem graph to a respective single qubit; mapping each edge of the problem graph to a respective single coupling device, where for pairs of qubits, each qubit of the pair is mapped to a respective pair of vertices. The problem graph may include one or more sub-graphs, one or more of the sub-graphs being a bipartite K3,3 graph.
