A recent development in solving challenging combinatorial optimization problems is the introduction of hardware that performs optimization by quantum annealing. Exploiting this hardware to solve a problem requires first solving a graph minor-embedding problem, which is also apparently intractable. Motivated by this application, we consider the special case of finding a minor-embedding of a planar graph in a grid graph. We introduce two algorithmic approaches to the problem, based on planarity-testing techniques. For one approach, we provide an implementation and an experimental evaluation demonstrating its potential.
Recently, Mančinska and Roberson proved that two graphs G and
G′ are quantum isomorphic if and only if they admit the same number of homomorphisms from all planar graphs. We extend this result to planar #CSP with any pair of sets
F and
F′ of real-valued, arbitrary-arity constraint functions. Graph homomorphism is the special case, in which each of
F and
F′ contains a single symmetric 0-1-valued binary constraint function. Our treatment uses the framework of planar Holant problems. To prove that quantum isomorphic constraint function sets give the same value on any planar #CSP instance, we apply a novel form of holographic transformation of Valiant, using the quantum permutation matrix
U defining the quantum isomorphism. Due to the noncommutativity of
U ’s entries, it turns out that this form of holographic transformation is only applicable to planar Holant. To prove the converse, we introduce the quantum automorphism group
Qut(F) of a set
F of constraint functions/tensors and characterize the intertwiners of
Qut(F) as the signature matrices of planar \(\text{Holant}{\mathcal {F}\,|\,\mathcal {EQ})\) quantum gadgets. Then, we define a new notion of (projective) connectivity for constraint functions and reduce their arity while preserving their inclusion in the original intertwiner space. Finally, to address the challenges posed by generalizing from 0-1 valued to real-valued constraint functions, we adapt a technique of Lovász in the classical setting for isomorphisms of real-weighted graphs to the setting of quantum isomorphisms.