On the uniqueness of compiling graphs under the parity transformation
A new pre-print by our team has just been released on arXiv! “On the uniqueness of compiling graphs under the parity transformation”, by Florian Dreier and Wolfgang Lechner, provides an in-depth mathematical framework for the ParityQC Architecture, using concepts from graph theory.
The paper is a step forward from the research previously conducted by the team of ParityQC, focused on novel compilation strategies for the Parity Transformation [1, 2] and encoding procedures for quantum optimization and quantum computation. These include, for example, a modular parallelization method for QAOA  and parity-encoded optimization problems, and two novel techniques to perform quantum optimization with neutral atom platforms using the ParityQC Architecture [4, 5]. The Parity Transformation, which is at the foundation of the ParityQC Architecture, has also been demonstrated to enable a new universal quantum computing approach  which leads to advantages for crucial quantum algorithms such as the quantum Fourier transform.
However, a pivotal practical question related to the Parity Transformation that the paper seeks to answer, is under which circumstances non-equivalent optimization problems (those that cannot be transformed from one to the other by re-labeling) can or cannot be solved with the same compiled physical layout. In other words: how can the set of optimization problems that can be compiled to a given hypergraph under the Parity Encoding be described, and when is the set uniquely determined? Does there exist a class of physical layouts which do have this uniqueness property? In the paper, the authors study such questions in more detail and investigate the case where the products in the optimization problems consist of two-body interactions.
The authors show that the Parity Transformation can be represented mathematically as a mapping between classes of equivalent hypergraphs and collections of classes of all possible compiled hypergraphs that can be utilized for designing physical layouts for quantum devices. The paper outlines the uniqueness properties of the mapping, and how it can be applied to classes of equivalent graphs.
This work provides deeper insights into the complexities of the Parity Transformation and allows to investigate further compilation strategies for the Parity Compilation, where the challenge is to transform any combinatorial optimization problem to a physical layout with local three- and four-body plaquettes with ancilla qubits.