## A Graph-Theoretic Framework for Free-Parafermion Solvability

August 20, 2024

Samuel Elman, David Wood, Adrian Chapman, and I have just uploaded to arXiv our paper "A Graph-Theoretic Framework for Free-Parafermion Solvability". In this paper we show that a quantum spin system has an exact free-parafermion solution if its frustration graph is an oriented indifference graph. Our characterisation extends that given for free-fermion solvability.

Fix $d\in\mathbb{Z}_{\geq2}$. Let $X_d:=\sum_{k\in\mathbb{Z}_d}\ket{k+1}\bra{k}$ and $Z_d:=\sum_{k\in\mathbb{Z}_d}\omega_d^k\ket{k}\bra{k}$ denote the *generalised Pauli operators* in a $d$-dimensional space, often referred to as the shift and clock operators. The *Weyl-Heisenberg group* in a $d$-dimensional space is generated by the operators

These operators form a complete basis for operators on a $d$-dimensional Hilbert space. A complete basis for operators on an $n$-qudit system can be formed by taking tensor products of these operators, that is,

$$\mathcal{W}_d(n) := \left\{\omega_d^{\frac{\alpha\cdot\beta}{2}}\bigotimes_{l\in\mathbb{Z}_n}X_d^{\alpha_l}Z_d^{\beta_l}\mid\alpha,\beta\in\mathbb{Z}_d^n \right\}.$$We consider $n$-qudit systems with Hamiltonians written in the generalised Pauli basis

$$H = \sum_{v \in V}h_v,$$where $V$ is subset of $\mathbb{Z}_d^{2n}$ and $h_v=b_vw_v$ for $b_v\in\mathbb{R}{\setminus}\{0\}$ and $w_v$ an element of $\mathcal{W}_d(n)$ determined by the label $v$ in the natural way. Note that the Hamiltonian is not necessarily Hermitian. However, it can be made Hermitian by adding its Hermitian conjugate. We shall restrict our attention to Hamiltonians that satisfy $h_uh_v=\omega_d^kh_vh_u$ with $k$ in $\{-1,0,1\}$ for all $u$ and $v$ in $V$. This condition is always true when $d=3$.

**Definition 1 (Frustration graph)**The

*frustration graph*of a Hamiltonian is the oriented graph $G=(V,E)$ with vertex set $V$ and edge set $E=\left\{(u,v) \mid h_uh_v=\omega_dh_vh_u\right\}$.

An *indifference ordering* of a graph is an ordering of the vertices such that every induced path is either increasing or decreasing with respect to the ordering. A graph is an *indifference graph* if it has an indifference ordering. A *perfect elimination ordering* of a graph is an ordering of the vertices such that, for each vertex $v$, the neighbours of $v$ that precede $v$ in the ordering form a clique.

Let $G$ be an oriented graph. An *oriented perfect elimination ordering* of $G$ is a perfect elimination ordering that is consistent with the orientation. An *oriented indifference graph* is an indifference graph that is oriented consistently with an indifference ordering.

Our main result may be stated as follows.

**Theorem 1**Let $H$ be a qudit Hamiltonian with an oriented indifference frustration graph. Then $H$ has an explicit free-parafermion solution.