Toward Minimum Graphic Parity Networks
Yixin Cao, Yiren Lu, Junhong Nie, Xiaoming Sun, Guojing Tian · 2025
Read Toward Minimum Graphic Parity Networks by Yixin Cao, Yiren Lu, Junhong Nie, Xiaoming Sun, Guojing Tian (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2509-10070.txt.
Introduction
Yixin Cao and 4 co-authors ask how few gates a parity network built on a graph can possibly use in a 2025 quantum computing paper. Circuits of CNOT and rotation gates sit inside many quantum algorithms, and a graphic parity network realises a graph's edges with CNOTs alone while returning every wire to its starting state. Synthesising the cheapest such circuit matters most for optimisation problems written as Ising models.
For a connected graph the authors prove a floor: the gate count must reach at least the edge count plus the vertex count minus one. When the shortest cycle runs to five or more, that floor rises by a term growing faster than the vertex count. A simple randomised construction nearly matches the stronger floor, and the paper starts sorting which graphs hit the basic bound exactly.
Catalog record
| CREATOR | Yixin Cao, Yiren Lu, Junhong Nie, Xiaoming Sun, Guojing Tian |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 62 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2509-10070
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Toward Minimum Graphic Parity Networks Yixin Cao, Yiren Lu, Junhong Nie, Xiaoming Sun, Guojing Tian Abstract Quantum circuits composed of CNOT and R z R_{z} are fundamental building blocks of many quantum algorithms, so optimizing the synthesis of such quantum circuits is crucial. We address this problem from a theoretical perspective by studying the graphic parity network synthesis problem. A graphic parity network for a graph G G is a quantum circuit composed solely of CNOT gates where each edge of G G is represented in the circuit, and the final state of the wires matches the original input. We aim to synthesize graphic parity networks with the minimum number of gates, specifically for quantum algorithms addressing combinatorial optimization problems with Ising formulations. We demonstrate that a graphic parity network for a connected graph with n n vertices and m m edges requires at least m + n − 1 m+n-1 gates. This lower bound can be improved to m + Ω ( m ) = m + Ω ( n 1.5 ) m+\Omega(m)=m+\Omega(n^{1.5}) when the shortest cycle in the graph has a length of at least five. We complement this result with a simple randomized algorithm that synthesizes a graphic parity network with expected m + O ( n 1.5 log n ) m+O(n^{1.5}\sqrt{\log n}) gates. Additionally, we begin exploring connected graphs that allow for graphic parity networks with exactly m + n − 1 m+n-1 gates. We conjecture that all such graphs belong to a newly defined graph class. Furthermore, we present a linear-time algorithm for synthesizing minimum graphic parity networks for graphs within this class. However, this graph class is not closed under taking induced subgraphs, and we show that recognizing it is 𝖭𝖯 \mathsf{NP} -complete, which is complemented with a fixed-parameter tractable algorithm parameterized by the treewidth. 1 Introduction Over the past decade, there has been significant progress in quantum computation, with advancements in both experimental and theoretical aspects [ 5 , 17 , 25 , 7 ] . Compared to classical circuits, quantum circuits are more sensitive to noise, which is one of the bottlenecks limiting the scalability of quantum computers. Each quantum gate in a circuit may introduce some noise to the output quantum state, and as the circuit size increases, the accumulated noise can overwhelm any meaningful computational results. Since we are still in the noisy intermediate-scale quantum ( nisq ) era, there exists a fundamental necessity to minimize the number of gates used in quantum circuits [ 23 , 32 , 15 , 34 ] , especially for two-qubit gates, which are even more vulnerable to noise than single-qubit gates [ 7 , 20 ] . Subcircuits consisting only of cnot and R_{z} gates appear in many quantum algorithms, such as quantum simulation [ 24 ] , quantum approximate optimization algorithm ( qaoa ) [ 10 ] , variational quantum eigensolver ( vqe ) [ 28 ] , etc. To optimize such quantum circuits with massive \{\textsc{cnot},R_{z}\} -only components, a widely employed method is to independently resynthesize these components, and this problem has been extensively treated by parity network synthesis [ 1 , 12 ] . Parity network is a cnot -only quantum circuit. In a sense, cnot gates can be viewed as the quantum analog of classical xor gates. 1 1 1 To make our work accessible to a general audience, we will minimize the use of quantum computing jargon in the main text. Consequently, our definitions and explanations might seem imprecise to quantum experts. For a more detailed and rigorous treatment, please refer to appendix A . A cnot gate applied to qubit wires i and j , denoted by \textsc{cnot}(i,j) , changes the value of wire j to a\oplus b , where a,b\in\mathbb{F}_{2} are the values of wires i and j , respectively. Here, wire i is the control wire , and wire j is the target wire . A cnot circuit is called a parity network for a set family S if every element of S appears in the circuit as a term at some intermediate point, and the final values of the wires are the same as the original input, denoted by {x_{1},x_{2},\dots,x_{n}\in\mathbb{F}_{2}} [ 1 ] , and we say that a wire has the term A=\{a_{1},\ldots,a_{|A|}\} on it if the value of a wire evaluates to x_{a_{1}}\oplus\cdots\oplus x_{a_{|A|}} . The set family S defines a hypergraph. In certain applications, it is actually a graph, namely all terms in S are two-element sets. For example, the maximum cut problem asks for a bipartition of the vertex set of a graph such that the number of edges between the two parts is maximized. The well-known quantum adiabatic algorithm ( qaa ) [ 11 ] and qaoa [ 10 ] use the following formulation to solve the maximum cut problem on a graph G : \max_{x\in\{-1,1\}^{|V(G)|}}\sum_{(u,v)\in E(G)}\frac{1-x_{u}x_{v}}{2}. A principal component of the quantum circuit of these algorithms is a parity network with each term being a two-element set. A similar approach has been taken by many authors [ 33 , 35 , 36 , 37 , 4 , 3 , 2 , 30 ] , and there have been preliminary physical demonstrations of these quantum algorithms on nisq devices [ 27 , 14 ] . Recently, heuristic attempts have been made to synthesize small parity networks [ 1 , 12 , 9 ] . As far as we know, however, none of them is accompanied with analysis of performance. Such parity networks where all terms in S are two-element sets are called graphic parity networks , and see fig. 1 as examples. This paper is mainly concerned with the graphic parity network synthesis problem. \{1\} \{2\} \{3\} \{4\} \{{1,2}\} \{2\} \{{3,4}\} \{4\} \{{1,3}\} \{3\} \{{1,4}\} \{4\} \{{2,3}\} \{3\} \{1\} \{2\} \{3\} \{4\} \gundef (a) \{1\} \{2\} \{3\} \{4\} \{{1,2}\} \{{1,3}\} \{{1,4}\} \{{2,3}\} \{{3,4}\} \{3\} \{2\} \{4\} \{1\} \{2\} \{3\} \{4\} \gundef (b) Figure 1 : Two graphic parity networks for the graph with edges \{\{1,2\},\{1,3\},\{1,4\},\{2,3\},\{3,4\}\} , shown in fig. 2(a) . Each line represents a qubit wire labeled at the left. We use i\boldsymbol{\cdot}\!\!-\!\!\oplus j to denote \textsc{cnot}(i,j) . Indicated at the above right corner of \oplus is the resulting term of this operation. The black terms correspond to the sets, and the red do not. 1 2 3 4 (a) 1 2 3 4 5 p \cdots (b) Figure 2: (a) A chordal graph, and (b) K_{2,p} , which can be made chordal by adding the edge (1,2) . Our contributions. The number of gates in a graphic parity network is called its size . Let G be the input graph, and let n and m denote the numbers of vertices and edges, respectively, in G . A trivial graphic parity network is in the fashion of Figure 1(a) ; i.e., generating an edge and cleaning it up immediately. This leads to a trivial upper bound of 2m , which is tight, as witnessed by graphs in which each component consists of one or two vertices. On the other hand, the definition implies a trivial lower bound, m , which, although tight, is uninteresting because it can only hold on edgeless graphs. Our