On the uniqueness of compiling graphs under the parity transformation
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912846768504832 |
|---|---|
| author | Dreier, Florian Lechner, Wolfgang |
| author_facet | Dreier, Florian Lechner, Wolfgang |
| contents | In this article, we establish a mathematical framework that utilizes concepts from graph theory to formalize the parity transformation, an encoding strategy for compiling optimization problems on quantum devices. We introduce the transformation as a mapping that encompasses all possible compiled hypergraphs and investigate its uniqueness properties in more detail. Specifically, by introducing so-called loop labelings, we derive an alternative expression of the preimage of any set of compiled hypergraphs under this encoding procedure when all equivalence classes of graphs are being considered. We then deduce equivalent conditions for the injectivity of the parity transformation on any subset of all equivalences classes of graphs. Through concrete examples, we demonstrate that the parity transformation is not an injective mapping, and also introduce an important class of physical layouts and their corresponding set of constraints whose preimage is uniquely determined. In addition, we provide an algorithm which is based on classical algorithms from theoretical computer science and computes a compiled physical layout in this class in polynomial time. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2401_11980 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | On the uniqueness of compiling graphs under the parity transformation Dreier, Florian Lechner, Wolfgang Quantum Physics Mathematical Physics Combinatorics In this article, we establish a mathematical framework that utilizes concepts from graph theory to formalize the parity transformation, an encoding strategy for compiling optimization problems on quantum devices. We introduce the transformation as a mapping that encompasses all possible compiled hypergraphs and investigate its uniqueness properties in more detail. Specifically, by introducing so-called loop labelings, we derive an alternative expression of the preimage of any set of compiled hypergraphs under this encoding procedure when all equivalence classes of graphs are being considered. We then deduce equivalent conditions for the injectivity of the parity transformation on any subset of all equivalences classes of graphs. Through concrete examples, we demonstrate that the parity transformation is not an injective mapping, and also introduce an important class of physical layouts and their corresponding set of constraints whose preimage is uniquely determined. In addition, we provide an algorithm which is based on classical algorithms from theoretical computer science and computes a compiled physical layout in this class in polynomial time. |
| title | On the uniqueness of compiling graphs under the parity transformation |
| topic | Quantum Physics Mathematical Physics Combinatorics |
| url | https://arxiv.org/abs/2401.11980 |