% This is samplepaper.tex, a sample chapter demonstrating the
% LLNCS macro package for Springer Computer Science proceedings;
% Version 2.20 of 2017/10/04
%
\documentclass[runningheads]{llncs}
%
\usepackage{graphicx}
\usepackage{amsmath}
\usepackage{amssymb}
%\usepackage{braket}
\usepackage{cleveref}
\usepackage{tikz}
\input{Qcircuit.tex}
\newcommand{\innerp}[2]{\mbox{$\bra{#1}\,#2\,\rangle$}}
\newcommand{\outerp}[2]{\mbox{$\ket{#1}\,\bra{#2}$}}
\newcommand{\triplep}[3]{\mbox{$\bra{#1}#2\ket{#3}$}}
\newcommand{\gatem}[1]{\mathsf{#1}}
\newcommand{\set}[1]{\{\,#1\,\}}
\newcommand{\braket}[1]{\langle #1 \rangle}
% Used for displaying a sample figure. If possible, figure files should
% be included in EPS format.
%
% If you use the hyperref package, please uncomment the following line
% to display URLs in blue roman font according to Springer's eBook style:
% \renewcommand\UrlFont{\color{blue}\rmfamily}

\newcommand{\explode}{\backslash\!\backslash}
\newsavebox{\fmbox}
\newenvironment{fmquote}[1]
{\vspace{1ex}\begin{center}\begin{lrbox}{\fmbox}\begin{minipage}{#1}\centering\vspace{0.5ex}}
{\vspace{0.2ex}\end{minipage}\end{lrbox}\fbox{\usebox{\fmbox}}\end{center}\vspace{1ex}}

\newenvironment{flquote}[1]
{\vspace{1ex}\begin{center}\begin{lrbox}{\fmbox}\begin{minipage}{#1}\vspace{0.5ex}}
{\vspace{0.2ex}\end{minipage}\end{lrbox}\fbox{\usebox{\fmbox}}\end{center}\vspace{1ex}}

\newcommand{\Ptime}{\mathsf{P}}
\newcommand{\NP}{\mathsf{NP}}
\newcommand{\sharpP}{\mathsf{\#P}}
\newcommand{\BQP}{\mathsf{BQP}}
\makeatletter
\newcommand{\raisedminus}{%
  \raisebox{0.2em}{\small $\m@th\scriptstyle{-}$}%
}
\newcommand{\mone}{\!\raisedminus\!1\!}
\newcommand{\um}[1]{{\raisedminus #1}}
\newcommand{\raisedplus}{%
  \raisebox{0.2em}{$\m@th\scriptscriptstyle{+}$}%
}
\newcommand{\up}[1]{{\raisedplus #1}}
\makeatother

\begin{document}
%
\title{Reducing Quantum Circuits Via Graphical Polymatroids
%\thanks{}
}
%
%\titlerunning{General Quantum Circuits and Polymatroids}
% If the paper title is too long for the running head, you can set
% an abbreviated paper title here
%
\author{Chaowen Guan\inst{1}\and %\orcidID{0000-1111-2222-3333} \and
Kenneth W. Regan\inst{1}}
%Second Author\inst{2,3}\orcidID{1111-2222-3333-4444} \and
%Third Author\inst{3}\orcidID{2222--3333-4444-5555}}
%%
%\authorrunning{F. Author et al.}
%% First names are abbreviated in the running head.
%% If there are more than two authors, 'et al.' is used.
%%
\institute{University at Buffalo (SUNY)}
%Springer Heidelberg, Tiergartenstr. 17, 69121 Heidelberg, Germany
%\email{lncs@springer.com}\\
%\url{http://www.springer.com/gp/computer-science/lncs} \and
%ABC Institute, Rupert-Karls-University Heidelberg, Heidelberg, Germany\\
%\email{\{abc,lncs\}@uni-heidelberg.de}}
%
\maketitle              % typeset the header of the contribution
%
\begin{abstract}
Certain much-studied bases for universal quantum circuits, such as the \emph{Clifford+T library}, allow their circuits $C$ to be translated into equivalent circuits of the form $C' = \mathsf{H}^{\otimes h} \mathsf{D} \mathsf{H}^{\otimes h}$, where $\mathsf{D}$ is diagonal in the computational basis and $h$ is the number of binary nondeterministic (wlog., Hadamard) gates in $C$.  It is well-known that when $\mathsf{D}$ consists only of $\mathsf{Z}$ and controlled-$\mathsf{Z}$ gates it defines a graph and that the resulting \emph{graph states} typify Clifford states.  We extend this scheme for the diagonal non-Clifford gates controlled-$\mathsf{S}$ and $\mathsf{T}$ and controlled-$\mathsf{T}$ and gates of finer fractional phase $1/K$.  The translation goes not to graphs but to \emph{graphical $K$-polymatroids}, which we define for $K \geq 4$, $K = 2^k$ as well as the standard $K = 2$ notion.  We augment these polymatroids with positive and negative isolated nodes in order to streamline the theory of generalized Tutte-Grothendieck invariants in the case $K = 2$ and indicate possible extension to $K \geq 4$.  We investigate the possibility of translations that reduce $K$.  They are impossible in general unless $\mathsf{P} = \mathsf{P^{\#P}}$, but we explore potential positive cases and approximations.

%\keywords{Graphs \and polymatroids \and quantum circuits.}
\end{abstract}
%
%
%
\section{Polymatroids and Generalized Graphs}
%The Tutte polynomial defined over graphs, was first introduced by William T. Tutte \cite{Tut09,Tut67,Tut54}. It has been shown that every graph is associated with an Tutte polynomial. It is a two-variable polynomial that can give us a considerable amount of information about the graph--the number of spanning trees, the number of spanning subgraphs, the number of ways to color, to name just a few. Many problems about graphs can be reduced to problems of finding and evaluating the Tutte polynomial at certain points.
%
%Crapo \cite{Cra69} and Brylawski \cite{Bry72} extended the definition of Tutte polynomial to matroids. Brylawski also identified the relevance of the Grothendieck ring in his paper, and this led to the convention of naming ``generalized Tutte-Grothendieck invariants''. In 1979, Oxley and Welsh proved a set of conditions for a graph invariant to be called a \emph{generalized Tutte-Grothendieck invariant} \cite{OW79}. This result is known as ``recipe theorem''. Since then a considerable amount of work focused on identifying connections between the Tutte polynomial and various different areas, of which a well-known discovery is the connection with \emph{Jones polynomial} by Vaughan Jones \cite{Jon97}.
%
%In 1993, Oxley and Whittle further extended the theory of Tutte invariants to 2-polymatroids (whose definition will be review in \Cref{sec:mtd}) \cite{OxWh93}. They introduced a two-variable polynomial named \emph{2-polynomatroid rank generating function}.


A \emph{matroid} is defined by a set $U$ and a function $f$ from finite subsets of $U$ to $\mathbb{N}$ that obeys the rules:

\begin{enumerate}
\item
$f(\emptyset) = 0$;
\item
for all $a \in U$, $f(\{a\}) \leq 1$;
\item
if $A \subseteq B$ then $f(A) \leq f(B)$; and
\item
if $A \subseteq B$ and $c \notin B$ then $f(A \cup \{c\}) - f(A) \geq f(B \cup \{c\}) - f(B)$.
\end{enumerate}

\noindent
The bellwether example is that the function $f$ giving the rank of sets of vectors in an ordinary vector space obeys these axioms.  We can get finite instances by letting $U$ be the set of columns of some $m \times n$ matrix $M$ over some field.

If we fix an integer $K$ and relax the second axiom to read $(\forall a \in U)\;f(\{a\}) \leq K$, then we define a \emph{$K$-polymatroid}.  A simple way to make one is to take a matrix with $Kn$ columns, partition the columns into blocks of $K$ consecutive ones, and define $U'$ to be the set of $n$-many blocks.  Then subsets of $U'$ are subsets of $U$ that respect the partition.  The function $f'$ induced by $f$ on subsets of $U'$ defines a {$K$-polymatroid}.  For example with $K = 2$:
\[
M = \begin{array}{|cc|cc|cc|cc|}
\hline
1 & 0 & 1 & 0 & 1 & 0 & 1 & 0\\
0 & 1 & 0 & 0 & 0 & 0 & 0 & 1\\
0 & 0 & 0 & 1 & 0 & 0 & 0 & 1\\
0 & 0 & 0 & 0 & 0 & 1 & 0 & 1\\
\hline
\end{array}
\]
Another canonical kind of example comes from undirected graphs $G = (V,E)$ where $E$ may contain not only self-loops but also multi-edges.  For any subset $A$ of edges, define $f(A)$ to be the number of vertices collectively touched by edges in $A$.  Then $(G,f)$ is a $2$-polymatroid.  The same holds if we augment $G$ with ``edges'' that touch no vertex, called \emph{circles}.  

Not all (finite) $2$-polymatroids arise from (finite) graphs in this manner.  The paritioned matrix $M$ is an example.  Each of its blocks has rank 2, so must be represented by an edge in $G$, not a loop or circle.  The edges must collectively touch four nodes and there must be four of them.  Every pair of blocks has rank $3$, so no double edges are allowed.  Any assignment of four simple edges among four nodes must have two non-incident edges, whose corresponding pair would have rank $4$, a contradiction.  

Those that do arise from graphs (with circles) are called \emph{graphical $2$-polymatroids}, G2PMs for short.  In matroid theory, two graphs are considered to define the same G2PM if they differ only in the addition or deletion of isolated nodes.  We will motivate retaining isolated nodes and giving them signs later in this paper.  

We would like to generalize G2PMs further to involve notions of ``half'' and ``quarter'' edges and loops, and so on.  Consider any function $w: E \to \mathbb{R}^+$ giving a positive weight to each edge.  For any node $v$ and $A \subseteq E$ define
\[
g_A(v) = \max\set{w(a): a \in A,\;a \text{ incident to } v},
\]
with $g_A(v) = 0$ if no edge in $A$ is incident to $v$.  Then define
\[
f_w(A) = \sum_{v \in V} g_A(v).
\]
Note that circles in all cases contribute zero to the rank and that isolated nodes are immaterial.  To see that this defines a polymatroid, we need only observe that if $A \subseteq B \subseteq E$, then for any node $v$ and edge $c \notin B$ incident to $v$,
\[
g_{B \cup \{c\}}(v) - g_B(v) \leq g_{A \cup \{c\}}(v) - g_A(v).
\]
In words, the impact of adding $c$ to raise the maximum weight among edges incident to $v$ can only be less when more edges are already present in $B$ than in $A$, never more.  We call a polymatroid arising this way a \emph{graphical $K$-polymatroid}, where $K/2$ is the maximum weight of an edge or $K$ the maximum weight of a loop (abbreviated G$K$PM, or GPM without specifying $K$).  

We are most interested in having $K$ a power of $2$, $K = 2^k$ with $k \geq 1$, where no loop has weight more than $K/2$.  Then we note an alternate proof by embedding $(G,f_w)$ into a graphical $2$-polymatroid $G'$ on $nK/2$ nodes.  We also want $G'$ not to have multiple edges or loops.  Assign $K/2$ nodes $v_1,\dots,v_{K/2}$ to every (non-isolated) node $v$ of $G$.  For each loop $e$ of weight $w$ at a node $v$, give $G'$ edges $(v_1,v_2),(v_3,v_4),\dots$ plus a final loop if $w$ is odd.  For each edge $(u,v)$ of weight $w$, $u \neq v$, place edges $(u_i,v_i)$ for $i = 1,\dots,w$.  

Then subsets $A$ of $E$ correspond to subsets $A'$ of $E'$ that are unions of the images of the edges in $A$.  By the strict ordering of $v_1,\dots,v_{K/2}$, $f_w(A) = f'(A')$ where $f'$ is the ordinary count of nodes touched by $A'$ in $G'$.  Since $(G',f')$ is a G2PM, the submodularity property is inherited by $(G,f_w)$.  

Section~\ref{QCGPM} shows how a wide class of quantum circuits yields graphical polymatroids where $K$ depends on the fractional phase of gates in the circuit.  Section~\ref{GPMreduction} shows how so-called \emph{stabilizer circuits} giving GPMs with $K = 4$ can be transformed into graphs with $K = 2$ that are equivalent in important respects.  This exemplifies and motivates our general problem of ``reducing'' $K$.  Section~\ref{GTGI} begins building mathematical tools to pursue this problem by characterizing the principal family of \emph{generalized Tutte-Grothendieck invariants} of G2PMs (see \cite{OxWh93,Nob06}) in a simplified manner.  The simplification involves adjoining ``negative isolated nodes'' to G2PMs (which formally do not have ordinary isolated nodes either) and carries independent interest.  Section~\ref{reduce} attempts to extend these invariants to GPMs $G'$ of higher $K$.  The above embedding of $G'$ into a G2PM does not accomplish the properties desired when extending these invariants, basically in the respects that $\mathbb{Z}_K$ differs from $\mathbb{Z}_2^k$, so a notion of ``promoting'' partial loops and edges is proposed.  A short conclusions section assesses the relevance of the new developments and frames new open problems.






%%%%%%%%%%%%%%
\section{Quantum Circuits and Graphical Polymatroids}\label{QCGPM}

%To study quantum computing, most of the time we don't need to understand quantum physics. A quantum circuit is a compact representation of a quantum system.
A quantum circuit consists of some number $n$ of \emph{qubit lines} and some number $s$ of gates acting on qubits. Quantum \emph{stabilizer circuits} use only gates from the set $\{ \mathsf{H}, \mathsf{S}, \mathsf{Z}, \mathsf{CZ}\}$ where
\[
\mathsf{H} = \frac{1}{\sqrt{2}} \begin{bmatrix} 1 & 1 \\ 1 & \mone \end{bmatrix}, \quad
\mathsf{S} = \begin{bmatrix} 1 & 0 \\ 0 & i \end{bmatrix}, \quad
\mathsf{Z} = \begin{bmatrix} 1 & 0 \\ 0 & \mone \end{bmatrix}, \quad
\mathsf{CZ} = \begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & \mone \end{bmatrix}.
\]
These gates generate the \emph{Clifford group} on $n$ qubits.  Note $\mathsf{Z} = \mathsf{S}^2$.  Other common gates obtainable by composing these include $\mathsf{NOT} = \mathsf{HZH}$ and the two-qubit $\mathsf{CNOT}$ (``controlled-not'') gate analogously using $\mathsf{H}$ and $\mathsf{CZ}$.  

Each circuit $C$ of these gates yields a $2^n \times 2^n$ unitary matrix whose entry for any row label $x \in \{0,1\}^n$ and column label $y \in \{0,1\}^n$ gives the complex \emph{amplitude} $\braket{y | C | x}$.  Stabilizer circuits are distinguished by these amplitudes being computable in deterministic polynomial time (\cite{Got98}, see also \cite{AaGo04}).  

\emph{Graph-state circuits} are the special case consisting of an initial Hadamard gate on each qubit line, then $\mathsf{Z}$, $\mathsf{CZ}$, and $\mathsf{S}$ gates placed ad-lib, then final Hadamard gates to close each line.  The $\mathsf{Z}$, $\mathsf{CZ}$, and $\mathsf{S}$ gates all commute so the order of placement between the Hadamard banks does not matter and cancellations can be removed.  The (surviving) $\mathsf{CZ}$ gates become edges and any $\mathsf{Z}$ gates become self-loops.  A possible leftover $\mathsf{S}$ gate on each line becomes a \emph{half-loop}, which takes us into the domain of G4PMs.

The following gates are also diagonal in the standard basis (so they commute with $\mathsf{Z}$, $\mathsf{CZ}$, and $\mathsf{S}$), but adding any one of them moves from the realm of known polynomial simulation to the full power of universal quantum computation:
\[
\mathsf{CS} = \begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & i \end{bmatrix},\quad
\mathsf{T} = \begin{bmatrix} 1 & 0 \\ 0 & e^{i\pi/4} \end{bmatrix}, \quad
\mathsf{CT} = \begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 &  e^{i\pi/4} \end{bmatrix},\quad
\mathsf{R_{z,k}} = \begin{bmatrix} 1 & 0 \\ 0 & e^{\frac{i\pi}{2^{k-1}}} \end{bmatrix},
\]
together with $\mathsf{CR_{z,k}}$ (controlled-$\mathsf{R_{z,k}}$).  The $\mathsf{CR_{z,k}}$ gates are all symmetric in that it doesn't matter which of the two qubit lines is considered the ``control' and which the ``target.'' The above gates up to $k=n$, plus the two-qubit swap gate, suffice for a standard and efficient construction of the \emph{quantum Fourier transform} (QFT) on $n$ qubits.  One can also define double-controlled versions of these gates, and so on, but doing so would involve us with hypergraphs.  A great deal of interest has centered on adding only $\mathsf{T}$ to the ``library'' of Clifford gates.

Circuits of the form $\mathsf{H}^{\otimes n} \mathsf{D} \mathsf{H}^{\otimes n}$, where $\mathsf{D}$ is diagonal in the standard basis, are known as \emph{instantaneous} quantum circuits, and polynomial-size familes of them are called \emph{IQP} circuits \cite{BJS10,BMS17}.  Little generality is lost by limiting $\mathsf{D}$ to the $\mathsf{R_{z,j}}$ and singly-controlled $\mathsf{CR_{z,j}}$ gates, $j = 1$ to $k$, whereupon we have a G$K$PM analogue of graph-state circuits.  We now show the sense in which GPM circuits typify all circuits over the Clifford+$\mathsf{CR_{z,k}}$ library.

\begin{theorem}\label{graphsim}
Given an $n$-qubit quantum circuit $C$ of $s$ Clifford+$\mathsf{CR_{z,k}}$ gates, we can construct, in time $O(s)$, a G$K$PM circuit $C'$ such that
\[
\braket{0^n | C | 0^n} = \sqrt{h}\braket{0^h | C' | 0^h},
\]
where $h$ is the number of Hadamard gates in $C'$ and $K = 2^k$.
\end{theorem}

The use of all-zero inputs and outputs may look special, but any desired input $x$ and test condition $y$ can be coded by incorporating $\mathsf{NOT}$ gates on the appropriate lines before and after $C$.  The proof uses a main theorem of \cite{RCG18} that constructs a polynomial $q_C$ over the ring of integers modulo $K$ that encodes all relevant information about $C$.  It follows that if $q_C = q_{C'}$, after appropriate substitution of the zero inputs and outputs, then $C$ and $C'$ are equivalent for those inputs.

\begin{proof}
Initially $q_C = 0$ and each qubit line $i$ has $x_i$ as its current \emph{annotation} $u_i$. In general, suppose the nondeterministic variables $y_1,\cdots, y_{\ell-1}$ have been allocated while transcribing the first $s-1$ gates of $C$.  The next gate falls into one of these cases:

\begin{itemize}
  \item
Hadamard gate on line $i$: Allocate a new variable $y_\ell$, do $q_C \;\text{+=}\; \frac{K}{2}u_i y_\ell$, and reassign $u_i$ to be $y_\ell$;
\item
$\mathsf{R_{z,j}}$ gate on line $i$: $q_C \;\text{+=}\; 2^{k-j}u_i^2$, no other change.  
  \item
$\mathsf{CR_{z,j}}$ gate on lines $i$ and $j$: $q_C \;\text{+=}\; 2^{k-j}u_i u_j$, no other change.
\end{itemize}

\noindent
At the end of each qubit line $i$, we can identify $z_i$ with the variable last denoted by $u_i$.  If $u_i$ never changes; i.e., if there are no Hadamard gates on line $i$, then we must insert two.  Let $h$ be the final number of nondeterministic variables, which here is the number of Hadamard gates in $C$.  If the input and output are $\ket{0}^{\otimes n}$, so that all $x_i$ and $z_i$ are zeroed out, we are left with a quadratic polynomial $q_C$ in the variables $y_1,\dots,y_h$ over $\mathbb{Z}_{K}$.  Schematically we obtain sets $L$ and $E$ and coefficients $a_i,b_{i,j} \in \{1,\dots,K-1\}$ so that
%
\begin{equation}\label{eq:quadraticform}
q_C(y_1, \cdots, y_h) = \sum_{i \in L} a_i y_i^2 + \sum_{(i,j) \in E} b_{i,j} y_i y_j \pmod{K}.
\end{equation}
%
The $a_i$ then become the weights on loops and $b_{i,j}$ the weights on edges.  Now we begin creating $C'$ by allocating Hadamard gates at the beginning and end of $h$ qubit lines.  Since the $x_i$ and $z_i$ variables will be zeroed out, the only active variables are the $y_1,\dots,y_h$ from the initial bank of Hadamard gates.  Since no other Hadamard gates will be added, the identification of $u_1,\dots,u_h$ with them for the purpose of the above rules will not change.  Because the other gates all commute, the order of placing them does not matter.  Thus for each $i$, we place as many $\mathsf{Z},\mathsf{S},\mathsf{T},\dots,\mathsf{R_{z,j}},\dots$ gates as needed to count up to $a_i$.  Then for each $(i,j) \in E$ we similarly place controlled gates to represent $b_{i,j}$ in binary notation.  Then $q_{C'}$ with its inputs and outputs zeroed is exactly the same as $q_C$ with its $x_i$ and $z_i$ zeroed.  The conclusion follows by the main theorem of \cite{RCG18}; the extra factor of $\sqrt{h}$ comes because $C'$ has $2h$ not $h$ Hadamard gates.
\end{proof}

For a simple example with $K = 2$, so the result is a simple graph, consider this circuit from the \emph{Qiskit} textbook's illustration of Grover's algorithm, followed by the result of substituting $\gatem{X} = \gatem{HZH}$ and simplifying $\gatem{HH} = \gatem{I}$ and $\gatem{ZZ} = \gatem{I}$.  The bar is standard notation for a controlled-$\gatem{Z}$ gate.
\[
\Qcircuit @C=1.0em @R=0.75em @!R {
& \gate{\gatem{H}} & \gate{\gatem{X}} & \ctrl{1} & \gate{\gatem{X}} & \gate{\gatem{H}} & \gate{\gatem{Z}} & \ctrl{1} & \gate{\gatem{H}} & \qw & \push{\rule{.6em}{0em}=\rule{.6em}{0em}} & & \gate{\gatem{Z}} & \gate{\gatem{H}} & \ctrl{1} & \gate{\gatem{H}} & \ctrl{1} & \gate{\gatem{H}} & \qw\\
& \gate{\gatem{H}} & \gate{\gatem{X}} & \ctrl{-1} & \gate{\gatem{X}} & \gate{\gatem{H}} & \gate{\gatem{Z}} & \ctrl{-1} & \gate{\gatem{H}} & \qw & \push{\rule{.6em}{0em}=\rule{.6em}{0em}} & & \gate{\gatem{Z}} & \gate{\gatem{H}} & \ctrl{-1} & \gate{\gatem{H}} & \ctrl{-1} & \gate{\gatem{H}} & \qw
}
\]
The circuit at right gives the polynomial 
\[
x_1^2 + x_2^2 + x_1 y_1 + x_2 y_2 + y_1 y_2  + y_1 y_3 + y_2 y_4 + y_3 y_4 + y_3 z_1 + y_4 z_2.
\]
Upon zeroing $x_1,x_2,z_1,z_2$ this leaves $y_1 y_2 + y_1 y_3 + y_2 y_4 + y_3 y_4$.  The graph $G'$ is just the undirected 4-cycle.  On input $\ket{00}$, the first circuit outputs $\ket{00}$ with certainty.  The circuit $C'$ on input $\ket{0000}$ produces
\[
\frac{1}{2}(\ket{0000} + \ket{0101} + \ket{1010} + \ket{1111}).
\]
This agrees with Theorem~\ref{graphsim} because $h = 4$ so $\sqrt{h} = 2$.  For a second example, note the simulation of the ternary \emph{Toffoli gate} over the Clifford+$\gatem{CS}$ library:
\[
\Qcircuit @C=1.0em @R=0.75em @!R {
& \ctrl{1} & \qw & &           
     & \qw & \qw & \qw & \ctrl{1} & \qw & \qw & \qw & \qw & \ctrl{1} & \qw & \ctrl{2} & \qw & \qw\\
& \ctrl{1} & \qw & \push{\rule{.3em}{0em}=\rule{.3em}{0em}} & 
     & \qw & \ctrl{1} & \gate{\gatem{H}} & \gate{\gatem{Z}} & \gate{\gatem{H}} & \ctrl{1} & \ctrl{1} & \gate{\gatem{H}} & \gate{\gatem{Z}} & \gate{\gatem{H}} & \qw & \qw & \qw\\
& \targ & \qw & & 
     & \gate{\gatem{H}} & \gate{\gatem{S}} & \qw & \qw & \qw & \gate{\gatem{Z}} & \gate{\gatem{S}} & \qw & \qw & \qw & \gate{\gatem{S}} &\gate{\gatem{H}} & \qw
}
\]
This has $K = 4$.  The polynomial is:
\[
2x_3 y_1 + x_2 y_1 + 2x_2 y_2 + 2 x_1 y_2 + 2 y_2 y_3 + 3 y_1 y_3 + 2 y_3 y_4  + 2 x_1 y_4 + 2 y_4 z_2 + x_1 y_1 + 2 y_1 z_3.
\]
Zeroing out the inputs and outputs leaves $2 y_2 y_3 + 3 y_1 y_3 + 2 y_3 y_4$.  This does not yield a graph---there is a ``one-and-a-half-edge'' between node $1$ and node $3$.  The result is a G4PM.  The original circuit on input $\ket{000}$ outputs $\ket{000}$ with certainty since both controls (of the Toffoli gate) fail.  The new one is:
\[
\Qcircuit @C=1.5em @R=0.75em @!R {
& \gate{\gatem{H}} & \qw & \ctrl{2}                & \ctrl{2}  & \qw  & \qw        & \qw &  \qw      & \qw  & \gate{\gatem{H}} & \qw\\
& \gate{\gatem{H}} & \qw & \qw                     &  \qw      & \qw  & \ctrl{1}   & \qw &  \qw      & \qw  & \gate{\gatem{H}} & \qw\\
& \gate{\gatem{H}} & \qw & \gate{\gatem{S}} & \ctrl{-2} & \qw  & \ctrl{-1} & \qw  & \ctrl{1} & \qw & \gate{\gatem{H}} & \qw\\
& \gate{\gatem{H}} & \qw  &        \qw             & \qw       &  \qw & \qw        & \qw  & \ctrl{-1} & \qw & \gate{\gatem{H}} & \qw
}
\]
On input $\ket{0000}$ it produces a state where $\ket{0000}$ has amplitude $0.5$, as required, as does $\ket{0010}$, while
$\ket{0101}$, $\ket{0111}$, $\ket{1101}$, and $\ket{1111}$ each have amplitude $\frac{1}{\sqrt{8}}$.  Note that if the circuit had an earlier Hadamard gate on line $1$, giving a variable $y_0$ in place of $x_1$, then the resulting term $y_0 y_1$ in place of $x_1 y_1$ would not have been zeroed, yielding a half-edge between the corresponding nodes.  This would happen upon using multiple Toffoli gates, which together with $\gatem{H}$ suffice for universal quantum computation \cite{Shi03}.  Indeed, adding any one non-Clifford gate to $\gatem{H},\gatem{S},gatem{CZ}$ yields a universal set.  The $\mathsf{CS}$ gate in this instances notionally produces the term $y_0^2 y_1^2$, but for binary arguments this is the same as $y_0 y_1$.

If we tried to model a Toffoli gate on lines $i,j,k$ directly, this would involve terms of degree $3$ such as $y_i y_j y_k$, which in turn would lead  into notions of \emph{hypergraphs}, whose edges may consist of more than two nodes.  The above example shows how the Clifford+$\mathsf{CR_{z,k}}$ libraries can already accomplish a kind of ``degree reduction.''  We have our eye instead on the goal of reducing $K$ in quantum circuits.  We do not expect full success down to G2PMs for everything, as that would yield $\mathsf{BQP} = \mathsf{P}$, but we will impart new algebraic and combinatorial considerations by way of attacking it.

A final simple example is that the one-qubit circuit $C$ consisting of one $\gatem{T}$ gate sandwiched between two $\gatem{H}$ gates gives a single node with a ``quarter-loop,'' which gives $K = 8$ and the polynomial $y_1^2$ over $\mathbb{Z}_8$.  Then $C$ is already a G8PM circuit and $\triplep{0}{C}{0} = \sqrt{\frac{1}{2} + \sqrt{\frac{1}{8}}}$.  This illustrates that having higher $K$ leads to the introduction of radicals into algebraic expressions associated to the amplitudes.  For the graphical polymatroids $G$ associated to the quantum circuits $C$, we write $a(G)$ for $\triplep{0}{C}{0}$ and $p(G)$ for $|\triplep{0}{C}{0}|^2$, figuratively the \emph{amplitude} and \emph{probability} of $G$ (for all-zero input to produce all-zero output).  The functions $a(G)$ and $p(G)$ are both multiplicative on unions of disjoint graphs.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Stabilizer Circuits and GPM Reduction}\label{GPMreduction}

In the case of a stabilizer circuit, that is, with $\gatem{H},\gatem{S},gatem{CZ}$ only (and $\gatem{Z} = \gatem{S}^2$), we obtain a G4PM $G$ that consists of a graph with half-loops but not half-edges.  We show how to convert $G$ into a G2PM $G'$---indeed, $G'$ will be a graph---such that $a(G') = p(G)$.  Thus we can ``reduce'' $K = 4$ to $K = 2$ while computing a quantity related to the original amplitude $a(G)$.  If this reduction were possible for G4PMs with half-edges as well as half-loops, then $\mathsf{BQP}$ would equal $\mathsf{P}$, since every G2PM arises from a stabilizer circuit and those have deterministic polynomial-time simulation (see \cite{Got98}).  \emph{Why} there are obstacles to extending the reduction will stimulate the rest of this paper.  For now we prove the one successful reduction case.

\begin{theorem}
Given any stabilizer circuit $C$ we can efficiently build a graph $G''$ such that $a(G'') = |\triplep{0}{C}{0}|^2$.
\end{theorem}

\begin{proof}
Take $G = (V,E,w)$ to be the G4PM obtained from $C$ after converting $q_C$ in the proof of Theorem~\ref{graphsim}.  Define $U_1$ to be the set of nodes $i$ such that $q_C$ has $y_i^2$, and $U_3$ the set of $j$ for which $q_C$ has $3y_j^2$.  If $U_1$ and $U_3$ are both empty, then $G$ is already a graph and $a(G)$ is real, so we are essentially done---we just make $G''$ include a duplicate copy of $G$ and we get $a(G'') = a(G)^2 = p(G)$.  Otherwise, we execute the following steps to create $G''$:

\begin{enumerate}
\item
Remove all loops and half-loops from nodes in $U_1 \cup U_3$ Nodes outside these sets may have loops.
\item
For all distinct $u,v \in U_1$, if $(u,v)$ is an edge then delete it; if it is not an edge then create it.  Do likewise with $U_3$.
\item
Make a duplicate copy of the graph as it stands now and define $U'_1,U'_3$ in mirror fashion.  
\item
For every $u \in U_1$ and $v' \in U'_3$, create the edge $(u,v')$.  Likewise make a complete bipartite subgraph between $U_3$ and $U'_1$.
\item
Choose any one node $u \in U_1 \cup U_3$.
\item
For every node $v$ such that the graph currently has an edge between $u$ and $v$ (including $v$ in the mirror copy):
\begin{itemize}
\item
for all nodes $w$ including $v$ itself: flip the edge/non-edge status of $(v,w)$.
\end{itemize}
\item
The node $u$ will then be isolated, and it is optional to delete it.
\end{enumerate}

Finally make $G''$ by adding two new nodes with an edge between them and nothing else; this is done merely to multiply the amplitude by $\frac{1}{2}$ so as to give $a(G'') = p(G)$ exactly.  The remaining details are as in the statement and proof of Lemma~5.2 in \cite{GuRe19}.  To supply some intuititon from that proof: At Step 5, there will not be any terms $u^2$ or $2 u^2$ remaining in $q_C$ by the deletion in step~1, but there may be terms $2uv$ (where $v$ can come from the mirror copy).  The loop over $w$ then substitutes $u$ by the sum of all the other variables (including $v$, which adds a term $2v^2$ to $q_C$ modulo $4$).  This makes the variable $u$ disappear, so we delete its node, but then must rectify the count corresponding to the use of $h$ in Theorem~\ref{graphsim}.
\end{proof}

For an example, consider the 3-qubit graph-state circuit $C$:
\[
\Qcircuit @C=1.5em @R=0.75em @!R {
& \gate{\gatem{H}} & \qw & \gate{\gatem{S}}                & \qw  & \ctrl{1}  & \qw  & \qw        & \qw &  \gate{\gatem{H}} & \qw\\
& \gate{\gatem{H}} & \qw & \gate{\gatem{S}}                & \qw  & \ctrl{-1}  & \qw & \ctrl{1}   & \qw &  \gate{\gatem{H}} & \qw\\

& \gate{\gatem{H}} & \qw & \gate{\gatem{S^*}}           & \qw  & \qw        & \qw  & \ctrl{-1} & \qw  & \gate{\gatem{H}} & \qw\\
}
\]
The quadratic form $q_C$ modulo $K = 4$ is $y_1^2 + y_2^2 + 3y_3^2 + 2 y_1 y_2 + 2 y_2 y_3$, so $U_1 = \{1,2\}$ and $U_3 = \{3\}$.  We have $\triplep{000}{C}{000} = \frac{1}{2}(1 + i)$, which gives probability $\frac{1}{8}$.   Here is how the G2PM $G_C$ is transformed into the graph $G''$ (without adding the extra disjoint edge):


\begin{figure}[ht]\label{G1}
\begin{center}
\tikzset{every picture/.style={line width=0.75pt}} %set default line width to 0.75pt        

\begin{tikzpicture}[x=0.75pt,y=0.75pt,yscale=-0.5,xscale=0.5]
%uncomment if require: \path (0,420); %set diagram left start at 0, and has height of 420

%Shape: Circle [id:dp02137051123592726] 
\draw  [fill={rgb, 255:red, 0; green, 0; blue, 0 }  ,fill opacity=1 ] (41.78,51.44) .. controls (41.67,46.46) and (45.61,42.34) .. (50.58,42.21) .. controls (55.55,42.09) and (59.67,46.03) .. (59.78,51) .. controls (59.89,55.97) and (55.95,60.1) .. (50.98,60.22) .. controls (46.01,60.34) and (41.89,56.41) .. (41.78,51.44) -- cycle ;
%Shape: Circle [id:dp2993718974285762] 
\draw  [fill={rgb, 255:red, 0; green, 0; blue, 0 }  ,fill opacity=1 ] (41.78,111.44) .. controls (41.67,106.46) and (45.61,102.34) .. (50.58,102.21) .. controls (55.55,102.09) and (59.67,106.03) .. (59.78,111) .. controls (59.89,115.97) and (55.95,120.1) .. (50.98,120.22) .. controls (46.01,120.34) and (41.89,116.41) .. (41.78,111.44) -- cycle ;
%Shape: Circle [id:dp8340571083435868] 
\draw  [fill={rgb, 255:red, 0; green, 0; blue, 0 }  ,fill opacity=1 ] (41.78,171.44) .. controls (41.67,166.46) and (45.61,162.34) .. (50.58,162.21) .. controls (55.55,162.09) and (59.67,166.03) .. (59.78,171) .. controls (59.89,175.97) and (55.95,180.1) .. (50.98,180.22) .. controls (46.01,180.34) and (41.89,176.41) .. (41.78,171.44) -- cycle ;
%Straight Lines [id:da9013756314500607] 
\draw [line width=3]    (50.78,51.22) -- (50.78,111.22) -- (50.78,171.22) ;

%Shape: Circle [id:dp5650436777784424] 
\draw  [fill={rgb, 255:red, 0; green, 0; blue, 0 }  ,fill opacity=1 ] (380,51.21) .. controls (379.89,46.24) and (383.83,42.11) .. (388.81,41.99) .. controls (393.78,41.87) and (397.9,45.8) .. (398.01,50.78) .. controls (398.11,55.75) and (394.17,59.88) .. (389.2,60) .. controls (384.23,60.12) and (380.11,56.19) .. (380,51.21) -- cycle ;
%Shape: Circle [id:dp2797044784451841] 
\draw  [fill={rgb, 255:red, 0; green, 0; blue, 0 }  ,fill opacity=1 ] (380,111.21) .. controls (379.89,106.24) and (383.83,102.11) .. (388.81,101.99) .. controls (393.78,101.87) and (397.9,105.8) .. (398.01,110.78) .. controls (398.11,115.75) and (394.17,119.88) .. (389.2,120) .. controls (384.23,120.12) and (380.11,116.19) .. (380,111.21) -- cycle ;
%Shape: Circle [id:dp06355151881967647] 
\draw  [fill={rgb, 255:red, 0; green, 0; blue, 0 }  ,fill opacity=1 ] (380,171.21) .. controls (379.89,166.24) and (383.83,162.11) .. (388.81,161.99) .. controls (393.78,161.87) and (397.9,165.8) .. (398.01,170.78) .. controls (398.11,175.75) and (394.17,179.88) .. (389.2,180) .. controls (384.23,180.12) and (380.11,176.19) .. (380,171.21) -- cycle ;
%Straight Lines [id:da5979533533610912] 
\draw [line width=3]    (389,111) -- (389,171) ;

%Shape: Circle [id:dp7535149160892065] 
\draw  [fill={rgb, 255:red, 0; green, 0; blue, 0 }  ,fill opacity=1 ] (450,51.21) .. controls (449.89,46.24) and (453.83,42.11) .. (458.81,41.99) .. controls (463.78,41.87) and (467.9,45.8) .. (468.01,50.78) .. controls (468.11,55.75) and (464.17,59.88) .. (459.2,60) .. controls (454.23,60.12) and (450.11,56.19) .. (450,51.21) -- cycle ;
%Shape: Circle [id:dp4392327639783895] 
\draw  [fill={rgb, 255:red, 0; green, 0; blue, 0 }  ,fill opacity=1 ] (450,111.21) .. controls (449.89,106.24) and (453.83,102.11) .. (458.81,101.99) .. controls (463.78,101.87) and (467.9,105.8) .. (468.01,110.78) .. controls (468.11,115.75) and (464.17,119.88) .. (459.2,120) .. controls (454.23,120.12) and (450.11,116.19) .. (450,111.21) -- cycle ;
%Shape: Circle [id:dp8336809156381897] 
\draw  [fill={rgb, 255:red, 0; green, 0; blue, 0 }  ,fill opacity=1 ] (450,171.21) .. controls (449.89,166.24) and (453.83,162.11) .. (458.81,161.99) .. controls (463.78,161.87) and (467.9,165.8) .. (468.01,170.78) .. controls (468.11,175.75) and (464.17,179.88) .. (459.2,180) .. controls (454.23,180.12) and (450.11,176.19) .. (450,171.21) -- cycle ;
%Straight Lines [id:da3328479454653843] 
\draw [line width=3]    (459,111) -- (459,171) ;

%Notched Right Arrow [id:dp4460913290692867] 
\draw   (80,105) -- (110,105) -- (110,100) -- (130,110) -- (110,120) -- (110,115) -- (80,115) -- (85,110) -- cycle ;
%Shape: Circle [id:dp25283918997762256] 
\draw  [fill={rgb, 255:red, 0; green, 0; blue, 0 }  ,fill opacity=1 ] (173,52.21) .. controls (172.89,47.24) and (176.83,43.11) .. (181.81,42.99) .. controls (186.78,42.87) and (190.9,46.8) .. (191.01,51.78) .. controls (191.11,56.75) and (187.17,60.88) .. (182.2,61) .. controls (177.23,61.12) and (173.11,57.19) .. (173,52.21) -- cycle ;
%Shape: Circle [id:dp04835833846191662] 
\draw  [fill={rgb, 255:red, 0; green, 0; blue, 0 }  ,fill opacity=1 ] (173,112.21) .. controls (172.89,107.24) and (176.83,103.11) .. (181.81,102.99) .. controls (186.78,102.87) and (190.9,106.8) .. (191.01,111.78) .. controls (191.11,116.75) and (187.17,120.88) .. (182.2,121) .. controls (177.23,121.12) and (173.11,117.19) .. (173,112.21) -- cycle ;
%Shape: Circle [id:dp4161917149623082] 
\draw  [fill={rgb, 255:red, 0; green, 0; blue, 0 }  ,fill opacity=1 ] (173,172.21) .. controls (172.89,167.24) and (176.83,163.11) .. (181.81,162.99) .. controls (186.78,162.87) and (190.9,166.8) .. (191.01,171.78) .. controls (191.11,176.75) and (187.17,180.88) .. (182.2,181) .. controls (177.23,181.12) and (173.11,177.19) .. (173,172.21) -- cycle ;
%Straight Lines [id:da21076635416517164] 
\draw [line width=3]    (182,112) -- (182,172) ;

%Shape: Circle [id:dp4779538089137749] 
\draw  [fill={rgb, 255:red, 0; green, 0; blue, 0 }  ,fill opacity=1 ] (243,52.21) .. controls (242.89,47.24) and (246.83,43.11) .. (251.81,42.99) .. controls (256.78,42.87) and (260.9,46.8) .. (261.01,51.78) .. controls (261.11,56.75) and (257.17,60.88) .. (252.2,61) .. controls (247.23,61.12) and (243.11,57.19) .. (243,52.21) -- cycle ;
%Shape: Circle [id:dp9663720991446234] 
\draw  [fill={rgb, 255:red, 0; green, 0; blue, 0 }  ,fill opacity=1 ] (243,112.21) .. controls (242.89,107.24) and (246.83,103.11) .. (251.81,102.99) .. controls (256.78,102.87) and (260.9,106.8) .. (261.01,111.78) .. controls (261.11,116.75) and (257.17,120.88) .. (252.2,121) .. controls (247.23,121.12) and (243.11,117.19) .. (243,112.21) -- cycle ;
%Shape: Circle [id:dp25541362742211504] 
\draw  [fill={rgb, 255:red, 0; green, 0; blue, 0 }  ,fill opacity=1 ] (243,172.21) .. controls (242.89,167.24) and (246.83,163.11) .. (251.81,162.99) .. controls (256.78,162.87) and (260.9,166.8) .. (261.01,171.78) .. controls (261.11,176.75) and (257.17,180.88) .. (252.2,181) .. controls (247.23,181.12) and (243.11,177.19) .. (243,172.21) -- cycle ;
%Straight Lines [id:da7399327808134892] 
\draw [line width=3]    (252,112) -- (252,172) ;

%Notched Right Arrow [id:dp8386751612377021] 
\draw   (310,105) -- (340,105) -- (340,100) -- (360,110) -- (340,120) -- (340,115) -- (310,115) -- (315,110) -- cycle ;
%Shape: Circle [id:dp7232056276655492] 
\draw  [fill={rgb, 255:red, 0; green, 0; blue, 0 }  ,fill opacity=1 ] (560,51.21) .. controls (559.89,46.24) and (563.83,42.11) .. (568.81,41.99) .. controls (573.78,41.87) and (577.9,45.8) .. (578.01,50.78) .. controls (578.11,55.75) and (574.17,59.88) .. (569.2,60) .. controls (564.23,60.12) and (560.11,56.19) .. (560,51.21) -- cycle ;
%Shape: Circle [id:dp341370261730898] 
\draw  [fill={rgb, 255:red, 0; green, 0; blue, 0 }  ,fill opacity=1 ] (560,111.21) .. controls (559.89,106.24) and (563.83,102.11) .. (568.81,101.99) .. controls (573.78,101.87) and (577.9,105.8) .. (578.01,110.78) .. controls (578.11,115.75) and (574.17,119.88) .. (569.2,120) .. controls (564.23,120.12) and (560.11,116.19) .. (560,111.21) -- cycle ;
%Shape: Circle [id:dp7500337577699479] 
\draw  [fill={rgb, 255:red, 0; green, 0; blue, 0 }  ,fill opacity=1 ] (560,171.21) .. controls (559.89,166.24) and (563.83,162.11) .. (568.81,161.99) .. controls (573.78,161.87) and (577.9,165.8) .. (578.01,170.78) .. controls (578.11,175.75) and (574.17,179.88) .. (569.2,180) .. controls (564.23,180.12) and (560.11,176.19) .. (560,171.21) -- cycle ;
%Straight Lines [id:da6546123255736456] 
\draw [line width=3]    (569,111) -- (569,171) ;

%Shape: Circle [id:dp3610397856604355] 
\draw  [fill={rgb, 255:red, 0; green, 0; blue, 0 }  ,fill opacity=1 ] (631.78,51.44) .. controls (631.67,46.46) and (635.61,42.34) .. (640.58,42.21) .. controls (645.55,42.09) and (649.67,46.03) .. (649.78,51) .. controls (649.89,55.97) and (645.95,60.1) .. (640.98,60.22) .. controls (636.01,60.34) and (631.89,56.41) .. (631.78,51.44) -- cycle ;
%Shape: Circle [id:dp352424577696558] 
\draw  [fill={rgb, 255:red, 0; green, 0; blue, 0 }  ,fill opacity=1 ] (630,111.21) .. controls (629.89,106.24) and (633.83,102.11) .. (638.81,101.99) .. controls (643.78,101.87) and (647.9,105.8) .. (648.01,110.78) .. controls (648.11,115.75) and (644.17,119.88) .. (639.2,120) .. controls (634.23,120.12) and (630.11,116.19) .. (630,111.21) -- cycle ;
%Shape: Circle [id:dp45433312007352034] 
\draw  [fill={rgb, 255:red, 0; green, 0; blue, 0 }  ,fill opacity=1 ] (630,171.21) .. controls (629.89,166.24) and (633.83,162.11) .. (638.81,161.99) .. controls (643.78,161.87) and (647.9,165.8) .. (648.01,170.78) .. controls (648.11,175.75) and (644.17,179.88) .. (639.2,180) .. controls (634.23,180.12) and (630.11,176.19) .. (630,171.21) -- cycle ;
%Notched Right Arrow [id:dp7522819180347922] 
\draw   (490,105) -- (520,105) -- (520,100) -- (540,110) -- (520,120) -- (520,115) -- (490,115) -- (495,110) -- cycle ;
%Straight Lines [id:da0421951436163972] 
\draw [line width=3]    (389,111) -- (459,171) ;

%Straight Lines [id:da7693150283560573] 
\draw [line width=3]    (389,171) -- (459,51) ;

%Straight Lines [id:da5737128023251963] 
\draw [line width=3]    (389,51) -- (459,171) ;

%Straight Lines [id:da6909418588125265] 
\draw [line width=3]    (389,171) -- (459,111) ;

%Straight Lines [id:da840099886241719] 
\draw [line width=3]    (569,171) -- (639,171) ;

%Shape: Circle [id:dp06579654106454624] 
\draw   (368.5,51) .. controls (368.5,39.67) and (377.68,30.5) .. (389,30.5) .. controls (400.33,30.5) and (409.5,39.67) .. (409.5,51) .. controls (409.5,62.32) and (400.33,71.5) .. (389,71.5) .. controls (377.68,71.5) and (368.5,62.32) .. (368.5,51) -- cycle ;
%Straight Lines [id:da21482306148961783] 
\draw    (450,190) -- (470,190) ;

%Straight Lines [id:da37496332338843663] 
\draw [line width=3]    (569,171) -- (640.78,51.22) ;

%Straight Lines [id:da2569188471747952] 
\draw [line width=3]    (569,171) -- (639,111) ;

%Curve Lines [id:da04044266395299223] 
\draw [line width=3]    (640.78,51.22) .. controls (695.5,51) and (694.5,171) .. (640,170) ;

%Curve Lines [id:da21215438106281836] 
\draw [line width=3]    (640,170) .. controls (706.5,173) and (641.5,239) .. (639,171) ;

%Straight Lines [id:da23978177610282025] 
\draw    (550,70) -- (590,30) ;

%Straight Lines [id:da4473059894164966] 
\draw    (550,30) -- (590,70) ;

% Text Node
\draw (23,50) node    {$S$};
% Text Node
\draw (23,110) node    {$S$};
% Text Node
\draw (23,170) node    {$S^{3}$};
% Text Node
\draw (152.5,51) node    {$U_{1}$};
% Text Node
\draw (152.5,111) node    {$U_{1}$};
% Text Node
\draw (152.5,171) node    {$U_{3}$};
% Text Node
\draw (280.5,52) node    {$U'_{1}$};
% Text Node
\draw (280.5,112) node    {$U'_{1}$};
% Text Node
\draw (280.5,172) node    {$U'_{3}$};
\end{tikzpicture}
\vspace{-3ex}
\caption{Transformation of G2PM $G$ into graph $G''$ giving $a(G'') = 2p(G)$.}
\end{center}
\end{figure}

\noindent
The graph $G''$ has $a(G'') = \frac{1}{4}$.  The two other choices of $u$ in step~5 give markedly different graphs but the same value of $a(G'')$.  Notice that one of them isolates a vertex other than $u$; it is OK to keep or delete it.



\begin{figure}[ht]\label{G2G3}
\begin{center}
\tikzset{every picture/.style={line width=0.75pt}} %set default line width to 0.75pt        

\begin{tikzpicture}[x=0.75pt,y=0.75pt,yscale=-0.5,xscale=0.5]
%uncomment if require: \path (0,420); %set diagram left start at 0, and has height of 420

%Shape: Circle [id:dp6346428979843324] 
\draw  [fill={rgb, 255:red, 0; green, 0; blue, 0 }  ,fill opacity=1 ] (21.5,240.72) .. controls (21.39,235.75) and (25.33,231.62) .. (30.3,231.5) .. controls (35.27,231.38) and (39.39,235.31) .. (39.5,240.28) .. controls (39.61,245.25) and (35.67,249.38) .. (30.7,249.5) .. controls (25.73,249.62) and (21.61,245.69) .. (21.5,240.72) -- cycle ;
%Shape: Circle [id:dp11951576646324313] 
\draw  [fill={rgb, 255:red, 0; green, 0; blue, 0 }  ,fill opacity=1 ] (21.5,300.72) .. controls (21.39,295.75) and (25.33,291.62) .. (30.3,291.5) .. controls (35.27,291.38) and (39.39,295.31) .. (39.5,300.28) .. controls (39.61,305.25) and (35.67,309.38) .. (30.7,309.5) .. controls (25.73,309.62) and (21.61,305.69) .. (21.5,300.72) -- cycle ;
%Shape: Circle [id:dp0310300267859287] 
\draw  [fill={rgb, 255:red, 0; green, 0; blue, 0 }  ,fill opacity=1 ] (21.5,360.72) .. controls (21.39,355.75) and (25.33,351.62) .. (30.3,351.5) .. controls (35.27,351.38) and (39.39,355.31) .. (39.5,360.28) .. controls (39.61,365.25) and (35.67,369.38) .. (30.7,369.5) .. controls (25.73,369.62) and (21.61,365.69) .. (21.5,360.72) -- cycle ;
%Straight Lines [id:da8382704034191841] 
\draw [line width=3]    (30.5,300.5) -- (30.5,360.5) ;

%Shape: Circle [id:dp07399925757002213] 
\draw  [fill={rgb, 255:red, 0; green, 0; blue, 0 }  ,fill opacity=1 ] (91.5,240.72) .. controls (91.39,235.75) and (95.33,231.62) .. (100.3,231.5) .. controls (105.27,231.38) and (109.39,235.31) .. (109.5,240.28) .. controls (109.61,245.25) and (105.67,249.38) .. (100.7,249.5) .. controls (95.73,249.62) and (91.61,245.69) .. (91.5,240.72) -- cycle ;
%Shape: Circle [id:dp15585766898463693] 
\draw  [fill={rgb, 255:red, 0; green, 0; blue, 0 }  ,fill opacity=1 ] (91.5,300.72) .. controls (91.39,295.75) and (95.33,291.62) .. (100.3,291.5) .. controls (105.27,291.38) and (109.39,295.31) .. (109.5,300.28) .. controls (109.61,305.25) and (105.67,309.38) .. (100.7,309.5) .. controls (95.73,309.62) and (91.61,305.69) .. (91.5,300.72) -- cycle ;
%Shape: Circle [id:dp5558033862015441] 
\draw  [fill={rgb, 255:red, 0; green, 0; blue, 0 }  ,fill opacity=1 ] (91.5,360.72) .. controls (91.39,355.75) and (95.33,351.62) .. (100.3,351.5) .. controls (105.27,351.38) and (109.39,355.31) .. (109.5,360.28) .. controls (109.61,365.25) and (105.67,369.38) .. (100.7,369.5) .. controls (95.73,369.62) and (91.61,365.69) .. (91.5,360.72) -- cycle ;
%Straight Lines [id:da0167533969048399] 
\draw [line width=3]    (100.5,300.5) -- (100.5,360.5) ;

%Notched Right Arrow [id:dp9762384239190125] 
\draw   (128.5,294.63) -- (147.4,294.63) -- (147.4,289.5) -- (160,299.75) -- (147.4,310) -- (147.4,304.88) -- (128.5,304.88) -- (133.63,299.75) -- cycle ;
%Straight Lines [id:da40805585208925144] 
\draw [line width=3]    (30.5,300.5) -- (100.5,360.5) ;

%Straight Lines [id:da3426683871763214] 
\draw [line width=3]    (30.5,360.5) -- (100.5,240.5) ;

%Straight Lines [id:da5606530533581107] 
\draw [line width=3]    (30.5,240.5) -- (100.5,360.5) ;

%Straight Lines [id:da6623772912099226] 
\draw [line width=3]    (30.5,360.5) -- (100.5,300.5) ;

%Shape: Circle [id:dp8497518299231881] 
\draw   (10,299.5) .. controls (10,288.18) and (19.18,279) .. (30.5,279) .. controls (41.82,279) and (51,288.18) .. (51,299.5) .. controls (51,310.82) and (41.82,320) .. (30.5,320) .. controls (19.18,320) and (10,310.82) .. (10,299.5) -- cycle ;
%Straight Lines [id:da7730402601829687] 
\draw    (91.5,379.5) -- (111.5,379.5) ;

%Straight Lines [id:da22451186216424857] 
\draw    (20,380) -- (40,380) ;

%Shape: Circle [id:dp7885216763432006] 
\draw  [fill={rgb, 255:red, 0; green, 0; blue, 0 }  ,fill opacity=1 ] (181.5,240.72) .. controls (181.39,235.75) and (185.33,231.62) .. (190.3,231.5) .. controls (195.27,231.38) and (199.39,235.31) .. (199.5,240.28) .. controls (199.61,245.25) and (195.67,249.38) .. (190.7,249.5) .. controls (185.73,249.62) and (181.61,245.69) .. (181.5,240.72) -- cycle ;
%Shape: Circle [id:dp5104876218975949] 
\draw  [fill={rgb, 255:red, 0; green, 0; blue, 0 }  ,fill opacity=1 ] (181.5,300.72) .. controls (181.39,295.75) and (185.33,291.62) .. (190.3,291.5) .. controls (195.27,291.38) and (199.39,295.31) .. (199.5,300.28) .. controls (199.61,305.25) and (195.67,309.38) .. (190.7,309.5) .. controls (185.73,309.62) and (181.61,305.69) .. (181.5,300.72) -- cycle ;
%Shape: Circle [id:dp21100252748823323] 
\draw  [fill={rgb, 255:red, 0; green, 0; blue, 0 }  ,fill opacity=1 ] (181.5,360.72) .. controls (181.39,355.75) and (185.33,351.62) .. (190.3,351.5) .. controls (195.27,351.38) and (199.39,355.31) .. (199.5,360.28) .. controls (199.61,365.25) and (195.67,369.38) .. (190.7,369.5) .. controls (185.73,369.62) and (181.61,365.69) .. (181.5,360.72) -- cycle ;
%Shape: Circle [id:dp8575475506915247] 
\draw  [fill={rgb, 255:red, 0; green, 0; blue, 0 }  ,fill opacity=1 ] (251.5,240.72) .. controls (251.39,235.75) and (255.33,231.62) .. (260.3,231.5) .. controls (265.27,231.38) and (269.39,235.31) .. (269.5,240.28) .. controls (269.61,245.25) and (265.67,249.38) .. (260.7,249.5) .. controls (255.73,249.62) and (251.61,245.69) .. (251.5,240.72) -- cycle ;
%Shape: Circle [id:dp3666999738673842] 
\draw  [fill={rgb, 255:red, 0; green, 0; blue, 0 }  ,fill opacity=1 ] (251.5,300.72) .. controls (251.39,295.75) and (255.33,291.62) .. (260.3,291.5) .. controls (265.27,291.38) and (269.39,295.31) .. (269.5,300.28) .. controls (269.61,305.25) and (265.67,309.38) .. (260.7,309.5) .. controls (255.73,309.62) and (251.61,305.69) .. (251.5,300.72) -- cycle ;
%Shape: Circle [id:dp42697476369770104] 
\draw  [fill={rgb, 255:red, 0; green, 0; blue, 0 }  ,fill opacity=1 ] (251.5,360.72) .. controls (251.39,355.75) and (255.33,351.62) .. (260.3,351.5) .. controls (265.27,351.38) and (269.39,355.31) .. (269.5,360.28) .. controls (269.61,365.25) and (265.67,369.38) .. (260.7,369.5) .. controls (255.73,369.62) and (251.61,365.69) .. (251.5,360.72) -- cycle ;
%Straight Lines [id:da914699656204693] 
\draw [line width=3]    (260.5,300.5) -- (260.5,360.5) ;

%Straight Lines [id:da4697200056837407] 
\draw [line width=3]    (190.5,300.5) -- (260.5,360.5) ;

%Straight Lines [id:da41498728815999497] 
\draw [line width=3]    (190.5,240.5) -- (260.5,360.5) ;

%Straight Lines [id:da07801482300565388] 
\draw [line width=3]    (190.5,360.5) -- (260.5,360.5) ;

%Straight Lines [id:da6246558559143953] 
\draw    (251.5,379.5) -- (271.5,379.5) ;

%Curve Lines [id:da9147361307586885] 
\draw [line width=3]    (190.5,360.5) .. controls (257,363.5) and (192,429.5) .. (189.5,361.5) ;

%Curve Lines [id:da42444168455446163] 
\draw [line width=3]    (191.28,241.72) .. controls (168.5,285) and (167.5,316) .. (190.5,360.5) ;

%Notched Right Arrow [id:dp403716403417661] 
\draw   (280,293.13) -- (298.9,293.13) -- (298.9,288.01) -- (311.5,298.26) -- (298.9,308.5) -- (298.9,303.38) -- (280,303.38) -- (285.12,298.26) -- cycle ;
%Shape: Circle [id:dp5421862914139892] 
\draw  [fill={rgb, 255:red, 0; green, 0; blue, 0 }  ,fill opacity=1 ] (332.99,239.22) .. controls (332.89,234.25) and (336.83,230.12) .. (341.8,230) .. controls (346.77,229.88) and (350.89,233.81) .. (351,238.79) .. controls (351.11,243.76) and (347.17,247.89) .. (342.19,248.01) .. controls (337.22,248.13) and (333.1,244.2) .. (332.99,239.22) -- cycle ;
%Shape: Circle [id:dp3921106504065377] 
\draw  [fill={rgb, 255:red, 0; green, 0; blue, 0 }  ,fill opacity=1 ] (332.99,299.22) .. controls (332.89,294.25) and (336.83,290.12) .. (341.8,290) .. controls (346.77,289.88) and (350.89,293.81) .. (351,298.79) .. controls (351.11,303.76) and (347.17,307.89) .. (342.19,308.01) .. controls (337.22,308.13) and (333.1,304.2) .. (332.99,299.22) -- cycle ;
%Shape: Circle [id:dp07886314141396977] 
\draw  [fill={rgb, 255:red, 0; green, 0; blue, 0 }  ,fill opacity=1 ] (332.99,359.22) .. controls (332.89,354.25) and (336.83,350.12) .. (341.8,350) .. controls (346.77,349.88) and (350.89,353.81) .. (351,358.79) .. controls (351.11,363.76) and (347.17,367.89) .. (342.19,368.01) .. controls (337.22,368.13) and (333.1,364.2) .. (332.99,359.22) -- cycle ;
%Shape: Circle [id:dp05178695780490861] 
\draw  [fill={rgb, 255:red, 0; green, 0; blue, 0 }  ,fill opacity=1 ] (402.99,239.22) .. controls (402.89,234.25) and (406.83,230.12) .. (411.8,230) .. controls (416.77,229.88) and (420.89,233.81) .. (421,238.79) .. controls (421.11,243.76) and (417.17,247.89) .. (412.19,248.01) .. controls (407.22,248.13) and (403.1,244.2) .. (402.99,239.22) -- cycle ;
%Shape: Circle [id:dp3149483547637084] 
\draw  [fill={rgb, 255:red, 0; green, 0; blue, 0 }  ,fill opacity=1 ] (402.99,299.22) .. controls (402.89,294.25) and (406.83,290.12) .. (411.8,290) .. controls (416.77,289.88) and (420.89,293.81) .. (421,298.79) .. controls (421.11,303.76) and (417.17,307.89) .. (412.19,308.01) .. controls (407.22,308.13) and (403.1,304.2) .. (402.99,299.22) -- cycle ;
%Shape: Circle [id:dp4654199084114967] 
\draw  [fill={rgb, 255:red, 0; green, 0; blue, 0 }  ,fill opacity=1 ] (402.99,359.22) .. controls (402.89,354.25) and (406.83,350.12) .. (411.8,350) .. controls (416.77,349.88) and (420.89,353.81) .. (421,358.79) .. controls (421.11,363.76) and (417.17,367.89) .. (412.19,368.01) .. controls (407.22,368.13) and (403.1,364.2) .. (402.99,359.22) -- cycle ;
%Curve Lines [id:da7724015066999328] 
\draw [line width=3]    (342,359) .. controls (408.5,362) and (343.5,428) .. (341,360) ;

%Curve Lines [id:da560996442144913] 
\draw [line width=3]    (342.78,240.22) .. controls (320,283.5) and (319,314.5) .. (342,359) ;

%Curve Lines [id:da25897904122328397] 
\draw [line width=3]    (412.99,358.01) .. controls (479.49,361.01) and (414.49,427.01) .. (412,359) ;

%Curve Lines [id:da3191035471246393] 
\draw [line width=3]    (413.77,239.23) .. controls (435.5,291) and (435.5,311) .. (412.99,358.01) ;

%Shape: Circle [id:dp2527330605203897] 
\draw  [fill={rgb, 255:red, 0; green, 0; blue, 0 }  ,fill opacity=1 ] (501.5,239.58) .. controls (501.39,234.61) and (505.33,230.48) .. (510.3,230.36) .. controls (515.27,230.24) and (519.39,234.17) .. (519.5,239.15) .. controls (519.61,244.12) and (515.67,248.25) .. (510.7,248.37) .. controls (505.73,248.49) and (501.61,244.55) .. (501.5,239.58) -- cycle ;
%Shape: Circle [id:dp7088051836115195] 
\draw  [fill={rgb, 255:red, 0; green, 0; blue, 0 }  ,fill opacity=1 ] (501.5,299.58) .. controls (501.39,294.61) and (505.33,290.48) .. (510.3,290.36) .. controls (515.27,290.24) and (519.39,294.17) .. (519.5,299.15) .. controls (519.61,304.12) and (515.67,308.25) .. (510.7,308.37) .. controls (505.73,308.49) and (501.61,304.55) .. (501.5,299.58) -- cycle ;
%Shape: Circle [id:dp6986593339178226] 
\draw  [fill={rgb, 255:red, 0; green, 0; blue, 0 }  ,fill opacity=1 ] (501.5,359.58) .. controls (501.39,354.61) and (505.33,350.48) .. (510.3,350.36) .. controls (515.27,350.24) and (519.39,354.17) .. (519.5,359.15) .. controls (519.61,364.12) and (515.67,368.25) .. (510.7,368.37) .. controls (505.73,368.49) and (501.61,364.55) .. (501.5,359.58) -- cycle ;
%Straight Lines [id:da701562607760136] 
\draw [line width=3]    (510.5,299.36) -- (510.5,359.36) ;

%Shape: Circle [id:dp7676102843849355] 
\draw  [fill={rgb, 255:red, 0; green, 0; blue, 0 }  ,fill opacity=1 ] (571.5,239.58) .. controls (571.39,234.61) and (575.33,230.48) .. (580.3,230.36) .. controls (585.27,230.24) and (589.39,234.17) .. (589.5,239.15) .. controls (589.61,244.12) and (585.67,248.25) .. (580.7,248.37) .. controls (575.73,248.49) and (571.61,244.55) .. (571.5,239.58) -- cycle ;
%Shape: Circle [id:dp16373769889661016] 
\draw  [fill={rgb, 255:red, 0; green, 0; blue, 0 }  ,fill opacity=1 ] (571.5,299.58) .. controls (571.39,294.61) and (575.33,290.48) .. (580.3,290.36) .. controls (585.27,290.24) and (589.39,294.17) .. (589.5,299.15) .. controls (589.61,304.12) and (585.67,308.25) .. (580.7,308.37) .. controls (575.73,308.49) and (571.61,304.55) .. (571.5,299.58) -- cycle ;
%Shape: Circle [id:dp8018334061711114] 
\draw  [fill={rgb, 255:red, 0; green, 0; blue, 0 }  ,fill opacity=1 ] (571.5,359.58) .. controls (571.39,354.61) and (575.33,350.48) .. (580.3,350.36) .. controls (585.27,350.24) and (589.39,354.17) .. (589.5,359.15) .. controls (589.61,364.12) and (585.67,368.25) .. (580.7,368.37) .. controls (575.73,368.49) and (571.61,364.55) .. (571.5,359.58) -- cycle ;
%Straight Lines [id:da7787348199437563] 
\draw [line width=3]    (580.5,299.36) -- (580.5,359.36) ;

%Shape: Circle [id:dp5335772645328107] 
\draw  [fill={rgb, 255:red, 0; green, 0; blue, 0 }  ,fill opacity=1 ] (681.5,239.58) .. controls (681.39,234.61) and (685.33,230.48) .. (690.3,230.36) .. controls (695.27,230.24) and (699.39,234.17) .. (699.5,239.15) .. controls (699.61,244.12) and (695.67,248.25) .. (690.7,248.37) .. controls (685.73,248.49) and (681.61,244.55) .. (681.5,239.58) -- cycle ;
%Shape: Circle [id:dp05667856394202886] 
\draw  [fill={rgb, 255:red, 0; green, 0; blue, 0 }  ,fill opacity=1 ] (681.5,299.58) .. controls (681.39,294.61) and (685.33,290.48) .. (690.3,290.36) .. controls (695.27,290.24) and (699.39,294.17) .. (699.5,299.15) .. controls (699.61,304.12) and (695.67,308.25) .. (690.7,308.37) .. controls (685.73,308.49) and (681.61,304.55) .. (681.5,299.58) -- cycle ;
%Shape: Circle [id:dp2308729575029811] 
\draw  [fill={rgb, 255:red, 0; green, 0; blue, 0 }  ,fill opacity=1 ] (681.5,359.58) .. controls (681.39,354.61) and (685.33,350.48) .. (690.3,350.36) .. controls (695.27,350.24) and (699.39,354.17) .. (699.5,359.15) .. controls (699.61,364.12) and (695.67,368.25) .. (690.7,368.37) .. controls (685.73,368.49) and (681.61,364.55) .. (681.5,359.58) -- cycle ;
%Straight Lines [id:da8058191518397477] 
\draw [line width=3]    (690.5,239.36) -- (690.5,299.36) ;

%Shape: Circle [id:dp22841045966417206] 
\draw  [fill={rgb, 255:red, 0; green, 0; blue, 0 }  ,fill opacity=1 ] (753.28,239.8) .. controls (753.17,234.83) and (757.11,230.7) .. (762.08,230.58) .. controls (767.05,230.46) and (771.17,234.39) .. (771.28,239.37) .. controls (771.39,244.34) and (767.45,248.47) .. (762.47,248.59) .. controls (757.5,248.71) and (753.38,244.78) .. (753.28,239.8) -- cycle ;
%Shape: Circle [id:dp03883671656236842] 
\draw  [fill={rgb, 255:red, 0; green, 0; blue, 0 }  ,fill opacity=1 ] (751.5,299.58) .. controls (751.39,294.61) and (755.33,290.48) .. (760.3,290.36) .. controls (765.27,290.24) and (769.39,294.17) .. (769.5,299.15) .. controls (769.61,304.12) and (765.67,308.25) .. (760.7,308.37) .. controls (755.73,308.49) and (751.61,304.55) .. (751.5,299.58) -- cycle ;
%Shape: Circle [id:dp6765776419706568] 
\draw  [fill={rgb, 255:red, 0; green, 0; blue, 0 }  ,fill opacity=1 ] (751.5,359.58) .. controls (751.39,354.61) and (755.33,350.48) .. (760.3,350.36) .. controls (765.27,350.24) and (769.39,354.17) .. (769.5,359.15) .. controls (769.61,364.12) and (765.67,368.25) .. (760.7,368.37) .. controls (755.73,368.49) and (751.61,364.55) .. (751.5,359.58) -- cycle ;
%Notched Right Arrow [id:dp6187867199434931] 
\draw   (611.5,293.37) -- (641.5,293.37) -- (641.5,288.37) -- (661.5,298.37) -- (641.5,308.37) -- (641.5,303.37) -- (611.5,303.37) -- (616.5,298.37) -- cycle ;
%Straight Lines [id:da7496004759909158] 
\draw [line width=3]    (510.5,299.36) -- (580.5,359.36) ;

%Straight Lines [id:da7858923565312517] 
\draw [line width=3]    (510.5,359.36) -- (580.5,239.36) ;

%Straight Lines [id:da6880942317423411] 
\draw [line width=3]    (510.5,239.36) -- (580.5,359.36) ;

%Straight Lines [id:da2702830117918076] 
\draw [line width=3]    (510.5,359.36) -- (580.5,299.36) ;

%Straight Lines [id:da6650342192304053] 
\draw [line width=3]    (692.28,239.59) -- (762.28,239.59) ;

%Shape: Circle [id:dp3891930043113976] 
\draw   (490,359.36) .. controls (490,348.04) and (499.18,338.86) .. (510.5,338.86) .. controls (521.82,338.86) and (531,348.04) .. (531,359.36) .. controls (531,370.69) and (521.82,379.86) .. (510.5,379.86) .. controls (499.18,379.86) and (490,370.69) .. (490,359.36) -- cycle ;
%Straight Lines [id:da9515637429508601] 
\draw    (570,320) -- (590,320) ;

%Straight Lines [id:da8768824861629103] 
\draw [line width=3]    (690.5,239.36) -- (760.5,359.36) ;

%Straight Lines [id:da7285705401470752] 
\draw [line width=3]    (690.5,239.36) -- (760,300) ;

%Curve Lines [id:da48702039119544804] 
\draw [line width=3]    (762.28,239.59) .. controls (817,239.37) and (816,359.37) .. (761.5,358.37) ;

%Curve Lines [id:da7284068448179462] 
\draw [line width=3]    (760,300) .. controls (826.5,303) and (761.5,369) .. (759,301) ;

%Straight Lines [id:da9887968580954514] 
\draw    (670,380) -- (710,340) ;

%Straight Lines [id:da2816368412467014] 
\draw    (670,340) -- (710,380) ;

%Straight Lines [id:da48015094167884986] 
\draw    (570,260) -- (590,260) ;

%Straight Lines [id:da21508710060085967] 
\draw    (500,320) -- (520,320) ;

%Curve Lines [id:da8104009871498106] 
\draw [line width=3]    (690.5,299.36) .. controls (757,302.36) and (692,368.36) .. (689.5,300.36) ;

%Curve Lines [id:da05746272264379004] 
\draw [line width=3]    (763.27,238.59) .. controls (820,279) and (738,293) .. (762.28,239.59) ;
\end{tikzpicture}
\vspace{-3ex}
\caption{Alternate transformations of the G2PM $G$ into graphs.}
\end{center}
\end{figure}

%If we include the negative isol, then it doubles the counts without changing that $G \explode e$ has $n-1$ nodes, so we get (\ref{ampedgerec}) in this case too.  
%Now we can start working out those constants for $\phi(G) = a(G)$. Recall that the rank value $f(A)$ in a graph $G$ is the number of distinct endpoints of edges in set $A$.
%\begin{align*}
%r &= a(U_{2,1}) = \frac{1}{2} \\
%s &= a(U_{0,1}) = -1 \\
%t &= a(U_{1,1}) = 0.
%\end{align*}
%If $e$ is not a separator, we only have two cases to consider--if $e$ is a self-loop or an edge connecting two vertices:
%\begin{itemize}
%  \item if $f(E \backslash e) = f(E)$ and $f(e) = 1$, then this edge $e$ is a self-loop and from above we have $a = 1, b = -1$;
%  \item if $f(E \backslash e) = f(E)-1$ and $f(e) = 2$, or $f(E \backslash e) = f(E)$ and $f(e) = 2$, then $e$ is an ordinary edge making $c = m = 1$ and $d = n = -\frac{1}{2}$.
%\end{itemize}
%Overall, this gives the set of parameters and hence the desired formula for $a(G)$ as stated in the above section.
%
%This in turn further simplifies to
%\[
%a(G) = \sum_{A \subseteq E} \frac{(-2)^{|A|}}{2^{f_G(A)}}.
%\]
%Noble \cite{Nob06} shows that computing $S_G(x,y)$ is $\#P$-hard for any constant rational $x,y$ whenever $xy \neq 1$.  The complex irrational point $(-\sqrt{2}i, \sqrt{2}i)$ has $xy = 2$ but evades his proof because having $y^2 = -2$ makes a denominator vanish.
%Other connections between quantum graph states and matroids have been shown by Sarvepalli \cite{Sar14}, and there is scope for further development along these lines.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Deletion-Contraction Recursion and Polynomial Invariants of GPMs}

The standard definition of \emph{contraction} of an edge $e = (u,v)$ in a graph $G$, written $G/e$, is to delete $e$ and identify the vertices $u$ and $v$.  This cannot create a self-loop, but can create a double edge, such as when contracting one edge of the three-node cycle.  The operations of deleting an edge ($G \setminus e$) and contracting an edge figure into the recurrences defining the \emph{Tutte polynomial} and the \emph{chromatic polynomial} of graphs.  In polymatroids, however, a different notion of contraction works better for several reasons, including respecting the map from $G$ to its \emph{dual} $G^{\perp}$.  We call it \emph{explosion} and denote it by $G \explode e$.  

As remarked in the introduction, graphical polymatroids formally do not have any notion of ``node,'' only the function $f(A)$ giving the rank of an edge subset $A$.  Since $f$ is unaffected by adding isolated nodes, the notion is indifferent to them.  The notion of $n$ being the count of node is deprecated in favor of the rank $f(E)$ of the entire edge set, which equals $n$ if and only if $G$ has no isolated nodes.  However, we will adjoin not only ``positive'' but also ``negative'' isolated nodes, denoting them by $\bullet$ and $\ominus$, respectively.  Compared to having $n = f(E)$, each normal isolated node increases $n$ by $1$ and each $\ominus$ decreases $n$ by $1$ in the formulas to follow.

We also modify the definition of ``explosion'' to include them.  Doing so enables a coherent account of contracting a \emph{loop} and avoids having to make exceptions for cases where deleting an edge yields one or two isolated nodes.

\begin{definition}
The explosion of an edge $(u,v)$ in a G2PM $G$ causes the following changes:
\begin{itemize}
\item
The edge $(u,v)$ and nodes $u,v$ are deleted.
\item
Other edges and loops incident only to $u$ and/or $v$ become circles.
\item
Every other edge $(u,w)$ or $(v,w)$ where $w \notin \{u,v\}$ becomes a loop at $w$.
\end{itemize}
The explosion of a loop $e$ at a node $u$ causes the following:
\begin{itemize}
\item
The loop $e$ is deleted and $u$ is replaced by a negative isolated node $\ominus$.
\item
Any other loops at $u$ are replaced by circles.
\item
Every other edge $(u,w)$ where $w \neq u$ becomes a loop at $w$.
\end{itemize}
The explosion of a circle leaves two $\ominus$ nodes.
In all cases, the resulting (augmented) G2PM is denoted by $G \explode e$.
\end{definition}

Figure~\ref{explosion} gives examples.  Note that explosion cannot cause multiple edges but can cause multiple loops.  Under our reduction modulo $K$, the triple loop in the figure will be replaceable by a single loop, while a double-loop disappears.  Moreover, we can consistently define the explosion of a \emph{non}-edge $e$ (or even a non-loop $e$) by putting a double edge (or loop) in its place and exploding one of its two members.  One point of introducing $\ominus$ is that now both cases of explosion always reduce $n$ by $2$.


\begin{figure}[ht]\label{explosion}
\begin{center}
\tikzset{every picture/.style={line width=0.75pt}} %set default line width to 0.75pt        

\begin{tikzpicture}[x=0.75pt,y=0.75pt,yscale=-0.5,xscale=0.5]
%uncomment if require: \path (0,300); %set diagram left start at 0, and has height of 300

%Shape: Circle [id:dp2605473228897339] 
\draw  [fill={rgb, 255:red, 0; green, 0; blue, 0 }  ,fill opacity=1 ] (25,39.21) .. controls (24.89,34.24) and (28.83,30.11) .. (33.81,29.99) .. controls (38.78,29.87) and (42.9,33.8) .. (43.01,38.78) .. controls (43.11,43.75) and (39.17,47.88) .. (34.2,48) .. controls (29.23,48.12) and (25.11,44.19) .. (25,39.21) -- cycle ;
%Shape: Circle [id:dp3109919093072513] 
\draw  [fill={rgb, 255:red, 0; green, 0; blue, 0 }  ,fill opacity=1 ] (25,99.21) .. controls (24.89,94.24) and (28.83,90.11) .. (33.81,89.99) .. controls (38.78,89.87) and (42.9,93.8) .. (43.01,98.78) .. controls (43.11,103.75) and (39.17,107.88) .. (34.2,108) .. controls (29.23,108.12) and (25.11,104.19) .. (25,99.21) -- cycle ;
%Shape: Circle [id:dp563659383635108] 
\draw  [fill={rgb, 255:red, 0; green, 0; blue, 0 }  ,fill opacity=1 ] (25,159.21) .. controls (24.89,154.24) and (28.83,150.11) .. (33.81,149.99) .. controls (38.78,149.87) and (42.9,153.8) .. (43.01,158.78) .. controls (43.11,163.75) and (39.17,167.88) .. (34.2,168) .. controls (29.23,168.12) and (25.11,164.19) .. (25,159.21) -- cycle ;
%Straight Lines [id:da5977058740499932] 
\draw [line width=3]    (34,99) -- (34,159) ;

%Shape: Circle [id:dp5494771627167425] 
\draw  [fill={rgb, 255:red, 0; green, 0; blue, 0 }  ,fill opacity=1 ] (96.78,39.44) .. controls (96.67,34.46) and (100.61,30.34) .. (105.58,30.21) .. controls (110.55,30.09) and (114.67,34.03) .. (114.78,39) .. controls (114.89,43.97) and (110.95,48.1) .. (105.98,48.22) .. controls (101.01,48.34) and (96.89,44.41) .. (96.78,39.44) -- cycle ;
%Shape: Circle [id:dp11706579118939953] 
\draw  [fill={rgb, 255:red, 0; green, 0; blue, 0 }  ,fill opacity=1 ] (95,99.21) .. controls (94.89,94.24) and (98.83,90.11) .. (103.81,89.99) .. controls (108.78,89.87) and (112.9,93.8) .. (113.01,98.78) .. controls (113.11,103.75) and (109.17,107.88) .. (104.2,108) .. controls (99.23,108.12) and (95.11,104.19) .. (95,99.21) -- cycle ;
%Shape: Circle [id:dp16595992221595246] 
\draw  [fill={rgb, 255:red, 0; green, 0; blue, 0 }  ,fill opacity=1 ] (95,159.21) .. controls (94.89,154.24) and (98.83,150.11) .. (103.81,149.99) .. controls (108.78,149.87) and (112.9,153.8) .. (113.01,158.78) .. controls (113.11,163.75) and (109.17,167.88) .. (104.2,168) .. controls (99.23,168.12) and (95.11,164.19) .. (95,159.21) -- cycle ;
%Straight Lines [id:da9323539553060634] 
\draw [line width=3]    (34,159) -- (104,159) ;

%Straight Lines [id:da27822989407394205] 
\draw [line width=3]    (34,159) -- (105.78,39.22) ;

%Straight Lines [id:da18232041933598975] 
\draw [line width=3]    (34,159) -- (104,99) ;

%Curve Lines [id:da5569674852372444] 
\draw [line width=3]    (105.78,39.22) .. controls (160.5,39) and (159.5,159) .. (105,158) ;

%Curve Lines [id:da695244797392937] 
\draw [line width=3]    (105,158) .. controls (171.5,161) and (106.5,227) .. (104,159) ;

%Straight Lines [id:da11101045669417875] 
\draw [line width=3]    (34,99) -- (34,39) ;

%Straight Lines [id:da661025502852501] 
\draw    (57,42) -- (80.1,65.57) ;
\draw [shift={(81.5,67)}, rotate = 225.57999999999998] [color={rgb, 255:red, 0; green, 0; blue, 0 }  ][line width=0.75]    (10.93,-3.29) .. controls (6.95,-1.4) and (3.31,-0.3) .. (0,0) .. controls (3.31,0.3) and (6.95,1.4) .. (10.93,3.29)   ;

%Shape: Circle [id:dp45045070251786234] 
\draw  [fill={rgb, 255:red, 0; green, 0; blue, 0 }  ,fill opacity=1 ] (208,40.21) .. controls (207.89,35.24) and (211.83,31.11) .. (216.81,30.99) .. controls (221.78,30.87) and (225.9,34.8) .. (226.01,39.78) .. controls (226.11,44.75) and (222.17,48.88) .. (217.2,49) .. controls (212.23,49.12) and (208.11,45.19) .. (208,40.21) -- cycle ;
%Shape: Circle [id:dp8435717073058884] 
\draw  [fill={rgb, 255:red, 0; green, 0; blue, 0 }  ,fill opacity=1 ] (208,100.21) .. controls (207.89,95.24) and (211.83,91.11) .. (216.81,90.99) .. controls (221.78,90.87) and (225.9,94.8) .. (226.01,99.78) .. controls (226.11,104.75) and (222.17,108.88) .. (217.2,109) .. controls (212.23,109.12) and (208.11,105.19) .. (208,100.21) -- cycle ;
%Shape: Circle [id:dp2826289987115802] 
\draw  [fill={rgb, 255:red, 0; green, 0; blue, 0 }  ,fill opacity=1 ] (278,100.21) .. controls (277.89,95.24) and (281.83,91.11) .. (286.81,90.99) .. controls (291.78,90.87) and (295.9,94.8) .. (296.01,99.78) .. controls (296.11,104.75) and (292.17,108.88) .. (287.2,109) .. controls (282.23,109.12) and (278.11,105.19) .. (278,100.21) -- cycle ;
%Shape: Circle [id:dp6904912037687985] 
\draw  [fill={rgb, 255:red, 0; green, 0; blue, 0 }  ,fill opacity=1 ] (278,160.21) .. controls (277.89,155.24) and (281.83,151.11) .. (286.81,150.99) .. controls (291.78,150.87) and (295.9,154.8) .. (296.01,159.78) .. controls (296.11,164.75) and (292.17,168.88) .. (287.2,169) .. controls (282.23,169.12) and (278.11,165.19) .. (278,160.21) -- cycle ;
%Curve Lines [id:da3690544031497738] 
\draw [line width=3]    (288,159) .. controls (354.5,162) and (289.5,228) .. (287,160) ;

%Straight Lines [id:da7876526299714584] 
\draw [line width=3]    (217,100) -- (217,40) ;

%Shape: Circle [id:dp7836357639090497] 
\draw  [fill={rgb, 255:red, 0; green, 0; blue, 0 }  ,fill opacity=1 ] (434,38.21) .. controls (433.89,33.24) and (437.83,29.11) .. (442.81,28.99) .. controls (447.78,28.87) and (451.9,32.8) .. (452.01,37.78) .. controls (452.11,42.75) and (448.17,46.88) .. (443.2,47) .. controls (438.23,47.12) and (434.11,43.19) .. (434,38.21) -- cycle ;
%Shape: Circle [id:dp2616636929791032] 
\draw  [fill={rgb, 255:red, 0; green, 0; blue, 0 }  ,fill opacity=1 ] (434,98.21) .. controls (433.89,93.24) and (437.83,89.11) .. (442.81,88.99) .. controls (447.78,88.87) and (451.9,92.8) .. (452.01,97.78) .. controls (452.11,102.75) and (448.17,106.88) .. (443.2,107) .. controls (438.23,107.12) and (434.11,103.19) .. (434,98.21) -- cycle ;
%Shape: Circle [id:dp4811178377330161] 
\draw  [fill={rgb, 255:red, 0; green, 0; blue, 0 }  ,fill opacity=1 ] (434,158.21) .. controls (433.89,153.24) and (437.83,149.11) .. (442.81,148.99) .. controls (447.78,148.87) and (451.9,152.8) .. (452.01,157.78) .. controls (452.11,162.75) and (448.17,166.88) .. (443.2,167) .. controls (438.23,167.12) and (434.11,163.19) .. (434,158.21) -- cycle ;
%Straight Lines [id:da7495107082815928] 
\draw [line width=3]    (443,98) -- (443,158) ;

%Shape: Circle [id:dp28088730718672905] 
\draw  [fill={rgb, 255:red, 0; green, 0; blue, 0 }  ,fill opacity=1 ] (505.78,38.44) .. controls (505.67,33.46) and (509.61,29.34) .. (514.58,29.21) .. controls (519.55,29.09) and (523.67,33.03) .. (523.78,38) .. controls (523.89,42.97) and (519.95,47.1) .. (514.98,47.22) .. controls (510.01,47.34) and (505.89,43.41) .. (505.78,38.44) -- cycle ;
%Shape: Circle [id:dp74247446942427] 
\draw  [fill={rgb, 255:red, 0; green, 0; blue, 0 }  ,fill opacity=1 ] (504,98.21) .. controls (503.89,93.24) and (507.83,89.11) .. (512.81,88.99) .. controls (517.78,88.87) and (521.9,92.8) .. (522.01,97.78) .. controls (522.11,102.75) and (518.17,106.88) .. (513.2,107) .. controls (508.23,107.12) and (504.11,103.19) .. (504,98.21) -- cycle ;
%Shape: Circle [id:dp20192906739810312] 
\draw  [fill={rgb, 255:red, 0; green, 0; blue, 0 }  ,fill opacity=1 ] (504,158.21) .. controls (503.89,153.24) and (507.83,149.11) .. (512.81,148.99) .. controls (517.78,148.87) and (521.9,152.8) .. (522.01,157.78) .. controls (522.11,162.75) and (518.17,166.88) .. (513.2,167) .. controls (508.23,167.12) and (504.11,163.19) .. (504,158.21) -- cycle ;
%Straight Lines [id:da005590742827641604] 
\draw [line width=3]    (105,158) -- (104,99) ;

%Straight Lines [id:da8076584321048592] 
\draw [line width=3]    (443,158) -- (514.78,38.22) ;

%Straight Lines [id:da595100682207357] 
\draw [line width=3]    (443,158) -- (513,98) ;

%Curve Lines [id:da26466978590811197] 
\draw [line width=3]    (514.78,38.22) .. controls (569.5,38) and (568.5,158) .. (514,157) ;

%Curve Lines [id:da8994938423215126] 
\draw [line width=3]    (514,157) .. controls (580.5,160) and (515.5,226) .. (513,158) ;

%Straight Lines [id:da6175201216570005] 
\draw [line width=3]    (443,98) -- (443,38) ;

%Straight Lines [id:da29956127815191147] 
\draw    (486,204) -- (508.4,187.2) ;
\draw [shift={(510,186)}, rotate = 503.13] [color={rgb, 255:red, 0; green, 0; blue, 0 }  ][line width=0.75]    (10.93,-3.29) .. controls (6.95,-1.4) and (3.31,-0.3) .. (0,0) .. controls (3.31,0.3) and (6.95,1.4) .. (10.93,3.29)   ;

%Shape: Circle [id:dp727989949870993] 
\draw  [fill={rgb, 255:red, 0; green, 0; blue, 0 }  ,fill opacity=1 ] (617,39.21) .. controls (616.89,34.24) and (620.83,30.11) .. (625.81,29.99) .. controls (630.78,29.87) and (634.9,33.8) .. (635.01,38.78) .. controls (635.11,43.75) and (631.17,47.88) .. (626.2,48) .. controls (621.23,48.12) and (617.11,44.19) .. (617,39.21) -- cycle ;
%Shape: Circle [id:dp22071285231677185] 
\draw  [fill={rgb, 255:red, 0; green, 0; blue, 0 }  ,fill opacity=1 ] (617,99.21) .. controls (616.89,94.24) and (620.83,90.11) .. (625.81,89.99) .. controls (630.78,89.87) and (634.9,93.8) .. (635.01,98.78) .. controls (635.11,103.75) and (631.17,107.88) .. (626.2,108) .. controls (621.23,108.12) and (617.11,104.19) .. (617,99.21) -- cycle ;
%Shape: Circle [id:dp9586968979279369] 
\draw  [fill={rgb, 255:red, 0; green, 0; blue, 0 }  ,fill opacity=1 ] (617,159.21) .. controls (616.89,154.24) and (620.83,150.11) .. (625.81,149.99) .. controls (630.78,149.87) and (634.9,153.8) .. (635.01,158.78) .. controls (635.11,163.75) and (631.17,167.88) .. (626.2,168) .. controls (621.23,168.12) and (617.11,164.19) .. (617,159.21) -- cycle ;
%Straight Lines [id:da4829288377892771] 
\draw [line width=3]    (626,99) -- (626,159) ;

%Shape: Circle [id:dp18863090804060434] 
\draw  [fill={rgb, 255:red, 0; green, 0; blue, 0 }  ,fill opacity=1 ] (688.78,39.44) .. controls (688.67,34.46) and (692.61,30.34) .. (697.58,30.21) .. controls (702.55,30.09) and (706.67,34.03) .. (706.78,39) .. controls (706.89,43.97) and (702.95,48.1) .. (697.98,48.22) .. controls (693.01,48.34) and (688.89,44.41) .. (688.78,39.44) -- cycle ;
%Shape: Circle [id:dp5883812742743424] 
\draw  [fill={rgb, 255:red, 0; green, 0; blue, 0 }  ,fill opacity=1 ] (687,99.21) .. controls (686.89,94.24) and (690.83,90.11) .. (695.81,89.99) .. controls (700.78,89.87) and (704.9,93.8) .. (705.01,98.78) .. controls (705.11,103.75) and (701.17,107.88) .. (696.2,108) .. controls (691.23,108.12) and (687.11,104.19) .. (687,99.21) -- cycle ;
%Straight Lines [id:da40075817044047657] 
\draw [line width=3]    (626,159) -- (697.78,39.22) ;

%Straight Lines [id:da266434599512791] 
\draw [line width=3]    (626,159) -- (696,99) ;

%Straight Lines [id:da41778914166553127] 
\draw [line width=3]    (626,99) -- (626,39) ;

%Notched Right Arrow [id:dp09396908758012201] 
\draw   (160,93) -- (181.6,93) -- (181.6,86) -- (196,100) -- (181.6,114) -- (181.6,107) -- (160,107) -- (167,100) -- cycle ;
%Notched Right Arrow [id:dp9433451446913996] 
\draw   (568,91) -- (589.6,91) -- (589.6,84) -- (604,98) -- (589.6,112) -- (589.6,105) -- (568,105) -- (575,98) -- cycle ;
%Curve Lines [id:da5143253085076345] 
\draw [line width=3]    (217,100) .. controls (283.5,103) and (241,41) .. (216.01,100.99) ;

%Curve Lines [id:da914002452516443] 
\draw [line width=3]    (287,160) .. controls (380,152) and (286,259) .. (286.01,160.99) ;

%Curve Lines [id:da34682760376389643] 
\draw [line width=3]    (288,159) .. controls (400,158) and (285,277) .. (287,160) ;

%Curve Lines [id:da7422470994230741] 
\draw [line width=3]    (287,100) .. controls (353.5,103) and (288.5,169) .. (286.01,100.99) ;

%Straight Lines [id:da3078591984257866] 
\draw [line width=3]    (287,160) -- (286.01,100.99) ;

%Straight Lines [id:da42798689978650484] 
\draw [line width=3]    (513,158) -- (512.01,98.99) ;

%Straight Lines [id:da6939863612756652] 
\draw [line width=3]    (513,158) -- (443,158) ;

%Curve Lines [id:da02978779339326021] 
\draw [line width=3]    (697,98) .. controls (763.5,101) and (698.5,167) .. (696,99) ;

%Curve Lines [id:da06806952743638361] 
\draw [line width=3]    (627,158) .. controls (693.5,161) and (628.5,227) .. (626,159) ;

%Curve Lines [id:da039426526990149036] 
\draw [line width=3]    (698.78,38.22) .. controls (762,43) and (720,-17) .. (697.78,39.22) ;

%Shape: Circle [id:dp39307047807847995] 
\draw   (689,161.5) .. controls (689,155.7) and (693.7,151) .. (699.5,151) .. controls (705.3,151) and (710,155.7) .. (710,161.5) .. controls (710,167.3) and (705.3,172) .. (699.5,172) .. controls (693.7,172) and (689,167.3) .. (689,161.5) -- cycle ;
%Shape: Circle [id:dp7674118461576034] 
\draw  [line width=3]  (270,42.5) .. controls (270,33.39) and (277.39,26) .. (286.5,26) .. controls (295.61,26) and (303,33.39) .. (303,42.5) .. controls (303,51.61) and (295.61,59) .. (286.5,59) .. controls (277.39,59) and (270,51.61) .. (270,42.5) -- cycle ;
%Curve Lines [id:da3158792524301208] 
\draw [line width=3]    (106.78,38.22) .. controls (170,43) and (128,-17) .. (105.78,39.22) ;

%Straight Lines [id:da04621976260087046] 
\draw    (689,161.5) -- (710,161.5) ;
\end{tikzpicture}
\vspace{-5ex}
\caption{Explosion of edges and loops in a graph $G$.  Exploding an edge that dislodges a loop leaves a circle, while exploding a loop leaves a negative isolated node, $\ominus$.}
\end{center}
\end{figure}


Now we define a general form of recursion based on these notions.  We justify the nomenclature right afterward.

\begin{definition}
A \emph{principal generalized Tutte-Grothendieck invariant} (PGTGI) is a mapping from G2PMs $G$ to some algebra $\mathcal{A}$ defined by some $x,y,\alpha,\beta \in \mathcal{A}$ and the rules:
\begin{enumerate}
\item
$\phi({\emptyset}) = 1$, $\phi(\bullet) = x$, $\phi({\ominus}) = y$;
\item
If $G$ is a disjoint union of $G_1$ and $G_2$, then $\phi(G) = \phi({G_1})\phi({G_2})$;
\item
For any edge or loop $e$ in $G$,
%
\begin{equation}\label{DErecurrence}
\phi(G) = \alpha\phi({G \setminus e}) + \beta\phi({G \explode e}).
\end{equation}
\end{enumerate}
%
\end{definition}



The stem paper \cite{OxWh93} defines a \emph{generalized Tutte-Grothendieck invariant} (GTGI) as a function from graphs to $\mathbb{C}$, but it is natural to allow complex polynomials.
%---that is, members of the ring $\mathbb{C}[X]$ for some finite set $X$ of variables.  
%Indeed, \cite{OxWh93} immediately exemplifies this kind of GTGI.  So we regard the following statement as inherent to \cite{OxWh93}.  
A set $S$ of edges is a \emph{separator} for a 2-polymatroid $(G,f)$ if $f(S) + f(E \backslash S) = f(E)$. In terms of graphs $G$, $S$ is a separator if and only if the set of vertices touched by $S$ is disjoint from those covered by $E \backslash S$.


\begin{definition}[\cite{OxWh93}]\label{GTGI}
A GTGI on 2-polymatroids is a function $\phi$ for which there exist $a, b, c, d, \mu, \nu, r, s, t \in \mathbb{C}[X]$ such that
\[
\phi(\bigcirc) = s, \quad \phi(\Game) = t, \quad \phi(G_2) = r,
\]
and for any graphic 2-polymatroid $(G,f)$,
\[
\phi(G) = \phi(G\backslash (E \backslash e)) \phi(G \backslash e) \quad \hbox{if $e$ is a separator of $(G,f)$};
\]
and if $e$ is not a separator (note: we write $\mu,\nu$ in place of the paper's $m,n$),
\begin{align*}
\phi(G) =
\left\{
  \begin{array}{ll}
    a \phi(G \backslash e) + b \phi(G \explode e), & \hbox{if $f(E\backslash e) = f(E)$ and $f(e) = 1$;} \\
    c \phi(G \backslash e) + d \phi(G \explode e), & \hbox{if $f(E\backslash e) = f(E) - 1$ and $f(e) = 2$;} \\
    \mu \phi(G \backslash e) + \nu \phi(G \explode e), & \hbox{if $f(E\backslash e) = f(E)$ and $f(e) = 2$.}
  \end{array}
\right.
\end{align*}
\end{definition}

\noindent
To characterize what we call the ``principal family'' of GTGIs, \cite{OxWh93} introduced the \emph{rank-generating} function $S_G$, adapting a similar function from \cite{OxWe79}.  We adjust its definition further to include the two kinds of isolated nodes.  Here $x$ and $y$ are formal variables and $S_G$ is a two-variable polynomial.  

\begin{definition}[cf.\ \cite{OxWh93}]\label{SG}
The (adjusted) \emph{rank-generating polynomial} $S'_G(x,y)$ is defined by recursion on $G = (V,E)$ by:
\begin{eqnarray}
S'_{\emptyset}(x,y) &=& 1, \quad S'_{\bullet}(x,y) = x, \quad S'_{\ominus}\!(x,y) = y;\\
S'_G(x,y) &=& S'_{G_1}(x,y)S'_{G_2}(x,y) ~\text{if $G$ is the disjoint union of $G_1$ and $G_2$};\\
S'_G(x,y) &=& S'_{G\setminus e}(x,y) + S'_{G \explode e}(x,y) ~\text{for any $e \in E$}.\label{Srec}
\end{eqnarray}
\end{definition}

This definition makes $S'_G$ automatically a PGTGI with $\alpha = \beta = 1$.  It differs from $S_G$ as defined in \cite{OxWh93} only in cases where $G$ has isolated nodes as a graph that are deemed absent when regarding $G$ as a G2PM.  The difference is a factor of $x^k y^{-\ell}$ where $k$ and $\ell$ are the counts of positive and negative isolated nodes.  What matters is that $S'_G$ gives the same basis values as \emph{defined} in \cite{OxWh93} for the three one-edge G2PMS: the circle $\bigcirc$, the graph $\Game$ of a self-loop at one node, and the graph $G_2$ of one edge between two nodes:
%
\begin{eqnarray*}
S'_{\bigcirc}(x,y) &=& 1 + y^2;\\
S'_{\Game}(x,y) &=& x + y;\\
S'_{G_2}(x,y) &=& x^2 + 1;
\end{eqnarray*}

The first benefit is that we can give the same non-recursive characterization used in \cite{OxWh93} for G2PMs with isolated nodes upon replacing ``$f(E)$'' by ``$n$'':

\begin{proposition}[cf.\ \cite{OxWh93}]\label{rankgen}
For any graph $G = (V,E)$ with $n = |V|$, including also graphs with circles, wisps, and negative isols,
\[
S'_G(x,y) = \sum_{A \subseteq E}x^{n - f(A)} y ^{2|A| - f(A)},
\]
and $S'_G(0,1)$ counts the number of spanning edge-subgraphs of $G$.
\end{proposition}

The proof is as given in \cite{OxWh93}, taking the above adjustments into account.  Henceforth we write $S'_G$ only when it is necessary to remind of the difference when $G$ may have isolated nodes.  After citing a theorem classifying GTGIs on G2PMs into families, where only the first one is governed by $S_G$, we state and prove our simpler characterization of that family.

\begin{theorem}[\cite{OxWh93}]\label{families}
Let $\phi$ be a generalized Tutte invariant on graphic 2-polymatroids.
% and suppose that at most two of $r,s,t,a,b,c,\mu,\nu$ are zero. 
%Then $\phi$ is of one of the following forms:
Then either:
\begin{enumerate}
  \item $a = \mu; d = \nu; \mu r = \mu\nu + c^2; \nu s = \mu\nu + b^2; t = b + c; \mu \neq 0; \nu \neq 0$ and $(\forall G)$:
\[
        \phi(G) = \mu^{|E| - f(E)/2} \nu^{f(E)/2} S_G(\frac{c}{(\mu\nu)^{1/2}}, \frac{b}{(\mu\nu)^{1/2}}); \quad\text{or}
\]
%  \item $t^2 = rs = ar + bt = ct + ds = \mu r + \nu s; st = at + bs; rt = cr + dt;$ and for all 2-polymatroids $G$,
%        \[
%        \phi(G) =
%        \left\{
%          \begin{array}{ll}
%            s^{|E| - f(E)} t^{f(E)}, & \hbox{if $f(E) \leq |E|$;} \\
%            r^{f(E) - |E|} t^{2|E| - f(E)}, & \hbox{otherwise.}
%          \end{array}
%        \right.
%        \]
\vspace{-1ex}
  \item $\phi$ belongs to other families whose details do not concern us here.
\end{enumerate}
\end{theorem}

%Now we state our second main theorem:

\begin{theorem}
%On graphical 2-polymatroids, the polynomial $Q_G(x)$ is a generalized Tutte-Grothendieck invariant belonging to the first family with:
A mapping $\phi$ from (augmented) G2PMs $G$ to polynomials $R_G(x,y)$ is a PGTGI if and only if it belongs to the first family of GTGIs with
\[
r  = x^2 - \frac{1}{2}, \quad s = -1, \quad t = x - 1, \quad a = \mu = 1, \quad b = -1, \quad c = x, \quad d = \nu = -\frac{1}{2}.
\]
\end{theorem}

\begin{proof}
\emph{Messy but crisp...}
\end{proof}

The essential ramification of all of this is that \emph{deletion-contraction recurrences in G2PMs correspond to evaluations of $S_G(x,y)$ at corresponding points.}  This puts focus on the complexity of evaluating $S_G(x,y)$ at these points.  The case of interest for quantum circuits has the recursion factors $\alpha = 1$ and $\beta = -0.5$.  We observe that this defines a polynomial $Q_G(x,y)$ in its own right.



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Extending PGTGIs for Higher $K$}



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Conclusions}



%
% ---- Bibliography ----
%
% BibTeX users should specify bibliography style 'splncs04'.
% References will then be sorted and formatted in the correct style.
%
 \bibliographystyle{splncs04}
 \bibliography{newpapers}
%
%\begin{thebibliography}{8}
%\bibitem{ref_article1}
%Author, F.: Article title. Journal \textbf{2}(5), 99--110 (2016)
%
%\bibitem{ref_lncs1}
%Author, F., Author, S.: Title of a proceedings paper. In: Editor,
%F., Editor, S. (eds.) CONFERENCE 2016, LNCS, vol. 9999, pp. 1--13.
%Springer, Heidelberg (2016). \doi{10.10007/1234567890}
%
%\bibitem{ref_book1}
%Author, F., Author, S., Author, T.: Book title. 2nd edn. Publisher,
%Location (1999)
%
%\bibitem{ref_proc1}
%Author, A.-B.: Contribution title. In: 9th International Proceedings
%on Proceedings, pp. 1--2. Publisher, Location (2010)
%
%\bibitem{ref_url1}
%LNCS Homepage, \url{http://www.springer.com/lncs}. Last accessed 4
%Oct 2017
%\end{thebibliography}
\end{document}
