# Layering and subpool exploration for adaptive Variational Quantum
Eigensolvers:
Reducing circuit depth, runtime, and susceptibility to noise

Christopher K. Long  Hitachi Cambridge Laboratory, J. J. Thomson Ave.,
Cambridge, CB3 0HE, United Kingdom  Cavendish Laboratory, Department of
Physics, University of Cambridge, Cambridge, CB3 0HE, United Kingdom  Kieran
Dalton  Hitachi Cambridge Laboratory, J. J. Thomson Ave., Cambridge, CB3 0HE,
United Kingdom  Cavendish Laboratory, Department of Physics, University of
Cambridge, Cambridge, CB3 0HE, United Kingdom  Crispin H. W. Barnes  Cavendish
Laboratory, Department of Physics, University of Cambridge, Cambridge, CB3
0HE, United Kingdom  David R. M. Arvidsson-Shukur  Hitachi Cambridge
Laboratory, J. J. Thomson Ave., Cambridge, CB3 0HE, United Kingdom  Normann
Mertig  Hitachi Cambridge Laboratory, J. J. Thomson Ave., Cambridge, CB3 0HE,
United Kingdom

###### Abstract

Adaptive variational quantum eigensolvers (ADAPT-VQEs) are promising
candidates for simulations of strongly correlated systems on near-term quantum
hardware. To further improve the noise resilience of these algorithms, recent
efforts have been directed towards compactifying, or layering, their ansatz
circuits. Here, we broaden the understanding of the algorithmic layering
process in three ways. First, we investigate the non-commutation relations
between the different elements that are used to build ADAPT-VQE ansätze. Doing
so, we develop a framework for studying and developing layering algorithms,
which produce shallower circuits. Second, based on this framework, we develop
a new subroutine that can reduce the number of quantum-processor calls by
optimizing the selection procedure with which a variational quantum algorithm
appends ansatz elements. Third, we provide a thorough numerical investigation
of the noise-resilience improvement available via layering the circuits of
ADAPT-VQE algorithms. We find that layering leads to an improved noise
resilience with respect to amplitude-damping and dephasing noise, which, in
general, affect idling and non-idling qubits alike. With respect to
depolarizing noise, which tends to affect only actively manipulated qubits, we
observe no advantage of layering.

##  I Introduction

Quantum chemistry simulations of strongly correlated systems are challenging
for classical computers McArdle  _et al._ (2020). While approximate methods
often lack accuracy McArdle  _et al._ (2020); Hartree and Hartree (1935); Kohn
and Sham (1965); Hohenberg and Kohn (1964); Rossi  _et al._ (1999), exact
methods become infeasible when the system sizes exceed more than 34 spin
orbitals—the largest system for which a full configuration interaction (FCI)
calculation has been conducted Rossi  _et al._ (1999). For this reason,
simulations of many advanced chemical systems, such as enzyme active sites and
surface catalysts, rely on knowledge-intense, domain-specific approximations
Bauer  _et al._ (2020). Therefore, developing general chemistry simulation
methods for quantum computers could prove valuable.

Variational quantum eigensolvers (VQEs) Peruzzo  _et al._ (2014); McArdle  _et
al._ (2020); Tilly  _et al._ (2022); Romero  _et al._ (2018); Grimsley  _et
al._ (2019); Yordanov  _et al._ (2021, 2022); Tang  _et al._ (2021); Dalton
_et al._ (2022); Anastasiou  _et al._ (2022); Liu  _et al._ (2022) are a class
of quantum-classical methods intended to perform chemistry simulations on
near-term quantum hardware. More specifically, VQEs calculate upper bounds to
the ground state energy $E_{0}$ of a molecular Hamiltonian $H$ using the
Rayleigh-Ritz variational principle

$\displaystyle E_{0}\leq
E(\vec{\theta})\equiv\Tr\left(H\Lambda(\vec{\theta})[\rho_{0}]\right).$ (1)

A quantum processor is used to apply a parametrized quantum circuit to an
initial state. In the presence of noise the quantum circuit can, in general,
be represented by the parameterized completely positive trace-preserving
(CPTP) map $\Lambda(\vec{\theta})$ and the initial state can be represented by
the density matrix $\rho_{0}$. We will use square brackets to enclose a state
acted upon by a CPTP map. This generates a parametrized trial state
$\rho(\vec{\theta})\equiv\Lambda(\vec{\theta})[\rho_{0}]$ that is hard to
represent on classical computers. The energy expectation value
$E(\vec{\theta})$ of $\rho(\vec{\theta})$ gives a bound on $E_{0}$, which can
be accurately sampled using polynomially few measurements McArdle  _et al._
(2020); Tilly  _et al._ (2022). A classical computer then varies
$\vec{\theta}$ to minimize $E(\vec{\theta})$ iteratively. Provided that the
ansatz circuit is sufficiently expressive, $E(\vec{\theta})$ converges to
$E_{0}$ and returns the ground state energy. Initial implementations of VQEs
on near-term hardware have been reported in Peruzzo  _et al._ (2014); Google
AI Quantum And Collaborators  _et al._ (2020); O’Malley  _et al._ (2016);
Kandala  _et al._ (2017); Hempel  _et al._ (2018); Xue  _et al._ (2022).
Despite these encouraging results, several refinements are needed to alleviate
trainability issues McClean  _et al._ (2018); Arrasmith  _et al._ (2021);
Cerezo and Coles (2021); Wang  _et al._ (2021) and to make VQEs feasible for
molecular simulations with larger numbers of orbitals. Moreover, recent
results indicate that the noise resilience of VQE algorithms must be improved
to enable useful simulations Dalton  _et al._ (2022); Wang  _et al._ (2021);
De Palma  _et al._ (2023).

Adaptive VQEs (ADAPT-VQEs) Grimsley  _et al._ (2019) are promising VQE
algorithms, which partially address the issues of trainability and noise
resilience. They operate by improving the ansatz circuits in $t_{\text{max}}$
consecutive steps

$\displaystyle\Lambda_{t}(\theta_{t},\ldots,\theta_{1})=A_{t}(\theta_{t})\circ\Lambda_{t-1}(\theta_{t-1},\ldots,\theta_{1}),$
(2)

starting from the identity map $\Lambda_{0}=\text{id}$. Here,
$t=1,...,t_{\text{max}}$ indexes the step and $\circ$ denotes functional
composition of the CPTP maps. An ansatz element $A_{t}(\theta_{t})$ is added
to the ansatz circuit in each step. The ansatz element $A_{t}(\theta_{t})$ is
chosen from an ansatz-element pool $\mathcal{P}$ by computing the energy
gradient for each ansatz element and picking the ansatz element with the
steepest gradient. Numerical evidence suggests that such ADAPT-VQEs are
readily trainable and can minimize the energy landscape Grimsley  _et al._
(2023). In the original proposal of ADAPT-VQE, the ansatz-element pool was
physically motivated, comprising single and double fermionic excitations.
Since then, different types of ansatz-element pools have been proposed to
minimize the number of CNOT gates in the ansatz circuit and thus improve the
noise resilience of ADAPT-VQE Yordanov  _et al._ (2021, 2022); Tang  _et al._
(2021); Yordanov  _et al._ (2020).

ADAPT-VQEs still face issues. Compared with other VQE algorithms, ADAPT-VQEs
make more calls to quantum processors. This is because in every iteration,
finding the ansatz element with the steepest energy gradient requires at least
$\mathcal{O}\left(|\mathcal{P}|\right)$ quantum processor calls. This makes
more efficient pool-exploration strategies desirable. Moreover, noise poses
serious restrictions on the maximum depth of useful VQE ansatz circuits Dalton
_et al._ (2022). This makes shallower ansatz circuits desirable. A recent
algorithm called TETRIS-ADAPT-VQE compresses VQE ansatz circuits into compact
layers of ansatz elements Anastasiou  _et al._ (2022). This yields shallower
ansatz circuits. However, it has not yet been demonstrated that shallower
ansatz circuits lead to improved noise resilience. It is, therefore, important
to evaluate whether such shallow ansatz circuits boost the noise resilience of
ADAPT-VQEs.

In this paper, we broaden the understanding of TETRIS-like layering
algorithms. First, we show how non-commuting ansatz elements can be used to
define a topology on the ansatz-element pool. Based on this topology, we
present Subpool Exploration: a pool-exploration strategy to reduce the number
of quantum-processor calls when searching for ansatz elements with large
energy gradients. We then investigate several flavors of algorithms to layer
and shorten ansatz circuits. Benchmarking these algorithms, we find that
alternative layering strategies can yield equally shallow ansatz circuits as
TETRIS-ADAPT-VQE. Finally, we investigate whether shallow VQE circuits are
more noise resilient. We do this by benchmarking both standard and layered
ADAPT-VQEs in the presence of noise. For amplitude damping and dephasing
noise, which globally affect idling and non-idling qubits alike, we observe an
increased noise resilience due to shallower ansatz circuits. On the other
hand, we find that layering is unable to mitigate depolarizing noise, which
acts locally on actively manipulated qubits.

The remainder of this paper is structured as follows: In Sec. II, we introduce
notation and the ADAPT-VQE algorithm. In Sec. III and Sec. IV, subpool
exploration and layering for ADAPT-VQE are described and benchmarked,
respectively. We study the runtime advantage of layering in Sec. V. In Sec.
VI, we investigate the effect of noise on layered VQE algorithms. Finally, we
conclude in Sec. VII.

##  II Preliminaries: Notation and the ADAPT-VQE

In what follows, we consider second-quantized Hamiltonians on a finite set of
$N$ spin orbitals:

$\displaystyle
H=\sum_{p,q=1}^{N}h_{pq}a_{p}^{\dagger}a_{q}\;+\sum_{p,q,r,s=1}^{N}h_{pqrs}a_{p}^{\dagger}a_{q}^{\dagger}a_{r}a_{s}.$
(3)

$a_{p}^{\dagger}$ and $a_{p}$ denote fermionic creation and annihilation
operators of the $p$th spin-orbital, respectively. The coefficients $h_{pq}$
and $h_{pqrs}$ can be efficiently computed classically—we use the Psi4 package
Turney  _et al._ (2012).

The Jordan-Wigner transformation McArdle  _et al._ (2020) is used to represent
creation and annihilation operators by

$\displaystyle a_{p}^{\dagger}\mapsto Q_{p}^{\dagger}\mathcal{Z}_{p}\quad\quad
a_{p}\mapsto Q_{p}\mathcal{Z}_{p},$ (4)

respectively. Here,

$\displaystyle
Q_{p}^{\dagger}\coloneqq\frac{1}{2}\left(X_{p}-iY_{p}\right)\quad\quad
Q_{p}\coloneqq\frac{1}{2}\left(X_{p}+iY_{p}\right),$ (5)

are the qubit creation and annihilation operators and $X_{p},Y_{p},Z_{p}$
denote Pauli operators acting on qubit $p$. The fermionic phase is represented
by

$\displaystyle\mathcal{Z}_{p}\coloneqq\displaystyle\bigotimes_{q<p}Z_{q}.$ (6)

Anti-Hermitian operators $T$ generate ansatz elements that form
Stone’s-encoded unitaries parametrized by one real parameter $\theta$:

$\displaystyle A(\theta)[\rho]\coloneqq\exp(\theta T)\rho\exp(-\theta T).$ (7)

Different ADAPT-VQE algorithms choose $T$ from different types of operator
pools. There are three common types of operator pools. The fermionic pool
$\mathcal{P}^{\rm{Fermi}}$ Grimsley  _et al._ (2019) contains fermionic single
and double excitations generated by anti-Hermitian operators:

$\displaystyle T^{p}_{q}$ $\displaystyle\coloneqq
a_{p}^{\dagger}a_{q}-a_{q}^{\dagger}a_{p},$ (8) $\displaystyle T^{pq}_{rs}$
$\displaystyle\coloneqq
a_{p}^{\dagger}a_{q}^{\dagger}a_{r}a_{s}-a_{s}^{\dagger}a_{r}^{\dagger}a_{q}a_{p},$
(9)

where $p,q,r,s=1,...,N$. The QEB pool $\mathcal{P}^{\text{QEB}}$ Yordanov  _et
al._ (2021) contains single and double qubit excitations generated by anti-
Hermitian operators:

$\displaystyle T^{p}_{q}$ $\displaystyle\coloneqq
Q_{p}^{\dagger}Q_{q}-Q_{q}^{\dagger}Q_{p},$ (10) $\displaystyle T^{pq}_{rs}$
$\displaystyle\coloneqq
Q_{p}^{\dagger}Q_{q}^{\dagger}Q_{r}Q_{s}-Q_{s}^{\dagger}Q_{r}^{\dagger}Q_{q}Q_{p}.$
(11)

The qubit pool $\mathcal{P}^{\text{qubit}}$ Tang  _et al._ (2021) contains
parameterized unitaries generated by strings of Pauli-operators
$\sigma_{p}\in\left\\{X_{p},Y_{p},Z_{p}\right\\}$:

$\displaystyle T_{pq}$ $\displaystyle\coloneqq i\sigma_{p}\sigma_{q},$ (12)
$\displaystyle T_{pqrs}$ $\displaystyle\coloneqq
i\sigma_{p}\sigma_{q}\sigma_{r}\sigma_{s}.$ (13)

Further definitions and discussions of all three pools are given in Appendix
F. It is worth noting that all ansatz elements have quantum-circuit
representations composed of multiple standard single- and two-qubit gates
Yordanov  _et al._ (2020). All three pools contain
$\mathcal{O}\left(N^{4}\right)$ elements.

ADAPT-VQEs optimize several objective functions. At iteration step $t$, the
energy landscape is defined by

$\displaystyle
E_{t}(\theta_{t},...,\theta_{1})\equiv\Tr\left[HA_{t}(\theta_{t})\circ\ldots\circ
A_{1}(\theta_{1})[\rho_{0}]\right].$ (14)

A global optimizer may repeatedly evaluate $E_{t}$ and its partial derivatives
at the end of the $t$th iteration to return a set of optimal parameters:

$\displaystyle(\theta_{t}^{*},\ldots,\theta_{1}^{*})=\operatorname*{arg\,min}_{(\theta_{t},\ldots,\theta_{1})\in\mathbb{R}^{t}}{E_{t}(\theta_{t},...,\theta_{1})}.$
(15)

These parameters set the upper energy bound of the $t$th iteration:

$\displaystyle\mathcal{E}_{t}=E_{t}(\theta_{t}^{*},\ldots,\theta_{1}^{*}).$
(16)

A loss function $L_{t}\colon\mathcal{P}\to\mathbb{R}$ is used to pick an
ansatz element from the operator pool $\mathcal{P}$ at each iteration $t$:

$\displaystyle A_{t}=\operatorname*{arg\,min}_{A\in\mathcal{P}}L_{t}(A).$ (17)

Throughout this paper, we use the standard gradient loss of ADAPT-VQEs,
defined in Eq. 20. We denote the state after $t-1$ iterations with optimized
parameters $\theta_{t-1}^{*},\ldots,\theta_{1}^{*}$ by

$\displaystyle\rho_{t-1}=\Lambda_{t-1}(\theta_{t-1}^{*},\ldots,\theta_{1}^{*})[\rho_{0}].$
(18)

Further, we define the energy expectation after adding the ansatz element
$A\in\mathcal{P}$ as

$\displaystyle E_{t,A}(\theta)=\Tr\left(HA(\theta)[\rho_{t-1}]\right).$ (19)

Then, the loss is defined by

$\displaystyle L_{t}(A)=-\left|\frac{\partial
E_{t,A}(\theta)}{\partial\theta}\right|_{\theta=0}=-\left|\Tr\left([H,T]\rho_{t-1}\right)\right|.$
(20)

We consider alternative loss functions in Appendix D.

The ADAPT-VQE starts by initializing a state $\rho_{0}$. Often, $\rho_{0}$ is
the Hartree-Fock state $\rho_{\text{HF}}$. The algorithm then builds the
ansatz circuit $\Lambda_{t}$ by first adding ansatz elements
$A_{t}\in\mathcal{P}$ of minimal loss $L_{t}$, according to Eq. 17. Then, the
algorithm optimizes the ansatz circuit parameters according to Eq. 15. This
generates a series of upper bounds,

$\displaystyle\mathcal{E}_{0}>\mathcal{E}_{1}>...>\mathcal{E}_{t},$ (21)

until the improvement of consecutive bounds drops below a threshold
$\varepsilon$ such that $\mathcal{E}_{t-1}-\mathcal{E}_{t}<\varepsilon$, or
the maximum iteration number $t_{\text{max}}$ is reached. The final bound
($\mathcal{E}_{t}$ or $\mathcal{E}_{t_{\text{max}}}$) is then returned to
approximate $E_{0}$. A pseudo-code of the ADAPT-VQE is given in Algorithm 1.

Algorithm 1 ADAPT-VQE Grimsley  _et al._ (2019)

1:Initialize state $\rho_{0}\leftarrow\rho_{\text{HF}}$, circuit
$\Lambda_{0}\leftarrow 1$, and pool $\mathcal{P}$.

2:Initialize energy bound $\mathcal{E}_{0}\leftarrow\infty$ and accuracy
$\varepsilon$.

3:for $t=1,...,t_{\text{max}}$ do

4: Select ansatz element:
$A_{t}\leftarrow\operatorname*{arg\,min}_{A\in\mathcal{P}}{L_{t}(A)}$

5: Set circuit: $\Lambda_{t}(\theta_{t},...,\theta_{1})\leftarrow
A_{t}(\theta_{t})\circ\Lambda_{t-1}(\theta_{t-1},...,\theta_{1})$

6: Optimize circuit:
$(\theta_{t}^{*},...,\theta_{1}^{*})\leftarrow\operatorname*{arg\,min}{E_{t}(\theta_{t},...,\theta_{1})}$

7: Update energy bound: $\mathcal{E}_{t}\leftarrow
E_{t}(\theta_{t}^{*},...,\theta_{1}^{*})$

8: Update state:
$\rho_{t}\leftarrow\Lambda_{t}(\theta_{t}^{*},...,\theta_{1}^{*})[\rho_{0}]$

9: if $\mathcal{E}_{t-1}-\mathcal{E}_{t}<\varepsilon$ then

10: return energy bound $\mathcal{E}_{t}$

11:return energy bound $\mathcal{E}_{t_{\text{max}}}$

##  III Subpool exploration and layering for ADAPT-VQEs

In this section, we present two subroutines to improve ADAPT-VQEs. The first
subroutine optimally layers ansatz elements, as depicted in Fig. 1. We call
the process of producing dense (right-hand side) ansatz circuits instead of
sparse (left-hand side) ansatz circuits “layering”. This subroutine can be
used to construct shallower ansatz circuits, which may make ADAPT-VQEs more
resilient to noise. The second subroutine is subpool exploration. It searches
ansatz-element pools in successions of non-commuting ansatz elements. Subpool
exploration is essential for layering and can reduce the number of calls an
ADAPT-VQE makes to a quantum processor. Combining both subroutines results in
algorithms similar to TETRIS-ADAPT-VQE Anastasiou  _et al._ (2022). Our work
focuses on developing and understanding layering algorithms from the
perspective of non-commuting sets of ansatz elements.

Figure 1: Layering: A sparse ansatz circuit (left), as produced by standard
ADAPT-VQEs, can be compressed to a dense structure (right) by layering. Boxes
denote ansatz elements. Each line represents a single qubit. Note that ansatz
circuit elements entangle two or four qubits.

###  III A Commutativity and Support

Commutativity of ansatz elements is a central notion underlying our
subroutines:

######  Definition 1 (Operator Commutativity)

Two ansatz elements $A,B\in\mathcal{P}$ are said to “operator commute” iff
$A\left(\theta\right)$ and $B\left(\phi\right)$ commute for all $\theta$ and
$\phi$:

$\displaystyle\\{A,B\\}_{\textrm{O}}=0\iff\forall\theta,\phi\in\mathbb{R}\;:\;\left[A\left(\theta\right),B\left(\phi\right)\right]=0.$
(22)

Conversely, two ansatz elements $A,B\in\mathcal{P}$ do not operator-commute
iff there exist parameters for which the corresponding operators do not
commute:

$\displaystyle\\{A,B\\}_{\textrm{O}}\neq
0\iff\exists\theta,\phi\in\mathbb{R}:\left[A\left(\theta\right),B\left(\phi\right)\right]\neq
0.$ (23)

######  Definition 2 (Operator non-commuting set)

Given an ansatz-element pool $\mathcal{P}$ and an ansatz element
$A\in\mathcal{P}$, we define its operator non-commuting set as follows

$\displaystyle\mathcal{N}_{\textrm{O}}(\mathcal{P},A)\coloneqq\left\\{B\in\mathcal{P}:\\{A,B\\}_{\textrm{O}}\neq
0\right\\}.$ (24)

Operator commutativity is central to layering. The operator non-commuting set
is central to subpool exploration. Structurally similar and more-intuitive
notions can be defined using qubit support:

######  Definition 3 (Qubit support)

Let $\mathcal{B}\left(\mathcal{H}\right)$ denote the set of superoperators on
a Hilbert space $\mathcal{H}$. Let
$\mathcal{H}_{\mathcal{Q}}\coloneqq\bigotimes_{q\in\mathcal{Q}}\mathcal{H}_{q}$
denote the Hilbert space of a set of all qubits
$\mathcal{Q}\equiv\left\\{1,\ldots,N\right\\}$ where $\mathcal{H}_{q}$ is the
Hilbert space corresponding to the $q$th qubit. Consider a superoperator
$A\in\mathcal{B}\left(\mathcal{H}_{\mathcal{Q}}\right)$. First, we define the
superoperator subset that acts on a qubit subset
$\mathcal{W}\subseteq\mathcal{Q}$ as

$\mathcal{B}_{\mathcal{W}}\coloneqq\left\\{B\otimes\text{id}\colon
B\in\mathcal{B}\left(\mathcal{H}_{\mathcal{W}}\right)\right\\}\subseteq\mathcal{B}\left(\mathcal{H}_{\mathcal{Q}}\right).$
(25)

Then, we define the qubit support of a superoperator $A$ as its minimal qubit
subset $\mathcal{W}$:

$\mathrm{Supp}\left(A\right)\coloneqq\left.\smashoperator[r]{\bigcap_{\begin{subarray}{c}{\mathcal{W}\subseteq\mathcal{Q}\colon
A\in\mathcal{B}_{\mathcal{W}}}\end{subarray}}^{}}\mathcal{W}\right..$ (26)

The notion of support extends to parameterized ansatz elements:

$\mathrm{Supp}\left(B\right)\coloneqq\bigcup_{\theta}\mathrm{Supp}\left(B\left(\theta\right)\right),$
(27)

where $B$ is a parameterized ansatz element.

Intuitively, the qubit support of an ansatz element $A$ is the set of all
qubits the operator $A$ acts on nontrivially Fig. 2. The concept of qubit
support allows one to define support commutativity of ansatz elements as
follows.

######  Definition 4 (Support commutativity)

Two ansatz elements $A,B\in\mathcal{P}$ are said to “support-commute” iff
their qubit support is disjoint.

$\displaystyle\\{A,B\\}_{\textrm{S}}=0\iff\mathrm{Supp}(A)\cap\mathrm{Supp}(B)=\emptyset.$
(28)

Conversely, two ansatz elements $A,B\in\mathcal{P}$ do not support-commute iff
their supports overlap

$\displaystyle\\{A,B\\}_{\textrm{S}}\neq
0\iff\mathrm{Supp}(A)\cap\mathrm{Supp}(B)\neq\emptyset.$ (29)

Figure 2: A diagram comparing support and operator commutativity. (a) The
elements both support and operator commute. Note that $R_{y}(\theta)$ only has
qubit support on the top qubit line. (b) The elements operator commute but do
not support commute. (c) The elements neither support nor operator commute.

######  Definition 5 (Support non-commuting set)

Given an ansatz-element pool $\mathcal{P}$ and an ansatz element
$A\in\mathcal{P}$, we define the set of ansatz elements with overlapping
support as

$\displaystyle\mathcal{N}_{\textrm{S}}(\mathcal{P},A)\coloneqq\left\\{B\in\mathcal{P}:\\{B,A\\}_{S}\neq
0\right\\}.$ (30)

Operator commutativity and support commutativity are not equivalent—see Fig.
2. However, the following properties hold. Elements supported on disjoint
qubit sets operator commute:

$\displaystyle\forall
A,B\in\mathcal{P}\quad\\{A,B\\}_{\textrm{S}}=0\implies\\{A,B\\}_{\textrm{O}}=0.$
(31)

Conversely, operator non-commuting ansatz elements act on, at least, one
common qubit which implies they are support non-commuting:

$\displaystyle\forall A,B\in\mathcal{P}\quad\\{A,B\\}_{\textrm{O}}\neq
0\implies\\{A,B\\}_{\textrm{S}}\neq 0.$ (32)

The last relation also implies that the operator non-commuting set of $A$ is
contained in its support non-commuting set

$\displaystyle\mathcal{N}_{\textrm{O}}(\mathcal{P},A)\subseteq\mathcal{N}_{\textrm{S}}(\mathcal{P},A).$
(33)

We further generalize the notions of operator and support commutativity in
Appendix J. Henceforth, we will use generalized commutativity to denote either
operator or support commutativity or any other type of commutativity specified
in Appendix J. Further, $\mathcal{N}_{\textrm{G}}$ and
$\\{\bullet,\bullet\\}_{\textrm{G}}$ will be used to denote the generalized
non-commuting set and the generalized commutator, respectively.

For later reference, we note that generalized non-commuting sets induce a
topology on $\mathcal{P}$ via the following discrete metric.

######  Definition 6 (Pool metric)

Let $d\colon\mathcal{P}\times\mathcal{P}\to\left\\{0,1,2\right\\}$ define a
discrete metric such that: (i) $\forall A\in\mathcal{P}$, set $d(A,A)=0$. (ii)
$\forall A,B\in\mathcal{P}$ with $A\neq B$ and $\\{A,B\\}_{\textrm{G}}\neq 0$,
set $d(A,B)=1$. (iii) $\forall A,B\in\mathcal{P}$ with $A\neq B$ and
$\\{A,B\\}_{\textrm{G}}=0$, set $d(A,B)=2$.

Figure 3: A diagram of the distance $d$ from an element $A\in\mathcal{P}$
under the pool metric, Definition 6. The ansatz element $A$ (black dot) is
surrounded by ansatz elements of the non-commuting set
$\mathcal{N}_{\textrm{G}}(\mathcal{P},A)$ of distance 1 (white circle). All
other elements $\mathcal{P}\setminus\mathcal{N}_{\textrm{G}}(\mathcal{P},A)$
have distance 2 (gray shaded region).

With this metric, the generalized non-commuting elements
$\mathcal{N}_{\textrm{G}}(\mathcal{P},A)$ form a ball of distance one around
each ansatz element $A\in\mathcal{P}$. The metric is represented
diagrammatically in Fig. 3. This allows us to identify an element
$A\in\mathcal{P}$ as a local minimum if there is no element with lower loss
within $A$’s generalized non-commuting set.

######  Property 1 (Local minimum)

Let $\mathcal{P}$ be an ansatz-element pool with the pool metric of Definition
6, and let $L:\mathcal{P}\to\mathbb{R}$ denote a loss function. Then, any
element $A\in\mathcal{P}$ for which

$L\left(A\right)=\min_{B\in\mathcal{N}_{\textrm{G}}\left(\mathcal{P},A\right)}L\left(B\right),$
(34)

is a local minimum on $\mathcal{P}$ with respect to $L$.

This property is important as we will later show that subpool exploration
always returns local minima.

To gain intuition about the previously defined notions, we consider the ansatz
elements of the QEB and the Pauli pools, Eqs. 10, 11, 12 and 13. The ansatz
elements of these pools have qubit support on either two or four qubits, as is
illustrated in Fig. 1. Commuting ansatz elements with disjoint support can be
packed into an ansatz-element layer, which can be executed on the quantum
processor in parallel. This is the core idea of layering, which helps to
reduce the depths of ansatz circuits. Moreover, as generalized non-commuting
ansatz elements must share at least one qubit, we conclude that the
generalized non-commuting set $\mathcal{N}_{\textrm{G}}(\mathcal{P},A)$ has at
most $\mathcal{O}\left(N^{3}\right)$ ansatz elements. This is a core component
of subpool exploration. Analytic expressions for the cardinalities of the
generalized non-commuting sets are given in Appendix H. In Appendix G, we
prove that two different fermionic excitations operator commute iff they act
on disjoint or equivalent sets of orbitals. The same is true for qubit
excitations. Pauli excitations operator commute iff the generating Pauli
strings differ in an even number of places within their mutual support.

###  III B Subpool exploration

In this section, we introduce subpool exploration, a strategy to explore
ansatz-element pools with fewer quantum-processor calls. Subpool exploration
differs from the standard ADAPT-VQE as follows. Standard ADAPT-VQEs evaluate
the loss of every ansatz element in the ansatz-element pool $\mathcal{P}$ in
every iteration of ADAPT-VQE, (Algorithm 1, Line 4). This leads to
$\mathcal{O}\left(|\mathcal{P}|\right)$ quantum-processor calls to identify
the ansatz element of minimal loss. Instead, subpool exploration evaluates the
loss of a reduced number of ansatz elements by exploring a sequence of
generalized non-commuting ansatz-element subpools. This can lead to a reduced
number of quantum-processor calls and returns an ansatz element which is a
local minimum of the pool $\mathcal{P}$. The details of subpool exploration
are as follows.

Algorithm:—Let $\mathcal{P}$ denote a given pool and $L$ a given loss
function. Instead of naïvely computing the loss of every ansatz element in
$\mathcal{P}$, our algorithm explores $\mathcal{P}$ iteratively by considering
subpools, $\mathcal{S}_{m}\subsetneq\mathcal{P}$, in consecutive steps. During
this process, the algorithm successively determines the ansatz element with
minimal loss within subpool $\mathcal{S}_{m}$ as

$\displaystyle A_{m}=\operatorname*{arg\,min}_{A\in\mathcal{S}_{m}}{L(A)}.$
(35)

Meanwhile, the corresponding loss value is stored:

$\displaystyle\mathcal{L}_{m}=L(A_{m}).$ (36)

Iterations are halted when loss values stop decreasing. The key point of
subpool exploration is to update the subpools $\mathcal{S}_{m}$ using the
generalized non-commuting set generated by $A_{m}$:

$\mathcal{S}_{m+1}=\mathcal{N}_{\textrm{G}}\left(\mathcal{P}\backslash\mathcal{S}_{\leq
m},A_{m}\right)\subseteq\mathcal{N}_{\textrm{G}}\left(\mathcal{P},A_{m}\right),\\!\quad\forall
m\geq 0,$ (37)

where $\mathcal{S}_{\leq m}\coloneqq\cup_{l=0}^{m}\mathcal{S}_{l}$. A pseudo-
code summary of subpool exploration is given in Algorithm 2, and a visual
summary is displayed in Fig. 4. We now discuss aspects of subpool exploration.

Algorithm 2 Subpool Exploration

1:Input: Pool $\mathcal{P}$ and loss function $L$.

2:Initialize subpool $\mathcal{S}_{0}$ and loss value
$\mathcal{L}_{0}\leftarrow\infty$.

3:for $m=0,...$ do

4: Select ansatz element
$A_{m}\leftarrow\operatorname*{arg\,min}_{A\in\mathcal{S}_{m}}{L(A)}$.

5: Update loss value $\mathcal{L}_{m}\leftarrow L(A_{m})$.

6: if $\mathcal{L}_{m}<\mathcal{L}_{m-1}$ then

7: Update subpool
$\mathcal{S}_{m+1}=\mathcal{N}_{\textrm{G}}\left(\mathcal{P}\backslash\mathcal{S}_{\leq
m},A_{m}\right)$.

8: else

9: return $A_{m},\mathcal{S}_{m}$.

Figure 4: Visualization of our strategy for subpool exploration. The pool
$\mathcal{P}$ is successively explored in subpools $\mathcal{S}_{m}$, with
ansatz elements $A_{m}$ of minimal loss generating future subpools through
their generalized non-commuting set.

Efficiency:— Let $m_{s}$ denote the index of the final iteration and define
the set of searched ansatz elements as

$\displaystyle\mathcal{S}\coloneqq\cup_{m=0}^{m_{s}}\mathcal{S}_{m}.$ (38)

As loss values of ansatz elements that have been explored are stored in a
list, it follows that subpool exploration requires only $|\mathcal{S}|$ loss
function calls. On the other hand, exploring the whole pool in ADAPT-VQE
requires $|\mathcal{P}|$ loss-function calls. Since $\mathcal{S}$ is a subset
of $\mathcal{P}$, subpool exploration may reduce the number of quantum-
processor calls:

$\displaystyle\mathcal{S}\subseteq\mathcal{P}\implies|\mathcal{S}|\leq|\mathcal{P}|.$
(39)

To give a specific example, consider the QEB and qubit pools. Those pools
contain $\mathcal{O}\left(N^{4}\right)$ ansatz elements. On the other hand,
generalized non-commuting sets have $\mathcal{O}\left(N^{3}\right)$ ansatz
elements. Thus, by choosing an appropriate initial subpool, we can ensure that
$|\mathcal{S}_{m}|=\mathcal{O}\left(N^{3}\right)$ for all subpools. Especially
if the number of searched subpools is $m_{s}=\mathcal{O}\left(1\right)$,
subpool exploration can return ansatz elements of low loss while exploring
only $\mathcal{O}\left(N^{3}\right)$ ansatz elements.

We note that this pool-exploration strategy ignores certain ansatz elements.
In particular, it may miss the optimal ansatz element with minimal loss.
Nevertheless, as explained in the following paragraphs, it will always return
ansatz elements which are locally optimal. This ensures that the globally
optimal ansatz element can always be added to the ansatz circuit later in the
algorithm.

Optimality:—As the set of explored ansatz elements $\mathcal{S}$ is a subset
of $\mathcal{P}$, the ansatz element returned by subpool exploration

$\displaystyle
A_{\mathcal{S}}^{*}\coloneqq\operatorname*{arg\,min}_{A\in\mathcal{S}}L(A),$
(40)

may be sub-optimal to the ansatz element returned by exploring the whole pool

$\displaystyle
A_{\mathcal{P}}^{*}\coloneqq\operatorname*{arg\,min}_{A\in\mathcal{P}}L(A).$
(41)

That is,

$\displaystyle\mathcal{S}\subset\mathcal{P}\implies\operatorname*{arg\,min}_{A\in\mathcal{P}}L(A)\leq\operatorname*{arg\,min}_{A\in\mathcal{S}}L(A).$
(42)

Yet, there are a couple of useful properties that pertain to the output
$A_{\mathcal{S}}^{*}$ of subpool exploration. At first, the outputs of subpool
exploration are local minima.

######  Property 2 (Local Optimality)

Any ansatz element $A_{\mathcal{S}}^{*}$ returned by subpool exploration is a
local minimum.

The proof of this property is immediate. Moreover, as subpool exploration
constructs subpools from generalized non-commuting sets, the only ansatz
elements $B\in\mathcal{P}$ with $L(B)<L(A_{\mathcal{S}}^{*})$ must necessarily
generalized commute with $A_{\mathcal{S}}^{*}\in\mathcal{P}$.

###### Property 3

(Better ansatz elements generalized commute) Let $\mathcal{P}$ denote a pool
and $L$ denote a loss function. Let $A_{\mathcal{S}}^{*}\in\mathcal{P}$ denote
the final output of subpool exploration. Then,

$\displaystyle\forall B\in\mathcal{P}\text{ with }L(B)<L(A_{\mathcal{S}}^{*})$
$\displaystyle\implies\\{A_{\mathcal{S}}^{*},B\\}_{\textrm{G}}=0$ (43)
$\displaystyle\implies\\{A_{\mathcal{S}}^{*},B\\}_{\textrm{O}}=0.$ (44)

  * Proof.

We prove this property by contradiction. Assume that there is an ansatz
element $L(B)<L(A_{\mathcal{S}}^{*})$ such that
$\\{A_{\mathcal{S}}^{*},B\\}_{\textrm{G}}\neq 0$. This implies that $B$ is in
the generalized non-commuting set
$\mathcal{N}_{\textrm{G}}(\mathcal{P},A_{\mathcal{S}}^{*})$ and exploring the
corresponding subpool would have produced $L(B)<L(A_{\mathcal{S}}^{*})$
leading to the exploration of $\mathcal{N}_{\textrm{G}}(\mathcal{P},B)$. This,
in turn, can only return an ansatz element with a loss $L(B)$ or smaller. This
would contradict $A_{\mathcal{S}}^{*}$ having been the final output of the
algorithm. Finally, we use Eq. 31 to show Eq. 44

Property 3 is useful as it ensures that subpool exploration can find better
ansatz elements, which first were missed, in subsequent iterations. To see
this, suppose a first run of subpool exploration returns a local minimum
$A\in\mathcal{P}$. Further, suppose there is another local minimum
$B\in\mathcal{P}$ such that $L(B)<L(A)$. Property 3 ensures that $A$ and $B$
generalized commute. Hence, by running subpool exploration repeatedly on the
remaining pool, we are certain to discover the better local minimum
eventually. Ultimately, this will allow for restoring the global minimum.

Initial subpool:—So far, we have not specified any strategy for choosing the
initial set $\mathcal{S}_{0}$. This can, for example, be done by taking the
subpool of a single random ansatz element $A_{0}\in\mathcal{P}$.
Alternatively, one can compose $\mathcal{S}_{0}$ of random ansatz elements
enforcing an appropriate pool size, e.g.,
$|\mathcal{S}_{0}|=\mathcal{O}\left(N^{3}\right)$ for QEB and qubit pools.

We will refer to the ADAPT-VQE with subpool exploration as the Explore-ADAPT-
VQE. This algorithm is realized by replacing Line 4 in Algorithm 1 with
subpool exploration, Algorithm 2, with $L\rightarrow L_{t}$.

###  III C Layering

Below, we describe two methods for arranging generalized non-commuting ansatz
elements into ansatz-element layers.

######  Definition 7 (Ansatz-element layer)

Let $\mathcal{A}$ be a subset of $\mathcal{P}$. We say that $\mathcal{A}$ is
an ansatz-element layer iff

$\displaystyle\\{A,B\\}_{\textrm{G}}=0\quad\forall A,B\in\mathcal{A}\text{
such that }A\neq B.$ (45)

We denote the operator corresponding to the action of the mutually
generalized-commuting ansatz elements of an ansatz-element layer $\mathcal{A}$
with

$\displaystyle\mathcal{A}^{\text{o}}(\vec{\theta})=\prod_{A\in\mathcal{A}}A(\theta_{A}).$
(46)

Here, $\vec{\theta}$ is the parameter vector for the layer:

$\displaystyle\vec{\theta}\equiv\left\\{\theta_{A}\colon
A\in\mathcal{A}\right\\}.$ (47)

We note that for support commutativity, the product can be replaced by the
tensor product.

Since ansatz-element layers depend on parameter vectors, the update rule is

$\displaystyle\Lambda_{t}(\vec{\vartheta}_{t})=\mathcal{A}^{\text{o}}(\vec{\theta}_{t})\circ\Lambda_{t-1}(\vec{\vartheta}_{t-1}),\quad\vec{\vartheta}_{t}=(\vec{\theta}_{t},\vec{\vartheta}_{t-1}),$
(48)

As before, the algorithm is initialized with $\Lambda_{0}=\text{id}$ and
$\vec{\vartheta}=()$. To make the dependence on the ansatz circuit explicit,
we denote the energy landscape as

$\displaystyle
E_{\Lambda}(\vec{\vartheta})\coloneqq\tr\left[H\Lambda(\vec{\vartheta})\left[\rho_{0}\right]\right].$
(49)

The energy landscape of the $t$th iteration is denoted as

$\displaystyle E_{t}(\vec{\vartheta}_{t})\equiv
E_{\Lambda_{t}}(\vec{\vartheta}_{t}),$ (50)

and its optimal parameters are

$\displaystyle\vec{\vartheta}_{t}^{*}=\operatorname*{arg\,min}_{\vec{\vartheta}}E_{t}(\vec{\vartheta}).$
(51)

Further, the gradient loss (c.f. Eq. 20) is

$\displaystyle
L_{\Lambda(\vec{\vartheta})}(A)\equiv-\left|\tr\left[\left[H,T_{A}\right]\Lambda(\vec{\vartheta})\left[\rho_{0}\right]\right]\right|,$
(52)

where the definitions in Eqs. 20 and 52 satisfy the following relation

$\displaystyle L_{t}(A)=L_{\Lambda_{t-1}(\vec{\vartheta}_{t-1}^{*})}(A).$ (53)

With this notation in place, we proceed to describe two methods to construct
ansatz-element layers.

####  III C 1 Static layering

Our algorithm starts by initializing an empty ansatz-element layer and the
remaining pool $\mathcal{P}^{\prime}$ to be the entire pool $\mathcal{P}$.
Further, the loss is set such that $L\leftarrow L_{\Lambda_{t-1}}$ for the
$t$th layer. The algorithm proceeds to fill the ansatz-element layer by
successively running subpool exploration to pick an ansatz element $A_{n}$ in
$n=0,\ldots,n_{\text{max}}$ iterations. This naturally induces an ordering on
the layer. At every step of the iteration, the corresponding generalized non-
commuting set $\mathcal{N}_{\textrm{G}}(\mathcal{P}^{\prime},A_{n})$ is
removed from the remaining pool $\mathcal{P}^{\prime}$. If the loss of the
selected ansatz element $A_{n}$ is smaller than a predefined threshold
$L(A)<\ell$, it is added to the ansatz-element layer $\mathcal{A}$. The layer
is completed once the pool is exhausted ($\mathcal{P}^{\prime}=\emptyset$) or
the maximal iteration count $n_{\text{max}}$ is reached. A pseudocode summary
of static layering is given in Algorithm 3.

Algorithm 3 Build Static Layer

1:Input: Pool $\mathcal{P}$, loss $L$, max. loss $\ell$, max. iteration
$n_{\text{max}}$

2:Initialize remaining pool $\mathcal{P}^{\prime}\leftarrow\mathcal{P}$

3:Initialize ansatz layer $\mathcal{A}\leftarrow\emptyset$

4:for $n=0,...,n_{\text{max}}$ do

5: Set $A\leftarrow\mathrm{SubpoolExploration}(\mathcal{P}^{\prime},L)$

6: if $L(A)<\ell$ then

7: Update layer $\mathcal{A}\leftarrow\mathcal{A}\cup\\{A\\}$.

8: Reduce pool
$\mathcal{P}^{\prime}\leftarrow\mathcal{P}^{\prime}\setminus\mathcal{N}_{\textrm{G}}(\mathcal{P}^{\prime},A)$

9: if $\mathcal{P}^{\prime}=\emptyset$ then break return $\mathcal{A}$

In Static-ADAPT-VQE, static layering is used to grow an ansatz circuit
iteratively. In each iteration, the layer is appended to the ansatz circuit,
and the ansatz-circuit parameters are re-optimized. Iterations halt once the
decrease in energy falls below $\varepsilon$, the energy accuracy per ansatz
element. A summary of Static-ADAPT-VQE is given in Algorithm 4.

Algorithm 4 Static-ADAPT-VQE

1:Initialize state $\rho_{0}\leftarrow\rho_{\text{HF}}$, ansatz circuit
$\Lambda_{0}\leftarrow 1$, pool $\mathcal{P}$.

2:Initialize energy bound $\mathcal{E}_{0}\leftarrow\infty$ and accuracy
$\varepsilon$.

3:Initialize maximal loss $\ell$ and iteration count $n_{\text{max}}$.

4:for $t=1,...,t_{\text{max}}$ do

5: Get layer:
$\mathcal{A}_{t}\leftarrow\mathrm{BuildStaticLayer}(\mathcal{P},L_{\Lambda_{t-1}},\ell,n_{\text{max}})$

6: Set ansatz circuit:
$\Lambda_{t}(\vec{\vartheta}_{t})\leftarrow\mathcal{A}^{\text{o}}_{t}(\vec{\theta}_{t})\circ\Lambda_{t-1}(\vec{\vartheta}_{t-1})$

7: Optimize ansatz circuit:
$\vec{\vartheta}_{t}^{*}\leftarrow\operatorname*{arg\,min}{E_{t}(\vec{\vartheta}_{t})}$

8: Set ansatz circuit:
$\Lambda_{t}\leftarrow\Lambda_{t}(\vec{\vartheta}_{t}*)$

9: Update energy bound: $\mathcal{E}_{t}\leftarrow
E_{t}(\theta_{t}^{*},...,\theta_{1}^{*})$

10: if
$\mathcal{E}_{t-1}-\mathcal{E}_{t}<\varepsilon\left|\mathcal{A}_{t}\right|$
then

11: return energy bound $\mathcal{E}_{t}$

12:return energy bound $\mathcal{E}_{t_{\text{max}}}$

Figure 5: Visualization of layer construction and successive pool reduction.
Gray areas indicate the removal of generalized non-commuting sets
corresponding to ansatz elements $A_{n}$ added to the layer $\mathcal{A}$.
Parameters can either be optimized once the whole layer is fixed (static
layering) or after adding each ansatz element (dynamic layering).

We establish the close relationship between static layering and TETRIS-ADAPT-
VQE in the following property.

###### Property 4

Assume that all ansatz elements $A,B\in\mathcal{P}$ have distinct loss
$L(A)\neq L(B)$. Using support commutativity and provided that $\ell=0$ and
$n_{\text{max}}$ are sufficiently large to ensure that the whole layer is
filled, Static-ADAPT-VQE and TETRIS-ADAPT-VQE will produce identical ansatz-
element layers.

This property is proven by induction. Assume that the previous iterations of
ADAPT-VQE have yielded a specific ansatz circuit
$\Lambda_{t-1}(\vec{\vartheta}^{*})$. The next layer of ansatz elements
$\mathcal{A}_{t}$ can be constructed either by Static-ADAPT-VQE or TETRIS-
ADAPT-VQE. For both algorithms, the equivalence of
$\Lambda_{t-1}(\vec{\vartheta}^{*})$ implies that the loss function, Eq. 53,
of any ansatz element is identical throughout the construction of the layer
$\mathcal{A}_{t}$. First, by picking $\ell=0$, we ensure that both TETRIS-
ADAPT-VQE and Static-ADAPT-VQE only accept ansatz elements with a non-zero
gradient. Next, we note that if an ansatz element is placed on a qubit by
Static-ADAPT-VQE, then by Property 3, there exists no ansatz element that acts
actively on this qubit and generates a lower loss. Moreover, there exists no
ansatz element with identical loss that acts nontrivially on qubit, as we
assume that all ansatz elements have a distinct loss. Similarly, TETRIS-ADAPT-
VQE places ansatz elements from lowest to highest loss and ensures no two
ansatz elements have mutual support. Thus, if an ansatz element is placed on a
qubit by TETRIS-ADAPT-VQE, there exists no ansatz element with a lower loss
that acts nontrivially on this qubit. Again, there also exists no ansatz
element with identical loss supported by this qubit, as we assume that all
ansatz elements have a distinct loss. Combining these arguments, both Static-
and TETRIS-ADAPT-VQE will fill the ansatz-element layer $\mathcal{A}_{t}$ with
equivalent ansatz elements. The ansatz elements may be chosen in a different
order. By induction, the equivalence of $\Lambda_{t-1}$ and $\mathcal{A}_{t}$
implies the equivalence of the ansatz circuit $\Lambda_{t}$.

Name |  H4 |  LiH |  H6 |  BeH2 |  H2O
---|---|---|---|---|---
Orbitals $N$ | 8 | 12 | 12 | 14 | 14
Structure |  @aH-[,,,,¡-¿]@bH-[,,,,¡-¿]@cH-[,,,,¡-¿]@dH a)--b)node[midway,sloped,yshift=5pt]$d$; b)--c)node[midway,sloped,yshift=5pt]$d$; c)--d)node[midway,sloped,yshift=5pt]$d$; |  @aLi-[,,,,¡-¿]@bH a)--b)node[midway,sloped,yshift=5pt]$d$; |  @aH-[,,,,¡-¿]@bH-[,,,,¡-¿]@cH-[,,,,¡-¿]@dH-[,,,,¡-¿]@eH-[,,,, ¡-¿]@fH a)--b)node[midway,sloped,yshift=5pt]$d$; b)--c)node[midway,sloped,yshift=5pt]$d$; c)--d)node[midway,sloped,yshift=5pt]$d$; d)--e)node[midway,sloped,yshift=5pt]$d$; e)--f)node[midway,sloped,yshift=5pt]$d$; |  @aH-[,,,,¡-¿]@bBe-[,,,,¡-¿]@cH a)--b)node[midway,sloped,yshift=5pt]$d$; b)--c)node[midway,sloped,yshift=5pt]$d$; |  -[::-52.25, 0.5,,,draw=none]@aH-[::104.5,,,,¡-¿]@bO-[::-104.5,,,,¡-¿]@cH a)--b)node[midway,sloped,yshift=5pt]$d$; b)--c)node[midway,sloped,yshift=5pt]$d$; [stealth-stealth,shorten ¡=1pt,shorten ¿=1pt]([shift=(0:0.5cm)]b)arc(0:0:0.5cm); [shift=(0.0:0.5cm+1pt)b,anchor=0.0+180,rotate=0.0+90,inner sep=0pt, outer sep=0pt]at(b)$\beta$;
| $d=$3\text{\,}\text{\AA}$$ | $d=$1.546\text{\,}\text{\AA}$$ | $d=$0.735\text{\,}\text{\AA}$$ | $d=$1.316\text{\,}\text{\AA}$$ | $d=$1.0285\text{\,}\text{\AA}$,$
|  |  |  |  | $\beta=$96.84\text{\,}\mathrm{\SIUnitSymbolDegree}$$
Table 1: Table of molecular conformations and the corresponding number of
spin-orbitals $N$ used in numerical simulations.

####  III C 2 Dynamic layering

In static layering, ansatz-circuit parameters are optimized after appending a
whole layer with several ansatz elements. In dynamic layering, on the other
hand, ansatz-circuit parameters are re-optimized every time an ansatz element
is appended to a layer. The motivation for doing so is to simplify the
optimization process. The price is having to run the global optimization more
times. We now describe how to perform dynamic layering.

The starting point is a given ansatz circuit $\Lambda$, a set of optimal
parameters $\vec{\vartheta}^{*}$ [Eq. 51] and their corresponding energy bound
$\mathcal{E}\equiv E_{\Lambda}(\vec{\vartheta}^{*})$. The remaining pool
$\mathcal{P}^{\prime}$ is initiated to be the entire pool $\mathcal{P}$.
Starting from an empty layer $\mathcal{A}^{\prime}$ and a temporary ansatz
circuit $\Lambda^{\prime}=\Lambda$, a layer is constructed dynamically by
iteratively adding ansatz elements $A$ to $\mathcal{A}^{\prime}$ and
$\Lambda^{\prime}$ while simultaneously re-optimizing the ansatz-circuit
parameters $\vec{\vartheta}^{*}$. Based on the loss $L^{\prime}$ induced by
the currently optimal ansatz circuit $\Lambda^{\prime}(\vec{\vartheta}^{*})$,
subpool exploration is used to select ansatz elements $A$. Simultaneously, the
pool of remaining ansatz elements $\mathcal{P}^{\prime}$ is shrunk by the
successive removal of the generalized non-commuting sets
$\mathcal{N}_{\textrm{G}}(\mathcal{P}^{\prime},A)$. Finally, ansatz elements
are only added to the layer $\mathcal{A}$ if their loss is below a threshold
$\ell$ and the updated energy bound $\mathcal{E}^{\prime}$ exceeds a gain
threshold of $\varepsilon$. A pseudocode summary is given in Algorithm 5

Dynamic-ADAPT-VQE iteratively builds dynamic layers $\mathcal{A}_{t}$ and
appends those to the ansatz circuit $\Lambda_{t-1}$. The procedure is repeated
until an empty layer is returned; that is, no ansatz element is found that
reduces the energy by more than $\varepsilon$. Alternatively, the algorithm
halts when the (user-specified) maximal iteration count $t_{\text{max}}$ is
reached. A pseudocode summary is given in Algorithm 6.

Algorithm 5 Build Dynamic Layer

1:Input: Ansatz $\Lambda$, bound $\mathcal{E}$, opt. params
$\vec{\vartheta}^{*}$

2:Get: Pool $\mathcal{P}$, accuracy $\varepsilon$, max. loss $\ell$,
$n_{\text{max}}$

3:Initialize: pool $\mathcal{P}^{\prime}\leftarrow\mathcal{P}$, layer
$\mathcal{A}^{\prime}\leftarrow\emptyset$, ansatz circuit
$\Lambda^{\prime}\leftarrow\Lambda$

4:for $n=0,...,n_{\text{max}}$ do

5: Update loss $L^{\prime}\leftarrow
L_{\Lambda^{\prime}(\vec{\vartheta}^{*})}$

6: Set
$A\leftarrow\mathrm{SubpoolExploration}(\mathcal{P}^{\prime},L^{\prime})$

7: if $L^{\prime}(A)<\ell$ then

8: Minimize
$(\theta^{*},\vec{\vartheta}^{*})\leftarrow\operatorname*{arg\,min}_{(\theta,\vec{\vartheta})}E_{A\circ\Lambda^{\prime}}(\theta,\vec{\vartheta})$

9: Set bound $\mathcal{E}^{\prime}\leftarrow
E_{A\circ\Lambda^{\prime}}(\theta^{*},\vec{\vartheta}^{*})$

10: if $\mathcal{E}-\mathcal{E}^{\prime}\geq\varepsilon$ then

11: Update layer $\mathcal{A}\leftarrow\mathcal{A}\cup\\{A\\}$

12: Update ansatz circuit $\Lambda^{\prime}\leftarrow A\circ\Lambda^{\prime}$

13: Update opt. params
$\vec{\vartheta}^{*}\leftarrow(\theta^{*},\vec{\vartheta}^{*})$

14: Reduce pool
$\mathcal{P}^{\prime}\leftarrow\mathcal{P}^{\prime}\setminus\mathcal{N}_{\textrm{G}}(\mathcal{P}^{\prime},A)$

15: if $\mathcal{P}^{\prime}=\emptyset$ then break return Layer
$\mathcal{A}^{\prime}$, optimal params $\vec{\vartheta}^{*}$, bound
$\mathcal{E}$.

Algorithm 6 Dynamic-ADAPT-VQE

1:Initialize state $\rho_{0}\leftarrow\rho_{\text{HF}}$, ansatz circuit
$\Lambda_{0}\leftarrow 1$, pool $\mathcal{P}$.

2:Initialize accuracy $\varepsilon$ and maximal loss $\ell$.

3:Initialize iteration counts $t_{\text{max}},n_{\text{max}}$.

4:Initialize energy bound $\mathcal{E}_{0}\leftarrow\infty$.

5:Initialize optimal params $\vartheta_{0}^{*}$ as empty vector.

6:for $t=1,...,t_{\text{max}}$ do

7:
$\mathcal{A}_{t},\vec{\vartheta}_{t}^{*},\mathcal{E}_{t}\leftarrow\mathrm{BuildDynamicLayer}(L_{\Lambda_{t-1}},\vec{\vartheta}_{t-1}^{*},\mathcal{E}_{t-1})$

8: if $\mathcal{A}_{t}=\emptyset$ then

9: return energy bound $\mathcal{E}_{t}$

10: Set ansatz circuit:
$\Lambda_{t}\leftarrow\mathcal{A}^{\text{o}}_{t}\circ\Lambda_{t-1}$

11:return energy bound $\mathcal{E}_{t_{\text{max}}}$

##  IV Benchmarking Noiseless Performance

In this section, we benchmark various aspects of subpool exploration and
layering in noiseless settings. To this end, we use numerical state-vector
simulations to study a wide variety of molecules summarized in Table 1. While
BeH2 and H2O are among the larger molecules to be benchmarked, H4 and H6 are
prototypical examples of strongly correlated systems. Our simulations
demonstrate the utility of subpool exploration in reducing quantum-processor
calls. Further, we show that when compared to standard ADAPT-VQE, both Static-
and Dynamic-ADAPT-VQE reduce the ansatz circuit depths to similar extents. All
simulations use the QEB pool because it gives a higher resilience to noise
than the fermionic pool and performs similarly to the qubit pool Dalton  _et
al._ (2022). Moreover, unless stated otherwise, we use support commutativity
to ensure that Static-ADAPT-VQE produces ansatz circuits equivalent to TETRIS-
ADAPT-VQE.

###  IV A Efficiency of subpool exploration

Figure 6: Histograms of the relative frequencies of the number of subpools
searched for identifying a suitable ansatz element $m_{s}$ with Explore-ADAPT-
VQE. The mean and uncertainty in the mean are indicated by solid and dashed
lines, respectively.

We begin by illustrating the ability of subpool exploration to reduce the
number of loss function calls when searching for a suitable ansatz element $A$
to append to an ansatz circuit. To this end, we present Explore-ADAPT-VQE
(ADAPT-VQE with subpool exploration) using the QEB pool, Eq. 10, and operator
commutativity. We set the initial subpool, $\mathcal{S}_{0}$, such that it
consists of a single ansatz element selected uniformly at random from the
pool. To provide evidence of a reduction in the number of loss-function calls,
we track the number of subpools searched, $m_{s}$, to find a local minimum.
The results are depicted in Fig. 6. There is a tendency to terminate subpool
exploration after visiting two or three subpools. This should be compared with
the maximum possible QEB-pool values of $m_{s}$: $N-2=6,10,10,12,12$ for H4,
LiH, H6, BeH2, and H2O, respectively. Thus, Fig. 6 shows that subpool
exploration reduces the number of loss-function calls in the cases tested.

###  IV B Reducing ansatz-circuit depth

Figure 7: The energy accuracy is plotted as a function of ansatz-circuit depth
(left) and the number of ansatz-circuit parameters (ansatz elements, right),
for QEB standard, Explore-, Static-(TETRIS)-, and Dynamic-ADAPT-VQE. These
simulations use support commutation. Each row shows data for a specific
molecule. The region of chemical accuracy is shaded.

Next, we compare the ability of Static-(TETRIS)- and Dynamic-ADAPT-VQE to
reduce the depth of the ansatz circuits as compared to standard and Explore-
ADAPT-VQE. The data is depicted in Fig. 7. Here, we depict the energy error,

$\displaystyle\Delta_{t}=\mathcal{E}_{t}-E_{FCI},$ (54)

given as the distance of the VQE predictions $\mathcal{E}_{t}$ from the FCI
ground state energy $E_{FCI}$ as a function of (left) the ansatz-circuit
depths and (right) the number of ansatz-circuit parameters. The left column
shows that layered ADAPT-VQEs achieve lower energy errors with shallower
ansatz circuits. Meanwhile, the right column demonstrates that all ADAPT-VQEs
achieve similar energy accuracy with respect to the number of ansatz-circuit
parameters.

###  IV C Reducing runtime

Figure 8: Energy accuracy against the number of loss function calls. Using the
QEB pool and support commutation, we compare standard-, Explore-,
Static-(TETRIS)-, and Dynamic-ADAPT-VQE. Each row shows data for a specific
molecule, with the number of orbitals increasing up the page. Energy
accuracies better than chemical accuracy are shaded in cream. Figure 9: Energy
accuracy against the number of times the ansatz is optimized (left column);
and the number of expectation values calculated during optimizer calls (right
column). Using the QEB pool and support commutation, we compare standard-,
Explore-, Static-(TETRIS)-, and Dynamic-ADAPT-VQE. Each row shows data for a
specific molecule, with the number of orbitals increasing up the page. Energy
accuracies better than chemical accuracy are shaded in cream.

In this section, we provide numerical evidence that subpool exploration and
layering reduce the runtime of ADAPT-VQE. A mathematical analysis of
asymptotic runtimes will follow in Section V. To provide evidence of a runtime
reduction in numerical simulations, we show that layered ADAPT-VQEs require
fewer expectation value evaluations (and thus shots and quantum processor
runtime) to reach a given accuracy. Our numerical results are depicted in
Figs. 8 and 9 for expectation-value evaluations related to calculating losses
and parameter optimizations, respectively. We now discuss our results.

To convert data accessible in numerical simulations (such as loss function and
optimizer calls) into runtime data (such as expectation values and shots), we
proceed as follows. For our numerical data, we evaluate runtime in terms of
the number of expectation value evaluations rather than processor calls or
shots. This is justified as the number of shots (or processor calls) is
directly proportional to the number of expectation values in our simulations,
as detailed in Appendix B. Next, we evaluate the runtime requirements
associated with loss-function evaluations by tracking the number of times a
loss function is called. The evaluation of the loss function over a subpool
$\mathcal{S}$ is recorded as $\left|\mathcal{S}\right|+1$ expectation-value
evaluations, assuming the use of a finite difference rule. Thus we produce the
data presented in Fig. 8. Finally, we evaluate the runtime requirements of the
optimizer by tracking the number of energy expectation values or gradients it
requests. The gradient of $P$ variables is then recorded as $P+1$ energy
expectation value evaluations, assuming the use of a finite difference rule.
This gives the data in Fig. 9.

In Fig. 8, we show that layered ADAPT-VQEs require fewer loss-related
expectation-value evaluations to reach a given energy accuracy. We attribute
this advantage to subpools gradually shrinking during layer construction. They
thus require fewer loss function evaluations per ansatz element added to the
ansatz-element circuit. We further notice that Explore-ADAPT-VQE does not
reduce the loss-related expectation values required for standard ADAPT-VQE. We
attribute this result to our examples’ small pool sizes, with only 8 to 14
qubits. As qubit sizes increase, we expect a more noticeable advantage for
Explore-ADAPT-VQE, as discussed in Sec. V.

In Fig. 9 (left), we show that Static-ADAPT-VQE reduces the number of
optimizer calls needed to reach a given accuracy. As expected, the left column
shows that Static-ADAPT-VQE calls the optimizer $\mathcal{O}\left(N\right)$
times less than any other algorithm. This is expected, as standard, Explore-,
and Dynamic-ADAPT-VQE calls the optimizer each time a new ansatz element is
added to the ansatz-element circuit. Meanwhile, Static-ADAPT-VQE calls the
optimizer only after adding a whole layer of $\mathcal{O}\left(N\right)$
ansatz elements to the ansatz-element circuit. In Fig. 9 (right), we analyze
how the reduced number of optimizer calls translates to the number of
optimizer-related expectation values required to reach a given accuracy. The
data was obtained using a BFGS optimizer with a gradient norm tolerance of
$10^{-12}$ Ha and a relative step tolerance of zero. Compared to the optimizer
calls on the left of the figure, we notice two trends. Dynamic-ADAPT-VQE,
while being on par with standard and Explore-ADAPT-VQE for optimizer calls,
tends to use a higher number of expectation value evaluations. Similarly,
Static-ADAPT-VQE, while having a clear advantage over standard and Explore-
ADAPT-VQE for optimizer calls, tends to have a reduced advantage (and for LiH,
even a disadvantage) when it comes to optimizer-related expectation value
evaluations. These observations hint towards an increased optimization
difficulty for layered ADAPT-VQEs. These observations may be highly optimizer
dependant and should be further investigated in the future.

###  IV D Additional bemchmarks

We close this section by referring the reader to additional benchmarking data
presented in the appendices. In Appendix C, we compare support to operator
commutativity for the qubit pool. In Appendix D, we compare the steepest-
gradient loss to the largest-energy-reduction loss. We also compare the QEB
pool to the qubit pool in Appendix D.

##  V Runtime analysis

In this section, we analyze the asymptotic runtimes of standard, Explore-,
Dynamic-, and Static-ADAPT-VQE. We find that under reasonable assumptions,
Static-ADAPT-VQE can run up to $\mathcal{O}\left(N^{2}\right)$ faster than
standard ADAPT-VQE. In what follows, we quantify asymptotic runtimes using
$\mathcal{O}\left(x\right)$, $\Omega\left(x\right)$, or $\Theta\left(x\right)$
to state that a quantity scales at most, at least, or exactly with $x$,
respectively. For definitions, see Appendix A. We begin our runtime analysis
by listing some observations, assumptions, and approximations.

  * (a)

Each algorithm operates on $N$ qubits.

  * (b)

Ansatz circuits are improved by successively adding ansatz elements with a
single parameter to the ansatz circuit. This results in iterations
$p=1,...,P$, where the $p$th ansatz circuit has $p$ parameters.

  * (c)

In each iteration $p$, the algorithm spends runtime on evaluating $N_{L}(p)$
loss functions.

  * (d)

In each iteration $p$, the algorithm spends runtime on optimizing $p$ circuit
parameters.

  * (e)

Using the finite difference method, we approximate each of the $N_{L}(p)$ loss
functions in (c) by using two energy-expectation values. This results in
evaluating at most $2N_{L}(p)$ energy expectation values on the quantum
computer in the $p$th iteration.

  * (f)

We assume that the optimizer in (d) performs a heuristic optimization of
ansatz circuits with $p$ parameters in polynomial time. Thus, in the $p$th
iteration, a quantum computer must conduct
$N_{O}(p)=\Theta\left(p^{\alpha}\right)$ evaluations of the energy landscape
and $N_{O}(p)=\Theta\left(p^{\alpha}\right)$ evaluations of energy expectation
values.

  * (g)

For each energy expectation value in (e) and (f), we assume that a constant
number of shots $N_{S}=\Theta\left(1\right)$ is needed to reach a given
accuracy. This is a standard assumption in VQE McArdle  _et al._ (2020); Tilly
_et al._ (2022), and further details justifying this assumption are discussed
in Appendix B.

  * (h)

For each shot in (g), one must execute an ansatz circuit with $p$ ansatz
elements. Here, we assume that the runtime $C(p)$ of an ansatz circuit with
$p$ ansatz elements is proportional to its depth $d(p)$, i.e.,
$C(p)=\Theta\left(d(p)\right)$.

Combining (e,g,h) and (f,g,h), we can estimate the runtime each algorithm
spends on evaluating losses and performing the optimization, respectively:

$\displaystyle R_{L}$
$\displaystyle=\sum_{p=1}^{P}2N_{L}(p)N_{S}C(p)=\sum_{p=1}^{P}N_{L}(p)\Theta\left(d(p)\right),$
(55a) $\displaystyle R_{O}$
$\displaystyle=\sum_{p=1}^{P}N_{O}(p)N_{S}C(p)=\sum_{p=1}^{P}\Theta\left(p^{\alpha}\right)\Theta\left(d(p)\right).$
(55b)

Below we analyze further these runtime estimates for standard, Explore-,
Dynamic-, and Static-ADAPT-VQE.

In standard ADAPT-VQE, we re-evaluate the loss of each ansatz element in every
iteration. Thus, $N_{L}(p)=|\mathcal{P}|$. Moreover, the circuit depth $d(p)$
is upper bounded by $d(p)=\mathcal{O}\left(p\right)$. In the best-case
scenario, ADAPT-VQE may arrange ansatz elements into layers accidentally. (An
effect more likely for large $N$.) This can compress the circuit depths down
to $d=\Omega\left(p/N\right)$. We summarize this range of possible circuit
depths using the compact expression $d(p)=\Theta\left(pN^{-\gamma}\right)$,
with $\gamma\in[0,1]$. In numerical simulations, we typically observe that
$\gamma\approx 0$, i.e., the depth of an ansatz circuit, is proportional to
the number of ansatz elements. These expressions for $N_{L}(p)$ and $d(p)$
allow us to estimate the runtime of standard ADAPT-VQE algorithms:

$\displaystyle R_{L}^{A}=|\mathcal{P}|\Theta\left(P^{2}N^{-\gamma}\right),$
(56a) $\displaystyle
R_{O}^{A}=\Theta\left(P^{2+\alpha_{A}}N^{-\gamma}\right).$ (56b)

Explore-ADAPT-VQE results in circuits of the same depths as ADAPT-VQE, i.e.,
$d=\Theta\left(pN^{-\gamma}\right)$. However, the use of subpool exploration
in Explore-ADAPT-VQE may reduce the number of loss-function evaluations
$N_{L}(p)$. As discussed in Section III B (paragraph on Efficiency), in the
best case scenario, the number of loss function evaluations per iteration is
lower bounded by $N_{L}(p)=\Omega\left(|\mathcal{P}|/N\right)$. In the worst
case scenario, subpool exploration may explore the whole pool of ansatz
elements, such that $N_{L}(p)=\mathcal{O}\left(|\mathcal{P}|\right)$. Based on
these relations, we can estimate the runtime of Explore-ADAPT-VQE:

$\displaystyle R_{L}^{E}$
$\displaystyle=\begin{cases}|\mathcal{P}|\Omega\left(P^{2}N^{-(1+\gamma)}\right)\\\
|\mathcal{P}|\mathcal{O}\left(P^{2}N^{-\gamma}\right)\end{cases},$ (57a)
$\displaystyle R_{O}^{E}$
$\displaystyle=\Theta\left(P^{2+\alpha_{E}}N^{-\gamma}\right).$ (57b)

Dynamic-ADAPT-VQE has the same scaling of the number of loss function
evaluations per iteration, $N_{L}(p)$, as Explore-ADAPT-VQE. Thus,
$N_{L}(p)=\Omega\left(|\mathcal{P}|/N\right)$ in the best case and
$N_{L}(p)=\mathcal{O}\left(|\mathcal{P}|\right)$ in the worst case. The
circuit depth of Dynamic-ADAPT-VQE scales as $d(p)=\Theta\left(p/N\right)$.
One can observe a clear benefit from layering. The upper bound,
$d(p)=\mathcal{O}\left(p\right)$, in standard and Explore-ADAPT-VQE becomes
$d(p)=\mathcal{O}\left(p/N\right)$ in Dynamic-ADAPT-VQE. Using these relations
for $N_{L}(p)$ and $d(p)$, we can estimate the runtime of Dynamic-ADAPT-VQE:

$\displaystyle R_{L}^{D}$
$\displaystyle=\begin{cases}|\mathcal{P}|\Omega\left(P^{2}N^{-2}\right)\\\
|\mathcal{P}|\mathcal{O}\left(P^{2}N^{-1}\right)\end{cases},$ (58a)
$\displaystyle R_{O}^{D}$
$\displaystyle=\Theta\left(P^{2+\alpha_{D}}N^{-1}\right).$ (58b)

The analysis of Static-ADAPT-VQE’s runtime is more straightforward with
respect to the layer count $t$ than to the parameter count $p$. Therefore, we
revisit and modify our previous observations, assumptions, and approximations.

  * (a)

Static-ADAPT-VQE operates on $N$ qubits.

  * (b)

Static-ADAPT-VQE builds ansatz circuits in layers indexed by
$t=1,...,t_{\text{max}}$. The $t$th layer contains
$n_{\textrm{tot}}(t)=\Theta\left(N\right)$ ansatz elements. Since each ansatz
element depends on a single parameter, a layer contains
$n_{\textrm{tot}}(t)=\Theta\left(N\right)$ circuit parameters. Summing the
parameters in each layer gives the total number of parameters in the circuit:
$P=\sum_{t=1}^{t_{\text{max}}}n_{\textrm{tot}}(t)$.

  * (c)

For each layer $t$, Static-ADAPT-VQE spends runtime on evaluating the loss of
$N_{L}(t)=|\mathcal{P}|$ ansatz elements.

  * (d)

For each layer $t$, Static-ADAPT-VQE spends runtime on optimizing
$p(t)=\sum_{t^{\prime}=1}^{t}n_{\textrm{tot}}(t^{\prime})=\Theta\left(N\right)t$
circuit parameters.

  * (e)

Using the finite difference method, we approximate each of the $N_{L}(t)$ loss
functions in (c) by using two energy expectation values. This results in
evaluating at most $2N_{L}(t)=2|\mathcal{P}|$ energy expectation values on the
quantum computer in the $t$th iteration.

  * (f)

Again, we assume that the optimizer in (d) performs a heuristic optimization
of ansatz circuits with $p(t)$ parameters in polynomial time. Thus, in the
$t$th layer a quantum computer must conduct
$N_{O}(t)=\Theta\left(p(t)^{\alpha_{S}}\right)$ evaluations of the energy
landscape and $N_{O}(t)=\Theta\left(p(t)^{\alpha_{S}}\right)$ evaluations of
energy expectation values. Using $p(t)=\Theta\left(N\right)t$ from (d), this
implies that $N_{O}(t)=\Theta\left(N^{\alpha_{S}}t^{\alpha_{S}}\right)$.

  * (g)

As before, for each energy expectation value in (e) and (f), we assume that a
constant number of shots $N_{S}=\Theta\left(1\right)$ is needed to reach a
given accuracy.

  * (h)

For each shot in (g), one must execute an ansatz circuit with $p(t)$ ansatz
elements. Again, we assume that the runtime $C(t)$ of an ansatz circuit with
$p(t)$ ansatz elements is proportional to its depth $d(p(t))$, i.e.,
$C(t)=\Theta\left(d(p(t))\right)$. Due to layering, the circuit depth of
Static-ADAPT-VQE scales as $d(p)=\Theta\left(p/N\right)$. (This scaling is
identical for Dynamic-ADAPT-VQE.) This results in
$C(t)=\Theta\left(p(t)/N\right)$. Further, using $p(t)=\Theta\left(N\right)t$
from (d), we find that each shot in (g) requires a circuit runtime of
$C(t)=\Theta\left(t\right)$.

Combining the updated (e,g,h) and (f,g,h), we find the loss- and optimization-
related runtimes of Static-ADAPT-VQE, respectively:

$\displaystyle R_{L}^{S}$
$\displaystyle=\sum_{t=1}^{t_{\text{max}}}2N_{L}(t)N_{S}C(t)=|\mathcal{P}|\Theta\left(t_{\text{max}}^{2}\right),$
(59a) $\displaystyle R_{O}^{S}$
$\displaystyle=\sum_{t=1}^{t_{\text{max}}}N_{O}(t)N_{S}C(t)=\Theta\left(N^{\alpha_{S}}t_{\text{max}}^{\alpha_{S}+2}\right).$
(59b)

Since $P=\Theta\left(N\right)t_{\text{max}}$ implies
$t_{\text{max}}=P\Theta\left(N^{-1}\right)$, we can simplify these runtime
estimates:

$\displaystyle R_{L}^{S}$
$\displaystyle=|\mathcal{P}|\Theta\left(P^{2}N^{-2}\right),$ (60a)
$\displaystyle R_{O}^{S}$
$\displaystyle=\Theta\left(P^{2+\alpha_{S}}N^{-2}\right).$ (60b)

We summarize this section by listing the ratios of asymptotic runtimes for
Explore-, Dynamic-, and Static-ADAPT-VQE divided by the asymptotic runtime of
standard ADAPT-VQE in Table 2. Here, we assume equal polynomial scaling
($\alpha_{A}=\alpha_{E}=\alpha_{D}=\alpha_{S}$) of the optimization runtime
for standard, Explore, Dynamic-, and Static-ADAPT-VQE. As expected from our
numerical runtime analysis in Section IV C, for typical ADAPT-VQE circuit
depth (where $\gamma=0$), Static-ADAPT-VQE can provide the largest runtime
reduction. This reduction is quadratic in the number of qubits:
$\Theta\left(N^{-2}\right)$. Further improvements to bounding the number of
losses in Explore- and Dynamic-ADAPT-VQE are discussed in Appendix I.

Algorithm |  | $R_{L}/R_{L}^{\text{ADAPT}}$ |  | $R_{O}/R_{O}^{\text{ADAPT}}$
---|---|---|---|---
Explore |  |  $\Omega\left(N^{-1}\right)$, $\mathcal{O}\left(1\right)$ |  | $\Theta\left(1\right)$
Dynamic |  |  $\Omega\left(N^{-2+\gamma}\right)$, $\mathcal{O}\left(N^{-1+\gamma}\right)$ |  | $\Theta\left(N^{-1+\gamma}\right)$
Static |  | $\Theta\left(N^{-2+\gamma}\right)$ |  | $\Theta\left(N^{-2+\gamma}\right)$
Table 2: The ratio of the runtimes of the listed algorithms to the runtime of
standard ADAPT-VQE. $N$ is the qubit number, and $P$ is the number of
parameters in the final ansatz circuit. See text for further explanation.

##  VI Noise

Figure 10: Circuit diagram visualizing the layer-by-layer noise model: on the
left, a noiseless ansatz-element layer with two support-commuting ansatz
elements is decomposed into columns of native gates. On the right, noise is
added to the ansatz-element layer. For global amplitude damping (or dephasing)
noise, the channel $\mathcal{F}$ (or $\mathcal{C}$) is applied to each qubit.
For local depolarizing noise, the channels $\mathcal{D}$ are applied to the
target of the noisy (two-qubit, CNOT) gate.

In this section, we explore the benefits of reducing ADAPT-VQEs’ ansatz-
circuit depths with respect to noise. Our main finding is that the use of
layering to reduce ansatz-circuit depths mitigates global amplitude-damping
and global dephasing noise, where idling and non-idling qubits are affected
alike. However, reduced ansatz-circuit depths do not mitigate the effect of
local depolarizing noise, which exclusively affects qubits operated on by
noisy (two-qubit, CNOT) gates. The explanation for this, we show, is that the
ansatz-circuit depth is a good predictor for the effect of global amplitude-
damping and dephasing noise. On the other hand, we show that the errors
induced by local depolarizing noise are approximately proportional, not to the
depth, but to the number of (CNOT) gates. For this reason, a shallower ansatz
circuit with the same number of noisy two-qubit gates will not reduce the
sensitivity to depolarizing noise.

###  VI A Noise models

Our noise models focus on superconducting architectures, where the native
gates are arbitrary single-qubit rotations and two-qubit CZ or iSWAP gates
Krantz  _et al._ (2019). Further, we assume all-to-all connectivity. We tune
our analysis towards the ibmq_quito (IBM Quantum Falcon r4T) processor. For
this processor, the quoted two-qubit gate times are for CNOT gates. Thus, we
will take CNOT gates to be our native two-qubit gate. To this end, our
simulations use one- and two-qubit gate-execution times of
$35.5\text{\,}\mathrm{ns}$ and $295.1\text{\,}\mathrm{ns}$,
respectively.111These values were taken from the IBM Quantum services. Similar
native gates and execution times apply to silicon quantum processors Stano and
Loss (2022).

In our simulations, we model amplitude damping of a single qubit by the
standard amplitude-damping channel. (For detailed expressions of the
amplitude-damping channel and the other noise channels we use, see Section
K.1.) Its decay constant is determined by the inverse $T_{1}$ time:
$\omega_{1}=1/T_{1}$. Similarly, we model dephasing of a single qubit by the
standard dephasing channel. The $T_{1}$ and $T_{2}^{*}$ times determine its
phase-flip probability via the decay constant
$\omega_{z}=2/T_{2}^{*}-1/T_{1}$. Finally, we model depolarization of a single
qubit by a symmetric depolarizing channel with depolarization strength
$p\in[0,1]$, where $p=0$ leaves a pure qubit pure and $p=1$ brings it to the
maximally mixed state.

In our simulations, we model the effects of amplitude damping, dephasing, and
depolarizing noise on the ansatz circuits $\Lambda_{t}$ in a layer-by-layer
approach. This is illustrated in Fig. 10. We decompose the ansatz circuit
$\Lambda_{t}$ into $l=1,...,L_{t}$ layers of support-commuting ansatz-element
layers $\left\\{\mathcal{A}_{l}\right\\}$:

$\displaystyle\Lambda_{t}=\mathcal{A}^{\text{o}}_{L_{t}}\circ\cdots\circ\mathcal{A}^{\text{o}}_{l}\circ\cdots\circ\mathcal{A}^{\text{o}}_{1}.$
(61)

For amplitude damping and dephasing noise, each ansatz-element layer
$\mathcal{A}^{\text{o}}_{l}$ is transpiled into columns of native gates that
can be implemented in parallel (see Ref. Yordanov  _et al._ (2020) for more
details). The native gate with the longest execution time of each native-gate
column sets the column execution time. The sum of the column execution times
then gives the execution time $\tau_{l}$ of the ansatz-element layer
$\mathcal{A}^{\text{o}}_{l}$. After each ansatz-element layer
$\mathcal{A}^{\text{o}}_{l}$, amplitude damping is implemented by applying an
amplitude-damping channel to every qubit $r=1,...,N$ in an amplitude-damping
layer. This results in an amplitude-damped ansatz circuit
$\Lambda_{t}(\omega_{1})$. Similarly, after each ansatz-element layer
$\mathcal{A}^{\text{o}}_{l}$, dephasing is implemented by applying a dephasing
channel to every qubit $r=1,...,N$ in a dephasing layer. This results in a
dephased ansatz circuit $\Lambda_{t}(\omega_{z})$. Finally, for depolarizing
noise, we apply the whole ansatz-element layer and then a depolarizing channel
to each qubit. The strength of a qubit’s depolarizing channel is determined by
the exact number of times that the qubit was the target in a CNOT gate in the
preceding layer. This results in a depolarized ansatz circuit
$\Lambda_{t}(p)$. For a visualization of our layer-by-layer-based noise model,
see Fig. 10. For detailed mathematical expressions, see Section K.2.

We note that applying the noise channels after each ansatz-element layer could
be refined by applying the noise channels after each gate in the ansatz-
element layer. However, as shown in Ref. Dalton  _et al._ (2022), such a gate-
by-gate noise model, as opposed to our layer-by-layer based noise model, would
increase computational costs and has limited effect on the results. In what
follows, we collectively refer to amplitude-damped ansatz circuits
$\Lambda_{t}(\omega_{1})$, dephased ansatz circuits $\Lambda_{t}(\omega_{z})$,
and depolarized ansatz circuits $\Lambda_{t}(p)$ as $\Lambda_{t}(\alpha)$.
Here, $\alpha$ refers to the key noise parameters $\omega_{1}$, $\omega_{z}$,
or $p$ of each respective noise model.

###  VI B Energy error and noise susceptibility

Figure 11: Energy error $\Delta_{t}(\alpha)$ for an ansatz circuit
$\Lambda_{t}$ of H4 as a function of noise strength $\alpha$. Connected dots
are calculated using full density-matrix simulations. Dashed lines show the
corresponding extrapolation using noise susceptibility.

Going forward, we analyze the effect of noise on the energy error [c.f. Eq.
54]

$\displaystyle\Delta_{t}(\alpha)=\mathcal{E}_{t}(\alpha)-E_{FCI}.$ (62)

$\Delta_{t}(\alpha)$ now depends, not only on the iteration step $t$, but also
the noise parameter $\alpha$, via the noise-dependent expectation value

$\displaystyle\mathcal{E}_{t}(\alpha)=\tr\left[H\Lambda_{t}(\alpha)\left[\rho_{0}\right]\right].$
(63)

To analyze the energy error, we expand the methodology of Ref. Dalton  _et
al._ (2022). More specifically, we decompose the energy error into two
contributions:

$\displaystyle\Delta_{t}(\alpha)=\Delta_{t}(0)+\left[\Delta_{t}(\alpha)-\Delta_{t}(0)\right].$
(64)

The first term, $\Delta_{t}(0)$, is the energy error of the noiseless ansatz
circuit. The second term, $\Delta_{t}(\alpha)-\Delta_{t}(0)$, is the energy
error due to noise. Subsequently, we Taylor expand the energy error due to
noise to first order:

$\displaystyle\left[\Delta_{t}(\alpha)-\Delta_{t}(0)\right]=\chi_{t}\alpha+\mathcal{O}\left(\alpha^{2}\right).$
(65)

As depicted in Fig. 11, in the regime of small noise parameters $\alpha$
(where energy errors are below chemical accuracy), the linear approximation is
an excellent predictor for the energy error. Conveniently, this allows us to
summarize the effect of noise on the energy error through the noise
susceptibility $\chi_{t}$, defined as

$\displaystyle\chi_{t}\coloneqq\left.\frac{\partial\mathcal{E}_{t}(\alpha)}{\partial\alpha}\right|_{\alpha=0}=\tr\left[H\left.\frac{\partial\Lambda_{t}(\alpha)}{\partial\alpha}\right|_{\alpha=0}\left[\rho_{0}\right]\right].$
(66)

In Appendix L, we calculate the noise susceptibility $\chi_{t}$ of amplitude
damping $\mathcal{F}$, dephasing $\mathcal{C}$, and depolarizing $\mathcal{D}$
noise:

$\displaystyle\chi_{t}^{\mathcal{F}}$
$\displaystyle\coloneqq\left.\frac{\partial\mathcal{E}_{t}(\omega_{1})}{\partial\omega_{1}}\right|_{\omega_{1}=0}=L_{t}N\times
d\mathcal{E}(\Lambda_{t},\mathcal{F}),$ (67a)
$\displaystyle\chi_{t}^{\mathcal{C}}$
$\displaystyle\coloneqq\left.\frac{\partial\mathcal{E}_{t}(\omega_{z})}{\partial\omega_{z}}\right|_{\omega_{z}=0}=L_{t}N\times
d\mathcal{E}(\Lambda_{t},\mathcal{C}),$ (67b)
$\displaystyle\chi_{t}^{\mathcal{D}}$
$\displaystyle\coloneqq\left.\frac{\partial\mathcal{E}_{t}(p)}{\partial
p}\right|_{p=0}=N_{II}\times d\mathcal{E}(\Lambda_{t},\mathcal{D}),$ (67c)

respectively. Here, $N$ denotes the number of qubits; $L_{t}$ is the number of
ansatz-element layers in the ansatz circuit $\Lambda_{t}$; $N_{II}$ is the
number of noisy (two-qubit, CNOT) gates in the ansatz circuit $\Lambda_{t}$;
and the $d\mathcal{E}$’s denote the average energy fluctuations, defined in
Eqs. (248) of Appendix L. As discussed further in Appendix L, the average
energy fluctuations can be calculated from noiseless expectation values. This
allows us to compute the noise susceptibility with faster state-vector
simulations rather than computationally demanding density-matrix simulations.

###  VI C Benchmarking layered circuits with noise

Figure 12: Amplitude-damping noise susceptibility as a function of (left)
energy accuracy and (right) the number of parameters in ansatz circuits
$\Lambda_{t}$. QEB-ADAPT is compared to support-based Dynamic-ADAPT-VQE. Each
row shows data for a specific molecule, with the number of orbitals increasing
up the page. Energy accuracies better than chemical accuracy are shaded in
cream. Figure 13: Same as Fig. 12, but for dephasing noise. Figure 14: Same as
Fig. 12, but for depolarizing noise. In addition, black crosses correspond to
density matrix simulations corroborating noise susceptibility via finite
differences. The black crosses are discussed further in Appendix E.

In this section, we compare the noise susceptibility of standard, Static-
(TETRIS-), and Dynamic-ADAPT-VQE in the presence of noise. As before, we
showcase these algorithms on a range of molecules (summarized in Table 1)
using the QEB pool with support commutativity. When performing our comparison,
we grow the ansatz circuits $\Lambda_{t}$ and optimize its parameters in
noiseless settings, as previously discussed in Dalton  _et al._ (2022). We
then compute the noise susceptibility of $\Lambda_{t}$ as described in the
previous section. The results for amplitude damping, dephasing, and
depolarizing noise are depicted in Fig. 12, Fig. 13, and Fig. 14,
respectively. In all three figures, we plot the noise susceptibility as a
function of (left) the noiseless energy accuracy $\Delta_{t}(0)$ or (right)
the number of parameters. The rows of each plot depict different molecules in
order of increasing spin orbitals from bottom to top: H4, H6, LiH, BeH2, and
H2O.

Layering benefits:— From Fig. 12, it is evident that layering is successful in
mitigating the effect of amplitude-damping noise. Here, we observe that the
noise susceptibility of Static- and Dynamic-ADAPT-VQE is approximately half
that of standard ADAPT-VQE. This is a clear indication that layering can
reduce the effect of noise. In Fig. 13, we observe that layering also tends to
reduce the noise susceptibility in the presence of dephasing noise. However,
in this scenario, the advantage is less consistent across different ansatz
circuits and molecules. Finally, in Fig. 14, we observe that for depolarizing
noise, all algorithms tend to produce similar noise susceptibilities.
Sometimes one shows an advantage over the other, and vice versa, depending on
the ansatz circuit and molecule. Our simulations indicate no clear
disadvantage of using layering in the presence of depolarizing noise. In
summary, our numerical simulations suggest that layering is useful for
mitigating global amplitude damping and dephasing noise. Moreover, layering
seems to have neither a beneficial nor a detrimental effect in the presence of
local depolarizing noise. In order to explain these findings, we further
investigate the dependence of noise susceptibility on several circuit
parameters in Sec. VI D.

Gate-fidelity requirements:— We now use the noise susceptibility data in Fig.
12, Fig. 13, and Fig. 14 to estimate the fidelity requirements for operating
ADAPT-VQEs. For this estimation, recall that quantum chemistry simulations of
energy eigenvalues target an accuracy of $1.6$ $\mathrm{mHa}$. To achieve this
chemical accuracy, we require the energy error due to noise to be smaller than
$\approx 1$ milli-Hartree: $\chi_{t}\alpha\lesssim 1\mathrm{mHa}$. Applying
this condition to amplitude damping (where $\alpha=1/T_{1}$), dephasing (where
$\alpha\approx 1/T_{2}^{*}$), and depolarizing noise (where $\alpha=p$), we
find a set of gate fidelity requirements:

$\displaystyle T_{1}\gtrsim\frac{\chi_{t}^{\mathcal{F}}}{1\mathrm{mHa}},\quad
T_{2}^{*}\gtrsim\frac{\chi_{t}^{\mathcal{C}}}{1\mathrm{mHa}},\quad
p\lesssim\frac{1\mathrm{mHa}}{\chi_{t}^{\mathcal{D}}}.$ (68)

The data presented in Figs. 12, 13, and 14, suggests the following
requirements for the gate operations to enable chemically accurate
simulations:

$\displaystyle T_{1}\gtrsim 1\mathrm{s},\quad T_{2}^{*}\gtrsim
100\mathrm{ms},\quad p\lesssim 10^{-6}.$ (69)

A more detailed breakdown of the maximal $p$ and minimal $T_{1}$ and
$T_{2}^{*}$ times for each algorithm and molecule is presented in Fig. 15.
These requirements are beyond the current state-of-the-art quantum processors
Ding  _et al._ (2023); Stano and Loss (2022). How much these requirements can
be improved by error-mitigation techniques Cai  _et al._ (2023) remains an
open question for future research.

Figure 15: The ratio of the minimal $T_{1}$ and $T_{2}^{*}$ times and maximal
depolarizing probability $p$ for Dynamic- and Static-ADAPT-VQE to standard
ADAPT-VQE required to reach an accuracy of $\Delta=10^{-7}$ $\mathrm{mHa}$ for
each molecule. Figure 16: Noise susceptibility for (a) amplitude-damping, (b)
dephasing, and (c) depolarizing noise as a function of (a, b) ansatz-circuit
depths $d$ and (c) the number of noisy CNOT-gates $N_{II}$. The top panels
show noise susceptibility as a function of $d$ (a, b) and $N_{II}$ (c). The
bottom panels of (a) and (b) show noise susceptibility divided by $d$, as a
function $d$. The bottom panel of (c) shows noise susceptibility divided by
$N_{II}$ as a function of $N_{II}$. The colored lines correspond to the
simulation of Dynamic-ADAPT-VQE using support commutation for a range of
molecules. The black lines represent simulations based on QEB-ADAPT-VQE.

###  VI D Noise-susceptibility scalings

In this section, we investigate the dependence of noise susceptibility on
basic circuit parameters, such as the number of qubits $N$, circuit depth
$d\propto L_{t}$, or the number of noisy (two-qubit, CNOT) gates $N_{II}$. Our
analysis will help in understanding why layering can mitigate global amplitude
damping and dephasing noise but not local depolarizing noise.

We study numerically how noise susceptibility scales with circuit depth and
the number of noisy (two-qubit, CNOT) gates $N_{II}$. The data is presented
Fig. 16. The top panels show the noise susceptibility in the presence of
amplitude damping (left), dephasing (center), and depolarizing noise (right)
for various algorithms and molecules. The noise-susceptibility data is
presented on a log-log plot as a function of circuit depths $d$ (left and
center) as well as $N_{II}$ (right), respectively. From Fig. 16, we find that
the noise susceptibility scales roughly linearly with the plotted parameters.
To further analyze this rough linearity, we produce a log-log plot in the
bottom panels of $\chi_{t}^{\mathcal{F}}/d$ (left), $\chi_{t}^{\mathcal{C}}/d$
(center), and $\chi_{t}^{\mathcal{D}}/N_{II}$ (right) as a function of $d$,
$d$, and $N_{II}$, respectively. Had the scalings of interest been linear, the
bottom panels would have depicted constant curves. This is not entirely the
case. But, the curves’ deviations from constants are sufficiently sublinear to
support our claim that the curves in the upper plots are roughly linear.

The scalings observed in Fig. 16 confirm our previous intuition. Based on Eq.
67, and using the assumption that $d\mathcal{E}$ is roughly constant, we would
expect that the noise susceptibility in the presence of amplitude damping or
dephasing noise is proportional to the circuit depth and the number of qubits:

$\displaystyle\chi_{t}^{\mathcal{F}}\mathchoice{\mathrel{\vbox{
\offinterlineskip\halign{\hfil$#$\cr\displaystyle\propto\cr\kern
2.0pt\cr\displaystyle\sim\cr\kern-2.0pt\cr}}}}{\mathrel{\vbox{
\offinterlineskip\halign{\hfil$#$\cr\textstyle\propto\cr\kern
2.0pt\cr\textstyle\sim\cr\kern-2.0pt\cr}}}}{\mathrel{\vbox{
\offinterlineskip\halign{\hfil$#$\cr\scriptstyle\propto\cr\kern
2.0pt\cr\scriptstyle\sim\cr\kern-2.0pt\cr}}}}{\mathrel{\vbox{
\offinterlineskip\halign{\hfil$#$\cr\scriptscriptstyle\propto\cr\kern
2.0pt\cr\scriptscriptstyle\sim\cr\kern-2.0pt\cr}}}}Nd\quad\text{and}\quad\chi_{t}^{\mathcal{C}}\mathchoice{\mathrel{\vbox{
\offinterlineskip\halign{\hfil$#$\cr\displaystyle\propto\cr\kern
2.0pt\cr\displaystyle\sim\cr\kern-2.0pt\cr}}}}{\mathrel{\vbox{
\offinterlineskip\halign{\hfil$#$\cr\textstyle\propto\cr\kern
2.0pt\cr\textstyle\sim\cr\kern-2.0pt\cr}}}}{\mathrel{\vbox{
\offinterlineskip\halign{\hfil$#$\cr\scriptstyle\propto\cr\kern
2.0pt\cr\scriptstyle\sim\cr\kern-2.0pt\cr}}}}{\mathrel{\vbox{
\offinterlineskip\halign{\hfil$#$\cr\scriptscriptstyle\propto\cr\kern
2.0pt\cr\scriptscriptstyle\sim\cr\kern-2.0pt\cr}}}}Nd.$ (86)

This claim is supported by Fig. 16. Moreover, previous studies Dalton  _et
al._ (2022) have found that the noise susceptibility scales linearly with the
number of depolarizing two-qubit gates:

$\displaystyle\chi_{t}^{\mathcal{D}}\mathchoice{\mathrel{\vbox{
\offinterlineskip\halign{\hfil$#$\cr\displaystyle\propto\cr\kern
2.0pt\cr\displaystyle\sim\cr\kern-2.0pt\cr}}}}{\mathrel{\vbox{
\offinterlineskip\halign{\hfil$#$\cr\textstyle\propto\cr\kern
2.0pt\cr\textstyle\sim\cr\kern-2.0pt\cr}}}}{\mathrel{\vbox{
\offinterlineskip\halign{\hfil$#$\cr\scriptstyle\propto\cr\kern
2.0pt\cr\scriptstyle\sim\cr\kern-2.0pt\cr}}}}{\mathrel{\vbox{
\offinterlineskip\halign{\hfil$#$\cr\scriptscriptstyle\propto\cr\kern
2.0pt\cr\scriptscriptstyle\sim\cr\kern-2.0pt\cr}}}}N_{II}.$ (95)

Also, this claim is supported by Fig. 16.

Thus, for global (amplitude damping and dephasing) noise, which affects idling
and non-idling qubits alike, our analysis indicates that circuit depth is a
good predictor of noise susceptibility. On the other hand, for local
(depolarizing) noise, which affects only the qubits which are nontrivially
operated on, $N_{II}$ is a good predictor of the noise susceptibility.
Consequently, we expect that compressing the depth of an ansatz circuit by
layering can mitigate noise in the former, but not the latter, of these
settings.

##  VII Summary and Conclusion

In this paper, we introduced layering and subpool-exploration strategies for
ADAPT-VQEs that reduced circuit depth, runtime, and susceptibility to noise.
In noiseless numerical simulations, we demonstrate that layering reduces the
depths of an ansatz circuit when compared to standard ADAPT-VQE. We further
showed that our layering algorithms achieve circuits that are as shallow as
TETRIS-ADAPT-VQE. The reduction in ansatz circuit depth is achieved without
increasing the number of ansatz elements, circuit parameters, or CNOT gates in
the ansatz circuit. The noiseless numerical simulations further provide
evidence that layering and subpool-exploration can reduce the runtime of
ADAPT-VQE by up to $\mathcal{O}\left(N^{2}\right)$, where $N$ is the number of
qubits in the simulation. Finally, we benchmarked the effect of reducing the
depth of ADAPT-VQEs on the algorithms’ noise susceptibility. For global noise
models, which affect idling and non-idling qubits alike (such as our
amplitude-damping and dephasing model), we show that the noise susceptibility
is approximately proportional to the ansatz-circuit depth. For these noise
models, reduced circuit depth due to layering is beneficial in reducing the
noise susceptibility of ADAPT-VQEs. For local noise models, where only non-
idling qubits are affected by noise (as with our depolarizing noise model), we
show that the noise susceptibility is approximately proportional to the number
of noisy (two-qubit, CNOT) gates. For these noise models, layering strategies
are neither useful nor harmful, as they hardly change the CNOT count of ADAPT-
VQEs. We finish our paper by stating three conclusions from our work.

To layer or not to layer?:—Depending on the dominant noise source of a quantum
processor, layering may or may not lead to improved noise resilience. For
processors where global noise dominates, we recommend layering.

Static or dynamic layering?:—Our paper considered static and dynamic layering.
Which of the two should be used? Static layering optimizes each layer once,
while dynamic layering optimizes the ansatz after adding each ansatz element.
Both layering strategies lead to ansatz circuits of similar depths and require
a similar number of parameters and CNOT gates to reach a certain energy
accuracy. However, static layering calculates significantly fewer energy
expectation values on the quantum processor. Therefore, we recommend static
layering for the small molecules studied in this work. For larger molecules,
dynamic layering could be preferable.

How useful is subpool exploration?:—Our paper introduced a new pool-
exploration strategy, that reduces the number of loss-function evaluations
and, thereby, the number of calls to the quantum processor. However, in the
examples studied in this work, the number of loss-function evaluations was
exceeded by the energy-expectation-value calls. Thus, subpool exploration had
little impact on the algorithms. Again, this could change when larger
molecules are studied.

### Acknowledgements

The authors thank Yordan S. Yordanov for the use of his codebase for VQE
protocols and Wilfred Salmon for insightful discussions. We further thank
Sophia E Economou, Nicholas J Mayhall, Edwin Barnes, Panagiotis G Anastasiou
and the Virginia Tech group for fruitful discussions. We acknowledge the use
of IBM Quantum services for this work. The views expressed are those of the
authors, and do not reflect the official policy or position of IBM or the IBM
Quantum team.

## References

  * McArdle  _et al._ (2020) S. McArdle, S. Endo, A. Aspuru-Guzik, S. C. Benjamin, and X. Yuan, Rev. Mod. Phys. 92, 015003 (2020).
  * Hartree and Hartree (1935) D. R. Hartree and W. Hartree, Proc. Math. Phys. Eng. Sci. 150, 9 (1935).
  * Kohn and Sham (1965) W. Kohn and L. J. Sham, Phys. Rev. 140, A1133 (1965).
  * Hohenberg and Kohn (1964) P. Hohenberg and W. Kohn, Phys. Rev. 136, B864 (1964).
  * Rossi  _et al._ (1999) E. Rossi, G. L. Bendazzoli, S. Evangelisti, and D. Maynau, Chem. Phys. Lett. 310, 530 (1999).
  * Bauer  _et al._ (2020) B. Bauer, S. Bravyi, M. Motta, and G. K.-L. Chan, Chem. Rev. 120, 12685 (2020).
  * Peruzzo  _et al._ (2014) A. Peruzzo, J. McClean, P. Shadbolt, M.-H. Yung, X.-Q. Zhou, P. J. Love, A. Aspuru-Guzik, and J. L. O’Brien, Nat. Commun. 5, 4213 (2014).
  * Tilly  _et al._ (2022) J. Tilly, H. Chen, S. Cao, D. Picozzi, K. Setia, Y. Li, E. Grant, L. Wossnig, I. Rungger, G. H. Booth, and J. Tennyson, Phys. Rep. 986, 1 (2022).
  * Romero  _et al._ (2018) J. Romero, R. Babbush, J. R. McClean, C. Hempel, P. J. Love, and A. Aspuru-Guzik, Quantum Sci. Technol. 4, 014008 (2018).
  * Grimsley  _et al._ (2019) H. R. Grimsley, S. E. Economou, E. Barnes, and N. J. Mayhall, Nat. Commun. 10, 3007 (2019).
  * Yordanov  _et al._ (2021) Y. S. Yordanov, V. Armaos, C. H. W. Barnes, and D. R. M. Arvidsson-Shukur, Commun. Phys. 4, 228 (2021).
  * Yordanov  _et al._ (2022) Y. S. Yordanov, C. H. W. Barnes, and D. R. M. Arvidsson-Shukur, Phys. Rev. A 106, 032434 (2022).
  * Tang  _et al._ (2021) H. L. Tang, V. Shkolnikov, G. S. Barron, H. R. Grimsley, N. J. Mayhall, E. Barnes, and S. E. Economou, PRX Quantum 2, 020310 (2021).
  * Dalton  _et al._ (2022) K. Dalton, C. K. Long, Y. S. Yordanov, C. G. Smith, C. H. W. Barnes, N. Mertig, and D. R. M. Arvidsson-Shukur, “Variational quantum chemistry requires gate-error probabilities below the fault-tolerance threshold,” (2022), arXiv:2211.04505 [quant-ph] .
  * Anastasiou  _et al._ (2022) P. G. Anastasiou, Y. Chen, N. J. Mayhall, E. Barnes, and S. E. Economou, “Tetris-adapt-vqe: An adaptive algorithm that yields shallower, denser circuit ansätze,” (2022), arXiv:2209.10562 [quant-ph] .
  * Liu  _et al._ (2022) X. Liu, A. Angone, R. Shaydulin, I. Safro, Y. Alexeev, and L. Cincio, IEEE Trans. Quantum Eng. 3, 1 (2022).
  * Google AI Quantum And Collaborators  _et al._ (2020) Google AI Quantum And Collaborators, F. Arute, K. Arya, R. Babbush, D. Bacon, J. C. Bardin, R. Barends, S. Boixo, M. Broughton, B. B. Buckley, D. A. Buell, B. Burkett, N. Bushnell, Y. Chen, Z. Chen, B. Chiaro, R. Collins, W. Courtney, S. Demura, A. Dunsworth, E. Farhi, A. Fowler, B. Foxen, C. Gidney, M. Giustina, R. Graff, S. Habegger, M. P. Harrigan, A. Ho, S. Hong, T. Huang, W. J. Huggins, L. Ioffe, S. V. Isakov, E. Jeffrey, Z. Jiang, C. Jones, D. Kafri, K. Kechedzhi, J. Kelly, S. Kim, P. V. Klimov, A. Korotkov, F. Kostritsa, D. Landhuis, P. Laptev, M. Lindmark, E. Lucero, O. Martin, J. M. Martinis, J. R. McClean, M. McEwen, A. Megrant, X. Mi, M. Mohseni, W. Mruczkiewicz, J. Mutus, O. Naaman, M. Neeley, C. Neill, H. Neven, M. Y. Niu, T. E. O’Brien, E. Ostby, A. Petukhov, H. Putterman, C. Quintana, P. Roushan, N. C. Rubin, D. Sank, K. J. Satzinger, V. Smelyanskiy, D. Strain, K. J. Sung, M. Szalay, T. Y. Takeshita, A. Vainsencher, T. White, N. Wiebe, Z. J. Yao, P. Yeh, and A. Zalcman, Science 369, 1084 (2020).
  * O’Malley  _et al._ (2016) P. J. J. O’Malley, R. Babbush, I. D. Kivlichan, J. Romero, J. R. McClean, R. Barends, J. Kelly, P. Roushan, A. Tranter, N. Ding, B. Campbell, Y. Chen, Z. Chen, B. Chiaro, A. Dunsworth, A. G. Fowler, E. Jeffrey, E. Lucero, A. Megrant, J. Y. Mutus, M. Neeley, C. Neill, C. Quintana, D. Sank, A. Vainsencher, J. Wenner, T. C. White, P. V. Coveney, P. J. Love, H. Neven, A. Aspuru-Guzik, and J. M. Martinis, Phys. Rev. X 6, 031007 (2016).
  * Kandala  _et al._ (2017) A. Kandala, A. Mezzacapo, K. Temme, M. Takita, M. Brink, J. M. Chow, and J. M. Gambetta, Nature 549, 242 (2017).
  * Hempel  _et al._ (2018) C. Hempel, C. Maier, J. Romero, J. McClean, T. Monz, H. Shen, P. Jurcevic, B. P. Lanyon, P. Love, R. Babbush, A. Aspuru-Guzik, R. Blatt, and C. F. Roos, Phys. Rev. X 8, 031022 (2018).
  * Xue  _et al._ (2022) X. Xue, M. Russ, N. Samkharadze, B. Undseth, A. Sammak, G. Scappucci, and L. M. K. Vandersypen, Nature 601, 343 (2022).
  * McClean  _et al._ (2018) J. R. McClean, S. Boixo, V. N. Smelyanskiy, R. Babbush, and H. Neven, Nat. Commun. 9, 4812 (2018).
  * Arrasmith  _et al._ (2021) A. Arrasmith, M. Cerezo, P. Czarnik, L. Cincio, and P. J. Coles, Quantum 5, 558 (2021).
  * Cerezo and Coles (2021) M. Cerezo and P. J. Coles, Quantum Sci. Technol. 6, 035006 (2021).
  * Wang  _et al._ (2021) S. Wang, E. Fontana, M. Cerezo, K. Sharma, A. Sone, L. Cincio, and P. J. Coles, Nat. Commun. 12, 6961 (2021).
  * De Palma  _et al._ (2023) G. De Palma, M. Marvian, C. Rouzé, and D. S. França, PRX Quantum 4, 010309 (2023).
  * Grimsley  _et al._ (2023) H. R. Grimsley, G. S. Barron, E. Barnes, S. E. Economou, and N. J. Mayhall, Npj Quantum Inf. 9, 19 (2023).
  * Yordanov  _et al._ (2020) Y. S. Yordanov, D. R. M. Arvidsson-Shukur, and C. H. W. Barnes, Phys. Rev. A 102, 062612 (2020).
  * Turney  _et al._ (2012) J. M. Turney, A. C. Simmonett, R. M. Parrish, E. G. Hohenstein, F. A. Evangelista, J. T. Fermann, B. J. Mintz, L. A. Burns, J. J. Wilke, M. L. Abrams, N. J. Russ, M. L. Leininger, C. L. Janssen, E. T. Seidl, W. D. Allen, H. F. Schaefer, R. A. King, E. F. Valeev, C. D. Sherrill, and T. D. Crawford, Wiley Interdiscip. Rev. Comput. Mol. 2, 556 (2012).
  * Krantz  _et al._ (2019) P. Krantz, M. Kjaergaard, F. Yan, T. P. Orlando, S. Gustavsson, and W. D. Oliver, Appl. Phys. Rev. 6, 021318 (2019).
  * Stano and Loss (2022) P. Stano and D. Loss, Nature Reviews Physics 4, 672 (2022).
  * Ding  _et al._ (2023) L. Ding, M. Hays, Y. Sung, B. Kannan, J. An, A. D. Paolo, A. H. Karamlou, T. M. Hazard, K. Azar, D. K. Kim, B. M. Niedzielski, A. Melville, M. E. Schwartz, J. L. Yoder, T. P. Orlando, S. Gustavsson, J. A. Grover, K. Serniak, and W. D. Oliver, “High-fidelity, frequency-flexible two-qubit fluxonium gates with a transmon coupler,” (2023), arXiv:2304.06087 [quant-ph] .
  * Cai  _et al._ (2023) Z. Cai, R. Babbush, S. C. Benjamin, S. Endo, W. J. Huggins, Y. Li, J. R. McClean, and T. E. O’Brien, “Quantum error mitigation,” (2023), arXiv:2210.00921 [quant-ph] .

##  Appendix A Big O, Omega, and Theta notations

This appendix defines big O, big Omega (Knuth definition), and big Theta
notations. For our purposes, the notations can, respectively, be defined as:

$\displaystyle f\left(x\right)=\mathcal{O}\left(g\left(x\right)\right)$
$\displaystyle\iff\lim_{x\to\infty}\frac{f\left(x\right)}{g\left(x\right)}<\infty,$
(96) $\displaystyle f\left(x\right)=\Omega\left(g\left(x\right)\right)$
$\displaystyle\iff\lim_{x\to\infty}\frac{f\left(x\right)}{g\left(x\right)}>0,$
(97) $\displaystyle f\left(x\right)=\Theta\left(g\left(x\right)\right)$
$\displaystyle\iff
0<\lim_{x\to\infty}\frac{f\left(x\right)}{g\left(x\right)}<\infty.$ (98)

##  Appendix B Variance, Required Shots, and Runtime

Figure 17: Variance against energy accuracy (left) and the number of ansatz-
circuit parameters (ansatz elements, right), for standard, Explore-, Static-,
and Dynamic-ADAPT-VQE using the QEB pool and support commutation. Each row
shows data for a specific molecule, with the number of orbitals increasing up
the page. Energy accuracies better than chemical accuracy are shaded in cream.
Figure 18: Energy accuracy against ansatz-circuit depths (left) and the number
of ansatz-circuit parameters (ansatz elements, right), for qubit-Dynamic-
ADAPT-VQE using support and operator commutation—dashed and solid lines,
respectively. Each row shows data for a specific molecule, with the number of
orbitals increasing up the page. Energy accuracies better than chemical
accuracy are shaded in cream.

Figure 19: Energy accuracy against ansatz-circuit depths (left), the number of
ansatz-circuit parameters (ansatz elements, center), and the number of CNOT
gates in the ansatz circuit (right), for qubit-Dynamic-ADAPT-VQE using support
commutation as well as QEB standard and Dynamic-ADAPT-VQE using support
commutation with both steepest gradient and largest energy reduction decision
rules, are compared. Each row shows data for a specific molecule, with the
number of orbitals increasing up the page. Energy accuracies better than
chemical accuracy are shaded in cream. Figure 20: Energy accuracy against the
number of loss function calls (left), the number of times the ansatz is
optimized (center), and the number of expectation values calculated during
optimizer calls (right), for qubit-Dynamic-ADAPT-VQE using support and
operator commutation, as well as QEB standard and Dynamic-ADAPT-VQE using
support commutation with both the steepest gradient and largest energy
reduction decision rules, are compared. Each row shows data for a specific
molecule, with the number of orbitals increasing up the page. Energy
accuracies better than chemical accuracy are shaded in cream.

This appendix analyzes the relationship between quantum-processor calls and
expectation value evaluations. As in Sec. IV C and Sec. V, here we will assume
gradients are calculated through the method of finite differences. Thus, we
need only consider expectation values of the Hamiltonian $H$. Note that the
runtimes to calculate two different expectation values will not generally be
the same. The standard error $\epsilon$ in the estimate of the expectation
value of the Hamiltonian $H$ can be bounded using Chebyshev’s inequality to
give

$\mathbb{P}\left(\left|\widetilde{\expectationvalue{H}}-\expectationvalue{H}\right|\geq\epsilon\right)\leq\frac{\operatorname{Var}H}{s\epsilon^{2}}$
(99)

where $s$ is the number of independent samples of the observable $H$ and
$\widetilde{\expectationvalue{H}}$ is the sample mean estimator for the
expectation value $\expectationvalue{H}$. However, our Hamiltonian $H$ is
represented by a sum of $g$ Pauli strings, so the total number of shots is
$S=gs$. Thus, we find the number of shots required is bounded:

$S\leq\frac{g\operatorname{Var}H}{q\epsilon^{2}}.$ (100)

where we have picked some desired confidence
$q=\mathbb{P}\left(\left|\widetilde{\expectationvalue{H}}-\expectationvalue{H}\right|\geq\epsilon\right)$.

Two factors contribute to variation in expectation value runtimes. Assuming
equality in Eq. 100 allows us to read off the first factor. That is, the
runtime is directly proportional to

$\operatorname{Var}H\equiv\Tr\left[H^{2}\rho_{t}\right]-\left(\Tr\left[H\rho_{t}\right]\right)^{2},$
(101)

which will generally vary throughout the algorithm through the dependence on
$\rho_{t}$. The evolutions of the variance $\operatorname{Var}H$ throughout
the four algorithms benchmarked in Sec. IV B and IV C are presented in Fig.
17. We observe that the variance is well predicted by the energy accuracy
independent of the algorithm (left column). This leads to the variance, like
the energy accuracy, being well predicted by the number of ansatz parameters
independent of the algorithm (right column).

The second factor is that each shot will have a runtime directly proportional
to the ansatz-circuit depth—this assumes that initialization and readout are
negligible.

Thus, we treat each expectation value evaluation as an oracle. The cost of
each oracle call is approximately the same for each algorithm for equal energy
accuracies or equal numbers of ansatz parameters—providing the algorithms
produce ansatz circuits with approximately equivalent depths. This is not true
when comparing Static- and Dynamic-ADAPT-VQE to standard and Explore-ADAPT-
VQE. That is the number of shots required per expectation value
$S\left(x\left(P\right)\right)$ (see Sec. V) as a function of the number of
parameters that is approximately the same for the four algorithms considered.

Further, comparisons of total expectation value evaluations (see Sec. IV C)
for a given energy convergence are a good proxy for directly comparing the
runtimes providing the algorithms produce ansatz circuits with approximately
equivalent ansatz-circuit depths. In the layered versus non-layered
comparison, the layering-based algorithms will have a faster runtime given by
the ratio of the depths—at best $\mathcal{O}\left(N\right)$.

##  Appendix C Commutativity vs Support

In this article, we introduced two notions of commutation that can be
leveraged in constructing ADAPT-VQE algorithms. They were operator commutation
and support commutation, and we will compare them here.

As noted in Appendix G, the operator and support non-commuting sets of the
ansatz elements in the QEB pool differ by, at most, two ansatz elements.
Additionally, both notions of commutation result in layers of constant depth
with respect to the number of qubits. On the other hand, the operator and
support non-commuting sets of the qubit pool differ by
$\Theta\left(N^{3}\right)$ ansatz elements. Thus, the two types of commutation
could construct vastly different ansätze. The ansätze constructed based on
support commutation will have layers of constant depth, while those
constructed based on operator commutation will have layers of depth
$\mathcal{O}\left(N^{3}\right)$. Thus, we consider both the support and
operator commutation variants of Dynamic-ADAPT-VQE using the qubit pool to
highlight the differences between the commutation types. Fig. 18 shows the
energy error (Eq. 54) as a function of depth and the number of parameters. For
LiH, H6, BeH2, and H2O we observe that support commutation outperforms
operator commutation. However, for H4, we find operator commutation
outperforms support commutation.

##  Appendix D Pool and Decision Rule Comparisons

This appendix includes additional comparisons of Dynamic-ADAPT-VQE with two
different loss functions and with the QEB and Pauli pools. We refer to the
loss function in Eq. 20 as gradient selection. An alternative loss function is

$L_{t}(A)=\min_{\theta}E_{t,A}(\theta),$ (102)

which we will refer to as energy selection. That is, we optimize the ansatz
with respect to the last parameter for each ansatz element in the subpool and
pick the ansatz element that reduces the energy by the most.

In Fig. 19, we see that both the energy and gradient selection rules perform
similarly in energy accuracy for a given depth, number of parameters, and
number of CNOT gates. Standard ADAPT-VQE with both gradient and energy
selection are included as reference points.

The QEB-Dynamic-ADAPT-VQE algorithms require fewer parameters and shallower
ansatz circuits than the qubit-Dynamic-ADAPT-VQE algorithms for a given energy
accuracy. However, the energy accuracy of QEB-Dynamic-ADAPT-VQE and qubit-
Dynamic-ADAPT-VQE for a given number of CNOT gates is similar, suggesting that
the number of two-qubit gates in the ansatz could be a good pool-independent
predictor of energy convergence.

Additionally, in Fig. 20, we see that evaluating the energy selection rule is
more expensive than the gradient selection rule. However, as the optimization
dominates the total number of expectation values we see for Dynamic-ADAPT-VQE,
the selection rule makes little difference for LiH, H6, and BeH2. That said,
the energy selection rule never significantly outperforms the gradient
selection rule, which justifies the use of the gradient selection rule
throughout this article.

##  Appendix E Noise Susceptibility Peaks

In this appendix, we comment on the peaks which appear in the noise
susceptibility data of Fig. 13 and Fig. 14. To verify that these apparent
features are not numerical errors, we computed not only the noise
susceptibility but also performed full density-matrix simulations with
depolarizing noise for a few points on the H6 plots. We compute
$\mathcal{E}_{t}(p=10^{-6})$ and $\mathcal{E}_{t}(p=0)$ at the values of $t$
located, before the peak, at the peak, and after the peak in Fig. 14,
respectively. Then, we used the finite-differences method to estimate
$\chi_{t}^{\mathcal{D}}$. The corresponding data points are depicted with
black crosses in Fig. 14, row 3, for H6. These points are in perfect agreement
with the noise-susceptibility data.

##  Appendix F Pool Definitions

In this appendix, we make more rigorous definitions of the pools referred to
throughout this article. These definitions will prove useful in analyzing the
runtime scalings of the algorithms.

Let $\mathcal{V}$ be some set of even integers. In the body of this paper, we
take $\mathcal{V}=\left\\{2,4\right\\}$ for all three pool definitions.
Additionally, let

$\mathcal{I}\left(\mathcal{V}\right)\coloneqq\left\\{\left(\vec{k},\vec{l}\>\right)\colon\vec{k},\vec{l}\in\mathbb{Z}^{q/2}_{n}\text{
such that }k_{0}\leq k_{i},l_{i}\text{ and all }k_{i},l_{i}\text{ are
distinct}\quad\forall i\in\left[q/2\right]\quad\forall
q\in\mathcal{V}\right\\}$ (103)

######  Definition 8 (Generalized Fermionic Pool)

All the distinct fermionic excitations that act on $q\in\mathcal{V}$ distinct
qubits are given by:

$\mathcal{P}^{f}\left(N\right)\coloneqq\left\\{T_{\vec{l}}^{\vec{k}}\colon\left(\vec{k},\vec{l}\>\right)\in\mathcal{I}\left(\mathcal{V}\right)\right\\}\quad\text{where}\quad
T_{\vec{l}}^{\vec{k}}\coloneqq\left[\prod_{i\in\vec{k}}a^{\dagger}_{i}\right]\left[\prod_{j\in\vec{l}}a_{j}\right]-h.c.$
(104)

This is the fermionic pool over $N$ qubits.

######  Definition 9 (Generalized QEB Pool)

All the distinct qubit excitations that act on $q\in\mathcal{V}$ distinct
qubits are given by:

$\mathcal{P}^{\text{QEB}}\left(N\right)\coloneqq\left\\{T_{\vec{l}}^{\vec{k}}\colon\left(\vec{k},\vec{l}\>\right)\in\mathcal{I}\left(\mathcal{V}\right)\right\\}\quad\text{where}\quad
T_{\vec{l}}^{\vec{k}}\coloneqq\left[\prod_{i\in\vec{k}}Q^{\dagger}_{i}\right]\left[\prod_{j\in\vec{l}}Q_{j}\right]-h.c.$
(105)

This is the QEB pool over $N$ qubits.

The cardinality of both the fermionic and QEB pools is:

$\left|\mathcal{P}^{f,\text{QEB}}\left(N\right)\right|=\sum_{\begin{subarray}{c}q\in\mathcal{V}\\\
\colon q\leq N\end{subarray}}\begin{pmatrix}q-1\\\
\frac{1}{2}q\end{pmatrix}\begin{pmatrix}N\\\
q\end{pmatrix}=\Theta\left(N^{\max\mathcal{V}}\right),$ (106)

where the second choice is the number of sets of $q$ distinct qubits of $N$,
and the first is the number of permutations of these qubits that give distinct
excitations.

######  Definition 10 (Generalized qubit Pool)

The qubit pool is the set of all the Pauli excitations with an odd number of
$Y$ gates in the generator that act on $q\in\mathcal{V}$ distinct qubits.

The cardinality of the qubit pool is:

$\left|\mathcal{P}^{\text{qubit}}\left(N\right)\right|=\sum_{\begin{subarray}{c}q\in\mathcal{V}\\\
\colon q\leq N\end{subarray}}2^{q-1}\begin{pmatrix}N\\\
q\end{pmatrix}=\Theta\left(N^{\max\mathcal{V}}\right),$ (107)

where the combinatorics follow as for the fermionic and QEB pools, but the
first choice is replaced with the factor $2^{q-1}$.

###### Lemma 1

For each
$\mathcal{P}\in\left\\{\mathcal{P}^{\rm{Fermi}},\mathcal{P}^{\text{QEB}},\mathcal{P}^{\text{qubit}}\right\\}$,
there exists a finite constant $V$, that will depend on the pool definition,
such that $\left|\mathcal{P}\left(N\right)\right|$ is a logarithmically
concave function of $N$ for $N\geq V$.

  * Proof.

Consider the polynomial

$f_{q}\left(x\right)\coloneqq\prod_{n=0}^{q-1}\left(x-n\right),$ (108)

which has $q$ integer roots: $\left[0,q-1\right]$. We note that the $k$th
derivative can be expressed as

$\derivative[k]{f_{q}}{x}=\sum_{\begin{subarray}{c}\vec{\alpha}\in\left[0,q-1\right]^{k}\\\
\colon\alpha_{i}\neq\alpha_{j}\forall
i,j\end{subarray}}f_{q,\vec{\alpha}}\left(x\right)\quad\text{where}\quad
f_{q,\vec{\alpha}}\left(x\right)\equiv\prod_{\begin{subarray}{c}n\in\left[0,q-1\right]\\\
\colon n\not\in\vec{\alpha}\end{subarray}}\left(x-n\right).$ (109)

Further, let

$g_{q,\vec{\alpha}}\left(x\right)\coloneqq\frac{f_{q}^{2}\left(x\right)}{\displaystyle\prod_{l\in\vec{\alpha}}\left(x-l\right)}.$
(110)

Using this notation, we will consider the following products

$\derivative[2]{f_{q}}{x}f_{q}\left(x\right)=\sum_{\begin{subarray}{c}\vec{\alpha}\in\left[0,q-1\right]^{2}\\\
\colon\alpha_{1}\neq\alpha_{2}\end{subarray}}f_{q,\vec{\alpha}}\left(x\right)f_{q}\left(x\right)=\sum_{\begin{subarray}{c}\vec{\alpha}\in\left[0,q-1\right]^{2}\\\
\colon\alpha_{1}\neq\alpha_{2}\end{subarray}}g_{q,\vec{\alpha}}\left(x\right),$
(111)

and

$\derivative{f_{q}}{x}\derivative{f_{q}}{x}=\sum_{\vec{\alpha}\in\left[0,q-1\right]^{2}}f_{q,\alpha_{1}}\left(x\right)f_{q,\alpha_{2}}\left(x\right)=\sum_{\begin{subarray}{c}\vec{\alpha}\in\left[0,q-1\right]^{2}\\\
\colon\alpha_{1}\neq\alpha_{2}\end{subarray}}g_{q,\vec{\alpha}}\left(x\right)+\sum_{\alpha_{1}=0}^{q-1}g_{q,\left(\alpha_{1},\alpha_{1}\right)}\left(x\right).$
(112)

Now note the first terms from each cancel in the difference of these products:

$\derivative{f_{q}}{x}\derivative{f_{q^{\prime}}}{x}-\derivative[2]{f_{q}}{x}f_{q^{\prime}}\left(x\right)=\sum_{\alpha_{1}=0}^{q-1}g_{q,\left(\alpha_{1},\alpha_{1}\right)}\left(x\right),$
(113)

which is non-negative for $x\geq q$.

Note $f_{q}\left(x\right)$ is logarithmically concave within some convex
domain iff
$\derivative[2]{f_{q}}{x}f_{q}\left(x\right)\leq\left[\derivative{f_{q}}{x}\right]^{2}$
within the convex domain. Thus, $f_{q}\left(x\right)$ is logarithmically
concave for $x\geq q$. As the discrete function $\begin{pmatrix}N\\\
q\end{pmatrix}=\frac{1}{q!}f_{q}\left(N\right)$ it must also be
logarithmically concave for $N\geq q$. However,
$\left|\mathcal{P}\left(N\right)\right|$ is a linear combination with non-
negative coefficients of such functions with $q\in\mathcal{V}$. Therefore
there will be a finite constant depending on these coefficients for which the
function $\begin{pmatrix}N\\\ \max\mathcal{V}\end{pmatrix}$ dominates
sufficiently that $\left|\mathcal{P}\left(N\right)\right|$ is logarithmically
concave.

##  Appendix G Generalized Non-Commutation Sets

In this appendix, we derive rules to determine whether two ansatz elements
from the same pool operator commute. We consider the qubit pool (Section G.1),
QEB pool (Section G.2), and Fermionic pool (Section G.3). All these ansatz
elements are Stones encoded unitaries, $e^{\theta T}$ for some skew-hermitian
generator $T$. Thus, two ansatz elements operator commute iff the
corresponding generators commute. Below we derive the conditions under which
the generators commute and hence the ansatz elements operator commute.

###  G.1 Pauli Excitations

For Pauli excitations, the generators are simply the Pauli strings of length
two and four with an odd number of $Y$ operators. Thus, the Pauli strings
operator commute iff the tensor factors in the strings with mutual support
differ in an even number of places.

###  G.2 Qubit Excitations

First, we will consider a generalization of qubit excitation generators which
will later prove useful for Fermionic excitation generators. Consider the
following definitions:

######  Definition 11 (Singleton Matrix)

Let $\left[M_{ij}\right]_{ab}\coloneqq\delta_{ai}\delta_{bj}$ be a singleton
matrix. Note that these matrices have the following properties:

  1. 1.

$M_{kl}M_{\gamma\delta}\equiv\delta_{l\gamma}M_{k\delta}$,

  2. 2.

$\left[M_{kl},M_{\gamma\delta}\right]\equiv\delta_{l\gamma}M_{k\delta}-\delta_{k\delta}M_{\gamma
l}$.

######  Definition 12 (Set of Singleton Matrices)

Let $\mathcal{M}_{l}\coloneqq\left\\{M_{ij}\colon
i,j\in\left[2^{l}\right]\right\\}\subset\mathbb{R}^{2^{l}\times 2^{l}}$ for
all $l\in\mathbb{N}_{0}$. Note that this family of sets has the following
properties:

  1. 1.

$\mathcal{M}_{0}\equiv\left\\{1\right\\}$,

  2. 2.

$\mathcal{M}_{l+m}\equiv\mathcal{M}_{l}\otimes\mathcal{M}_{m}\quad\forall
l\geq 1$.

Representing the set of operators
$\mathcal{Q}_{l}\coloneqq\left\\{Q,Q^{\dagger}\right\\}^{\otimes l}$ in the
computational basis is an injection
$\mathcal{Q}_{l}\to\left\\{M_{ij}\in\mathcal{M}_{l}\colon i\neq j\right\\}$
for $l\geq 1$. Thus, we consider the following skew-Hermitian operator
$T=M_{ij}+aM_{ji}$, which could represent a qubit excitation generator in the
computational basis when $a=-1$.

######  Theorem 1 (Singleton Matrix Excitation Commutation)

Consider the following two operators acting on a tripartite vector space:

$\displaystyle T_{1}$ $\displaystyle=\mathds{1}\otimes M_{ij}\otimes
M_{kl}+a_{1}\mathds{1}\otimes M_{ji}\otimes M_{lk},$ (114) $\displaystyle
T_{2}$ $\displaystyle=M_{\alpha\beta}\otimes\mathds{1}\otimes
M_{\gamma\delta}+a_{2}M_{\beta\alpha}\otimes\mathds{1}\otimes
M_{\delta\gamma},$ (115)

such that $i\neq j$, $k\neq l$, $\alpha\neq\beta$, and $\gamma\neq\delta$.

$T_{1}$ and $T_{2}$ commute if and only if any of the following three
conditions hold:

  1. 1.

$T_{1}$ and $T_{2}$ have disjoint support (i.e. $M_{kl}=M_{\gamma\delta}=1$),

  2. 2.

$T_{1}\propto T_{2}$,

  3. 3.

$T_{1}$ and $T_{2}$ have equivalent support and $k$, $l$, $\gamma$ and
$\delta$ are all distinct.

  * Proof.

Condition 1 follows trivially, as operators with disjoint support always
commute. Thus, henceforth, we will assume
$M_{kl},M_{\gamma\delta}\in\mathcal{M}_{l}$ for $l\geq 1$ (the compliment of
Condition 1). Now consider the product

$\displaystyle T_{1}T_{2}=$ $\displaystyle M_{ij}\otimes
M_{\alpha\beta}\otimes\left(M_{kl}M_{\gamma\delta}\right)$ (116)
$\displaystyle+a_{1}M_{ji}\otimes
M_{\alpha\beta}\otimes\left(M_{lk}M_{\gamma\delta}\right)$ (117)
$\displaystyle+a_{2}M_{ij}\otimes
M_{\beta\alpha}\otimes\left(M_{kl}M_{\delta\gamma}\right)$ (118)
$\displaystyle+a_{1}a_{2}M_{ji}\otimes
M_{\beta\alpha}\otimes\left(M_{lk}M_{\delta\gamma}\right).$ (119)

Thus, we find the commutator using Property 2 of Definition 11:

$\displaystyle\left[T_{1},T_{2}\right]=$ $\displaystyle M_{ij}\otimes
M_{\alpha\beta}\otimes\left(\delta_{l\gamma}M_{k\delta}-\delta_{k\delta}M_{\gamma
l}\right)$ (120) $\displaystyle+a_{1}M_{ji}\otimes
M_{\alpha\beta}\otimes\left(\delta_{k\gamma}M_{l\delta}-\delta_{l\delta}M_{\gamma
k}\right)$ (121) $\displaystyle+a_{2}M_{ij}\otimes
M_{\beta\alpha}\otimes\left(\delta_{l\delta}M_{k\gamma}-\delta_{k\gamma}M_{\delta
l}\right)$ (122) $\displaystyle+a_{1}a_{2}M_{ji}\otimes
M_{\beta\alpha}\otimes\left(\delta_{k\delta}M_{l\gamma}-\delta_{l\gamma}M_{\delta
k}\right).$ (123)

First, suppose the tensor factors in parentheses are non-zero and $M_{ij}\neq
1$. Line 120 cannot cancel with Line 121 or 123 due to the first tensor
factor: $M_{ji}\neq M_{ij}$. Further, Line 120 cannot cancel with Line 122 due
to the bracketed tensor factor as $\gamma\neq\delta$. Thus, $T_{1}$ and
$T_{2}$ do not commute if $M_{ij}\neq 1$ and the first condition is not met.
By symmetry, the same argument can be applied if we suppose the tensor factors
in parentheses are non-zero and $M_{\alpha\beta}\neq 1$. Therefore, if the
first condition is not met, then we require $M_{ij}=M_{\alpha\beta}=1$ in
order for $T_{1}$ and $T_{2}$ to commute—that is, we require equivalent
support.

Suppose now that $T_{1}$ and $T_{2}$ do have equivalent support. We can
simplify the commutator to:

$\displaystyle\left[T_{1},T_{2}\right]=$
$\displaystyle\delta_{l\gamma}M_{k\delta}-\delta_{k\delta}M_{\gamma l}$ (124)
$\displaystyle+a_{1}\left(\delta_{k\gamma}M_{l\delta}-\delta_{l\delta}M_{\gamma
k}\right)$ (125)
$\displaystyle+a_{2}\left(\delta_{l\delta}M_{k\gamma}-\delta_{k\gamma}M_{\delta
l}\right)$ (126)
$\displaystyle+a_{1}a_{2}\left(\delta_{k\delta}M_{l\gamma}-\delta_{l\gamma}M_{\delta
k}\right).$ (127)

By noting if $\delta_{ab}=1$ and $a\neq c$ then $\delta_{cb}=0$ and that
$M_{ab}$ is linearly independent from $M_{cd}$ if $a\neq c$ or $b\neq d$ we
can pair the lines as follows: $A\coloneqq\left\\{\eqref{eq:commutator simple
1},\eqref{eq:commutator simple 4}\right\\}$ and
$B\coloneqq\left\\{\eqref{eq:commutator simple 2},\eqref{eq:commutator simple
3}\right\\}$ where no term in $A$ can cancel with a term in $B$. For the terms
in $A$ to cancel we require $k=\delta$ and $l=\gamma$ and $a_{1}a_{2}=1$ as
$k\neq l$ and $\gamma\neq\delta$, or $k\neq\delta$ and $l\neq\gamma$.
Similarly, for terms in $B$ to cancel we require $k=\gamma$ and $l=\delta$ and
$a_{1}=a_{2}$ as $k\neq l$ and $\gamma\neq\delta$ , or $k\neq\gamma$ and
$l\neq\delta$.

Now we can try to combine these conditions. First, consider combining the
conditions:

$\begin{cases}k=\delta\text{ and }l=\gamma\text{ and
}\alpha_{1}\alpha_{2}=1,\\\ k=\gamma\text{ and }l=\delta\text{ and
}\alpha_{1}=\alpha_{2}\end{cases}\implies k=l=\gamma=\delta\text{ and
}\alpha_{1}=\alpha_{2}=\pm 1.$ (128)

However, we know $k\neq l$ and $\gamma\neq\delta$, so these conditions cannot
apply simultaneously. Next, we try the combination:

$\begin{cases}k=\delta\text{ and }l=\gamma\text{ and
}\alpha_{1}\alpha_{2}=1,\\\ k\neq\gamma\text{ and
}l\neq\delta\end{cases}\implies k=\delta\neq l=\gamma\text{ and
}\alpha_{1}\alpha_{2}=1,$ (129)

which is possible and corresponds to $T_{1}\propto T_{2}$ (Condition 2).
Similarly:

$\begin{cases}k\neq\delta\text{ and }l\neq\gamma,\\\ k=\gamma\text{ and
}l=\delta\text{ and }\alpha_{1}=\alpha_{2}\end{cases}\implies k=\gamma\neq
l=\delta\text{ and }\alpha_{1}=\alpha_{2},$ (130)

is possible and also corresponds to $T_{1}\propto T_{2}$ (Condition 2).
Finally, consider the combination:

$\begin{cases}k\neq\delta\text{ and }l\neq\gamma,\\\ k\neq\gamma\text{ and
}l\neq\delta\end{cases}\implies\left\\{k,l,\gamma,\delta\right\\}\text{ are
all distinct,}$ (131)

which is Condition 3; where we have used the $k\neq l$ and $\gamma\neq\delta$.

######  Corollary 1.1 (Qubit Excitation Commutation)

Now consider qubit excitation generators defined as follows:

$T=G+aG^{\dagger}\quad\text{where }G\in\mathcal{Q}_{l}.$ (132)

If two such generators have equivalent support, then either Condition 2 or 3
must hold. Thus, two-qubit excitation generators commute iff they have
disjoint or equivalent support.

###  G.3 Fermionic Excitations

A Fermionic excitation generator generalizes to an operator of the form:

######  Definition 13 (Generalized Fermionic Excitation)

$T=K+bK^{\dagger}\quad\text{where
}K\coloneqq\prod_{i\in\vec{i}}a_{i}^{\left(x_{i}\right)},\quad
a^{\left(x_{i}\right)}_{i}\coloneqq\begin{cases}a^{\dagger}_{i},&x_{i}=0\\\
a_{i},&x_{i}=1\end{cases},$ (133)

and $x$ is a bit-string and $\vec{i}$ is a tuple of unique orbital indices.

In the Jordan-Wigner encoding $a_{i}=Q_{i}\otimes\mathcal{Z}_{i}$ where
$\mathcal{Z}_{i}=\bigotimes_{j=1}^{i-1}Z_{j}$ is a Pauli string of $Z$
operators. Now we will define the commutation product and use it to express
the generalized Fermionic excitation generators as the tensor product of a
singleton matrix excitation generator and a Pauli string of $Z$ operators:

######  Definition 14 (Commutation Product)

Let $\left(\bullet,\bullet\right):\mathcal{H}^{\times
2}\times\mathcal{H}^{\times 2}\to\left\\{0,\pm 1\right\\}$ be a mapping from a
pair of operators on the Hilbert space $\mathcal{H}$ to $\left\\{0,\pm
1\right\\}$ such that

$\left(A,B\right)\coloneqq\begin{cases}1,&\left[A,B\right]=0,\\\
-1,&AB+BA=0,\\\ 0,&\text{otherwise},\end{cases}$ (134)

which satisfies:

  1. 1.

$\left(A,A\right)=1$,

  2. 2.

$\left(A,B\right)=\left(B,A\right)$,

  3. 3.

$\left(A,BC\right)=\left(A,B\right)\left(A,C\right)=\left(A,CB\right)$,

  4. 4.

$AB=\left(A,B\right)BA$,

  5. 5.

$AB=\left(A,B\right)BA$ if $\left(A,B\right)=\pm 1$.

Using 3 let

$\left(A,\prod_{i}B_{i}\right)\equiv\left(A,\left\\{B_{i}\right\\}_{i}\right).$
(135)

Note that $Q$ and $Q^{\dagger}$ anti-commute with $Z$ (i.e.
$\left(Q^{\left(\dagger\right)},Z\right)=-1$).

######  Lemma 2 (Generalized Fermionic Excitation Tensor Factorisation)

Generalized Fermionic excitation generators can be expressed as follows:

$T=\pm T_{s}\otimes\tilde{\mathcal{Z}},$ (136)

where $T_{s}$ is a singleton matrix excitation generator and
$\tilde{\mathcal{Z}}\in\left\\{\mathds{1},Z\right\\}^{\otimes m}$ for some
$m\in\mathbb{N}$.

  * Proof.

$\displaystyle K$
$\displaystyle\coloneqq\prod_{i\in\vec{i}}a_{i}^{\left(x_{i}\right)}$ (137)
$\displaystyle=\prod_{i\in\vec{i}}\left[Q^{\left(x_{i}\right)}_{i}\mathcal{Z}_{i}\right],\quad\text{where
}Q^{\left(x_{i}\right)}_{i}\coloneqq\begin{cases}Q^{\dagger}_{i},&x_{i}=0\\\
Q_{i},&x_{i}=1\end{cases}$ (138)
$\displaystyle=\left[\bigotimes_{i\in\vec{i}}Q^{\left(x_{i}\right)}_{i}\right]\cdot\left[\prod_{n=1}^{\dim\vec{i}}\left(\left\\{Q_{i_{m}}^{\left(x_{i_{m}}\right)}\right\\}_{m=1}^{n-1},\mathcal{Z}_{i_{n}}\right)\mathcal{Z}_{i_{n}}\right]$
(139)
$\displaystyle=\left[\prod_{n=1}^{\dim\vec{i}}\left(\left\\{Q_{i_{m}}^{\left(x_{i_{m}}\right)}\right\\}_{m=1}^{n-1},\mathcal{Z}_{i_{n}}\right)\right]\cdot\left[\bigotimes_{i\in\vec{i}}Q^{\left(x_{i}\right)}_{i}\right]\cdot\left[\prod_{n=1}^{\dim\vec{i}}\mathcal{Z}_{i_{n}}\right].$
(140)

Now note that

$\displaystyle QZ=-Q;$ $\displaystyle Q^{\dagger}Z=Q^{\dagger}.$ (141)

Thus, the mutual support of
$\left[\bigotimes_{i\in\vec{i}}Q^{\left(x_{i}\right)}_{i}\right]$ and
$\left[\prod_{n=1}^{\dim\vec{i}}\mathcal{Z}_{i_{n}}\right]$ can be removed by
replacing the $Z$ operators within the mutual support with $\mathds{1}$ and
obtaining a factor of $1$ or $-1$. In this process the factor
$\left[\bigotimes_{i\in\vec{i}}Q^{\left(x_{i}\right)}_{i}\right]$ is unchanged
and
$\left[\prod_{n=1}^{\dim\vec{i}}\mathcal{Z}_{i_{n}}\right]\mapsto\tilde{\mathcal{Z}}$.
Additionally,

$\left[\prod_{n=1}^{\dim\vec{i}}\left(\left\\{Q_{i_{m}}^{\left(x_{i_{m}}\right)}\right\\}_{m=1}^{n-1},\mathcal{Z}_{i_{n}}\right)\right]\in\left\\{1,-1\right\\},$
(142)

which can be combined with the factor of $1$ or $-1$ from earlier to produce a
factor $\pm 1$. Therefore we find:

$\displaystyle
K\equiv\pm\left[\bigotimes_{i\in\vec{i}}Q^{\left(x_{i}\right)}_{i}\right]\otimes\tilde{\mathcal{Z}};$
$\displaystyle
K^{\dagger}\equiv\pm\left[\bigotimes_{i\in\vec{i}}Q^{\left(x_{i}\right)}_{i}\right]^{\dagger}\otimes\tilde{\mathcal{Z}}.$
(143)

Finally, we can substitute this into the form of $T$:

$T=\pm\left(\left[\bigotimes_{i\in\vec{i}}Q^{\left(x_{i}\right)}_{i}\right]+b\left[\bigotimes_{i\in\vec{i}}Q^{\left(x_{i}\right)}_{i}\right]^{\dagger}\right)\otimes\tilde{\mathcal{Z}},$
(144)

and note that the tensor factor in brackets is a singleton matrix excitation
generator.

Moving forward with this form of generalized fermionic excitation generators
allows us to use Theorem 1 to show the following commutation relations hold
for generalized fermionic excitations:

######  Theorem 2 (Generalized Fermionic Excitation Commutation)

Two generalized fermionic excitations $T_{1}$ and $T_{2}$ commute iff any of
the following conditions are satisfied:

  1. 1.

$T_{s1}$ and $T_{s2}$ have disjoint support and
$\left|\mathrm{Supp}T_{s1}\cap\mathrm{Supp}\tilde{\mathcal{Z}}_{2}\right|+\left|\mathrm{Supp}T_{s2}\cap\mathrm{Supp}\tilde{\mathcal{Z}}_{1}\right|$
is even,

  2. 2.

$T_{s1}\propto T_{s2}$,

  3. 3.

$T_{s1}$ and $T_{s2}$ have equivalent support and can be written as

$\displaystyle T_{s1}\equiv M_{rs}+b_{1}M_{sr};$ $\displaystyle T_{s2}\equiv
M_{tu}+b_{2}M_{ut}$ . (145)

where $r$, $s$, $t$ and $u$ are all distinct.

  * Proof.

Consider the product

$\displaystyle T_{1}T_{2}$
$\displaystyle=c_{1}T_{s1}\otimes\tilde{\mathcal{Z}}_{1}\cdot
c_{2}T_{s2}\otimes\tilde{\mathcal{Z}}_{2}$ (146)
$\displaystyle=c_{1}c_{2}T_{s1}\otimes\tilde{\mathcal{Z}}_{1}\cdot
T_{s2}\otimes\tilde{\mathcal{Z}}_{2}$ (147)
$\displaystyle=c_{1}c_{2}\left(\tilde{\mathcal{Z}}_{1},T_{s2}\right)T_{s1}T_{s2}\tilde{\mathcal{Z}}_{1}\tilde{\mathcal{Z}}_{2},\quad\text{where
tensor products with the identity are implied}$ (148)
$\displaystyle=c_{1}c_{2}\left(\tilde{\mathcal{Z}}_{1},T_{s2}\right)T_{s2}T_{s1}\tilde{\mathcal{Z}}_{1}\tilde{\mathcal{Z}}_{2}+c_{1}c_{2}\left(\tilde{\mathcal{Z}}_{1},T_{s2}\right)\left[T_{s1},T_{s2}\right]\tilde{\mathcal{Z}}_{1}\tilde{\mathcal{Z}}_{2}$
(149)
$\displaystyle=\left(\tilde{\mathcal{Z}}_{1},T_{s2}\right)\left(\tilde{\mathcal{Z}}_{2},T_{s1}\right)c_{2}T_{s2}\otimes\tilde{\mathcal{Z}}_{2}\cdot
c_{1}T_{s1}\otimes\tilde{\mathcal{Z}}_{1}+c_{1}c_{2}\left(\tilde{\mathcal{Z}}_{1},T_{s2}\right)\left[T_{s1},T_{s2}\right]\tilde{\mathcal{Z}}_{1}\tilde{\mathcal{Z}}_{2}$
(150)
$\displaystyle=\left(\tilde{\mathcal{Z}}_{1},T_{s2}\right)\left(\tilde{\mathcal{Z}}_{2},T_{s1}\right)T_{2}T_{1}+c_{1}c_{2}\left(\tilde{\mathcal{Z}}_{1},T_{s2}\right)\left[T_{s1},T_{s2}\right]\tilde{\mathcal{Z}}_{1}\tilde{\mathcal{Z}}_{2},$
(151)

where $c_{1},c_{2}\in\left\\{1,-1\right\\}$ and we have used the fact that
$\left(\tilde{\mathcal{Z}}_{m},T_{sn}\right)\in\left\\{1,-1\right\\}$ for all
$m,n\in\left\\{1,2\right\\}$.

Therefore, we can write the commutator as

$\left[T_{1},T_{2}\right]=\left[\left(\tilde{\mathcal{Z}}_{1},T_{s2}\right)\left(\tilde{\mathcal{Z}}_{2},T_{s1}\right)-1\right]T_{2}T_{1}+c_{1}c_{2}\left(\tilde{\mathcal{Z}}_{1},T_{s2}\right)\left[T_{s1},T_{s2}\right]\tilde{\mathcal{Z}}_{1}\tilde{\mathcal{Z}}_{2}.$
(152)

The entries of $T_{sn}$ are drawn from the set $\left\\{0,1\right\\}$. Thus,
if $T_{s1}$ and $T_{s2}$ do not commute, then $T_{s2}T_{s1}$ and
$\left[T_{s1},T_{s2}\right]$ are linearly independent, so for
$\left[T_{1},T_{2}\right]=0$ we require both both terms to vanish:

$\displaystyle\left[\left(\tilde{\mathcal{Z}}_{1},T_{s2}\right)\left(\tilde{\mathcal{Z}}_{2},T_{s1}\right)-1\right]T_{2}T_{1}=0,$
and (153) $\displaystyle
c_{1}c_{2}\left(\tilde{\mathcal{Z}}_{1},T_{s2}\right)\left[T_{s1},T_{s2}\right]\tilde{\mathcal{Z}}_{1}\tilde{\mathcal{Z}}_{2}=0.$
(154)

Which simplifies to

$\displaystyle\left[\left(\tilde{\mathcal{Z}}_{1},T_{s2}\right)\left(\tilde{\mathcal{Z}}_{2},T_{s1}\right)-1\right]=0\quad\text{or}\quad
T_{2}T_{1}=0,$ and (155) $\displaystyle\left[T_{s1},T_{s2}\right]=0.$ (156)

Thus, Condition 156 requires we satisfy at least one of the three conditions
from Theorem 1. Therefore, each condition in Theorem 2 corresponds to the
condition with the same number in Theorem 1. However, Condition 155 requires
us to strengthen the conditions in Theorem 2.

First, consider when $T_{2}T_{1}=0$. The $\tilde{\mathcal{Z}_{n}}$ factors
will only produce phase factors and so $T_{2}T_{1}=0\iff T_{s2}T_{s1}=0$.
Using the identities

$\displaystyle T_{s1}\equiv M_{rs}+b_{1}M_{sr},$ $\displaystyle T_{s2}\equiv
M_{tu}+b_{2}M_{ut}$ , (157)

where $r\neq s$ and $t\neq u$ we find

$0=T_{s2}T_{s1}=\delta_{ur}M_{ts}+b_{2}\delta_{tr}M_{us}+b_{1}\delta_{us}M_{tr}+b_{2}b_{1}\delta_{ts}M_{ur}.$
(158)

We note $M_{ts}$, $M_{us}$, $M_{tr}$, and $M_{ur}$ are linearly independent as
$r\neq s$ and $t\neq u$. Thus, $T_{2}T_{1}=0$ iff:

$\displaystyle u\neq r,$ (159) $\displaystyle t\neq r,$ (160) $\displaystyle
u\neq s,$ (161) $\displaystyle t\neq s.$ (162)

Combining these conditions with $r\neq s$ and $t\neq u$ implies $T_{2}T_{1}=0$
iff $r$, $s$, $t$ and $u$ are all distinct. We already obtained this condition
from Condition 156, giving us Condition 3.

Finally, as $Q$ and $Q^{\dagger}$ anti-commute with $Z$, then
$\left[\left(\tilde{\mathcal{Z}}_{1},T_{s2}\right)\left(\tilde{\mathcal{Z}}_{2},T_{s1}\right)-1\right]=0$
occurs iff
$\left|\mathrm{Supp}T_{s1}\cap\mathrm{Supp}\tilde{\mathcal{Z}}_{2}\right|+\left|\mathrm{Supp}T_{s2}\cap\mathrm{Supp}\tilde{\mathcal{Z}}_{1}\right|$
is even. As $T_{s1}\propto T_{s2}$ implies
$\left|\mathrm{Supp}T_{s1}\cap\mathrm{Supp}\tilde{\mathcal{Z}}_{2}\right|+\left|\mathrm{Supp}T_{s2}\cap\mathrm{Supp}\tilde{\mathcal{Z}}_{1}\right|$