Mathematical Preliminaries

A qubit serves as the quantum counterpart to the classical bit, forming the fundamental unit of quantum information. In the computational basis, we conventionally express the state of a single qubit using the basis states $\ket{0}$ and $\ket{1}$ or as a superposition of both, denoted as $\alpha\ket{0} + \beta\ket{1}$. Here, $\alpha$ and $\beta$ are complex probability amplitudes that satisfy the normalization condition $|\alpha|^2 + |\beta|^2 = 1$. Beyond the computational basis, another frequently employed basis for single qubits is the Hadamard basis. In this basis, we define two states: $\ket{+} = \frac{1}{\sqrt{2}}(\ket{0} + \ket{1})$ and $\ket{-} = \frac{1}{\sqrt{2}}(\ket{0} - \ket{1})$. The Hadamard basis is particularly valuable for quantum algorithms and quantum gates, providing a versatile framework for qubit manipulation and quantum state transformations. The states $\ket{+}$ and $\ket{-}$ represent equal superpositions with opposite relative phases.

To evolve qubit states we act unitary operators on them. Unitary operators are mathematical transformations that preserve the norm of a quantum state, ensuring that the probabilities associated with different outcomes sum to one. The evolution of qubit states through unitary operators is a fundamental concept in quantum mechanics and underpins the quantum circuit model. When a unitary operator acts on a qubit state, it induces a transformation, allowing the qubit to exist in a superposition of states. Mathematically, if $U$ is a unitary operator and $\ket{\psi}$ is the initial state of a qubit, the evolved state is given by $\ket{\psi'} = U\ket{\psi}$. This transformation preserves the inner product of the state vector, maintaining the normalisation condition. Unitary operations form the basis for quantum gates in quantum circuits. These gates manipulate qubit states by applying specific unitary transformations, allowing for the execution of quantum algorithms. Examples include: Hadamard gate, cnot gate and the Pauli–$X$, Pauli–$Y$, Pauli–$Z$ gates.

A Hamilonian, $H$, is a self–adjoint (Hermitian) operator that represents the total energy of a quantum system. The spectrum of a Hamiltonian, $\sigma(H)$, is the set of all possible eigenenergy values for the system. The ground state energy of a Hamilonian, $\lambda_0$ is the lowest eigenenergy value in the spectrum. The ground state of a Hamiltonian, $\ket{\psi_0}$, is the corresponding eigenstate. A $k$–local Hamiltonian is a Hamiltonian that can be expressed as a sum of terms, each of which acts non–trivially on at most $k$ qubits. A $k$–local Hamiltonian is said to be frustration–free if there exists a non–trivial state that is simultaneously an eigenstate of each term in the Hamiltonian.

A local Hamiltonian is said to have an interaction graph that completely specifies the interactions between particles. The interaction graph $G = (V,E)$ contains vertices that correspond to the particles. The (hyper)edges in the graph occur for each individual Hamiltonian term present and act over the respective particles. A simple example is a $2$–local Hamiltonian on $n$ qubits. The interaction graph has $|V(G)|=n$ and all edges correspond directly to each $2$–local term.

The partition function, $Z = \text{Tr}(e^{-\beta H})$, contains all the information about the Hamiltonian's spectrum. The quantity is central to statistical mechanics and can be used to find all thermodynmaical quantities of a system. The quantity $\beta = 1/k_B T$ is commonly referred to as the inverse temperature.

Model Preliminaries

In each model definition below, we adopt a general approach, leaving the exact interaction type and underlying geometry unspecified. We represent the underlying graph by $\Lambda$. The particles involved in the Hamiltonian interactions are labeled using Roman indices. The interaction distance can sometimes be inferred from the underlying geometry. For instance, on a 2D square lattice, interactions are assumed to be nearest neighbors unless explicitly specified otherwise. However, this restriction may not apply to a spatially sparse lattice. This highlights the subtle difference that can arise with algebraically local interactions and geometrically local ones.

The definitions outlined in this section are not exhaustive but cover a significant proportion of commonly occurring examples. As an additional point, it is crucial to note that interaction strengths, such as $J_{ij}$, $K$, $t_{\text{hop}}$, etc., do not possess predetermined values in the general setting. To maintain consistency with the information provided on the website, we propose a novel naming convention for Pauli Hamiltonians. This convention aims to establish a universal naming standard that completely specifies the terms present, minimizing ambiguities in model names. While the primary focus of this work is on $2$–local Hamiltonians, it is important to highlight that the proposed convention is adaptable to other locality degrees. Throughout our discussion, we provide illustrative examples to emphasize each aspect of the proposed naming convention. These examples serve as practical demonstrations, enhancing understanding and showcasing the convention's applicability. As a final note, we mention the addition of new Hamiltonian prefixes. Simply stating "the antiferromagnetic [name] Hamiltonian ..." is insufficient in the realm of complexity theory; this is because the prefix 'antiferromagnetic' does not completely specify the problem instance. Antiferromagnetism only refers to the interaction strengths being non–negative, not about the uniformity. We, therefore, propose compact prefix notation to help specify the exact interaction strengths of a given model.

Naming Convention

  1. 2–local and 1–local terms are divided via '$/$' where the left hand side represents 2–local terms.
  2. Repeated ($XX, YY, ZZ$), are represented by a single letter such that the repetition is implied for terms on the left.
    • (x/z)–H = $\displaystyle\sum_{i,j} J_{ij}X_iX_j + \displaystyle\sum_{i,j} h_iZ_i$
  3. Cross ($XZ, YX, ZY, \ldots$), the terms are bracketed $[*]$ or $[\![ * ]\!]$ (for when both cross terms appear).
    1. If it is known that both cross terms are present under different general parameters, then the superscript $*$ can be used.
    • ([xz]/.)–H = $\displaystyle\sum_{i,j} Q_{ij} X_iZ_j$
    • ($[\![$xy$]\!]$/z)–H = $\displaystyle\sum_{i,j} P_{ij}\big( X_iY_j + Y_iX_j \big) + \displaystyle\sum_{i,j} h_iZ_i$
    • ([xz]-[zx]/.)–H = ($[\![$xy$]\!]$*/.)–H = $\displaystyle\sum_{i,j} Q_{ij} X_iZ_j + T_{ij}Z_iX_j$
  4. The name follows the lexicographical ordering.
  5. Terms which adhere to different parameters are separated via a '$-$'.
    • (x-yz/.)–H = $\sum_{i,j} J_{ij}X_iX_j + K_{ij}\big(Y_iY_j + Z_iZ_j\big)$
  6. Each parameter, $J, K, \ldots$, is assumed to be in $\mathbb{R}$.
    1. If all parameters are $\in\mathbb{R}^\pm$ then use the superscript $\pm$.
      • (x/z)+–H = $\displaystyle\sum_{i,j} J_{ij}^{^{(\geq 0)}}X_iX_j + \displaystyle\sum_{i,j} h_i^{^{(\geq 0)}}Z_i$
    2. Underline the terms for which the parameters are uniform.
      • ([xz]--[zx]/.)–H = $\displaystyle\sum_{i,j} Q^{^{(\leq 0)}} X_iZ_j + T_{ij}Z_iX_j$

It should be noted that, like all other naming conventions, there are Hamiltonian instances that are difficult to attribute a cohesive name to that completely specifies the terms. For example, a Hamiltonian with several different mixed terms and repeating terms, all of which adhere to different types of interaction strengths, can be too complex for a specific name. In such an example, it is beneficial to just state the Hamiltonian outright and if relevant, attribute a unique name to it. The naming convention above is proposed as a compact way of referring to common model instances in many–body physics, such that, in the complexity sector, it becomes easy to see how each model is related.

Model Prefixes

The two frequent subclasses of many–body models fall into ferromagnetic and antiferromagnetic. We define the ferromagnetic regime as each interaction strength (where appropriate) having some non–positive value. We define the antiferromagnetic regime as each interaction strength (where appropriate) having some non–negative value. To further specify different model types, we note that a given model can either have variable interaction strengths or constant interaction strengths. By variable, we refer to the fact that $J_{ij}$ — the interaction strength between qubit $i$ and qubit $j$, need not be the same as $J_{ik}$ — the interaction strength between qubit $i$ and qubit $k$. Constant interaction strengths then refer to $J_{ij} = J$ for all $i,j\in\Lambda$.

Here we stick to the antiferromagnetic (aF) sector of a model; the same principles apply to the ferromagnetic sector also. The two immediate subclasses of a general Hamiltonian like $$ H = \displaystyle\sum_{i,j} J_{ij}X_iX_j + K_{ij}Y_iY_j $$ are clearly, $$ H = \displaystyle\sum_{i,j} J^{^{(\geq 0)}}_{ij}X_iX_j + K^{^{(\geq 0)}}_{ij}Y_iY_j \quad\quad H = \displaystyle\sum_{i,j} J^{^{(\geq 0)}}X_iX_j + K^{^{(\geq 0)}}Y_iY_j $$ We refer to the left example as Isotropic Antiferromagnetic and the right as Homogeneous Antiferromagnetic. The need for this subtle difference can be seen in a number of instances. For example, a HaF instance on a positively weighted graph is an equivalent to the IaF instance. Further, an IaF instance on a weighted graph that has positive and negative weights is equivalent to the general instance. Another angle can be seen from the conclusions of [SV09] and [PM15], who both showed the complexity of a specific instance of the Heisenberg Hamiltonian. The former demonstrated that the antiferromagnetic Heisenberg Hamiltonian with some global parameter $J$ and external fields was QMA–complete. The latter showed a similar result with interaction strengths $J_{ij}$ but without external fields. The question whether the HaF–Heisenberg Hamiltonian, on an interaction graph with constant weights, can simulate the IaF–Heisenberg Hamiltonian (as seen in [PM15]) is not so trivial and remains an open problem.

Notice that in the event $K=J$, in either of the above cases, we actually reduce to another model. Let us refer to the event where all interaction parameters have the same value as the Uniform case. We make a note there that for situations concerning the Heisenberg Hamiltonian or (xz/.)–Hamiltonian, for example, the HaF case is entirely equivalent to the Uniform aF case. Clearly however, for the example above, the Uniform–(x–y/.)–Hamiltonian is equivalent to the (xy/.)–Hamiltonian. This is one instance where the novel naming convention becomes particularly useful.

For the more niche examples, such as $$ H = \displaystyle\sum_{i,j} J_{ij}X_iX_j + K^{^{(\geq 0)}}_{ij}Y_iY_j + LZ_iZ_j, $$ where there is a mixture of different interaction strength conditions. On the one hand, simply referring to this as an instance of the (x–y–z/.)–Hamiltonian is acceptable but does not capture the full picture. We therefore propose an indication of this outlier example by introducing the prefix Mixed.

Model Definitions

Parent Pauli Hamiltonian

$$ H =\sum_{i,j \in \Lambda} a_{i}^\mu \sigma_\mu \otimes b_{j}^\nu \sigma_\nu $$

(x–y–z/.) Hamiltonian

$$ H=\sum_{i,j\in\Lambda}J_{ij}X_iX_j + K_{ij}Y_iY_j + L_{ij}Z_iZ_j $$

(xy–z/.) Hamiltonian

$$ H=\sum_{i,j\in\Lambda}J_{ij}\big(X_iX_j + Y_iY_j\big) + L_{ij}Z_iZ_j $$

This is often refered to as the "$XXZ$–Hamiltonian" in physics literature.

(x–y/.) Hamiltonian

$$ H=\sum_{i,j\in\Lambda}J_{ij}X_iX_j + K_{ij}Y_iY_j $$

This Hamiltonian and the (xy/.) Hamiltonian are often confused. It can be found that each are refered to as "the $XY$–Hamiltonian". With the present convention, this ambiguity is removed and the confusion no longer persists.

(xy/.) Hamiltonian

$$ H=\sum_{i,j\in\Lambda}J_{ij} \big(X_iX_j + Y_iY_j\big) $$ Notice this Hamiltonian is a restricted version of the (x–y/.) Hamiltonian; specifically when $K_{ij} = J_{ij}$

(x–z/x–z) Hamiltonian

$$ H=\sum_{i,j\in\Lambda} J_{ij} X_iX_j + L_{ij} Z_iZ_j + \sum_{i\in\Lambda} f_i X_i + h_i Z_i $$ This Hamiltonian is referred to as the $ZZXX$–Hamiltonian in [BL08]. This is a somewhat confusing name if no prior exposure to the Hamiltonian's explicit form is present. The new naming convention creates a clear picture of the terms involved.

($[\![$xz$]\!]$*/x–z) Hamiltonian

$$ H=\sum_{i,j} Q_{ij} X_iZ_j + T_{ij} Z_iX_j + \sum_{i\in\Lambda} f_i X_i + h_i Z_i $$ This Hamiltonian is referred to as the $ZX$–Hamiltonian in [BL08]. This is a somewhat confusing name if no prior exposure to the Hamiltonian's explicit form is present. The new naming convention creates a clear picture of the terms involved.

Weighted (xyz/.) Hamiltonian

$$ H=\sum_{i,j\in\Lambda} J_{ij} \big( \alpha X_iX_j + \beta Y_iY_j + \gamma Z_iZ_j\big) $$ We use the term weighted to signify the parameters, $\alpha$, $\beta$ and $\gamma$. Technically, for arbitary parameters, this model is entirely equivalent to the (x–y–z/.) Hamiltonian. For the purposes of the work conducted in [PM15], this definition is appropriate.

General Heisenberg Model

$$ H=\sum_{i,j\in\Lambda}J_{ij}\big(X_iX_j + Y_iY_j + Z_iZ_j\big) $$ It is common for the Heisenberg Hamiltonian to be defined with a single external field. In this work we stick to the above defintion for clarity. Within complexity classifications, external fields can have a significant impact on the outcome. We would therefore refer to a Heisenberg Hamiltonian with external fields in that context; it is also important to ensure the specification of the external fields.

General Transverse Ising Model

$$ H =\sum_{i,j\in\Lambda}L_{ij}Z_iZ_j + \sum_{i\in\Lambda}f_iX_i $$

General Fermi–Hubbard Model

$$ H = \sum_{i,j\in\Lambda}\sum_{\sigma}t_{ij} c_{i\sigma}^\dagger c_{j\sigma} + t_{ji} c_{j\sigma}^\dagger c_{i\sigma} + \sum_{i\in\Lambda}U_{i}n_{i\uparrow}n_{i\downarrow} $$

General Bose–Hubbard Model

$$ H = \sum_{i,j\in\Lambda}t_{ij} a_i^\dagger a_j + t_{ji} a_j^\dagger a_i + \frac{1}{2}\sum_{i\in\Lambda}U_{i}n_i(n_i - 1) $$

General Electronic Structre Hamiltonian

$$ H = \sum_{i,j \in [n]}\sum_{\sigma} t_{ij} c_{i\sigma}^\dagger c_{j\sigma} + t_{ji} c_{j\sigma}^\dagger c_{i\sigma} + \frac{1}{2} \sum_{i,j,k,l \in [n]}\sum_{\sigma,\tau} u_{ijkl}c_{i\sigma}^\dagger c_{j\tau}^\dagger c_{k\sigma} c_{l\sigma} $$

The $t$–$J$ Model*

$$ H = \sum_{i,j\in\Lambda}\frac{4t_{ij}^2}{U} \boldsymbol{\sigma}_i \cdot \boldsymbol{\sigma}_j $$