# Defining optimal fermion–qubit mappings

Mitchell Chiew  Sergii Strelchuk  DAMTP, Centre for Mathematical Sciences,
University of Cambridge, Cambridge CB30WA, UK

(August 27, 2024)

###### Abstract

Simulating fermionic systems on a quantum computer requires a high–performing
mapping of fermionic states to qubits. The key characteristic of an efficient
mapping is its ability to translate local fermionic interactions into local
qubit interactions, leading to easy–to–simulate qubit Hamiltonians.

All fermion–qubit mappings must use a numbering scheme for the fermionic modes
in order to make translation to qubit operations possible. We make a
distinction between the unordered, symbolic labelling of fermions and the
ordered, numeric labelling of the qubits to which the fermionic system maps.
This separation shines light on a new way to design fermion–qubit mappings by
making use of the extra degree of freedom – the enumeration scheme for the
fermionic modes. This allows well–defined concepts of optimal fermion–qubit
mappings: for example, the main focus of this paper is in identifying
Jordan–Wigner transformations that minimise the average number of Pauli
matrices in each term of the qubit Hamiltonians they produce. Given a
fermionic system, choosing the optimal fermionic enumeration schemes to
minimise practical cost functions of the target qubit Hamiltonian does not
expend any resources.

We demonstrate how Mitchison and Durbin’s enumeration pattern is optimal for
minimising the average Pauli weight of Jordan–Wigner transformations of the
systems interacting in square fermionic lattices. This leads to qubit
Hamiltonians consisting of terms with average Pauli weights 13.9% shorter than
previously known. Furthermore, by adding only two ancilla qubits we introduce
a new class of fermion–qubit mappings, and reduce the average Pauli weight of
Hamiltonian terms by 37.9% compared to previous methods. For other natural
$n$–mode fermionic systems we find enumeration patterns which result in
$n^{\frac{1}{4}}$ improvement in average Pauli weight over naïve enumeration
schemes.

##  I Introduction

Simulating physical systems is one of the most promising applications of
quantum computers. Fermionic systems are essential components in several
fields of theoretical and experimental physics, from quantum physics [1, 2, 3,
4] to quantum chemistry and condensed matter [5, 6, 7] to quantum field
theories [8]. Fermions pose complex, often intractable computational
challenges when studied with the aid of classical computers, such as the
electronic structure problem [9], studying properties of gauge theories that
govern strong interactions between quarks and gluons [10], determining ground
state properties of fermionic Hamiltonians [11] and many others.

One can break down all quantum algorithms for fermionic simulation into three
sequential steps: 1) initialising the quantum register, 2) applying unitary
gates to the qubits, and 3) measuring the result to obtain an estimate for the
desired molecular property or other quantity of interest. Within this
framework, algorithms may encode the fermionic Hamiltonian via first or second
quantisation. Fermi–Dirac statistics impose asymmetry on fermionic systems’
wavefunctions, and using first quantisation of the system’s Hamiltonian, one
can incorporate this asymmetry into the qubit basis itself or use the qubits
to directly encode the wavefunction into real–time and real–space [12, 13, 14,
15]. In contrast, second quantisation encodes the asymmetry into the qubit
operators rather than the quantum states [16], and provides a number of
distinct advantages over representations in the first quantisation [17, 18].

Quantum algorithms employing second quantisation require an important fourth,
pre-emptive step: the fermion–qubit mapping, which we label 0). In the second
quantisation picture, a quantum algorithm must map each term of the fermionic
Hamiltonian into a sequence of Pauli matrices acting on qubits. The original
problem thus becomes a $k$–local Hamiltonian problem, where $k$ depends on the
choice of fermion–qubit mapping.

Figure 1: Schematic showing the purpose of a fermion–qubit mapping, the
factors that influence its effectiveness, and various cost functions under
which one might judge the effectiveness of a mapping.

This work introduces a new approach to defining and designing fermion–qubit
mappings, which directly leads to a significant reduction in the complexity of
some quantum simulation algorithms. There is practical value in any
improvement to the sleekness of quantum simulation algorithms’ designs. While
the $k$–local Hamiltonian problem is $\QMA$–complete [19], enormous value
remains in finding or approximating solutions in the average case–scenarios
for practical problems, such as molecular electronic structure [20]. Turning
from complexity theory, then, to focus on the more practical elimination of
redundant costs in steps 0)–3) of existing fermionic simulation algorithms,
there have been a number of recent developments in quantum computing that
could make solutions to the above problems feasible [12, 16, 15, 14, 21, 20,
13]. Many of these approaches [12, 13] rely on phase estimation [22, 23] and
thus require an impractically large number of qubits and operations in order
to keep the register of the quantum computer coherent [24]. Algorithms for
near–term quantum computers have sprung up in answer to these challenges, such
as the variational quantum eigensolver [24, 25, 16], which is only just coming
within reach of current technology.

Some improvements to quantum simulation algorithms come with no caveats: for
example, careful parallelisation of Hamiltonian terms during Trotterisation in
step 2) of a phase estimation algorithm can cancel out long strings of Pauli
matrices, a simple adjustment that does not come at the expense of any
additional resources [26]. However, the search for the best fermion–qubit
mapping has largely not been met with much progress because the task of
simulating fermionic interactions in a complexity–theoretic sense is very
difficult to formalise. To bring the problem of fermionic simulation closer to
meeting constraints of near–term quantum technology, it is crucially important
to establish optimal protocols that strike a balance between competing
resources, such as the number of qubits, local quantum operation counts, or
quantum circuit depth. This is a complex challenge, as the definition of an
optimal protocol may depend on the topology of the physical system to be
simulated (e.g. the optimal strategy for simulating a fermionic square lattice
may be different to that of a molecule), or the limitations of the quantum
hardware at hand (e.g. only permitting nearest–neighbour interactions between
qubits).

The century–old work of Jordan and Wigner [27] inspired the idea of
fermion–qubit mappings, when Lieb et al. used their method to solve the
$XY$–model Hamiltonian classically in 1961 [28]. In 2001, Ortiz employed the
transformation as a fermion–qubit mapping in the first explicit proposal of a
quantum simulation of a fermionic Hamiltonian [21]. The Jordan–Wigner
transformation is intuitive and performs well in simulating nearest–neighbour
Hamiltonians acting on 1D chains of fermionic modes, but experiences
impracticably large overheads in higher dimensions.

Fermion–qubit mappings |  $\overline{\text{JW}}_{f_{\text{S}}}$ [17] |  $\overline{\text{JW}}_{f_{\text{M}}}$ (III) |  $\overline{\text{JW}}_{f_{\text{M}}+2}$ (IV) | BK superfast [29] | VC [17] | AQM [30]
---|---|---|---|---|---|---
($H_{\text{fermion}}=$ $N$$\times$$N$ square lattice | (S–pattern) | (pattern from [31]) | (+2 qubits) |  |  |
Qubit number | $N^{2}$ | $N^{2}$ | $N^{2}+2$ | $2N^{2}-2N$ | $2N^{2}$ | $2N^{2}-N$
Qubit/mode ratio | 1 | 1 | $1+\frac{2}{N^{2}}$ | $2-\frac{2}{N}$ | 2 | $2-\frac{1}{N}$
Average $X$$X$ hopping weight | $\frac{1}{2}N+\frac{3}{2}$ | $0.43N+1.78$ | $0.31N+1.78$ | $\mathcal{O}(1)$ | $\mathcal{O}(1)$ | $\mathcal{O}(1)$
Table 1: Comparison between fermion–qubit mappings based on the number of
qubits required and the average Pauli weight of hopping terms of the form
$XZZ...ZX$ in the qubit Hamiltonian. In this case, the comparison is for
fermionic Hamiltonians of $N^{2}$–mode systems where hopping terms form a
square lattice of interactions. The mapping from Section III gives the minimum
average Pauli weight without the assistance of ancilla qubits, and the mapping
from Section IV improves this result while also maintaining a qubit/mode ratio
of $1+\mathcal{O}\left({\frac{1}{N^{2}}}\right)$.

Fermionic systems that permit only local interactions on a 2D or 3D lattice
are a major focus of study [32]. These systems are difficult to simulate, even
for quantum computers, because an overwhelming number of local fermionic
interactions become non–local – and hence timely and costly to simulate – once
mapped to the qubit picture. In recent years, there have been a flurry of
results tackling this challenge introducing new fermion–qubit mappings as well
as generalising the existing ones to higher dimensions [33, 34, 35, 30, 36]. A
common theme among these proposals is the use of ancilla qubits [35, 17, 30].
Such mappings can produce local qubit Hamiltonians, and could make small
instances of a problem within reach of modest quantum computers.

Our new approach makes use of a new degree of freedom of fermion–qubit
mappings: the ability to index the fermionic modes in any order, a process we
dub choosing the fermionic enumeration scheme. While trivial for a string of
fermions interacting only with nearest–neighbours modes, the choice of
enumeration scheme has the potential to dramatically improve the average
locality of the fermion–qubit mappings for fermionic systems in 2D and above.
Examining enumeration schemes, and finding the most efficient ones, we show
how to reduce various cost functions of the target qubit Hamiltonian relating
to scarce physical resources. This requires no additional resources such as
additional Hamiltonian terms or ancilla qubits!

Thus, we arrive at the crux of our work: for a given fermionic system and a
given quantum computing technology, a fermion–qubit mapping cannot be
considered optimal unless its fermionic enumeration scheme minimises the
scarcest physical resource. Many innovations in fermion–qubit mappings have
been in aid of reducing the maximum number of qubits upon which any one term
in the Hamiltonian acts [29, 34, 30, 35] This is an important metric in a
complexity–theoretic sense – it is the ‘$k$’ in ‘$k$–local Hamiltonian’.

Other metrics may be more practical in near–term quantum algorithms. For
example, the number of Pauli measurements in a variational quantum eigensolver
depends on the overall number of Pauli matrices appearing in all terms in the
qubit Hamiltonian, not just the longest term. While our method could be
tailored to improve many metrics of fermion–qubit mappings, the focus of this
work is on improving the average locality of the qubit Hamiltonian terms. The
only other work that has used this metric for fermion–qubit mappings is [36],
which we discuss and incorporate into our work in Section II.6. We believe
this paper is the first to focus in detail on minimising the average Pauli
weight of fermion–qubit mappings.

In a broad class of problem fermionic Hamiltonians with non–local hopping
terms, we show that minimising the average Pauli weight of a Jordan–Wigner
type mapping is equivalent to the edgesum problem from graph theory [31, 37,
38, 39]. When compared to the only other ancilla–free mapping for the 2D
fermionic lattice – which uses the S–pattern enumeration scheme, introduced by
Verstraete and Cirac [17] – our method directly reduces the average Pauli
weight of the terms in the qubit Hamiltonian by a constant factor ($\approx$
$13.9\%$). Our optimal fermion–qubit mapping uses a carefully selected
enumeration scheme based on a special pattern recognised by Mitchison and
Durbin in their seminal work [31], and culminates in:

Theorem 1 [Informal] For a fermionic Hamiltonian acting on a system of
$n=N^{2}$ local fermionic modes with interactions only between nearest
neighbours on the square $N$$\times$$N$ lattice, the Jordan–Wigner
transformation that uses the Mitchison–Durbin pattern to enumerate the modes
minimises the average Pauli weight of the qubit Hamiltonian.

The structure of the paper is as follows: in Section II we provide a
self–contained introduction to fermion–qubit mappings and identify the role
that fermionic enumeration schemes play. We give a new, broad definition that
encapsulates all $n$–mode to $n$–qubit mappings before narrowing our focus to
the Jordan–Wigner transformation. We follow with results from complexity
theory that will be used to prove our main result.

In Section III, we discuss the maximum Pauli weight and measurement depth of
qubit Hamiltonians, which are practical figures of merit worth minimising in
fermion–qubit mappings. We present Theorem 1 for constructing Jordan–Wigner
transformations for 2D fermionic lattice systems that they minimise the
average Pauli weight of qubit Hamiltonian terms. We argue that our approach
can improve simulations for many fermionic systems, and use an heuristic
approach to find Jordan–Wigner transformations for certain $n$–mode fermionic
systems that provide average Pauli weights shorter than those of naïve
alternatives by a factor of $\mathcal{O}(n^{1/4})$.

In Section IV, we explain auxiliary qubit mapping techniques and modify our
fermion–qubit mapping to improve Theorem 1’s 13.9% advantage over the Z– and
S–patterns to nearly 38% using just two ancilla qubits.

Finally, in Section V we discuss open problems and directions for further
research. We also mention the qubit routing problem as a potential
generalisation of the optimisation problems described in this paper.

##  II Defining fermion–qubit mappings

This section outlines the theory of fermion–qubit mappings: Section II.1
describes the motivation, while Section II.2 the requirements of a mapping.
The naïve definition of the Jordan–Wigner transformation appears in Section
II.3, before we introduce the Jordan–Wigner transformation with fermion
enumeration schemes in Section II.4, which is the working definition we use
for the rest of the paper. We generalise our definition of fermion–qubit
mappings in Section II.5 to demonstrate that the principle of optimising over
enumeration schemes is a valid for improving all fermion–qubit mappings, with
a specific example in Section II.6. In Section II.7 we detail the graph theory
related to the problem of finding optimal Jordan–Wigner transformations with
fermion enumeration schemes.

###  II.1 Goal of fermion–qubit mappings

Figure 2: The role of enumeration schemes is hidden in naïve descriptions of
fermion–qubit mappings, but becomes apparent in our general definition; it is
also recognisable in the ternary tree transformation.

Typical second–quantised fermionic Hamiltonians of interest, such as molecular
electronic Hamiltonians, have the form

$\displaystyle H_{\text{fermion}}$
$\displaystyle=\sum_{i,j=0}^{n-1}(c_{\alpha_{i}\alpha_{j}})a_{\alpha_{i}}^{\dagger}a_{\alpha_{j}}$
(1)
$\displaystyle\qquad+\frac{1}{2}\sum_{i,j,k,l=0}^{n-1}(c_{\alpha_{i}\alpha_{j}}^{\alpha_{k}\alpha_{l}})a_{\alpha_{i}}^{\dagger}a_{\alpha_{j}}^{\dagger}a_{\alpha_{k}}a_{\alpha_{l}}\,,$

where the indices $\\{\alpha_{0},\alpha_{1},\dots,\alpha_{n-1}\\}$ are
distinct, unordered, symbolic labels for the $n$ fermionic modes, treating
excitation states of each individual electron as distinct modes. For example,
in the Fermi–Hubbard model [40] the fermions are electrons, and the
coefficients $c_{\alpha_{i}\alpha_{j}}$ and
$c_{\alpha_{i}\alpha_{j}}^{\alpha_{k}\alpha_{l}}$ are respectively one– and
two–electron overlap integrals. A fermionic Hamiltonian consisting of just
quadratic single–particle terms $a_{\alpha_{i}}^{\dagger}a_{\alpha_{j}}$ may
easily be diagonalised and its eigenvalues simply read off [41]. The presence
of quartic terms
$a^{\dagger}_{\alpha_{i}}a^{\dagger}_{\alpha_{j}}a_{\alpha_{k}}a_{\alpha_{l}}$
usually makes simulation of the Hamiltonian classically intractable, and as
such an object of interest for prospective quantum algorithms.

A fermion–qubit mapping is a tool to translate from the fermionic picture into
a Hamiltonian that can be implemented on qubits in a laboratory:

$\displaystyle H_{\text{fermion}}\longmapsto$ $\displaystyle
H_{\text{qubit}}=\sum_{ij}({c}_{\alpha_{i}\alpha_{j}})A_{i}^{\dagger}A_{j}+\frac{1}{2}\sum_{ijkl}({c}_{\alpha_{i}\alpha_{j}}^{\alpha_{k}\alpha_{l}})A_{i}^{\dagger}A_{j}^{\dagger}A_{k}A_{l}$
(2)

The $A_{i}$ are the qubit equivalents of the annihilation operators
$a_{\alpha_{i}}$ and are members of the Pauli group $G_{n}$ on $n$ qubits:

$\displaystyle
G_{n}\coloneqq=\text{span}_{\mathds{C}}\big{\\{}\\{\mathds{1},X,-iY,Z\\}^{\otimes
n}\big{\\}}\,.$ (3)

We use the notation $X=\sigma_{x}$, $Y=i\sigma_{y}$, $Z$ $=$ $\sigma_{z}$ for
the Pauli operators on a single qubit, and use the subscript $i$ on the Pauli
operators to indicate action on the $i$th qubit.

###  II.2 Canonical anticommutation relations

As in [29], our convention is to treat fermionic modes as either occupied or
unoccupied, treating any spin–up and spin-down modes as distinct. Thus, a
system of $n$ identical fermionic modes inhabits a $2^{n}$–dimensional
complex–valued Hilbert space.

Given a quantum system with $n$ fermionic modes, its Hamiltonian
$H_{\text{fermion}}$ is of the form of Equation 1. The canonical
anticommutation relations fully describe the fermionic operators:

$\displaystyle\\{a_{\alpha_{i}},a_{\alpha_{j}}\\}=0\,,\,\\{a_{\alpha_{i}}^{\dagger},a_{\alpha_{j}}^{\dagger}\\}=0\,,\,\\{a_{\alpha_{i}},a_{\alpha_{j}}^{\dagger}\\}$
$\displaystyle=\delta_{ij}\mathds{1}\,.$ (4)

For each fermionic label $\alpha_{i}\in\\{\alpha_{0},\dots\alpha_{n-1}\\}$,
there are two labels
$\beta_{2i},\beta_{2i+1}\in\\{\beta_{0},\dots,\beta_{2n-1}\\}$ which relate
the operators $a_{\alpha_{i}}$ and $a_{\alpha_{i}}^{\dagger}$ via the Majorana
operators:

$\displaystyle\gamma_{\beta_{2i}}$
$\displaystyle=a_{\alpha_{i}}+a^{\dagger}_{\alpha_{i}}$ (5)
$\displaystyle\gamma_{\beta_{2i+1}}$
$\displaystyle=-i(a_{\alpha_{i}}-a_{\alpha_{i}}^{\dagger})\,.$ (6)

The Majorana operators
$\\{\gamma_{\beta_{0}},\gamma_{\beta_{1}},\dots,\gamma_{\beta_{2n-1}}\\}$ form
an alternative set of fermionic operators, equivalent to the complete set of
creation and annihilation operators
$\\{a_{\alpha_{0}},a^{\dagger}_{\alpha_{0}},\dots,a_{\alpha_{n-1}},a^{\dagger}_{\alpha_{n-1}}\\}$.
Each of the Majorana operators is its own Hermitian conjugate, and, by
construction, neither $\gamma_{\beta_{2i}}$ nor $\gamma_{\beta_{2i+1}}$ are
involved in the definition of any other $a_{\alpha_{j}}$ for $j\neq i$. The
Majoranic equivalent to the anticommutation relations 4 is thus simply

$\displaystyle\gamma_{\beta_{i}}=\gamma_{\beta_{i}}^{\dagger}\,,\quad\\{\gamma_{\beta_{i}},\gamma_{\beta_{j}}\\}=2\delta_{ij}\mathds{1}\,.$
(7)

for $i,j\in\\{0,1,\dots,2n-1\\}$.

In Sections III and IV, we use the language of creation and annihilation
operators $a_{\alpha}^{\dagger},a_{\alpha}$, since they are the ingredients of
the Jordan–Wigner transformation. However, Majorana operators are necessary to
explore the complete picture of enumeration schemes’ role within fermion–qubit
mappings, as we explore in Section II.5.

###  II.3 The standard (naïve) definition of the Jordan–Wigner transformation

Suppose that the labels for the fermionic modes were ordered via the scheme
$\alpha_{0}\mapsto 0,\alpha_{1}\mapsto 1,\dots,\alpha_{n-1}\mapsto n-1$. Then,
with the notion of order for the fermionic modes, we could define the system’s
Fock space with the occupancy number basis
$\\{\ket{j_{0},j_{1},\dots,j_{{n-1}}}:j_{i}\in\\{0,1\\}\\}$, where $j_{i}$
denotes the occupancy of the $i$th fermionic mode. The annihilation operators
act as

$\displaystyle
a_{\alpha_{i}}|j_{0}\dots\underbrace{0}_{\makebox[0.0pt]{\footnotesize$i$th
mode}}\dots j_{{n-1}}\rangle=0$ (8) $\displaystyle
a_{\alpha_{i}}|j_{0}\dots\underbrace{1}_{\makebox[0.0pt]{\footnotesize$i$th
mode}}\dots j_{{n-1}}\rangle$ (9)
$\displaystyle\qquad\qquad=(-1)^{\sum_{k=1}^{i-1}j_{k}}|j_{0}\dots\underbrace{0}_{\makebox[0.0pt]{\footnotesize$i$th
mode}}\dots j_{{n-1}}\rangle\,,$

while $a^{\dagger}_{\alpha_{i}}$ acts as the Hermitian conjugate of $a_{i}$.
Equations 8 and 9 are equivalent to Equation 4 [41]. This formulation allows
us to define the Jordan–Wigner transformation in the original way [27], as a
map from an $n$–mode fermionic system to an $n$–qubit system, where the qubits
also have ordered labels $0,1,\dots,n-1$:

######  Definition 1.

_(Naïve Jordan–Wigner transformation.)_ The naïve Jordan–Wigner transformation
for a system with $n$ fermionic modes is a linear map
$\overline{\text{JW}}_{\text{naïve}}$ from the complex span of the $2n$
fermionic creation and annihilation operators to the Pauli group $G_{n}$. In
particular, $\overline{\text{JW}}_{\text{naïve}}$ restricts to a bijection
between the the annihilation operators and a subset
$\overline{\text{JW}}=\\{A_{0},A_{1},\dots,A_{n-1}\\}$ of $G_{n}$. That is,

$\displaystyle\overline{\text{JW}}_{\text{naïve}}$
$\displaystyle:\text{span}_{\mathds{C}}\\{a_{\alpha_{0}}^{(\dagger)},\dots,a_{\alpha_{n-1}}^{(\dagger)}\\}\longrightarrow
G_{n}$ (10) $\displaystyle\overline{\text{JW}}_{\text{naïve}}$
$\displaystyle:a_{\alpha_{i}}\longmapsto
A_{i}=\left(\bigotimes_{k=0}^{i-1}Z_{k}\right)\frac{1}{2}\left(X+Y\right)_{i}\,\,.$
(11)

Since $\\{Z_{i},X_{i}\\}=\\{Z_{i},Y_{i}\\}=0$, the naïve Jordan–Wigner
transformation satisfies Equation 4, the core requirement of a fermion–qubit
mapping:

$\displaystyle\\{A_{i}^{(\dagger)},A_{j}^{(\dagger)}\\}=0\,,\,\\{A_{i},A_{j}^{\dagger}\\}=\delta_{ij}\mathds{1}\,.$
(12)

###  II.4 A definition for the Jordan–Wigner transformation that incorporates
enumeration schemes

The standard description of the Jordan–Wigner transformation does not make
clear that one of its inherent components is an enumeration scheme for the
fermionic modes, a bijective mapping from unordered fermionic labels to the
natural number labels of qubits. The following definition makes the role of
the enumeration scheme explicit:

######  Definition 2.

The Jordan–Wigner transformation with a fermionic enumeration scheme for a
system with $n$ fermionic modes is a linear map $\overline{\text{JW}}_{f}$
from the the complex span of the $2n$ fermionic creation and annihilation
operators to the Pauli group $G_{n}$, equipped with a bijective enumeration
scheme $f$ for the fermionic modes:

$f:\\{\alpha_{0},\dots,\alpha_{n-1}\\}\longrightarrow\\{0,\dots,n-1\\}\,.$
(13)

In particular, $\overline{\text{JW}}_{f}$ restricts to a bijection between the
annihilation operators and a subset
$\overline{\text{JW}}=\\{A_{0},\dots,A_{n-1}\\}$ of $G_{n}$. That is,

$\displaystyle\overline{\text{JW}}_{f}$
$\displaystyle:\text{span}_{\mathds{C}}\\{a_{\alpha_{0}}^{(\dagger)},\dots,a_{\alpha_{n-1}}^{(\dagger)}\\}\longrightarrow
G_{n}\,,$ (14) $\displaystyle\overline{\text{JW}}_{f}$
$\displaystyle:a_{\alpha_{i}}\longmapsto\,A_{f(\alpha_{i})}\,,$ (15)

where $A_{i}$ has the same expression as in Definition 1.

The purpose of generalising the Jordan–Wigner transformation to Definition 2
is to demonstrate that there is complete freedom in labelling the fermionic
modes: no matter the ordering $f$, we recover the canonical anticommutation
relations of Equation 4. The operators $A_{i}$ are still drawn from the set
$\overline{\text{JW}}$, which satisfies Equation 12. For example, the
enumeration scheme $f(\alpha_{i})=i$ recovers the naïve mapping from
Definition 1.

The topic of discussion of Sections III and IV is defining the degree of
freedom $f$ in $\overline{\text{JW}}_{f}$ and how to exploit it for material
gain. Before we come to that, first let us fully generalise the concept of
fermion–qubit mappings.

###  II.5 A general definition for fermion–qubit mappings that incorporates
enumeration schemes

As it turns out, the freedom of choice to associate each of the annihilation
operators $a_{\alpha_{i}}$ with a unique linear combination of of Pauli
strings $A_{f(\alpha_{i})}$ in Definition 2 does not capture the full degree
of freedom in the choice of enumeration schemes in general. The Majorana
fermionic operators $\\{\gamma_{\beta_{0}},\dots,\gamma_{\beta_{2n-1}}\\}$
from Equations 5 and 6 are equivalent building blocks for any fermionic system
described by Equation 4, and have the benefit of obeying the more concise
anticommutation relations of Equation 7.

We propose that the broadest definition of a fermion–qubit mapping from $n$
modes to $n$ qubits is as follows:

######  Definition 3.

_(General fermion–qubit mapping.)_ A fermion–qubit mapping for a system with
$n$ fermionic modes system is a linear map $\text{F}_{f}$ from the complex
span of the $2n$ creation and annihilation operators to the $n$–qubit Pauli
group $G_{n}$, equipped with a bijective enumeration scheme $f$ for the
Majorana modes

$\displaystyle
f:\\{\beta_{0},\dots,\beta_{2n-1}\\}\longrightarrow\\{0,1,\dots,2n-1\\}\,.$
(16)

The restriction of $\text{F}_{f}$ to the Majorana operators is a bijection to
$2n$ pairwise–anticommuting Pauli strings
$\text{F}=\\{\Gamma_{0},\dots,\Gamma_{2n-1}\\}$, with
$\Gamma_{i}\in\\{\mathds{1},X,-iY,Z\\}^{\otimes n}$. That is,

$\displaystyle\text{F}_{f}$
$\displaystyle:\text{span}_{\mathds{C}}\\{a^{(\dagger)}_{\alpha_{0}},\dots,a^{(\dagger)}_{\alpha_{n-1}}\\}\longrightarrow
G_{n}\,,$ (17) $\displaystyle\text{F}_{f}$
$\displaystyle:\gamma_{\beta_{i}}\longmapsto\Gamma_{f(\beta_{i})}\,.$ (18)

Since the elements $\Gamma_{i}$ of F are Hermitian Pauli strings and
pairwise–anticommute, they satisfy

$\Gamma_{i}=\Gamma_{i}^{\dagger}\,,\quad\\{\Gamma_{i},\Gamma_{j}\\}=2\delta_{ij}\mathds{1}$
(19)

for all $i,j=0,1,\dots,2n-1$, thus reproducing the fermionic system described
by Equation 7.

######  Corollary 1.

The restriction of the fermion–qubit mapping $\text{F}_{f}$ to the
annihilation operators $\\{a_{\alpha_{0}},\dots,a_{\alpha_{n-1}}\\}$ is a
bijection to a subset $\\{A_{0},\dots,A_{n-1}\\}$ of $G_{n}$ defined by

$\displaystyle\text{F}_{f}:a_{\alpha_{i}}$ $\displaystyle\longmapsto
A_{i}=\frac{1}{2}\left(\Gamma_{f(\beta_{2i})}+i\Gamma_{f(\beta_{2i+1})}\right)\,,$
(20)

for $i=0,1,\dots,n-1$. This arises from Equations 5 and 6, which give for
$i=0,1,\dots,n-1$

$a_{\alpha_{i}}=\frac{1}{2}\left(\gamma_{\beta_{2i}}+i\gamma_{\beta_{2i+1}}\right)\,.$
(21)

The $A_{i}$ satisfy Equation 12 by construction.

Figure 2 visualises the relation between the operators $A_{i}$ arising from a
general fermion–qubit mapping in Definition 3 and the $A_{i}$ operators that
arise from naïve mappings such as the Jordan–Wigner transformation in
Definition 1. The most general form of the Jordan–Wigner transformation is
thus:

######  Example 1.

_(General Jordan–Wigner transformation)_ The general Jordan–Wigner
transformation for a system with $n$ fermionic modes is a fermion–qubit
mapping $\text{JW}_{f}$ which restricts to a bijection between the Majorana
operators and a set of $2n$ pairwise–anticommuting Pauli strings
$\text{JW}=\\{\Gamma_{0},\dots,\Gamma_{2n-1}\\}$, defined for $i=0,\dots,n-1$
by

$\displaystyle\Gamma_{2i}$
$\displaystyle=\left(\bigotimes_{k=0}^{i-1}Z_{k}\right)X_{i}\,,$ (22)
$\displaystyle\Gamma_{2i+1}$
$\displaystyle=\left(\bigotimes_{k=0}^{i-1}Z_{k}\right)(-iY_{i})\,.$ (23)

That is,

$\displaystyle\text{JW}_{f}$
$\displaystyle:\text{span}_{\mathds{C}}\\{a^{(\dagger)}_{\alpha_{0}},\dots,a^{(\dagger)}_{\alpha_{n-1}}\\}\longrightarrow
G_{n}\,,$ (24) $\displaystyle\text{JW}_{f}$
$\displaystyle:\gamma_{\beta_{i}}\longmapsto\Gamma_{f(\beta_{i})}\,.$ (25)

Note that the Pauli strings $\Gamma_{i}$ have length $\mathcal{O}(n)$. The
annihilation operators of the general Jordan–Wigner transformation map to:

$\displaystyle\text{JW}_{f}:a_{\alpha_{i}}\longmapsto
A_{i}=\frac{1}{2}\left(\Gamma_{f(\beta_{2i})}+i\Gamma_{f(\beta_{2i+1})}\right)\,,$
(26)

which satisfy Equation 12 by construction.

######  Remark 1.

If the Majorana fermionic enumeration scheme $f$ is such that
$f(\beta_{2i+1})=f(\beta_{2i})+1$ for all $i=0,1,\dots,n-1$, then
${\text{JW}}_{f}$ reduces to $\overline{\text{JW}}_{f}^{\,{}^{\,}}$ from
Definition 2. Thus, the Jordan–Wigner transformation with a fermionic
enumeration scheme in Definition 2 does not capture the true degree of freedom
in enumeration schemes – it is only a special case of the general
Jordan–Wigner transformation described by Equation 26.

######  Remark 2.

_(Notation.)_ The most general form of a fermion–qubit mapping, which we write
as $\text{F}_{f}$, maps Majorana operators to Pauli strings. We use the
overline notation $\overline{\text{F}}_{f}$ for mappings between annihilation
operators and elements of $G_{n}$. The expression
$\overline{\text{F}}_{\text{naïve}}$ denotes mappings that unnecessarily force
a specific enumeration scheme such as $f(\alpha_{i})=i$, which aims to
highlight their naïveté. For example, the relation between these different
classes of mappings for the Jordan–Wigner transformation is:

$\displaystyle\overline{\text{JW}}_{\text{naïve}}$
$\displaystyle=\overline{\text{JW}}_{f}\text{ where }f(\alpha_{i})=i\,;$ (27)
$\displaystyle\overline{\text{JW}}_{f}$
$\displaystyle=\text{JW}_{f^{\prime}}\text{ where
}f^{\prime}(\beta_{2i})=f(\alpha_{i})\text{ and}$ (28)
$\displaystyle\qquad\qquad\qquad\quad
f^{\prime}(\beta_{2i+1})=f(\alpha_{i}+1)\,.$

Definition 3 encapsulates all forms of the Jordan–Wigner, Bravyi–Kitaev [29],
ternary tree [36], and other $n$–qubit transformations, and thus allows a fair
comparison between them as in Section II.6 and [42]. By expanding the
definition of the pairwise–anticommuting Pauli strings to
$\Gamma_{i}\in\\{\mathds{1},X,-iY,Z\\}^{\otimes m}$ for $m\geq n$ such that 19
still holds, the general definition here could be extended to include mappings
with ancilla qubits such as [17, 30, 35]; we leave such extension for future
work.

###  II.6 Comparison between different mapping types and the notion of an
optimal fermion–qubit mapping

Through the lens of Definition 3, the feature that identifies a mapping as
being of Jordan–Wigner type is that it associates Majorana fermionic operators
with a set of Pauli strings JW of the forms in Equations 22 and 23.

In the literature, the search for more efficient mappings beyond the
Jordan–Wigner transformation resulted in the Bravyi–Kitaev transformation
[29], which yields exponentially shorter Pauli strings in the asymptotic
limit. The Bravyi–Kitaev transformation does not outperform the Jordan–Wigner
on modest fermionic systems, however, and has a similar T–gate count [43].
Aside from its intuitive definition, the Jordan–Wigner mapping has also gained
widespread use because it demands far fewer degrees of connectivity from the
qubit architecture [30].

We can construct the most general definition for other types of fermion–qubit
mappings, where the identifying feature of each mapping type is the unique set
of Pauli strings to which it maps the Majorana fermionic operators. For
example, the most general definition for the Bravyi–Kitaev transformation [29]
is:

######  Example 2.

_(General Bravyi–Kitaev transformation.)_ The general Bravyi–Kitaev
transformation for a system with $n$ fermionic modes is a fermion–qubit
mapping $\text{BK}_{f}$ which restricts to a bijection between the Majorana
operators and a set of $2n$ pairwise–anticommuting Pauli strings
$\text{BK}=\\{\Gamma_{0},\dots,\Gamma_{2n-1}\\}$, defined for $i=0,\dots,n-1$
by

$\displaystyle\Gamma_{2i}$ $\displaystyle=X_{U(i)}X_{i}Z_{P(i)}\,,$ (29)
$\displaystyle\Gamma_{2i+1}$ $\displaystyle=X_{U(i)}(-iY)_{i}Z_{R(i)}\,.$ (30)

That is,

$\displaystyle\text{BK}_{f}$
$\displaystyle:\text{span}_{\mathds{C}}\\{a^{(\dagger)}_{\alpha_{0}},\dots,a^{(\dagger)}_{\alpha_{n-1}}\\}\longrightarrow
G_{n}\,,$ (31) $\displaystyle\text{BK}_{f}$
$\displaystyle:\gamma_{\beta_{i}}\longmapsto\Gamma_{f(\beta_{i})}\,,$ (32)

Here, using the notation of Seeley et al. [44], the sets are $U(i)$, $P(i)$
and $R(i)$ are subsets of $\\{0,1,\dots,n-1\\}$ of size $\sim\log_{2}n$.

Much like the Jordan–Wigner transformation, this general definition of the
Bravyi–Kitaev transformation is more extensive than the usual naïve
presentation, which simply maps annihilation operators to their qubit
equivalents $\overline{\text{BK}}$ with the trivial enumeration scheme
$f:\alpha_{i}\mapsto i$:

$\displaystyle\overline{\text{BK}}_{\text{naïve}}:a_{\alpha_{i}}$
$\displaystyle\longmapsto
A_{i}=\frac{1}{2}\left(\Gamma_{2i}+i\Gamma_{2i+1}\right)\,.$ (33)

######  Example 3.

_(Ternary tree transformation.)_ Unlike the naïve versions of the
Bravyi–Kitaev and Jordan–Wigner transformations, the base definition of the
ternary tree transformation [36] is already similar to Definition 3: it is a
map $\text{TT}_{f}$ that identifies the Majorana fermionic operators
$\\{\gamma_{\beta_{0}},\dots,\gamma_{\beta_{2n-1}}\\}$ with Hermitian,
pairwise–anticommuting Pauli strings
$\text{TT}=\\{\Gamma_{0},\dots,\Gamma_{2n-1}\\}$ defined by

$\displaystyle\text{TT}=\big{\\{}$
$\displaystyle\Gamma_{0}=X_{0}X_{1}X_{4}...X_{\frac{n-1}{3}}\,,$ (34)
$\displaystyle\Gamma_{1}=X_{0}X_{1}X_{4}...(-iY)_{\frac{n-1}{3}},$
$\displaystyle\Gamma_{2}=X_{0}X_{1}X_{4}...Z_{\frac{n-1}{3}}\,,$
$\displaystyle\dots\,,$
$\displaystyle\Gamma_{2n-2}=Z_{0}Z_{3}Z_{12}...X_{n-1}\,,$
$\displaystyle\Gamma_{2n-1}=Z_{0}Z_{3}Z_{12}...(-iY)_{n-1}\big{\\}}\,.$

Figure 3: A general fermion–qubit mapping $\text{F}_{f}$ for a system with $n$
fermionic modes described by Majorana operators
$\\{\gamma_{\beta_{0}},\gamma_{\beta_{1}},\dots,\gamma_{\beta_{2n-1}}\\}$
consists of a set of pairwise–anticommuting Pauli strings
$\text{F}=\\{\Gamma_{0},\Gamma_{1},\dots,\Gamma_{2n-1}\\}$ along with an
enumeration scheme
$f:\\{\beta_{0},\dots,\beta_{2n-1}\\}\mapsto\\{0,1,\dots,2n$ $-$ $1\\}$. This
diagram displays three well–known fermion–qubit mappings: the Jordan–Wigner,
Bravyi–Kitaev, and ternary tree mappings, and shows how the enumeration scheme
dictates the properties physical operators, which are products of
$a_{\alpha_{i}}^{\dagger}=\frac{1}{2}(\gamma_{\beta_{2i}}-i\gamma_{\beta_{2i+1}})$
and $a_{\alpha_{j}}=\frac{1}{2}(\gamma_{\beta_{2j}}+i\gamma_{\beta_{2j+1}})$
for $i,j\in\\{0,1,\dots,n-1\\}$. Suppose that $f$ and $f^{\prime}$ are two
distinct Majorana enumeration schemes with
$f(\\{\beta_{2i},\beta_{2i+1},\beta_{2j},\beta_{2j+1}\\})$ $=$
$\\{14,15,16,17\\}$ respectively, and
$f^{\prime}(\\{\beta_{2i},\beta_{2i+1},\beta_{2j},\beta_{2j+1}\\})$ $=$
$\\{30,31,0,1\\}$ respectively. The interaction terms $A_{7}^{\dagger}A_{8}$
and $A^{\dagger}_{15}A_{0}$ are noticeably distinct under $f$ compared to
$f^{\prime}$, for all three fermion–qubit mapping types.

We mention the mapping here for the purpose of making its dependence on an
enumeration scheme $f$ explicit, rather than implicit as in its initial
presentation in [36]:

$\displaystyle\text{TT}_{f}$
$\displaystyle:\text{span}_{\mathds{C}}\\{a^{(\dagger)}_{\alpha_{0}},\dots,a^{(\dagger)}_{\alpha_{n-1}}\\}\longrightarrow
G_{n}\,,$ (35) $\displaystyle\text{TT}_{f}$
$\displaystyle:\gamma_{\beta_{i}}\longmapsto\Gamma_{f(\beta_{i})}\,.$ (36)

Strictly speaking, Equation 34 only describes TT if $2n+1$ is a power of 3.
The mapping can be altered slightly to accommodate other values of $n$ without
suffering any ill effects: namely, the remarkable $\sim\log_{3}(2n)$ Pauli
weight of each of the $\Gamma_{i}$ qubit operators, which is the provably
optimal average Pauli weight of any such set of Pauli strings F in an
$n$–fermion to $n$–qubit mapping [36].

Examples 1–3 demonstrate that the Pauli strings $\Gamma_{i}$ in the
Jordan–Wigner, Bravyi–Kitaev and ternary tree mappings have maximum weight
$n$, $\sim\log_{2}(n)$ and $\sim\log_{3}(2n)$. This might incline one to
declare the Bravyi–Kitaev transformation to be an improvement on
Jordan–Wigner, and the ternary tree mapping to be the best of all possible
mappings.

However, recall from Section II.1 that the goal of any fermion–qubit mapping
is to simulate a fermionic Hamiltonian $H_{\text{fermion}}$ with physical
interaction terms of the form $a^{\dagger}_{\alpha_{i}}a_{\alpha_{j}}$ and
$a^{\dagger}_{\alpha_{i}}a^{\dagger}_{\alpha_{j}}a_{\alpha_{k}}a_{\alpha_{l}}$.
These terms are linear combinations of products of particular Majorana
operators $\gamma_{\beta_{i}}$. Given a fermion–qubit mapping $\text{F}_{f}$,
the terms in the qubit Hamiltonian $H_{\text{qubit}}$ are of the form
$A_{i}^{\dagger}A_{j}$ and $A^{\dagger}_{i}A^{\dagger}_{j}A_{k}A_{l}$, which
are linear combinations of products of the Pauli strings
$\Gamma_{i}\in\text{F}=\\{\Gamma_{0},\dots,\Gamma_{2n-1}\\}$. Even for the
ternary tree mapping, the Pauli weight of the physical interaction terms
varies depending on the enumeration scheme $f$, as Figure 3 demonstrates.

Moreover, there are a multitude of properties of the qubit Hamiltonian
$H_{\text{qubit}}$ that one might want to minimise depending on the quantum
technology at hand. For example, the average Pauli weight or the Pauli
measurement depth of the terms in $H_{\text{qubit}}$ are quantities that can
determine the resource cost in near–term algorithms such as the variational
quantum eigensolver. The maximum Pauli weight of any one term in
$H_{\text{qubit}}$ is a measure of complexity in long–term algorithms
involving phase estimation.

Therefore, we argue that the notion of an optimal fermion–qubit mapping is
only well–defined given these two contexts: the problem Hamiltonian
$H_{\text{fermion}}$, and a physical resource cost $C$ to minimise in
$H_{\text{qubit}}$. Given these inputs, the total search space for an optimal
fermion–qubit mapping $\text{F}_{f}$ of the form given in Definition 3 is
characterised by:

  1. 1.

The set of mutually–anticommuting Pauli strings
$\text{F}=\\{\Gamma_{0},\dots,\Gamma_{2n-1}\\}$, determined by the type of
fermion–qubit mapping, e.g. Jordan–Wigner, Bravyi–Kitaev, or ternary tree;
and,

  2. 2.

The enumeration scheme
$f:\\{\beta_{0},\dots,\beta_{2n-1}\\}\rightarrow\\{0,\dots,2n-1\\}$.

There is a one–to–one relation between each such mapping $\text{F}_{f}$ and an
invertible binary $n$$\times$$n$ matrix [30]: there are therefore
$\mathcal{O}\left(\exp(n^{2})\right)$ mappings to search. By any classical
means, it is impossible to find the optimal $\text{F}_{f}$.

In this work, we argue that it is possible to make meaningful headway in the
search for an optimal fermion–qubit mapping in a reduced search–space. In this
paper, we propose the approach of fixing the mapping type F and searching for
the optimal fermion enumeration scheme $f$.

######  Definition 4.

_(Optimal fermion–qubit mapping of type F.)_ Let $H_{\text{fermion}}$ be a
fermionic Hamiltonian on $n$ modes, let F be a fermion–qubit mapping type, and
suppose we possess a qubit architecture with some limiting resource. Then for
any fermion–qubit mapping $\text{F}_{f}$, let $C=C(f)$ be the cost function of
the qubit Hamiltonian $H_{\text{qubit}}\coloneqq
H_{\text{qubit}}(f)=\text{F}_{f}(H_{\text{fermion}})$ with respect to that
resource. The $C$–optimal fermion–qubit mapping of type F for
$H_{\emph{fermion}}$ is the fermion–qubit mapping $\text{F}_{f^{*}}$, where
$f^{*}$ is a Majorana fermionic enumeration scheme satisfying

$\displaystyle f^{*}=\operatorname*{arg\,min}_{f}C(f)\,.$ (37)

In Section III, we find optimal fermion–qubit mappings of Jordan–Wigner type
$\overline{\text{JW}}_{f}$ for various common problem Hamiltonians
$H_{\text{fermion}}$, and various common cost functions $C$ such as the
average and maximum Pauli weight of terms in $H_{\text{qubit}}$. In Section
IV, we loosen Definition 2 of the Jordan–Wigner transformation
$\overline{\text{JW}}_{f}$ to find fermion–qubit with two ancilla qubits that
outperform the optimal mappings from Section III.

###  II.7 Complexity–theoretical preliminaries

Figure 4: Complexity–theoretic hierarchy of problems generalising the edgesum
problem.

This section introduces the notation and complexity theoretic problems that
underpin the results of Section III. Awareness of these problems is necessary
to find optimal fermion–qubit mappings of Jordan–Wigner type as described in
Definition 4. Figure 4 gives a summary of the hierarchy of these problems, all
of which start with some variation of the following ingredients:

  1. 1.

A graph $G=(V,E)$ with $|V|=n$ vertices and edge set $E\subseteq V\times V$,
and

  2. 2.

a weight function $w:E\longrightarrow\mathds{R}$ which assigns a value
$w(\alpha,\beta)$ to the edge $(\alpha,\beta)$ between vertices
$\alpha,\beta\in V$, and

  3. 3.

a list $L$ of possible locations for the vertices, and

  4. 4.

a distance function $d:L\times L\rightarrow\mathds{R}$ describing the spatial
separation between the locations.

All optimisation problems in this section have –complete decision versions,
and are thus –hard. They share the objective of finding an injective
assignment function $f:V\longrightarrow L$ to place the vertices in locations
so as to minimise a cost function. We call $f$ a vertex enumeration scheme
when $L=\\{0,1,\dots,n-1\\}$.

The problems in this section appear in order of descending complexity, in that
subsequent problems are special cases of earlier problems. The following
problem was introduced by Koopmans and Beckmann [45]

QUADRATIC ASSIGNMENT INSTANCE: Graph $G=(V,E)$, weight function
$w:E\rightarrow\mathds{R}$, vertex locations $L$, distance function $d:L\times
L\rightarrow\mathds{R}$. PROBLEM: Find the location assignment function
$f:V\rightarrow L$ in such a way as to minimise the assignment function
$\displaystyle C(f)=\sum_{(\alpha,\beta)\in E}w(\alpha,\beta)\cdot
d\left(f(\alpha),f(\beta)\right)\,.$ (38)

The optimal linear arrangement problem was first studied by Garey and Johnson
[37]. Note that it is different to the “optimal linear arrangement” in their
book [39].

OPTIMAL LINEAR ARRANGEMENT INSTANCE: Graph $G=(V,E)$, weight function
$w:E\rightarrow\mathds{Z}$. PROBLEM: Find the enumeration scheme
$f:V\rightarrow\\{0,1,\dots,n-1\\}$ that minimises the assignment function
$C(f)=\sum_{(\alpha,\beta)\in
E}w(\alpha,\beta)\cdot\left|f(\alpha)-f(\beta)\right|\,.$ (39)

This is a special case of the quadratic assignment problem: the weight
function $w$ is restricted to integer values, the vertex locations $L$ are
$\\{1,2,\dots,n\\}$, and the distance metric is $d(i,j)=\left|i-j\right|$.

The minimum $p$–sum problem was studied by Mitchison and Durbin [31], Garey
and Johnson [38], and Juvan and Mohar [46].

MINIMUM $p$–SUM INSTANCE: Graph $G=(V,E)$, integer $p\in\mathds{Z}$. PROBLEM:
Find the enumeration scheme $f:V\rightarrow\\{0,1,\dots,n-1\\}$ that minimises
the assignment function $\displaystyle C^{p}(f)=\left(\sum_{(\alpha,\beta)\in
E}\left|f(\alpha)-f(\beta)\right|^{p}\right)^{1/p}\,.$ (40)

This is a special case of the optimal linear arrangement problem, because its
weight function is effectively
$w(\alpha,\beta)=|f(\alpha)-f(\beta)|^{p-1}\in\mathds{Z}$. The decision
version of the problem is –complete for $p=1$ [37], $p=2$ [47] and
$p\rightarrow\infty$ [48]. One could also consider the broader class of
problems where $p\in\mathds{R}^{+}$, as done by Mitchison and Durbin [31].
These problems are likely to be at least as hard as their integer–$p$
equivalents.

####  II.7.1 Special cases of minimum $p$–sum

The edgesum problem was introduced in [37], and the study of this problem is
the key ingredient to our optimal Jordan–Wigner transformations in Section
III:

EDGESUM (or SIMPLE OPTIMAL LINEAR ARRANGEMENT, MINIMUM 1–SUM) INSTANCE: Graph
$G=(V,E)$. PROBLEM: Find the enumeration scheme
$f:V\rightarrow\\{0,1,\dots,n-1\\}$ that minimises the assignment function
$\displaystyle C(f)=\sum_{(\alpha,\beta)\in
E}\left|f(\alpha)-f(\beta)\right|\,.$ (41)

Figure 5: Graph families with known solutions to their edgesum problems. The
formula for the minimum edgesum appears beneath each graph’s image, if it
exists, or the cost of the best–known classical algorithm for solving that
graph’s edgesum problem if not. References for the solution of these graphs
appear in Lai [49], Horton [48], and Mitchison’s [31] works as indicated.

The decision version of this problem is known to be $\NP$–complete via a
reduction to the simple max–cut problem [37]. Figure 5 surveys the graphs with
known solutions, as of the date of publication of Horton’s PhD thesis [48]
which cites a solution for outerplanar graphs by Frederickson and Hambrusch
[50]. Other sources include a survey by Lai [49], and solution for tree graphs
by Chung [51].

As an example of a comparable problem, consider the following:

BANDWIDTH (or MINIMUM $\infty$–SUM) INSTANCE: Graph $G=(V,E)$. PROBLEM: Find
the enumeration scheme $f:V\rightarrow\\{0,1,\dots,n-1\\}$ that minimises cost
function $\displaystyle C^{\infty}(f)=\max_{(\alpha,\beta)\in
E}\left|f(\alpha)-f(\beta)\right|\,.$ (42)

This is the minimum $p$–sum problem as $p\rightarrow\infty$. The decision
version of the bandwidth problem is $\NP$–complete for e.g. an arbitrary tree
graph [38]; conversely, Saxe proves that the decision problem as to whether
the bandwidth is less than or equal to $k=O(1)$ is efficiently solvable [52].

##  III Optimal fermion–qubit mappings of Jordan–Wigner type

This section demonstrates the key idea of our approach: using enumeration
schemes to optimise fermion–qubit mappings for practical cost functions.
Section III.1 establishes the scope of the search for optimal Jordan–Wigner
mappings in this work, defining optimality in terms of practical cost
functions for quantum computers. Section III.2 sets out the broad class of
problem Hamiltonians that this search will consider. Section III.3 derives
expressions for the cost functions of the search, which are related to
problems in graph theory. Section III.4 states Theorem 1 for minimising the
average Pauli weight of a Jordan–Wigner transformation of a system of fermions
interacting in a square lattice, with proof in Section VI.2. In Section III.5,
we consider an heuristic approach to minimising the average Pauli weight of a
Jordan–Wigner transformation of cellular lattice fermionic systems. In Section
III.6, we consider the task of minimising the average $p$th power of Pauli
weight of a Jordan–Wigner transformation of square lattice fermionic systems,
for $p>1$.

###  III.1 Objective

In practice, it is very difficult to find the optimal fermion–qubit mapping
for a given Hamiltonian $H_{\text{fermion}}$ as defined in Definition 4.
Within the scope of this paper, instead consider the subproblem of finding the
optimal Jordan–Wigner transformation with a fermionic enumeration scheme as in
Definition 2:

######  Definition 5.

_(Optimal Jordan–Wigner transformations with fermionic enumeration schemes.)_
Let $H_{\text{fermion}}$ be a fermionic Hamiltonian on $n$ modes. Let $C=C(f)$
be the cost function of the qubit Hamiltonian
$H_{\text{qubit}}=H_{\text{qubit}}(f)\coloneqq\overline{\text{JW}}_{f}(H_{\text{fermion}})$
with respect to some scarce physical resource. The $C$–optimal Jordan–Wigner
transformation with a fermionic enumeration scheme for $H_{\emph{fermion}}$ is
the fermion–qubit mapping $\overline{\text{JW}}_{f^{*}}$, where $f^{*}$ is a
fermionic enumeration scheme satisfying

$\displaystyle f^{*}=\operatorname*{arg\,min}_{f}C(f)\,.$ (43)

In this work, we discuss optimal Jordan–Wigner transformations with fermionic
enumeration schemes for three example cost functions:

######  Example 4.

_( $C=APV$, average Pauli weight.)_ Given a fermionic Hamiltonian
$H_{\text{fermion}}$, a Jordan–Wigner mapping with minimum average Paul weight
is a fermion–qubit mapping $\overline{\text{JW}}_{f^{*}}$ where the fermionic
enumeration scheme $f^{*}$ satisfies

$\displaystyle f^{*}$
$\displaystyle=\operatorname*{arg\,min}_{f}\big{(}APV(H_{\text{qubit}}(f))\big{)}\,,$
(44)

where $APV(H_{\text{qubit}})$ is the average Pauli weight of all terms in
$H_{\text{qubit}}(f)=\overline{\text{JW}}_{f}(H_{\text{fermion}})$.

The average Pauli weight of a qubit Hamiltonian could be a limiting resource
in near–term algorithms such as the variational quantum eigensolver (VQE),
where $APV(H_{\text{qubit}})$ represents the total number of single–qubit
measurements involved in each step of the VQE.

######  Example 5.

_( $C=MPV$, maxium Pauli weight.)_ As in Example 4, except that $f^{*}$
satisfies

$\displaystyle f^{*}$
$\displaystyle=\operatorname*{arg\,min}_{f}\big{(}MPV(H_{\text{qubit}}(f))\big{)}\,,$
(45)

where $MPV(H_{\text{qubit}})$ is the maximum Pauli weight of any one term in
the qubit Hamiltonian.

The maximum Pauli weight of $H_{\text{qubit}}$ is a complexity–theoretic
measure of the cost of simulating $H_{\text{qubit}}$ via long–term algorithms
such as phase estimation. In the $k$–local Hamiltonian problem for
$H_{\text{qubit}}$, the quantity $MPV(H_{\text{qubit}})$ is the value $k$.

######  Example 6.

_( $C=MD$, Pauli measurement depth)_ As in Example 4, except that $f^{*}$
satisfies

$\displaystyle
f^{*}=\operatorname*{arg\,min}_{f}\big{(}MD(H_{\text{qubit}}(f))\big{)}\,,$
(46)

where $MD(H_{\text{qubit}})$ is the minimum number of groupings of the terms
in $H_{\text{qubit}}$ such that each group contains no terms that act on
shared qubits.

The quantity $MD(H_{\text{qubit}})$ corresponds to the number of distinct
timesteps required to run all Hamiltonian terms in parallel, indicating, for
example, the total clock time required to perform all measurements during an
iteration of a variational quantum eigensolver algorithm.

###  III.2 Problem Hamiltonians

The terms in a general fermionic Hamiltonian $H_{\text{fermion}}$ as specified
in Equation 1 represent quadratic one–particle and quartic two–particle
interactions. The Jordan–Wigner transformation $\overline{\text{JW}}_{f}$ maps
each of the one–particle terms to

$\displaystyle\overline{\text{JW}}_{f}:a^{\dagger}_{\alpha_{i}}a_{\alpha_{i}}\longmapsto\frac{1}{2}\left(\mathds{1}-Z\right)_{f(\alpha_{i})}$
(47)
$\displaystyle\overline{\text{JW}}_{f}:a^{\dagger}_{\alpha_{i}}a_{\alpha_{j}}\longmapsto$
(48)
$\displaystyle\quad\frac{1}{2}\left(X-Y\right)_{f(\alpha_{i})}\left(\bigotimes_{k=f(\alpha_{i})}^{f(\alpha_{j})-1}Z_{k}\right)\frac{1}{2}\left(X+Y\right)_{f(\alpha_{j})}\,,$

where $f(\alpha_{i})<f(\alpha_{j})$ in Equation 48. However, the term
$c_{\alpha_{i}\alpha_{j}}a^{\dagger}_{\alpha_{i}}a_{\alpha_{j}}$ will always
appear in $H$ alongside its conjugate term
$(c_{\alpha_{i}\alpha_{j}})^{*}a^{\dagger}_{\alpha_{j}}a_{\alpha_{i}}$. The
expression
$c_{\alpha_{i}\alpha_{j}}a^{\dagger}_{\alpha_{i}}a_{\alpha_{j}}+(c_{\alpha_{i}\alpha_{j}})^{*}a^{\dagger}_{\alpha_{j}}a_{\alpha_{i}}$
is known as the hopping term between fermionic modes $\alpha_{i}$ and
$\alpha_{j}$. The hopping terms of $H_{\text{fermion}}$ lead to non–local
terms in the qubit Hamiltonian of the form

$\displaystyle\overline{\text{JW}}_{f}$
$\displaystyle:c_{\alpha_{i}\alpha_{j}}a^{\dagger}_{\alpha_{i}}a_{\alpha_{j}}+(c_{\alpha_{i}\alpha_{j}})^{*}a^{\dagger}_{\alpha_{j}}a_{\alpha_{i}}$
(49)
$\displaystyle\quad\longmapsto\quad\frac{\real(c_{\alpha_{i}\alpha_{j}})}{2}\left(\bigotimes_{k=f(\alpha_{i})+1}^{f(\alpha_{j})-1}Z_{k}\right)$
$\displaystyle\qquad\quad\times\left(X_{f(\alpha_{i})}\otimes
X_{f(\alpha_{j})}-Y_{f(\alpha_{i})}\otimes Y_{f(\alpha_{j})}\right)$
$\displaystyle\qquad\quad+\frac{i\imaginary(c_{\alpha_{i}\alpha_{j}})}{2}\left(\bigotimes_{k=f(\alpha_{i})+1}^{f(\alpha_{j})-1}Z_{k}\right)$
$\displaystyle\qquad\quad\times(Y_{f(\alpha_{i})}\otimes
X_{f(\alpha_{j})}-X_{f(\alpha_{i})}\otimes Y_{f(\alpha_{j})})\,.$

In the case where the coefficients of the conjugate one–particle interaction
terms are $c_{ij}=(c_{ij})^{*}=1$, the transformation of the hopping term is
simply

$\displaystyle\overline{\text{JW}}_{f}:a^{\dagger}_{\alpha_{i}}a_{\alpha_{j}}+a^{\dagger}_{\alpha_{j}}a_{\alpha_{i}}\longmapsto$
(50)
$\displaystyle\frac{1}{2}\left(\bigotimes_{k=f(\alpha_{i})+1}^{f(\alpha_{j})-1}Z_{k}\right)(X_{f(\alpha_{i})}\otimes
X_{f(\alpha_{j})}-Y_{f(\alpha_{i})}\otimes Y_{f(\alpha_{j})})\,.$

Figure 6 illustrates the conversion of these simpler hopping terms into qubit
Hamiltonian terms.

Figure 6: Jordan–Wigner transformation with a fermionic enumeration scheme
$\overline{\text{JW}}_{f}$, in this diagram with the naïve enumeration scheme
$f:\alpha_{i}\mapsto i$. For any enumeration scheme $f$, the fermion–qubit
mapping $\overline{\text{JW}}_{f}$ transforms hopping terms
$a_{\alpha_{i}}^{\dagger}a_{\alpha_{j}}+a_{\alpha_{j}}^{\dagger}a_{\alpha_{i}}\mapsto
A_{f(\alpha_{i})}^{\dagger}A_{f(\alpha_{j})}+A_{f(\alpha_{j})}^{\dagger}A_{f(\alpha_{i})}$.

Literature on quantum simulation algorithms tends to permit quartic terms in
the fermionic Hamiltonian that transform into local qubit operations. For
example, Verstraete and Cirac [17] and Derby and Klassen [35] consider terms
of the form

$\displaystyle\overline{\text{JW}}_{f}:a_{\alpha_{i}}^{\dagger}a_{\alpha_{i}}a^{\dagger}_{\alpha_{j}}a_{\alpha_{j}}\longmapsto$
(51)
$\displaystyle\qquad\qquad\frac{1}{4}(\mathds{1}-Z)_{f(\alpha_{i})}(\mathds{1}-Z)_{f(\alpha_{j})}\,.$

The quartic terms make diagonalisation of the fermionic Hamiltonian
$H_{\text{fermion}}$ exponentially difficult to solve on a classical computer.
However, they become simple 1– or 2–local Pauli operations after the
Jordan–Wigner transformation maps them into the local Pauli operations in
Equation 51. Thus, a fermionic Hamiltonian $H_{\text{fermion}}$ consisting of
self–interactions $a^{\dagger}_{\alpha_{i}}a_{\alpha_{i}}$, hopping terms, and
quartic terms of the form
$a^{\dagger}_{\alpha_{i}}a_{\alpha_{i}}a^{\dagger}_{\alpha_{j}}a_{\alpha_{j}}$
transforms under $\overline{\text{JW}}_{f}$ to a qubit Hamiltonian
$H_{\text{qubit}}$ where the only non–local terms are of the form in Equation
48. Moreover, the hopping terms are the only Pauli strings with weight
dependent on the enumeration scheme $f$ of the Jordan–Wigner mapping.

Consider fermionic Hamiltonians of the general form

$\displaystyle H_{\text{fermion}}$
$\displaystyle=\sum_{i,j=0}^{n-1}(c_{\alpha_{i}\alpha_{j}})a^{\dagger}_{\alpha_{i}}a_{\alpha_{j}}$
(52)
$\displaystyle\quad+\sum_{i,j=0}^{n-1}(c^{\prime}_{\alpha_{i}\alpha_{j}})a^{\dagger}_{\alpha_{i}}a_{\alpha_{i}}a_{\alpha_{j}}^{\dagger}a_{\alpha_{j}}$
(hereon referred to as quartic terms) $\displaystyle=\sum_{\text{pairs
}(i,j)}\left((c_{\alpha_{i}\alpha_{j}})a^{\dagger}_{\alpha_{i}}a_{\alpha_{j}}+(c_{\alpha_{i}\alpha_{j}}^{*})a_{\alpha_{i}}a_{\alpha_{j}}^{\dagger}\right)$
$\displaystyle\quad+\text{quartic terms}$ (53)
$\displaystyle=\sum_{(\alpha,\beta)\in
E}\left((c_{\alpha\beta})a_{\alpha}^{\dagger}a_{\beta}+(c_{\alpha\beta}^{*})a_{\alpha}a_{\beta}^{\dagger}\right)$
(54) $\displaystyle\quad+\text{quartic terms}\,,$

where $E$ is the edge set of the graph $G_{\text{F}}(V,E)$ with
$V=\\{\alpha_{0},\dots,\alpha_{n-1}\\}$ and $(\alpha,\beta)\in E\subseteq
V\times V$ if and only if $c_{\alpha\beta}\neq 0$.

For convenience of notation, assume that $c_{\alpha\beta}=1$ for all
$(\alpha,\beta)\in E$, so that only hopping terms of the form in Equation 48
are of concern. If our task were to find the optimal fermion–qubit mapping as
in Definition 4, this assumption would reduce the variety of problem
Hamiltonians described by Equation 54. However, focused as we are on finding
optimal Jordan–Wigner transformation as defined in Examples 4–6, the
assumption $c_{\alpha\beta}=1$ comes with no loss of generality in the form of
the problem Hamiltonians. This is because the weights of the Pauli strings of
$H_{\text{qubit}}=\overline{\text{JW}}_{f}(H_{\text{fermion}})$ in Equation 49
with coefficients $\real(c_{\alpha\beta})$ and $\imaginary(c_{\alpha\beta})$
are equal. Useful properties such as $APV$, $MPV$ and $MD$ of
$H_{\text{qubit}}$ are unchanged by setting all nonzero $c_{\alpha\beta}$ to
1. For the remainder of this paper, we can thus assume problem Hamiltonians
take the form:

$\displaystyle H_{\text{fermion}}$ $\displaystyle=\sum_{(\alpha,\beta)\in
E}\left(a^{\dagger}_{\alpha}a_{\beta}+a_{\alpha}a^{\dagger}_{\beta}\right)$
(55) $\displaystyle\quad+\text{quartic terms}\,.$

This assumption would not hold if instead the task were to find, for example,
the optimal enumeration scheme for Bravyi–Kitaev type mappings
$\overline{\text{BK}}_{f}$. This is because the Bravyi–Kitaev transformation
does not transform the hopping terms of $H_{\text{fermion}}$ in Equation 54
into a sum of Pauli strings of equal length [44, 42].

###  III.3 Expressions for cost functions of qubit Hamiltonians

For problem Hamiltonians of the form in Equation 55, there is a simple
relation for the Pauli weight of the Jordan–Wigner transformation of hopping
terms:

$\displaystyle\text{Pauli
weight}\big{(}\overline{\text{JW}}_{f}(a_{\alpha}^{\dagger}a_{\beta}$
$\displaystyle+a_{\alpha}a_{\beta}^{\dagger})\big{)}$ (56)
$\displaystyle=|f(\alpha)-f(\beta)|+1\,,$

since the Pauli strings of
$\overline{\text{JW}}_{f}(a_{\alpha}^{\dagger}a_{\beta}+a_{\alpha}a_{\beta}^{\dagger})$
contain $|f(\alpha)-f(\beta)|-1$ $Z$ gates and two $X$ or $Y$ gates, from
Equation 48.

Recall from Section II.7 that $C^{p}(f)$, the $p$–sum of a graph $G(V,E)$ with
vertex enumeration scheme $f$, is

$\displaystyle C^{p}(f)\coloneqq\bigg{(}\sum_{(\alpha,\beta)\in
E}|f(\alpha)-f(\beta)|^{p}\bigg{)}^{1/p}\,.$ (57)

This notation, along with Equation 56, allows for simple expressions for the
the cost functions $APV$ and $MPV$ from Examples 4 and 5, respectively.

Average Pauli weight (Example 4). The formula for the average Pauli weight of
a Jordan–Wigner transformation $\overline{\text{JW}}_{f}$ of a problem
Hamiltonian $H_{\text{fermion}}$ of the form in Equation 55 is

$\displaystyle APV(f)\coloneqq\frac{C^{1}(f)}{|G_{\mathrm{F}}|}+1\,,$ (58)

where $G_{\text{F}}$ is the number of edges in $G_{\mathrm{F}}$. In fact,
Equation 58 neglects the contribution of the quartic terms in
$H_{\text{fermion}}$ to the average Pauli weight, because they are independent
of the fermion enumeration scheme $f$ and hence have no effect in determining
the optimal enumeration scheme $f^{*}$ as described in Example 4. The extra
term of 1 accounts for the fact that the weight of a Pauli string between
qubits with labels $i$ and $j$ is $|i-j|+1$.

Figure 7 lists the average Pauli weight of the Jordan–Wigner transformation
$\overline{\text{JW}}_{f}$ of a fermionic Hamiltonian $H_{\text{fermion}}$
with fermionic interaction graph $G_{\text{F}}$ equal to the 6$\times$6
lattice for three enumeration schemes: the S–pattern $f_{\mathrm{S}}$, the
Z–pattern $f_{\mathrm{Z}}$, and the Mitchison–Durbin pattern,
$f_{\mathrm{M}}$, which underlies the results of Section III.4.

Finding Jordan–Wigner transformations with minimum average Pauli weight is
equivalent to finding enumeration scheme of $G_{\text{F}}$ that minimise
$C^{1}(f)$, which is the –hard edgesum problem from Section II.7. In Section
III.4, we present Theorem 1 for an enumeration scheme $f_{\mathrm{M}}$ that
minimises the average Pauli weight of a Jordan–Wigner transformation of
$H_{\text{fermion}}$ where if $G_{\mathrm{F}}$ is the $N$$\times$$N$ square
lattice. Through Corollary 2, this is an improvement of up to $\approx 13.9$%
upon existing methods.

Average $p$th power of Pauli weight. One might want to penalise the qubit
Hamiltonian via some other measure, such as the average $p$th power of the
Pauli weights where $p\in\mathds{R}^{+}$. Minimising this property corresponds
to the –hard minimum $p$–sum problem of minimising $C^{p}(f)$ from Section
II.7. In Section III.6, we present numerical results for the minimum $p$–sum
problem to illustrate how one might optimise Jordan–Wigner transformations for
this objective function.

Maximum Pauli weight (Example 5) The cost function for the maximum Pauli
weight of a Jordan–Wigner transformation $\overline{\text{JW}}_{f}$ is

$\displaystyle MPV(f)=C^{\infty}(f)+1\,,$ (59)

which corresponds to the –hard bandwidth problem from Section II.7. However,
for fermionic Hamiltonians $H_{\text{fermion}}$ with hopping terms on a
square–lattice $G_{\text{F}}$, it is straightforward to see that any fermionic
enumeration scheme with $C^{\infty}(f)=N$ will minimise the maximum Pauli
weight of the qubit Hamiltonian. One such enumeration scheme is the Z–pattern
$f_{\text{Z}}$.

Pauli measurement depth (Example 6). Finding Jordan–Wigner transformations
with minimum Pauli measurement depths is beyond the scope of this work. Figure
8 demonstrates the variation of Pauli measurement depth of
$H_{\text{qubit}}=\overline{\text{JW}}_{f}(H_{\text{fermion}})$, where the
fermionic interaction graph $G_{\text{F}}$ is the 6$\times$6 lattice, for
different enumeration schemes: $f_{\mathrm{S}}$, $f_{\mathrm{Z}}$, and
$f_{\mathrm{M}}$.

Other properties. One may also consider other cost functions. For example, if
the qubits have a connectivity graph $G_{\mathrm{Q}}$, it may be desirable to
make the Pauli strings in $H_{\text{qubit}}$ as local as possible on
$G_{\mathrm{Q}}$. A discussion of this optimisation appears in Section V.2.

Figure 7: The Jordan–Wigner transformation $\overline{\text{JW}}_{f}$ produces
qubit Hamiltonians that depend on the choice of enumeration scheme $f$. If the
fermionic Hamiltonian contains hopping terms that form a square lattice, the
Mitchison–Durbin pattern produces qubit Hamiltonians with hopping terms of the
minimum possible average weight. Figure 8:  Comparison of the Pauli
measurement depth of the hopping terms in qubit Hamiltonians
$H_{\text{qubit}}=\overline{\text{JW}}_{f}(H_{\text{fermion}})$ produced by
three different enumeration schemes on a 6$\times$6 square lattice of
fermions.

###  III.4 Jordan–Wigner transformations of square–lattice fermionic
Hamiltonians with minimum average Pauli weight

Consider fermionic problem Hamiltonians $H_{\text{fermion}}$ of the form in
Equation 55 with interaction graphs $G_{\text{F}}$ equal to the $N$$\times$$N$
square lattice. The solution to the edgesum problem for $G_{\text{F}}$ is
related to the work of Graeme Mitchison and Richard Durbin, from their studies
of the organisation of nerve cells in the brain cortex [31]. Figure 9 displays
the Mitchison–Durbin pattern $f_{\text{M}}$, which is dramatically different
to the S–pattern and its variations [17, 30]. The proof of our main result
below, Theorem 1, makes use of this curious arrangement to construct a
Jordan–Wigner transformation with minimum average Pauli weight.

Figure 9: Graeme Mitchison’s sculpture of the optimal numbering of a
7$\times$7 array. Reproduced with the permission of Richard Durbin.

######  Theorem 1.

_Jordan–Wigner transformations of square–lattice fermionic Hamiltonians with
minimum average Pauli weight.)_ Given a system of $n=N^{2}$ fermionic modes,
suppose that the system has a Hamiltonian $H_{\text{fermion}}$ of the form in
Equation 55 with a square–lattice interaction graph $G_{\text{F}}$. Then, the
fermion–qubit mapping $\overline{\text{JW}}_{f_{\text{M}}}$ is a Jordan–Wigner
transformation with minimum average Pauli weight for $H_{\text{fermion}}$,
where $f_{\text{M}}$ is the Mitchison–Durbin pattern.

###### Proof.

Proof in Section VI.2. ∎

######  Remark 3.

Finding Jordan–Wigner transformations with minimum average Pauli weight for
arbitrary Hamiltonians $H_{\text{fermion}}$ is $\NP$–hard.

Remark 4 details all known scenarios to date where the optimal fermionic
enumeration scheme is solvable in $(n)$ time.

######  Remark 4.

_(Solutions for other graph types $G_{\mathrm{F}}$.)_ If the Hamiltonian
$H_{\text{fermion}}$ is as defined in Theorem 1, and if $G_{\mathrm{F}}$
belongs to any of the graph families in Figure 5, then a classical computer
can efficiently find the Jordan–Wigner transformation with minimum average
Pauli weight for $H_{\text{fermion}}$.

Figure 10: Edgesums for some enumeration schemes of
$(n$$\times$$n)\times(N$$\times N)$ cellular arrangement patterns.

######  Corollary 2.

Using the Mitchison–Durbin pattern $f_{\mathrm{M}}$ in a Jordan–Wigner
transformation for a fermionic system with square–lattice–interacting hopping
terms produces Pauli strings in the qubit Hamiltonian $H_{\text{qubit}}$ with
an average weight of $\frac{1}{3}\left(4-\sqrt{2}\right)\approx 0.86$ times
the corresponding average Pauli weight that the Z–pattern $f_{\mathrm{Z}}$ and
the S–pattern $f_{\mathrm{S}}$ produce.

###### Proof.

On an $N$$\times$$N$ lattice, the Mitchison–Durbin pattern $f_{\mathrm{M}}$
and the S–pattern $f_{\mathrm{S}}$ have edgesums

$\displaystyle C^{1}(f_{\mathrm{Z}})$ $\displaystyle=N^{3}-N\,,$ (60)
$\displaystyle C^{1}(f_{\mathrm{S}})$ $\displaystyle=N^{3}-N\,,$ (61)
$\displaystyle C^{1}(f_{\mathrm{M}})$
$\displaystyle=N^{3}-xN^{2}+2x^{2}N-\frac{2}{3}x^{3}+N^{2}$ (62)
$\displaystyle\qquad\qquad\qquad\quad-xN-2N+\frac{2}{3}x\,,$

respectively. The edgesum $C^{1}(f_{\mathrm{Z}})$ is straightforward to
calculate; see Appendix VI.1 for the derivation of $C^{1}(f_{\mathrm{S}})$,
and Section VI.2 for the derivation of $C^{1}(f_{\mathrm{M}})$. In Equation
62, the value of $x$ is the closest integer to
$N-\frac{1}{2}\sqrt{2N^{2}-2N+\frac{4}{3}}$. Using Equation 58 and the number
of hopping terms $|G_{\text{F}}|=2N(N-1)$, the average Pauli weights are

$\displaystyle APV(f_{\mathrm{Z}})=APV(f_{\mathrm{S}})$
$\displaystyle=\frac{1}{2}N+\frac{3}{2}$ (63)

and, for large $N$,

$\displaystyle APV(f_{\mathrm{M}})$
$\displaystyle\approx\frac{1}{6}(4-\sqrt{2})N+\frac{1}{12}(20+\sqrt{2})$ (64)
$\displaystyle=0.43N+1.78\,.$ (65)

For small $N$, explicit calculation verifies that
$APV(f_{\mathrm{S}})>APV(f_{\mathrm{M}})$ for $N\geq 6$. The ratio of average
Pauli weights is thus
$APV(f_{\mathrm{M}})/APV(f_{\mathrm{S}})=APV(f_{\mathrm{M}})/APV(f_{\mathrm{Z}})\approx\frac{1}{3}(4-\sqrt{2})\approx
0.86$. ∎

We can conclude from Corollary 2 that, simply by labelling the fermionic modes
using the Mitchison–Durbin pattern rather than the S–pattern as proposed in
[17] or Z–pattern, we can produce a qubit Hamiltonian with terms that are
13.9% more local on average. Our proposal immediately translates to a
reduction by the same amount in the number of single–qubit measurements
required in a VQE protocol. Even in the case of simulating small fermionic
systems, this method provides a worthwhile advantage. For example, in Figure 7
where $N=6$, the ratio of the average Pauli weight using $f_{\mathrm{M}}$
versus $f_{\mathrm{S}}$ is $4.33/4.5\approx 0.96$. That is, even for the
$6$$\times$$6$ lattice, applying Theorem 1 will reduce the number of Pauli
measurements by 4%.

For $2\leq N\leq 100$, Figure 15 shows the resulting average Pauli weights of
various enumeration schemes on $N$$\times$$N$ lattices. Even for small
lattices, the Mitchison–Durbin pattern can yield a meaningful reduction: for
$N=20$, $C^{1}(f_{\mathrm{M}})/C^{1}(f_{\mathrm{S}})=\frac{7140}{7980}\approx
89.5\%$.

###  III.5 Reducing the average Pauli weight for cellular fermionic lattices

Theorem 1 reduces the average Pauli weight of qubit Hamiltonians by making
judicious use of the solutions to the edgesum problem. Remark 4 refers to the
scarce number of other graph families for $G_{\text{F}}$ for which edgesum
solutions are known. It is tempting to think that there is not much use for
our approach if the fermionic interaction graph $G_{\mathrm{F}}$ does not
belong to one of these families. In this section, however, we show example
fermionic Hamiltonians for which the enumeration schemes arising from
approximate edgesum solutions can provide order–of–magnitude reductions in the
average Pauli weight of the qubit Hamiltonians.

Consider fermionic Hamiltonians of the form in Equation 55 with hopping terms
between modes such that $G_{\text{F}}$ is an
$(n$$\times$$n)$$\times$$(N$$\times$$N)$ cellular arrangement of square
lattices, where each $n$$\times$$n$ sub-lattice connects to adjacent sub-
lattices via a single edge. Here we use the cellular pattern in Figure 10,
where the connections are from each $n$$\times$$n$ lattice’s top left vertex
to the two closest vertices from neighbouring $N$$\times$$n$ lattice.

It is possible to enumerate the fermionic modes with the Z–pattern
$f_{\mathrm{Z}}$ or the S–pattern $f_{\mathrm{S}}$ from Section III.4,
treating the whole graph $G_{\text{F}}$ as a single square lattice. As Figure
10 shows, another way of enumerating the modes is to enumerate each sub-
lattice locally before moving on to the next, progressing through the entire
graph via an S– or Z–pattern. We call these two enumeration procedures
$f_{\mathrm{S}^{\prime}}$ and $f_{\mathrm{Z}^{\prime}}$, respectively.

The edgesums of these schemes on the cellular arrangement graph are:

$\displaystyle C^{1}(f_{\mathrm{S}})$
$\displaystyle=\begin{cases}(Nn)^{3}-Nn&\\\ -N(N-1)(n-1)&\\\
-\sum_{k=0}^{N-1}\sum_{i=kn+2}^{(k+1)n}(2i-1)\,,&n\text{ even}\\\
(Nn)^{3}-Nn&\\\ -N(N-1)(n-1)&\\\
-\sum_{k=0}^{N-1}\sum_{i=kn+1}^{(k+1)n-1}(2i-1)\,,&n\text{ odd,}\end{cases}$
(66) $\displaystyle C^{1}(f_{\mathrm{Z}})$
$\displaystyle=(Nn)^{3}-Nn-N(N-1)(n-1)$ (67) $\displaystyle\quad-
nN^{2}(n-1)(N-1)\,,$ $\displaystyle C^{1}(f_{\mathrm{Z}^{\prime}})$
$\displaystyle=\begin{cases}N^{3}n^{2}+n^{3}N^{2}-n^{2}N^{2}&\\\
\quad-2nN^{2}-n^{2}N+2N^{2}&\\\ \quad+2nN+n^{2}-2N-n\,,&n\text{ even}\\\
N^{3}n^{2}+n^{3}N^{2}-n^{2}N^{2}&\\\ \quad-nN^{2}-n^{2}N+N^{2}&\\\
\quad+2nN+n^{2}-2N-2n+1\,,&n\text{ odd,}\end{cases}$ (68)

and while the value of $C^{1}(f_{\mathrm{S}^{\prime}})$ also depends on the
parities of $n$ and $N$, it is strictly greater than
$C^{1}(f_{\mathrm{Z^{\prime}}})$.

By using $f_{\mathrm{Z}^{\prime}}$ rather than $f_{\mathrm{Z}}$, the edgesum
of a large cellular arrengement graph reduces by an order of magnitude:

$\displaystyle\lim_{N\rightarrow\infty}\frac{C^{1}(f_{\mathrm{Z}^{\prime}})}{C^{1}(f_{\mathrm{Z}})}$
$\displaystyle=\frac{n^{2}}{n^{3}-n^{2}+n}=\mathcal{O}\left(\frac{1}{n}\right)\,;$
(69)
$\displaystyle\lim_{n\rightarrow\infty}\frac{C^{1}(f_{\mathrm{Z}^{\prime}})}{C^{1}(f_{\mathrm{Z}})}$
$\displaystyle=\frac{1}{N}\,.$ (70)

If $n=\mathcal{O}(N)$, then the system has $\mathcal{O}(N^{4})$ fermionic
modes. From choosing $f_{\mathrm{Z}^{\prime}}$ rather than $f_{\mathrm{Z}}$,
the $\mathcal{O}(1/N)$ factor reduction in the average Pauli weight of the
qubit Hamiltonian is thus proportional to the fourth root of the number of
fermionic modes. This is much more striking than the constant–factor
improvement proffered by Corollary 2, even though there is no proof that
$f_{\mathrm{Z}^{\prime}}$ is an optimal enumeration scheme for this type of
fermionic interaction graph $G_{\text{F}}$.

###  III.6 Reducing the average $p$th power of Pauli weight for a square
lattice

Section III.3 introduced the average $p$th power of Pauli weight for $p>1$ as
a cost function for the qubit Hamiltonian. For a fermionic Hamiltonian
$H_{\text{fermion}}$ with interaction graph $G_{\mathrm{F}}$, consider the
task of finding an enumeration scheme $f$ that minimises the $p$–sum

$\displaystyle C^{p}(f)=\left(\sum_{(u,v)\in
G_{\text{F}}}|f(u)-f(v)|^{p}\right)^{1/p}\,.$ (71)

Figure 11: Results for the minimum $p$–sum problem for the square lattice for
$p\geq 1$. While the Mitchison–Durbin pattern $f_{\mathrm{M}}$ minimises
$C^{p}(f)$ for $p=1$, it performs the worst of all the options for $p>1$. The
diagonal pattern $f_{\mathrm{D}}$ performs better than the rest for $p>2$.

The $p=1$ case is the edgesum problem and via Remark 3 is –hard. George and
Pothen showed that the minimum 2–sum problem is also –hard [47]. They develop
spectral approaches to solving the minimum 1–sum and 2–sum problems for any
graph $G_{\mathrm{F}}$. Separately, Mitchison and Durbin [31] explored the
minimum $p$–sum problem for square lattices, and conclude with Proposition 1:

######  Proposition 1.

_(Mitchison and Durbin’s results for the minimum $p$–sum problem on an
$N$$\times$$N$ lattice [31])_ Let $G$ be the $N$$\times$$N$ square lattice.
Then the following are the lower limits for the value of $C^{p}(f)$:

  1. _(a)_

If $0<p<\frac{1}{2}$, then there exists an enumeration scheme $f$ with
$C^{p}(f)=\mathcal{O}(N^{2})$.

  2. _(b)_

If $\frac{1}{2}<p<1$, then
$C^{p}(f)\displaystyle\geq\frac{1}{2p+1}N^{1+2p}+\mathcal{O}\left(N^{2p}\right)$.

  3. _(c)_

If $p=1$, then $f_{\mathrm{M}}$ gives the minimum value as shown in Theorem 1.

  4. _(d)_

If $p>1$, then $C^{p}(f)\displaystyle\geq\frac{4}{2^{p}(p+2)}N^{p+2}$.

The lower bounds in _(b)_ and _(d)_ are theoretical limits, and to date there
are no known enumeration schemes that achieve their low coefficients. However,
the “diagonal pattern” $f_{\mathrm{D}}$ has edgesum

$\displaystyle
C(f_{\mathrm{D}})\approx\frac{4}{p+2}N^{p+2}+\mathcal{O}(N^{p+1})\,,$ (72)

which has the same order of magnitude in $N$ as the theoretical limit in
_(d)_.

###### Proof.

See Propositions 2–4 of [31]. ∎

######  Remark 5.

_(Best known results for the minimum $p$–sum problem on a square lattice,
$p\geq 1$)_

Figure 11 provides a table of known results for four enumeration schemes
$f_{\mathrm{S}}$, $f_{\mathrm{M}}$, $f_{\mathrm{Z}}$, and $f_{\mathrm{D}}$
(the diagonal pattern) in the regimes $p=1$ and $p>1$. The diagonal pattern is
the solution to the bandwidth problem (from Section II.7) on rectangles [31],
and is the best–performing pattern for the minimum $p$–sum problem for $p>1$,
$N\rightarrow\infty$.

##  IV Improving beyond optimality with ancilla qubits

The fermion–qubit mappings in Definitions 1–4, Examples 1–3, and in Section
III are all mappings between $n$–mode fermionic systems and $n$–qubit systems.
Theorem 1, for example, details the Jordan–Wigner mapping with minimum average
Pauli weight when using $N^{2}$ qubits to simulate a fermionic system on
$N^{2}$ modes. However, there is a storied interplay between the qubit count
of a fermion–qubit mapping and the locality of its Hamiltonian. As both qubits
and quantum gates are costly with current technology, the tradeoff begs the
question: what is the maximum benefit a mapping could gain by using an extra
one or two qubits?

In Section IV.1, we describe Steudtner and Wehner’s template for auxiliary
qubit mappings [30]. In Section IV.2, we give an example of this process in
the form of a new auxiliary qubit mapping. We augment the Mitchison–Durbin
pattern to produce an auxiliary qubit mapping
$\overline{\text{JW}}_{f_{\text{M}+2}}$ which achieves a 37.9% reduction over
the average Pauli weight of $\overline{\text{JW}}_{f_{\text{S}}}$, using only
two extra qubits. Thus, taking advantage of the Mitchison–Durbin pattern we
see that a constant number of additional qubits almost triples the advantage
provided by Theorem 1, thus improving our earlier results ‘beyond optimality’.

###  IV.1 Background: auxiliary qubit mappings

Moll et al. [53] show how to reduce the number of qubits required by a
Jordan–Wigner transformation at the cost of introducing more terms into the
molecular Hamiltonian. Auxiliary qubit mappings [17, 30, 35, 34, 54] show the
converse: that by introducing more qubits into a simulation of
$H_{\text{fermion}}$, it is possible to vastly simplify the qubit Hamiltonian
$H_{\text{qubit}}$. Verstraete and Cirac demonstrated a fermion–qubit mapping
between a fermionic Hamiltonian $H_{\text{fermion}}$ with a square–lattice
interaction graph $G_{\text{F}}$ [17] and a qubit Hamiltonian
$H_{\text{qubit}}$ on $2N^{2}$ qubits consisting of only local terms. That is,
rather than producing long strings of Pauli terms of weight $\mathcal{O}(N)$
that wind around the qubit lattice (as in, for example, Figure 17), the
auxiliary qubit mappings produce operations of weight $\mathcal{O}(1)$.

Steudtner and Wehner’s formulation of auxiliary qubit mappings [30] is thus:
suppose that a fermion–qubit mapping produces the qubit Hamiltonian

$\displaystyle H_{\text{fermion}}\longmapsto H_{\text{q}}\coloneqq
H_{\text{qubit}}=\sum_{h\in\Lambda}c_{h}h\,,$ (73)

where $\Lambda\subseteq\\{\mathds{1},X,-iY,Z\\}^{\otimes n}=G_{n}$, and the
$c_{h}\in\mathds{C}$ ensure that $H_{\text{q}}$ is Hermitian. Denote by the
subscript ‘dat’ the $n$–qubit data system upon which the Hamiltonian
$H_{\text{q}}$ acts. Given a state $\ket{\psi}_{\text{dat}}$ of the data
system, the goal is to reduce the complexity of simulating the time–evolved
state $e^{-iH_{\text{q}}t}\ket{\psi}_{\text{dat}}$. An auxiliary qubit mapping
achieves this goal by instead mapping

$H_{\text{fermion}}\longmapsto\widetilde{H}_{\text{q}}\,,$ (74)

where $\widetilde{H}_{\text{q}}$ is a simplified qubit Hamiltonian that acts
on both the data register and ancilla qubits in an auxiliary register, denoted
‘aux’. The following three steps detail how to construct Steudtner and
Wehner’s type of auxiliary qubit mapping.

  1. 1.

Choose a subset $\Lambda_{\text{non-loc}}\subseteq\Lambda$ of terms in the
Hamiltonian $H_{\text{q}}$. These are the terms which will be shorter in
$\widetilde{H}_{\text{q}}$. For each $h\in\Lambda_{\text{non-loc}}$, choose a
Pauli string $p^{h}$ where $h=h_{\text{loc}}\,p^{h}$ such that the weight of
$h_{\text{loc}}$ is less than that of $h$. In total, only use $r$ distinct
$p$–strings. That is, several $h\in\Lambda_{\text{non-loc}}$ may contain the
same $p^{h}$.

Denote the set of all $p^{h}$ by $\\{p_{i}\\}_{i=1}^{r}$. That is, for any
$h\in\Lambda_{\text{non-loc}}$, then $p^{h}=p_{i}$ for some
$i\in\\{1,\dots,r\\}$.

  2. 2.

Introduce $r$ ancilla qubits in the auxiliary register, and devise a unitary
mapping

$\displaystyle V:\ket{\psi}_{\text{dat}}\ket{0}^{\otimes
r}_{\text{aux}}\longmapsto|\widetilde{\psi}\rangle_{\text{dat,aux}}$ (75)

where $\ket{\smash{\widetilde{\psi}}}_{\text{dat,aux}}$ is such that for each
$i\in\\{1,\dots,r\\}$, there exists $\sigma_{i}\in\\{\mathds{1},X,-iY,Z\\}$
acting on the $i$th auxiliary qubit such that

$\displaystyle((p_{i})_{\text{dat}}\otimes(\sigma_{i})_{\text{aux}})|\widetilde{\psi}\rangle_{\text{dat,aux}}=\ket{\smash{\widetilde{\psi}}}_{\text{dat,aux}}\,.$
(76)

The $p_{i}\otimes\sigma_{i}$ are the stabilisers of the combined data and
auxiliary system.

Requirement 1: The choice of $\\{p_{i}\\}_{i=1}^{r}$ must allow for the
existence of $\ket{\smash{\widetilde{\psi}}}_{\text{dat,aux}}$ obeying
Equation 76. A necessary but insufficient condition is that $[p_{i},p_{j}]=0$
for all $i,j\in\\{1,\dots,r\\}$.

  3. 3.

Modify each $h\in\Lambda$ via

$\displaystyle h_{\text{dat}}\longmapsto
h_{\text{dat}}\otimes\kappa^{h}_{\text{aux}}\,,$ (77)

where $\kappa^{h}$ is a Pauli string acting on the auxiliary qubits such that

$\displaystyle[h_{\text{dat}}\otimes(\kappa^{h})_{\text{aux}},\,(p_{i})_{\text{dat}}\otimes(\sigma_{i})_{\text{aux}}]=0$
(78)

for all $i\in\\{1,\dots,r\\}$. The rationale for this step is as follows:
Suppose that $h=h_{\text{loc}}\,p^{h}$, where $p^{h}=p_{i}$. Then, we can
multiply each $h=h_{\text{loc}}\,p^{h}\in\Lambda_{\text{non-loc}}$ by its
corresponding stabiliser, thus producing a lower–weight Hamiltonian term,
$\big{(}(h_{\text{loc}})_{\text{dat}}\otimes(\sigma_{i})_{\text{aux}}\big{)}$:

$\displaystyle(h_{\text{dat}}\otimes\mathds{1}_{\text{aux}})\ket{\smash{\widetilde{\psi}}}_{\text{dat,aux}}$
(79)
$\displaystyle\quad=\big{(}(h_{\text{loc}}\,p^{h})_{\text{dat}}\otimes\mathds{1}_{\text{aux}}\big{)}\ket{\smash{\widetilde{\psi}}}_{\text{dat,aux}}$
$\displaystyle\quad=\big{(}\left(h_{\text{loc}}\,p_{i}\right)_{\text{dat}}\otimes\mathds{1}_{\text{aux}}\big{)}\ket{\smash{\widetilde{\psi}}}_{\text{dat,aux}}$
(80)
$\displaystyle\quad=\big{(}\left(h_{\text{loc}}\,p_{i}\right)_{\text{dat}}\otimes\mathds{1}_{\text{aux}}\big{)}$
(81)
$\displaystyle\qquad\qquad\qquad\big{(}(p_{i})_{\text{dat}}\otimes(\sigma_{i})_{\text{aux}}\big{)}\ket{\smash{\widetilde{\psi}}}_{\text{dat,aux}}$
$\displaystyle\quad=\big{(}(h_{\text{loc}})_{\text{dat}}\otimes(\sigma_{i})_{\text{aux}}\big{)}\ket{\smash{\widetilde{\psi}}}_{\text{dat,aux}}\,.$
(82)

To replicate the time evolution $e^{-iH_{\text{q}}t}\ket{\psi}_{\text{dat}}$
of the system, it is necessary to be able to generate any stabiliser
$((p_{j})_{\text{dat}}\otimes(\sigma_{j})_{\text{aux}})$ at the step in
Equation 81 and commute it past any Hamiltonian term
$h_{\text{dat}}\otimes\mathds{1}_{\text{aux}}$ where $h$ can now be any
element of $\Lambda$. If
$[h_{\text{dat}}\otimes\mathds{1}_{\text{aux}},\,(p_{j})_{\text{dat}}\otimes(\sigma_{j})_{\text{aux}}]=[h,p_{j}]\neq
0$, then application of the Hamiltonian term produces a state

$\displaystyle|\widetilde{\psi}\,\smash{{}^{\prime}}\rangle_{\text{dat
aux}}=(h_{\text{dat}}\otimes\mathds{1}_{\text{aux}})\ket{\smash{\widetilde{\psi}}}_{\text{dat,aux}}$
(83)

that no longer satisfies Equation 76 for all $i$, and thus it is impossible to
generate and apply more stabilisers as required by Equation 81.

Requirement 2: Crucially, the $\kappa^{h}$ must be such that they preserve the
time evolution of the data system. That is,

$\displaystyle
V^{\dagger}(h_{\text{dat}}\otimes(\kappa^{h})_{\text{aux}})\ket{\smash{\widetilde{\psi}}}_{\text{dat,aux}}$
(84)
$\displaystyle\qquad\qquad\qquad\qquad=h\ket{\psi}_{\text{dat}}\otimes\ket{0}^{\otimes
r}_{\text{aux}}\,.$

Otherwise, the system would not retain any useful information. The requirement
for the existence of $\kappa^{h}$ for $h\in\Lambda$ places a restriction on
$V$.

After satisfying the above three steps, observe that

$\displaystyle\left(e^{-iH_{\text{q}}t}\ket{\psi}_{\text{dat}}\right)\otimes\ket{0}^{\otimes
r}_{\text{aux}}=\left(V^{\dagger}e^{-i\widetilde{H}_{\text{q}}t}\right)\ket{\smash{\widetilde{\psi}}}_{\text{dat,aux}}\,,$
(85)

where the effective qubit Hamiltonian $\widetilde{H}_{\text{q}}$ achieves the
goal of reducing the Pauli weight of the strings in $\Lambda_{\text{non-
loc}}$, and acts on both the data and auxiliary systems:

$\displaystyle\widetilde{H}_{\text{q}}=$
$\displaystyle\sum_{h\in\Lambda_{\text{non-
loc}}}c_{h}\big{(}(h_{\text{loc}})_{\text{dat}}\otimes(\kappa^{h}\sigma^{h})_{\text{aux}}\big{)}$
(86) $\displaystyle\qquad\qquad+\sum_{h\in\Lambda\backslash\Lambda_{\text{non-
loc}}}c_{h}(h_{\text{dat}}\otimes(\kappa^{h})_{\text{aux}})\,.$

In Equation 86, the Pauli matrix $\sigma^{h}$ is the matrix $\sigma_{i}$ from
the stabiliser $p_{i}\otimes\sigma_{i}$ corresponding to
$h=h_{\text{loc}}\,p^{h}$ via $p^{h}=p_{i}$. Assuming the cost of implementing
$V$ is insignificant compared to cost of implementing time evolution by
$\widetilde{H}_{\text{q}}$, then Equation 85 shows the advantage of the
auxiliary qubit mapping: $V^{\dagger}e^{-i\widetilde{H}_{\text{q}}t}$ is less
costly to implement than $e^{-iH_{\text{q}}t}$.

Note that this is not the most general form of auxiliary qubit mapping. An
example of one that does not fit this template is the Verstraete–Cirac
mapping, which uses stabilisers that are of the form
$p_{\text{dat}}\otimes\tau_{\text{aux}}$ where $\tau_{\text{aux}}$ acts on
more than one qubit [17].

Figure 12: Stabilisers and adjusted Hamiltonian hopping terms for the
auxiliary qubit mapping using our augmented Mitchison–Durbin pattern,
‘$f_{\dot{h}^{\prime}+2}$’. Initialising the $(N^{2}$$+$$2)$–qubit system in a
state stabilised by the strings $p_{i}\otimes\sigma_{i}$ nullifies the most
costly contributions to the edgesum of the Mitchison–Durbin pattern, resulting
in a significantly reduced average Pauli weight for the qubit Hamiltonian
$\widetilde{H}_{\text{q}}$. As the text details, setting $x\approx 0.40N$ in
the enumeration scheme $\dot{h}^{\prime}$ yields the minimum average Pauli
weight.

###  IV.2 Using 2 ancilla qubits to reduce average Pauli weight by 37.9%
compared to the S–pattern

By modifying the proposal in Theorem 1, it is possible to use techniques
inspired by the Mitchison–Durbin pattern to produce a ‘super–efficient’
fermion–qubit mapping $\overline{\text{JW}}_{f_{\text{M}}+2}$ for problem
Hamiltonians $H_{\text{fermion}}$, with interaction graphs $G_{\text{F}}$
equal to the $N$$\times$$N$ square lattice, using just $N^{2}+2$ qubits. This
auxiliary Jordan–Wigner transformation has an average Pauli weight
approximately 37.9% less than that of the original
$\overline{\text{JW}}_{f_{\text{S}}}$ presented in [17], and 27.9% less than
our result $\overline{\text{JW}}_{f_{\text{M}}}$ presented in Theorem 1, which
was provably optimal for $n$–mode to $n$–qubit Jordan–Wigner transformations
of the form in Definition 2.

Begin with a data register of $N^{2}$ qubits, and take a fermionic Hamiltonian
$H_{\text{fermion}}$ of the form in Equation 55, where $G_{\mathrm{F}}=(V,E)$
is the $N$$\times$$N$ square lattice. As the quartic terms become local under
any Jordan–Wigner transformation, consider only the hopping terms of the
resulting qubit Hamiltonian

$\displaystyle H_{\text{q}}$
$\displaystyle\coloneqq\overline{\text{JW}}_{\dot{h}^{\prime}}\left(\sum_{(\alpha,\beta)\in
E}a_{\alpha}^{\dagger}a_{\beta}+a_{\alpha}a_{\beta}^{\dagger}\right)$ (87)
$\displaystyle=\sum_{h\in\Lambda}c_{h}h\,,$ (88)

where $\Lambda$ is the subset of the Pauli group $G_{n}$ consisting of the
terms of $H_{\text{q}}$, and $\dot{h}^{\prime}$ is the Mitchison–Durbin
pattern with a variable value for $x$, as in Lemma 5. In $f_{\text{M}}$ the
value $x\approx$ $0.29N$; however this only minimises $C^{1}(f_{\mathrm{M}})$
for Jordan–Wigner transformations with zero ancilla qubits. Since we are
permitting ancillas, as in the proof of Theorem 1, treat
$x\in\\{1,2,\dots,N/2\\}$ as a variable, its optimal value currently unknown.

Note that the edgesum $C^{1}(f_{\mathrm{M}})$ has two costly contributions:
the $\mathcal{O}(x^{2}N)$–valued difference between adjacent vertices in the
$AD$– and $DG$–interfaces as labelled in Figure 26. We will construct an
auxiliary qubit mapping that reduces the contributions of these edges to
$C^{1}(f_{\mathrm{M}})$, and hence reduces the average Pauli weight of the
qubit Hamiltonian.

The fermion–qubit mapping we construct here uses only two ancilla qubits and
takes a similar approach to the E–type auxiliary qubit mapping from [30]. We
will follow the formulation of auxiliary qubit mappings from Section IV:

Figure 13: A circuit for $V$, which initialises the stabiliser state
$\ket{\smash{\widetilde{\psi}}}_{\text{dat,aux}}$ from
$\ket{\psi}_{\text{dat}}\ket{0}^{\otimes 2}_{\text{aux}}$ while preserving the
time–evolution of the underlying data system. Figure 14: Comparison between
the average Pauli weights of Jordan–Wigner mappings generated by the
Mitchison–Durbin pattern $f_{\mathrm{M}}$ (left) and our auxiliary qubit
pattern $f_{\mathrm{M}+2}$ (right). The bottom right image shows the reduction
of the Pauli weight of long hopping terms after multiplication by stabilisers.
Terms that partially overlap the stabilisers must also be adjusted.

  1. 1.

Choose $p$–strings $\\{p_{1},p_{2}\\}$ that correspond to the longest
individual strings of Pauli $Z$ matrices of any term $h\in\Lambda$. In this
case, we choose

$\displaystyle p_{1}$
$\displaystyle=\left(\bigotimes_{i=x(x-1)+1}^{xN-1}Z_{i}\right)\otimes\left(\bigotimes_{\text{other
}}\mathds{1}_{i}\right)$ (89) $\displaystyle p_{2}$
$\displaystyle=\left(\bigotimes_{i=(N-x)N}^{N^{2}-x^{2}+x-2}Z_{i}\right)\otimes\left(\bigotimes_{\text{other
}i}\mathds{1}_{i}\right)\,.$ (90)

These bridge the gaps between the outermost vertices on the $AD$– and
$DG$–interfaces, respectively. Figure 12 depicts the two $p$–strings for
differing values of $x$; the indices of the first and last qubits of each
$p$–string result from inspecting the label guide in Figure 27.

Then, define $\Lambda_{\text{non-loc}}$ to be all of the Hamiltonian terms
$h\in\Lambda$ that contain less $Z$ matrices upon multiplication by either
$p_{1}$ or $p_{2}$. Note that none of the $h\in\Lambda$ would benefit from
multiplication by both $p$–strings, unless $x=N/2$ exactly as, in that case,
there is no column of vertices separating the stabilisers. Figure 14 shows
this in detail with $N=6$ and $x=3$. These $p$–strings trivially satisfy
Requirement 1’s preliminary condition that $[p_{1},p_{2}]=0$.

  2. 2.

Introduce two auxiliary qubits, labelled $-1$ and $N^{2}$. Define the unitary
mapping $V$ to be a cascade of controlled–NOT operations, storing the net
parity of the qubits appearing in $p_{i}$ in the phase of the $i$th auxiliary
qubit. Figure 13 shows a valid circuit for $V$.

For any state $\ket{\psi}_{\text{dat}}$ of the original $N^{2}$–qubit system,
now consider the state

$\displaystyle\ket{\smash{\widetilde{\psi}}}_{\text{dat,aux}}=V\ket{\psi}_{\text{dat}}\ket{0}^{\otimes
2}_{\text{aux}}\,.$ (91)

This state has two stabilisers:

$\displaystyle\big{(}(p_{1})_{\text{dat}}\otimes(Z\otimes\mathds{1})_{\text{aux}}\big{)}\ket{\smash{\widetilde{\psi}}}_{\text{dat,aux}}=\ket{\smash{\widetilde{\psi}}}_{\text{dat,aux}}\,,$
(92) $\displaystyle\big{(}(p_{2})_{\text{dat}}\otimes(\mathds{1}\otimes
Z)_{\text{aux}}\big{)}\ket{\smash{\widetilde{\psi}}}_{\text{dat,aux}}=\ket{\smash{\widetilde{\psi}}}_{\text{dat,aux}}\,.$
(93)

The existence of the stabiliser state
$\ket{\smash{\widetilde{\psi}}}_{\text{dat,aux}}$ satisfies Requirement 1.

  3. 3.

To identify which terms $h\in\Lambda$ do not commute with $p_{1}$ and $p_{2}$,
recall the form of the hopping terms from Equation 50. The only relevant
feature of a term $h$ is the location of the endpoint matrices of its
non–identity Pauli strings, i.e. its $X$ and $Y$ matrices. For brevity, and
without loss of generality, abbreviate the terms to just the Pauli string
$XZZ...ZX$:

$\displaystyle h_{\text{dat}}=\left(X\otimes Z\otimes\dots\otimes Z\otimes
X\right)\otimes\left(\bigotimes_{\text{other}}\mathds{1}\right)\,.$ (94)

As $p_{1}$ and $p_{2}$ comprise only $Z$ matrices, $[h,p_{i}]=0$ if and only
if the Pauli string $XZZ...ZX$ of $h$ intersects completely, or not at all,
with the Pauli string $ZZZ...Z$ of $p_{i}$, because $[X,Z]=-2Y\neq 0$. Thus
the vast majority of the hopping terms already commute with both $p$–strings;
it is only the hopping terms with Pauli strings that have one endpoint in
$p_{i}$ and the other not in $p_{i}$ that need to be modified so that they
commute with both stabilisers. If $[h,p_{1}]\neq 0$, make the adjustment

$\displaystyle h_{\text{dat}}$ $\displaystyle\longmapsto
h_{\text{dat}}\otimes\left(X\otimes\mathds{1}\right)_{\text{aux}}\,;$ (95)

if $[h,p_{2}]\neq 0$, make the adjustment

$\displaystyle h_{\text{dat}}$ $\displaystyle\longmapsto
h_{\text{dat}}\otimes\left(\mathds{1}\otimes X\right)_{\text{aux}}\,.$ (96)

If $x=N/2$ exactly, then some of the horizontal hopping terms across the $BD$–
and $DF$–interfaces will not commute with either $p_{1}$ or $p_{2}$, and need
both adjustments (as depicted in Figure 14). Abbreviating each correction by
$\kappa^{h}$, adjusted Hamiltonian terms then satisfy

$\displaystyle[h_{\text{dat}}\otimes\kappa^{h}_{\text{aux}},(p_{i})_{\text{dat}}\otimes(\sigma_{i})_{\text{aux}}]=0$
(97)

for $i=1,2$ because $[X_{\text{dat}}\otimes
X_{\text{aux}},Z_{\text{dat}}\otimes Z_{\text{aux}}]=0$. Figure 12 shows which
hopping terms need adjustment in this way.

Finally, check that $V$ and $\kappa^{h}$ satisfy Requirement 2. Let $h$ be a
hopping term that does not commute with $p_{1}$. Consider an arbitrary state
for the quantum register

$\displaystyle\ket{\psi}_{\text{dat}}=\sum_{\vec{a},\smash{\vec{b}},\vec{c}}\gamma\ket{a_{0}a_{1}\dots,\,b_{0}b_{1}\dots,\,c_{0}c_{1}\dots}_{\text{dat}}\,,$
(98)

where $a_{j},b_{j},c_{j}\in\\{0,1\\}$ such that $\vec{a}$ contains the
parities of all the qubits involved in $p_{1}$, $\vec{b}$ contains the
parities of the qubits not involved in either $p$–string, and $\vec{c}$
contains the parities of the qubits involved in $p_{2}$. The coefficients
$\gamma\in\mathds{C}$ depend on the bit strings $\vec{a}$, $\vec{b}$ and
$\vec{c}$.

As $h$ does not commute with $p_{1}$, one of the $X$ matrices in its Pauli
string must act on a qubit in $\vec{a}$ and the other $X$ matrix most act on a
qubit in either $\vec{b}$ (if $x<N/2$) or $\vec{c}$ (if $x=N/2$ exactly).
Consider the case $x<N/2$ and let the endpoint qubits of the Pauli string of
$h$ be the $j$th and $k$th qubits in each string, respectively. Therefore, the
output of $h\ket{\psi}_{\text{dat}}$ is

$\displaystyle
h\ket{\psi}_{\text{dat}}=\sum_{\vec{a},\smash{\vec{b}},\vec{c}}\gamma^{\prime}\ket{a_{1}...\,\overline{a_{j}}...,\,b_{1}...\,\overline{b_{k}}...,\,c_{1}c_{2}...}_{\text{dat}}\,,$
(99)

where each $\gamma^{\prime}$ is equal to $\gamma$ up to a sign depending on
the effect of the $Z$ matrices in $h$. Meanwhile, our prescription for
$\kappa^{h}$ is to apply an $X$ on the first auxiliary qubit. Noting that
$V=V^{\dagger}$, observe that

$\displaystyle V(h\otimes\kappa^{h})\ket{\smash{\widetilde{\psi}}}$
$\displaystyle=V(h\otimes\kappa^{h})\sum_{\vec{a},\smash{\vec{b}},\vec{c}}\gamma\ket{a_{0}a_{1}...,\,b_{0}b_{1}...,\,c_{0}c_{1}...}_{\text{dat}}\otimes\left(\ket{\oplus_{l}\,a_{l}}\ket{\oplus_{l}\,c_{l}}\right)_{\text{aux}}$
(100)
$\displaystyle=V\sum_{\vec{a},\smash{\vec{b}},\vec{c}}\gamma^{\prime}\ket{a_{0}...\overline{a_{j}}...,\,b_{0}...\overline{b_{k}}...,\,c_{0}c_{1}...}_{\text{dat}}\otimes\left(|\overline{\oplus_{l}\,a_{l}}\rangle\ket{\oplus_{l}\,c_{l}}\right)_{\text{aux}}$
(101)
$\displaystyle=V\sum_{\vec{a},\smash{\vec{b}},\vec{c}}\gamma^{\prime}\ket{a_{0}...\overline{a_{j}}...,\,b_{0}...\overline{b_{k}}...,\,c_{0}c_{1}...}_{\text{dat}}\otimes\left(|a_{0}\oplus...\oplus\overline{a_{j}}\oplus...\rangle\ket{\oplus_{l}\,c_{l}}\right)_{\text{aux}}$
(102)
$\displaystyle=\sum_{\vec{a},\smash{\vec{b}},\vec{c}}\gamma^{\prime}\ket{a_{0}...\overline{a_{j}}...,\,b_{0}...\overline{b_{k}}...,\,c_{0}c_{1}...}_{\text{dat}}\otimes\left(\ket{0}\ket{0}\right)_{\text{aux}}$
(103) $\displaystyle=h\ket{\psi}_{\text{dat}}\otimes\ket{0}^{\otimes
2}_{\text{aux}}\,$ (104)

as required. Progressing from Equation 102 to Equation 103 uses fact that $V$
is a cascade of controlled–NOT gates. A symmetric argument follows for all
$h\in\Lambda$ which do not commute for $p_{2}$. For the case $x=N/2$, there
will also be Hamiltonian terms that flip $a_{j}$ and $c_{k}$, and a similar
argument applies.

This establishes a modified qubit Hamiltonian $\widetilde{H}_{\text{q}}$ via
Equation 86 and hence an auxiliary qubit mapping with two ancilla qubits,
which we denote by $\overline{\text{JW}}_{\dot{h}^{\prime}+2}$:

$\displaystyle\overline{\text{JW}}_{\dot{h}^{\prime}+2}:\big{(}H_{\text{fermion}}\text{
hopping terms}\big{)}\longmapsto\widetilde{H}_{\text{q}}\,.$ (105)

By construction, this mapping follows the rules set out in Section IV.1. The
mapping has one degree of freedom: the value of $x$ in the enumeration scheme
$\dot{h}^{\prime}$, which relates the $n$ fermionic modes to the $n$ data
qubits.

As established in Section III for $n$–mode to $n$–qubit mappings, there are
many possible cost functions for the qubit Hamiltonian. In extending this
concept to our new $n$–mode to $(n+2)$–qubit mapping
$\overline{\text{JW}}_{\dot{h}^{\prime}+2}$, we will determine the optimal
value for $x$ in order to minimise the average Pauli weight of
$\widetilde{H}_{\text{q}}$.

The total Pauli weight of all terms in the modified Hamiltonian
$\widetilde{H}_{\text{q}}$ is (1) the total Pauli weight of the original
$H_{\text{q}}$, plus (2) the difference between the new and old $Z$–matrix
counts of the terms in $\Lambda_{\text{non-loc}}$ after multiplication by
stabilisers, plus (3) the cost of extra operations on the auxiliary qubits
from making the $\kappa^{h}$ adjustments to terms in
$\Lambda\backslash\Lambda_{\text{non-loc}}$. That is,

Total Pauli weight of $\widetilde{H}_{\text{q}}$ (106)
$\displaystyle\qquad=\text{(1) Total Pauli weight of $H_{\text{q}}$}$
$\displaystyle\qquad\quad+\text{(2) difference in $Z$--matrix count of
$\widetilde{H}_{\text{q}}$ and $H_{\text{q}}$}$
$\displaystyle\qquad\quad+\text{(3) number of adjusted terms in
$\widetilde{H}_{\text{q}}$ that are}$ not multiplied by stabilisers

Figure 15: Average Pauli weights $APV(f)$ of enumeration schemes $f$ on
$N$$\times$$N$ lattices. Random $f$ is a randomly–generated enumeration
scheme.

Begin by only considering the effects of the first stabiliser,
$(p_{1})_{\text{dat}}\otimes\left(Z\otimes\mathds{1}\right)_{\text{aux}}$. For
(1), recall from Equation 58 that the total Pauli weight of the square lattice
qubit Hamiltonian $H_{\text{q}}$ is $C^{1}(f_{\mathrm{M}})+2N(N-1)$.

For (2): First determine which hopping terms should be multiplied by
stabilisers. In the original Hamiltonian $H_{\text{q}}$, a term $h\in\Lambda$
between vertices $\alpha$ and $\beta$ of $G_{\mathrm{F}}$ has Pauli weight
$|f_{\mathrm{M}}(\alpha)-f_{\mathrm{M}}(\beta)|+1$; as hopping terms consist
of a string of $Z$ matrices between a pair of $X$ or $Y$ matrices, the total
number of $Z$ matrices in such a term is then

$\displaystyle\\#(Z\text{ matrices in
$h$})=|f_{\mathrm{M}}(\alpha)-f_{\mathrm{M}}(\beta)|-1\,.$ (107)

Referring to the region labels $A,B,...,D$ in Figure 27, it is clear that all
of the lengthy hopping terms between vertices on the $AD$–interface will have
less $Z$ matrices after multiplication by the stabiliser
$(p_{1})_{\text{dat}}\otimes\left(Z\otimes\mathds{1}\right)_{\text{aux}}$.
Using the labels from Figure 27 in Equation 107, the original number of $Z$
matrices in each of these terms is then

$\displaystyle\\#(Z\text{ matrices in each row of $AD$, {before}})$ (108)
$\displaystyle\qquad\qquad\qquad=Nx-x(x-1)-1\,.$

By inspection, the topmost hopping term across the $AD$–interface after
multiplication by
$(p_{1})_{\text{dat}}\otimes\left(Z\otimes\mathds{1}\right)_{\text{aux}}$ will
consist of a single $Z$ matrix on the first auxiliary qubit. For the hopping
terms across the $AD$–interface in the $j$th row beneath the top row, there
will be $2j$ $Z$ matrices after multiplication by
$(p_{1})_{\text{dat}}\otimes\left(Z\otimes\mathds{1}\right)_{\text{aux}}$,
including the one on the auxiliary qubit. Thus, the correction term for the
$AD$–interface is

$\displaystyle\Delta[\\#(\text{$Z$ matrices in $AD$})]$ (109)
$\displaystyle\qquad\qquad=1-\big{(}Nx-(x(x-1))\big{)}$
$\displaystyle\qquad\qquad\quad+\sum_{j=1}^{x-1}\bigg{(}2j-\big{(}Nx-(x(x-1))\big{)}\bigg{)}\,.$

Hopping terms across the $BD$–interface and the first row of the
$CD$–interface may benefit from multiplication by
$(p_{1})_{\text{dat}}\otimes(Z\otimes\mathds{1})_{\text{aux}}$. Call the
collection of these hopping terms the $(BC)D$–interface, and consider its
$i$th row: once again, the labels from Figure 27 in Equation 107 yield

$\displaystyle\\#(Z\text{ matrices in $i$th row of $(BC)D$, {before}})$ (110)
$\displaystyle\qquad\qquad=Nx+x-1+i-(x^{2}+ix-1)-1\,.$

By inspection, these terms will have $(2+i)x+i-2$ $Z$ matrices after
multiplication by the stabiliser
$(p_{1})_{\text{dat}}\otimes\left(Z\otimes\mathds{1}\right)_{\text{aux}}$,
including the $Z$ matrix on the auxiliary qubit.

As Figure 12 shows, if $x$ is large enough then it is possible that a small
number of vertical hopping terms within the region $C$ will benefit from
stabiliser multiplication as well. Although this reduces the average Pauli
weight of the qubit Hamiltonian even further, its effect is negligible
compared to the savings across the $(BC)D$–interface, and we omit it for
simplicity. The correction term for the $(BC)D$–interface is thus

$\displaystyle\Delta[\\#(\text{$Z$ matrices in $(BC)D$})]$ (111)
$\displaystyle\qquad\qquad=\sum_{i=1}^{K}\bigg{(}(2+i)x+i-2$
$\displaystyle\qquad\qquad\qquad-\big{(}Nx+x-1+i-(x^{2}+ix-1)-1\big{)}\bigg{)}\,.$

The value $K$ depends on the size of $x$, as Figure 12 illustrates. From a
naïve inspection of Equation 111, the $i$th row of the $(BC)D$–interface
hopping terms will observe a reduction in $Z$–matrix count after stabiliser
multiplication as long as

$\displaystyle(2+i)x+i-2$ $\displaystyle<Nx+x+i-(x^{2}+ix+1)$ (112)
$\displaystyle i$ $\displaystyle<\frac{1}{2x}+\frac{N-x-1}{2}$ (113)
$\displaystyle\leq\frac{N-x-1}{2}\,.$ (114)

This might tempt us to set $K=\left\lfloor(N-x-1)/2\right\rfloor$. However,
there are $N-2x+1$ rows in the $(BC)D$–interface, so the expression in
Equation 111 is only valid if

$\displaystyle
K=\min\left\\{\left\lfloor\frac{N-x-1}{2}\right\rfloor,\,N-2x+1\right\\}\,.$
(115)

These two values are equal if $x=\lfloor(N+4)/3\rfloor$. Figure 12 shows the
two scenarios where $x$ is above or below this threshold value.

For (3), note that we must adjust all of the hopping terms $h$ that do not
commute with $p_{1}$ by multiplication by $\kappa^{h}$, which is a single $X$
matrix targeting the first auxiliary qubit. However, in (2) we have already
accounted for the cost of an extra auxiliary $Z$ matrix on each of the terms
in the $AD$– and $BD$–interfaces that benefited from stabiliser
multiplication. This $Z$ matrix will become $(-Y)$ upon prior adjustment by
$\kappa^{h}$ (multiplication by $X$). We therefore need only count hopping
terms that partially overlap with $p_{1}$: by inspection of Figure 12, the
total number of such terms is

$\displaystyle\\#(\text{$X$ matrices from correction to terms})$ (116)
$\displaystyle\quad=2x-1+(N-x-K-1)$ $\displaystyle\quad=N+x-K-1\,.$

As the Mitchison–Durbin pattern is symmetric, the same rules apply when
considering the effects of the second stabiliser,
$(p_{2})_{\text{dat}}\otimes\left(\mathds{1}\otimes Z\right)_{\text{aux}}$. We
can now finally substitute these values into Equation 106 and express the
total Pauli weight of $\widetilde{H}_{\text{q}}$. Note that the factor of 2 in
Equation 117 takes into account both stabilisers:

$\displaystyle\text{Total Pauli weight of }\widetilde{H}_{\text{q}}$ (117)
$\displaystyle\quad=C^{1}(f_{\mathrm{M}})+2N(N-1)$
$\displaystyle\quad\quad+2\bigg{(}\left(1-(Nx-x(x-1)-1\right)$
$\displaystyle\qquad\qquad+\sum_{j=1}^{x-1}\big{(}2j-(Nx-x(x-1))\big{)}$
$\displaystyle\qquad\qquad+\sum_{i=1}^{K}\big{(}\left((2+i)x+i-2\right)$
$\displaystyle\qquad\qquad\qquad-\left(Nx+x+i-(x^{2}+ix+1)\right)\big{)}$
$\displaystyle\qquad\qquad+N+x-K-1\bigg{)}\,.$

For example, using the value for $x$ of $\approx 0.29N$ from the original
Mitchison–Durbin pattern $f_{\text{M}}$ and dividing the total Pauli weight by
the number of hopping terms, $2N(N-1)$, the average Pauli weight of our
auxiliary qubit mapping, here nicknamed ‘$f_{\dot{h}^{\prime}+2}$’, produces a
dramatic improvement:

$\displaystyle APV\left(f_{\dot{h}^{\prime}+2}\big{|}_{x\approx 0.29N}\right)$
$\displaystyle\approx 0.33N+1.77$ (118)

However, in the scenario $x\leq\lfloor(N+4)/3\rfloor$ with
$K=\lfloor(N-x-1)/2\rfloor$, the expression in Equation 117 is actually
minimised at the extremum $x=\lfloor(N+4)/3\rfloor$. The average Pauli weight
for large $N$ in this instance is:

$\displaystyle
APV\left(f_{\dot{h}^{\prime}+2}\Big{|}_{x=\left\lfloor\frac{N+4}{3}\right\rfloor}\right)$
$\displaystyle\approx\frac{26}{81}N+\frac{289}{162}$ (119)
$\displaystyle=0.32N+1.78\,.$ (120)

But there is a better value yet for $x$: in the other scenario, where
$x>\lfloor(N+4)/3\rfloor$, the value of $K$ is $N-2x+1$. An approximately
optimal value for $x$ to minimise the total Pauli weight in this instance is

$\displaystyle x$
$\displaystyle=\frac{1}{8}\left(7+N+\sqrt{\frac{15N^{2}-18N-53}{3}}\right)$
(121) $\displaystyle\approx\frac{1}{8}\left(1+\sqrt{5}\right)N$ (122)
$\displaystyle=0.40N\,,$ (123)

which is the result of replacing floor brackets with normal parentheses in
Equation 117. It is for this reason that we define our new pattern
$f_{\mathrm{M}+2}$ to have $x$ equal to the rounded value of that in Equation
121, i.e. $x\approx 0.40N$. For large $N$, this yields an average Pauli weight
of

$\displaystyle APV\left(f_{\mathrm{M}+2}\right)$
$\displaystyle=APV\left(f_{\dot{h}^{\prime}+2}\big{|}_{x\approx 0.40N}\right)$
(124) $\displaystyle\approx 0.31N+1.68\,.$ (125)

Comparing our auxiliary qubit mapping to the S–pattern of [17] and the
Mitchison–Durbin pattern of Theorem 1,

$\displaystyle\lim_{N\rightarrow\infty}\frac{APV(f_{\mathrm{M}+2})}{APV(f_{\text{S}})}$
$\displaystyle\approx 0.62$ (126)
$\displaystyle\lim_{N\rightarrow\infty}\frac{APV(f_{\mathrm{M}+2})}{APV(f_{\text{M}})}$
$\displaystyle\approx 0.72\,,$ (127)

yielding a 37.9% improvement over the Z– and S–patterns.

Figure 15 shows the average Pauli weights of fermion–qubit mappings
$\overline{\text{JW}}_{f}$ using all the enumeration schemes $f$ for the
$N$$\times$$N$ fermionic lattice discussed in this paper. This analysis does
not include the cost of initialising the stabiliser state
$\ket{\smash{\widetilde{\psi}}}_{\text{dat,aux}}$ via the unitary operation
$V$. It is possible to implement $V$ using fewer gates than the circuit in
Figure 13 at the cost of more ancilla qubits [55]. However, even adding the
cost of the circuit in Figure 13, which is $4(xN-x^{2}+(x-1))+2$ CNOTs, to
Equation 117 has negligible effects on the calculations in this section. The
value $x\approx 0.40N$ in Equation 123 still holds.

Figure 14 concludes by demonstrating the advantage of our auxiliary qubit
mapping $\overline{\text{JW}}_{\text{M}+2}$ for simulating fermionic
Hamiltonians $H_{\text{fermion}}$ with $G_{\text{F}}$ equal to the 6$\times$6
lattice. When $N=6$ and $x=3$, the qubit Hamiltonian
$\widetilde{H}_{\text{q}}$ has a total Pauli weight of 222. (This value is
slightly different than direct substitution into Equation 117, because the
6$\times$6 lattice has no region $D$ and some hopping terms benefit from
multiplication by both stabilisers.) Using $\overline{\text{JW}}_{\text{M}+2}$
produces a qubit Hamiltonian $\widetilde{H}_{\text{q}}$ with an average Pauli
weight of $\frac{222}{60}=3.70$, which is a 14.6% improvement on the result
$\frac{260}{60}=4.33$ of
$\overline{\text{JW}}_{f_{\text{M}}}(H_{\text{fermion}})$, which is optimal
for $n$–mode to $n$–qubit mappings. It is also a 17.8% improvement on the
average of $\frac{270}{60}=4.5$ for
$\overline{\text{JW}}_{f_{\text{Z}}}(H_{\text{fermion}})$ and
$\overline{\text{JW}}_{f_{\text{S}}}(H_{\text{fermion}})$.

##  V Discussion

Figure 16: Fermionic enumeration techniques can influence the layout of Pauli
strings on nonlinear qubit architectures. Figure 17: When working with
elaborate qubit architectures such as the 2D lattice, the fermionic
enumeration scheme need not follow the underlying qubit connectivity. This
figure highlights the freedom to choose any scheme to enumerate fermions,
yielding averages for the Pauli weights independent of the actual qubit
connectivity.

###  V.1 Summary of results

By identifying the inherent place of fermion enumeration schemes in all
$n$–fermionic mode to $n$–qubit mappings, we identified novel methods for
creating new and improved mappings, demonstrating two main results.

The first (Section III): when used as enumeration schemes for fermionic modes
in Jordan–Wigner transformations of a broad class of $n$–mode problem
fermionic Hamiltonians, solutions to well–known graph problems can minimise
practical cost functions of the qubit Hamiltonians. Theorem 1 illustrates the
effect for fermionic Hamiltonians with hopping terms forming a square lattice
of interactions, and identifies an $n$–qubit Jordan–Wigner transformation that
uses the Mitchison–Durbing pattern to produce a qubit Hamiltonian with the
minimum possible average Pauli weight. This is an improvement of 13.9%
compared to previous methods using the S–pattern. Even for fermionic
interaction graphs without known edgesum solutions, classical heuristic
techniques may provide enumeration schemes that drastically reduce the average
Pauli weight, as in the case of cellular arrangements in Section III.5.

The second result combines our fermionic enumeration technique with the common
strategy of employing auxiliary qubits to further preserve locality of
interactions. In Section IV, we provide an improved Jordan–Wigner
transformation for fermionic Hamiltonians with square–lattice interactions.
Unlike all other auxiliary qubit mappings in the literature, this mapping
requires only two auxiliary qubits, regardless of the number of fermionic
modes $n$, and thus can be compared with the results of Theorem 1, which it
improves upon by reducing the average Pauli weight by 37.9% compared to
previous methods using the S–pattern.

Summarising our results, Table 1 compares Verstraete and Cirac’s S–pattern to
our optimal ancilla–free mapping using $f_{\mathrm{M}}$, and our low–ancilla
mapping $f_{\mathrm{M}+2}$. Auxiliary qubit mappings with scalable numbers of
ancilla qubits are included for comparison.

###  V.2 Nonlinear qubit architectures and qubit routing

Most results involving the Jordan–Wigner and Bravyi–Kitaev transformations
rely on qubits with connectivity constraints. In particular, Verstraete and
Cirac [17] pursue a Jordan–Wigner type auxiliary qubit mapping to transform a
local Hamiltonian on a fermionic lattice to a local Hamiltonian on a qubit
lattice. Subsequent works have followed suit, usually working towards
preserving geometric locality between the fermions and qubits, where the
assumption is that the qubit architecture is the same as the fermionic graph
[35, 54, 30, 34].

Fermionic enumeration schemes influence the distribution of quantum gates
throughout nonlinear qubit architectures. To see this, consider decomposing a
fermion–qubit mapping from a fermionic graph $G_{\mathrm{F}}$ to a qubit graph
$G_{\mathrm{Q}}$ into two components: 1) the enumeration of the fermionic
modes, which projects the fermionic connectivity graph $G_{\mathrm{F}}$ onto a
1D array of qubits, and then 2) the embedding of the 1D array of qubits into
the qubit architecture $G_{\mathrm{Q}}$. Figure 16 visualises the distinction
between the two processes.

Verstraete and Cirac’s approach is to introduce the S–pattern to enumerate the
fermions, and to use an S–pattern embedding to weave Pauli strings into the
qubit lattice, as in the top row of Figure 17. In this work we emphasise that
these are two distinct processes, and the choice of fermionic enumeration
scheme can be done in an entirely separate way to the method of the embedding
process. Indeed, as the second row of Figure 17 shows, the path of the
fermionic enumeration scheme need not follow the connectivity of the qubit
architecture at all to provide a valid mapping.

As mentioned in Section VI.2.1, it is possible to conceive of metrics for
qubit Hamiltonians that depend on qubit architectures. For example, the qubit
routing problem concerns the distribution of Pauli strings on a nonlinear
qubit connectivity $G_{\mathrm{Q}}$ [56]. The cost function for qubit routing
should penalise strings of Pauli gates that spread through $G_{\mathrm{Q}}$
sparsely, and reward clustered Pauli strings. This poses a different problem
to minimising the average Pauli weight of the qubit Hamiltonian, as the
optimal enumeration scheme for the fermion–qubit mapping will need to cluster
the Pauli strings of the qubit Hamiltonian while also minimising their weight.
We expect that finding optimal enumeration schemes for cost functions that
incorporate qubit architecture is a much more difficult family of problems
than simply minimising a cost function of the Pauli weight as we have done
here.

###  V.3 Future work: optimal enumeration schemes for general fermion–qubit
mappings

Sections III and IV only concerned Jordan–Wigner transformations of the form
in Definition 2. A more general class of mappings to search over would be the
general Jordan–Wigner transformation in Example 1. The potential of using
enumeration schemes as a method to define optimal Bravyi–Kitaev or
ternary–tree mappings of the forms in Example 2 and 3 is completely unexplored
and the subject of our upcoming work [42].

Acknowledgements MC is funded by Cambridge Australia Allen and DAMTP
Scholarship and the Royal Society PhD studentship. SS acknowledges support
from the Royal Society University Research Fellowship scheme.

##  VI Appendix

###  VI.1 Edgesum of the S–pattern

######  Lemma 2.

On an $N$$\times$$N$ lattice, the S–pattern $f_{\mathrm{S}}$ has edgesum
$C^{1}(f_{\mathrm{S}})=N^{3}-N$.

###### Proof.

Figure 18 displays the S–pattern enumeration procedure for an $N$$\times$$N$
square lattice, as well as the differences between adjacent vertices’ indices.

Regardless of whether $N$ is odd or even, the cost is thus

$\displaystyle C^{1}(f_{\mathrm{S}})$ $\displaystyle=(N-1)\times\text{no. of
rows}$ (128) $\displaystyle\quad+\sum_{i=1}^{N}(2i-1)\times(\text{no. of
rows}-1)$ $\displaystyle=N^{2}-N+(N-1)(N(N+1)-N)$ (129)
$\displaystyle=N^{2}-N-N^{2}+N+N(N^{2}-1)$ (130)
$\displaystyle=N^{3}-N\,.\qed$ (131)

The average Pauli weight for the S–pattern on a square lattice is then

$\displaystyle APV(f_{\mathrm{S}})$
$\displaystyle=\frac{C^{1}(f_{\mathrm{S}})}{|E|}+1=\frac{N^{3}-N}{2N(N-1)}+1$
(132) $\displaystyle=\frac{1}{2}N+\frac{3}{2}.$ (133)

Figure 18: Top: S–pattern enumeration on the $N$$\times$$N$ square lattice.
Bottom: Differences between vertex labels using the S–pattern enumeration,
with row totals on the far right.

###  VI.2 Proof of Theorem 1

This section contains a more elaborate version of the original proof [31] that
the Mitchison–Durbin pattern $f_{\mathrm{M}}$ solves the edgesum problem for
an $N$$\times{}$$N$ lattice. Figure 19 chronicles the proof, which starts with
an arbitrary enumeration scheme for the $N^{2}$ vertices before performing
five sequential modifications (Proposition 2 and Lemmas 3–6) which exhaust all
possible ways to reduce the edgesum, to give the Mitchison–Durbin pattern
$f_{\mathrm{M}}$.

The edgesum problem is the minimum–$p$–sum problem described in Section II.7
with $p=1$. The first part of the proof, Proposition 2, holds for all $p\geq
1$; the rest of the proof concerns only the case $p=1$.

Given a graph $G=(V,E)$ and an enumeration scheme
$f:V\rightarrow\\{0,1,\dots,N^{2}-1\\}$ for $G$, the cost function $C^{p}(f)$
for the minimum $p$–sum problem is

$\displaystyle\left(C^{p}(f)\right)^{p}$
$\displaystyle=\sum_{(\alpha,\beta)\in E}|f(\alpha)-f(\beta)|^{p}\,.$ (134)

In the case that $G$ is a square lattice, the edge set $E$ consists of pairs
of horizontally and vertically adjacent vertices, leading to horizontal and
vertical contributions:

$\displaystyle\left(C^{p}(f)\right)^{p}$ (135)
$\displaystyle=\sum_{\begin{subarray}{c}(\alpha,\beta)\in E;\\\
\text{horizontally
adjacent}\end{subarray}}|f(\alpha)-f(\beta)|^{p}+\sum_{\begin{subarray}{c}(\alpha,\beta)\in
E;\\\ \text{vertically adjacent}\end{subarray}}|f(\alpha)-f(\beta)|^{p}\,.$

Figure 19: Overview of the proof that the Mitchison–Durbin pattern is a
solution to the edgesum problem for the square lattice.

######  Definition 6.

Let $G=(V,E)$ be the $N$$\times$$N$ square lattice, and let $f$ be an
enumeration scheme for $G$. Say $f$ is horizontally ordered if, for any vertex
$\alpha\in V$, $f(\beta)>f(\alpha)$ for all vertices $\beta$ to the right of
$\alpha$, and say $f$ is vertically ordered if $f(\beta)>f(\alpha)$ for all
vertices $\beta$ below $\alpha$.

Figure 20: Swapping the labels of vertices in a row of the $N$$\times$$N$
square lattice as part of the process of constructing a horizontally ordered
enumeration scheme. Figure 21: Swapping vertex labels within a row will affect
some of the contributions to the $p$–sum of the enumeration scheme from
vertically adjacent vertices. Figure 22: Illustration of the contradiction
that would arise if a vertical ordering $f_{hv}$ of a horizontally ordered
enumeration scheme $f_{h}$ were not itself horizontally ordered.

######  Proposition 2.

Let $G=(V,E)$ be the $N$$\times$$N$ square lattice, let $p\geq 1$, and let $f$
be an enumeration scheme $f$ for $G$. Then there exists a horizontally and
vertically ordered enumeration scheme $g$ such that $C^{p}(g)\leq C^{p}(f)$.

###### Proof.

From $f$, construct the enumeration scheme $f_{h}$ by permuting each row of
the lattice so that vertex index values ascending from left to right. Call
$f_{h}$ the horizontal ordering of $f$. Similarly, construct $f_{hv}$ from
$f_{h}$ by permuting vertex labels under $f_{h}$ within each column to
increase from top to bottom down. Call $f_{hv}$ the vertical ordering of
$f_{h}$. We will prove Proposition 2 via the statements S1 and S2 below:

  1. S1.

$C^{p}(f_{h})\leq C^{p}(f)$.

  2. S2.

The enumeration scheme $f_{hv}$ is horizontally ordered.

To prove S1, first consider the impact of horizontal ordering on the
horizontal contributions to $C^{p}(f)$ in Equation 135.

Claim: The horizontal contributions to $C^{p}(f_{h})$ are less than or equal
to the horizontal contributions to $C^{p}(f)$.

Proof: (See Figure 20.) Suppose $f$ is not horizontally ordered, and so there
is a row of the lattice consisting of vertices
$\alpha_{0},\alpha_{1},\dots,\alpha_{N-1}$ such that
$f(\alpha_{i})>f(\alpha_{i+1})$ for some $0<i\leq N-1$. The horizontal
contributions to $C^{p}(f)$ from this row are

$\displaystyle|f(\alpha_{0})-f(\alpha_{1})|^{p}+\dots$
$\displaystyle+|f(\alpha_{i-1})-f(\alpha_{i})|^{p}$ (136)
$\displaystyle+|f(\alpha_{i})-f(\alpha_{i+1})|^{p}$ $\displaystyle+\dots$
$\displaystyle+|f(\alpha_{N-2})-f(\alpha_{N-1})|^{p}\,.$

Consider the enumeration scheme $\tilde{f}$ that is identical to $f$ save that
$\tilde{f}(\alpha_{i})=f(\alpha_{i+1})$ and
$\tilde{f}(\alpha_{i+1})=f(\alpha_{i})$, i.e. $\tilde{f}$ swaps the labels on
vertices $\alpha_{i}$ and $\alpha_{i+1}$ so that
$\tilde{f}(\alpha_{i})<\tilde{f}(\alpha_{i+1})$. Thus, $\tilde{f}$ is at least
‘partially’ horizontally ordered, moreso than $f$. The horizontal
contributions to $C^{p}(\tilde{f})$ from this row are:

$\displaystyle|\tilde{f}(\alpha_{0})-\tilde{f}(\alpha_{1})|^{p}+\dots$
$\displaystyle+|\tilde{f}(\alpha_{i-1})-\tilde{f}(\alpha_{i+1})|^{p}$ (137)
$\displaystyle+|\tilde{f}(\alpha_{i+1})-\tilde{f}(\alpha_{i})|^{p}$
$\displaystyle+\dots$
$\displaystyle+|\tilde{f}(\alpha_{N-2})-\tilde{f}(\alpha_{N-1})|^{p}\,.$

The difference between the horizontal contributions to $C^{p}(f)$ and to
$C^{p}(\tilde{f})$ is thus

$\displaystyle|\tilde{f}(\alpha_{i+1})-\tilde{f}(\alpha_{i})|^{p}+|\tilde{f}(\alpha_{i-1})-\tilde{f}(\alpha_{i+1})|^{p}$
(138)
$\displaystyle\qquad-|f(\alpha_{i})-f(\alpha_{i+1})|^{p}-|f(\alpha_{i-1})-f(\alpha_{i})|^{p}$
$\displaystyle=|\tilde{f}(\alpha_{i-1})-\tilde{f}(\alpha_{i+1})|^{p}-|f(\alpha_{i-1})-f(\alpha_{i})|^{p}$
(139)
$\displaystyle=|f(\alpha_{i-1})-f(\alpha_{i})|^{p}-|f(\alpha_{i-1})-f(\alpha_{i})|^{p}$
(140) $\displaystyle<0\,,$

since $p\geq 1$ and $f(\alpha_{i-1})<f(\alpha_{i+1})<f(\alpha_{i})$.

To construct $f_{h}$ is to perform as many swaps of the above form
(transforming $f$ into $\tilde{f}$) as is necessary in order to label all $N$
vertices in each row of the lattice in ascending order. Thus, the horizontal
contributions to $C^{p}(f_{h})$ are less than the horizontal contributions to
$C^{p}(f)$, with equality if and only if $f=f_{h}$. $\blacksquare$

To finish proving S1, consider the impact of horizontal ordering on the
vertical contributions to $C^{p}(f)$ in Equation 135.

Claim: The vertical contributions to $C^{p}(f_{h})$ are less than or equal to
the vertical contributions to $C^{p}(f)$.

Proof: (See Figure 21.) Suppose that $f$ is not horizontally ordered, and that
we are in the process of constructing $f_{h}$ from $f$ by re-ordering vertex
labels row-by-row. Then there is a row of the lattice consisting of vertices
$\beta_{0},\beta_{1},\dots,\beta_{N-1}$ such that
$f(\beta_{i})>f(\beta_{i+1})$ for some $i$. Let $\alpha_{i}$ and
$\alpha_{i+1}$ be the vertices directly above vertices $\beta_{i}$ and
$\beta_{i+1}$, respectively; thus $f(\alpha_{i})<f(\alpha_{i+1})$.

The vertical contributions to $C^{p}(f)$ from these four vertices is

$\displaystyle|f(\beta_{i})-f(\alpha_{i})|^{p}+|f(\beta_{i+1})-f(\alpha_{i+1})|^{p}\,.$
(141)

Because $f(\alpha_{i})<f(\alpha_{i+1})$ and $f(\beta_{i})>f(\beta_{i+1})$, the
values $|f(\alpha_{i})-f(\beta_{i})|^{p}$ and
$|f(\alpha_{i+1})-f(\beta_{i+1})|^{p}$ in Equation 141 are unequal, with the
latter being less than the former.

Consider the enumeration scheme $\tilde{f}$ that arises by swapping the labels
of vertices $\beta_{i}$ and $\beta_{i+1}$, so
$\tilde{f}(\beta_{i})=f(\beta_{i+1})$ and
$\tilde{f}(\beta_{i+1})=f(\beta_{i})$. The vertical contributions to
$C^{p}(\tilde{f})$ from the four vertices is

$\displaystyle|f(\alpha_{i})-f(\beta_{i+1})|^{p}+|f(\alpha_{i+1})-f(\beta_{i})|^{p}\,.$
(142)

Note that for $p>1$, if $a+b$ is a constant value then $a^{p}+b^{p}$ reduces
in value the closer in value $a$ is to $b$. Therefore, the vertical
contributions to $C^{p}(\tilde{f})$ in Equation 142 are less than the vertical
contributions to $C^{p}(f)$ in Equation 141. If $p=1$, the contributions are
equal. This proves the claim, and furthermore S1. $\blacksquare$

To prove S2, consider the horizontally ordered enumeration scheme $f_{h}$, as
in Figure 22. Suppose that $f_{h}$ is not vertically ordered, and let $f_{hv}$
be the vertical ordering of $f_{h}$. It remains to show that $f_{hv}$ is
horizontally ordered. Suppose that it is not horizontally ordered: thus, there
exists $j\in\\{0,\dots,N-1\\}$ such that the $j$th row of the lattice contains
vertices $\alpha_{j}$, $\beta_{j}$, with $\beta_{j}$ to the right of
$\alpha_{j}$ and $f_{hv}(\alpha_{j})>f_{hv}(\beta_{j})$.

Denote vertices in the column with $\beta_{j}$ by
$\beta_{0},\dots,\beta_{N-1}$, and similarly define the vertices
$\alpha_{0},\dots,\alpha_{N-1}$ as those sharing the column of $\alpha_{j}$.
Because $f_{hv}$ is vertically ordered, then
$f_{hv}(\alpha_{j})>f_{hv}(\alpha_{k})$ and
$f_{hv}(\beta_{j})>f_{hv}(\beta_{k})$ for all $0\leq k\leq j-1$. As
$f_{hv}(\alpha_{j})>f_{hv}(\beta_{j})$, then under $f_{hv}$, both the $j-1$
vertices above $\alpha_{j}$ and the $j-1$ vertices above $\beta_{j}$ have
labels less than $f_{hv}(\beta_{j})$. Since all that separates $f_{h}$ and
$f_{hv}$ is a permutation of vertex labels that fixes the labels within
columns of the lattice, then there should be exactly $j-1$ vertices with
labels less than $f_{hv}(\beta_{j})$ in both the
$\alpha_{0},\dots,\alpha_{N-1}$ and $\beta_{0},\dots,\beta_{N-1}$ columns of
the lattice under enumeration scheme $f_{h}$ as well.

Because $f_{h}$ is horizontally ordered, $f_{h}(\alpha_{j})<f_{h}(\beta_{j})$.
Therefore at least one of $\alpha_{j}$ and $\beta_{j}$ will have a different
label under $f_{h}$ than under $f_{hv}$. Suppose, without loss of generality,
that the vertex $\beta_{j}$ satisfies this: that $f_{h}(\beta_{j})\neq
f_{hv}(\beta_{j})$ and thus there exists some $i\in\\{0,\dots,N-1\\}$ such
that $f_{h}(\beta_{i})=f_{hv}(\beta_{j})$. Under $f_{h}$, there are $j-1$
vertices in the $\beta_{0},\dots,\beta_{N-1}$ column with label less than
$f_{hv}(\beta_{j})$, as was the case under $f_{hv}$. However, consider the
vertices in the $\alpha_{0},\dots,\alpha_{N-1}$ column. Each vertex
$\alpha_{k}$ to the left of a vertex $\beta_{k}$ with
$f_{h}(\beta_{k})<f_{hv}(\beta_{j})$ also satisfies
$f_{h}(\alpha_{k})<f_{hv}(\beta_{j})$ due to horizontal ordering; there are
$j-1$ of these vertices. Distinct from these vertices, there is also the
vertex $\alpha_{i}$ to the left of $\beta_{i}$ which must also have
$f_{h}(\alpha_{i})<f_{h}(\beta_{i})=f_{hv}(\beta_{j})$. This is the
contradiction.

This proves S2 and hence Proposition 2. ∎

Section III.6 discusses the case $p>1$. Henceforth, this proof of Theorem 1
only concerns the case $p=1$.

Let $G=(V,E)$ be the $N$$\times$$N$ square lattice. As a result of Proposition
2, we need only consider horizontally and vertically ordered enumeration
schemes in the search for the solution to the edgesum problem for $G$. Let
$f_{hv}$ be the horizontal and vertical ordering of a vertex enumeration
scheme $f$ for $G$. Let $\alpha_{i,j}$ denote the vertex of $G$ in the $i$th
row and $j$th column, using matrix index notation so that the top–left vertex
is $\alpha_{1,1}$. Then the edgesum of $f_{hv}$ is

$\displaystyle C^{1}(f_{hv})$
$\displaystyle=\sum_{i,j=1}^{N-1}\big{(}f_{hv}(\alpha_{i+1,j})-f_{hv}(\alpha_{i,j})$
(143)
$\displaystyle\qquad\qquad+f_{hv}(\alpha_{i,j+1})-f_{hv}(\alpha_{i,j})\big{)}$
$\displaystyle=2f_{hv}(\alpha_{N,N})+\sum_{i=2}^{N-1}f_{hv}(\alpha_{i,N})$
(144)
$\displaystyle\quad\quad\quad+\sum_{j=2}^{N-1}f_{hv}(\alpha_{N,j})-\sum_{i=2}^{N-1}f_{hv}(\alpha_{i,1})$
$\displaystyle\quad\quad\quad-\sum_{j=2}^{N-1}f_{hv}(\alpha_{1,j})-2f_{hv}(\alpha_{1,1})$
$\displaystyle=\sum_{\alpha\in V_{\mathrm{b}}}f_{hv}(\alpha)+\sum_{\alpha\in
V_{\mathrm{r}}}f_{hv}(\alpha)$ (145)
$\displaystyle\quad\quad\quad-\bigg{(}\sum_{\alpha\in
V_{\mathrm{l}}}f_{hv}(\alpha)+\sum_{\alpha\in
V_{\mathrm{t}}}f_{hv}(\alpha)\bigg{)}\,,$

where $V_{\mathrm{l}}$, $V_{\mathrm{r}}$, $V_{\mathrm{t}}$, $V_{\mathrm{b}}$
are the vertices in the left column, right column, top row and bottom row of
the square lattice, respectively. This result greatly simplifies the
calculation of $C^{1}(f_{hv})$ for the square lattice.

Due to horizontal and vertical ordering, $f_{hv}(\alpha_{1,1})=0$ and
$f_{hv}(\alpha_{N,N})=N^{2}-1$. Without loss of generality, assume that
$f_{hv}(\alpha_{N,1})<f_{hv}(\alpha_{1,N})$. As detailed in Figure 19, define
$U_{f}$ to be the set of vertices with labels between $f_{hv}(\alpha_{1,1})=0$
and $f_{hv}(\alpha_{N,1})$, and let $V_{f}$ be the set of vertices with labels
between $f_{hv}(\alpha_{N,1})$ and $f_{hv}(\alpha_{N,N})=N^{2}-1$. Define
$S(U_{f})$ and $S(V_{f})$ to be the sums of the labels of vertices on the
boundary of the lattice in the regions $U_{f}$ and $V_{f}$, respectively, and
define $S(\overline{U_{f}\cap V_{f}})$ to be the difference between the sum of
labels of vertices in $\overline{U_{f}\cap V_{f}}$ in the bottom and top rows
of the lattice. By Equation 145, these quantities completely determine the
edgesum:

$\displaystyle C^{1}(f_{hv})=S(V_{f})+S(\overline{U_{f}\cap
V_{f}})-S(U_{f})\,.$ (146)

The task now is to identify an improved enumeration scheme $f^{\prime}$ with
the least edgesum of all schemes $g$ that have $U_{g}=U_{f}$ and
$V_{g}=V_{f}$. That is, find an enumeration scheme $f^{\prime}$ such that

$\displaystyle f^{\prime}$
$\displaystyle=\operatorname*{arg\,min}_{\begin{subarray}{c}\text{enumerations
}g\\\ U_{g}=U_{f},V_{g}=V_{f}\end{subarray}}C^{1}(g)$ (147)
$\displaystyle=\operatorname*{arg\,min}_{\begin{subarray}{c}\text{enumerations
}g\\\
U_{g}=U_{f},V_{g}=V_{f}\end{subarray}}\bigg{(}S(V_{g})+S(\overline{U_{g}\cap
V_{g}})-S(U_{g})\bigg{)}\,.$ (148)

Note that if $f$ is such that $U_{f}$ and $V_{f}$ are the same regions as
those yielded by a solution to the edgesum problem, then any $f^{\prime}$
satisfying Equation 148 is a solution to the edgesum problem. Lemma 3 details
how to construct an $f^{\prime}$ given $f$; using this result, Lemmas 4–6
detail how to set $f$ such that this $f^{\prime}$ is a solution to the edgesum
problem, completing the proof.

######  Lemma 3.

Let $G=(V,E)$ be the $N$$\times$$N$ square lattice, with $\alpha_{i,j}\in V$
denoting the vertex in the $i$th row and $j$th column. Let $f_{hv}$ be the
horizontal and vertical ordering of an enumeration scheme $f$ for $G$,
dividing the lattice into regions $U_{f}$, $V_{f}$ and $\overline{U_{f}\cap
V_{f}}$ as defined above. Then, the steps below construct a horizontally and
vertically ordered enumeration scheme $f^{\prime}$ that satisfies Equation
148. Note that while $U_{f^{\prime}}=U_{f}$, $S(U_{f^{\prime}})$ may not be
equal to $S(U_{f})$ and so on.

  1. 1.

To maximise $S(U_{f^{\prime}})$:
Rule A: starting at the beginning of a row $\alpha_{1,j}$ (resp. column
$\alpha_{i,1}$), the enumeration scheme $f^{\prime}$ proceeds rightwards along
the row (resp. downwards along the column) into the interior of $U_{f}$ as far
as possible without violating horizontal and vertical ordering.