# Efficient Multi-Objective Neural Architecture Search via Pareto Dominance-
based Novelty Search

An Vo  University of Information TechnologyHo Chi Minh CityVietnam Vietnam
National UniversityHo Chi Minh CityVietnam<EMAIL_ADDRESS>and  Ngoc
Hoang Luong  University of Information TechnologyHo Chi Minh CityVietnam
Vietnam National UniversityHo Chi Minh CityVietnam<EMAIL_ADDRESS>
(2024)

###### Abstract.

Neural Architecture Search (NAS) aims to automate the discovery of high-
performing deep neural network architectures. Traditional objective-based NAS
approaches typically optimize a certain performance metric (e.g., prediction
accuracy), overlooking large parts of the architecture search space that
potentially contain interesting network configurations. Furthermore,
objective-driven population-based metaheuristics in complex search spaces
often quickly exhaust population diversity and succumb to premature
convergence to local optima. This issue becomes more complicated in NAS when
performance objectives do not fully align with the actual performance of the
candidate architectures, as is often the case with training-free metrics.
While training-free metrics have gained popularity for their rapid performance
estimation of candidate architectures without incurring computation-heavy
network training, their effective incorporation into NAS remains a challenge.
This paper presents the Pareto Dominance-based Novelty Search for multi-
objective NAS with Multiple Training-Free metrics (MTF-PDNS). Unlike
conventional NAS methods that optimize explicit objectives, MTF-PDNS promotes
population diversity by utilizing a novelty score calculated based on multiple
training-free performance and complexity metrics, thereby yielding a broader
exploration of the search space. Experimental results on standard NAS
benchmark suites demonstrate that MTF-PDNS outperforms conventional methods
driven by explicit objectives in terms of convergence speed, diversity
maintenance, architecture transferability, and computational costs.

novelty search, neural architecture search, multiobjective optimization,
training-free metrics

††journalyear: 2024††copyright: acmlicensed††conference: Genetic and
Evolutionary Computation Conference; July 14–18, 2024; Melbourne, VIC,
Australia††booktitle: Genetic and Evolutionary Computation Conference (GECCO
’24), July 14–18, 2024, Melbourne, VIC, Australia††doi:
10.1145/3638529.3654064††isbn: 979-8-4007-0494-9/24/07††ccs: Computing
methodologies Neural networks††ccs: Computing methodologies Genetic
algorithms††ccs: Computing methodologies Ensemble methods

##  1\. Introduction

Neural Architecture Search (NAS), a subfield of automated machine learning,
aims to efficiently automate the design process of neural network
architectures (Elsken et al., 2019; White et al., 2023). It is driven by the
goal of discovering optimal configurations in a large-scale design space with
minimal manual intervention. Vanilla NAS methods (Zoph and Le, 2017; Real et
al., 2019) are often designed to optimize specific performance metrics, and
these methods tend to prioritize optimization of performance objectives.
However, this focus can inadvertently constrain the exploration of the vast
search space, overlooking potentially innovative configurations that lie
outside the objective-driven search trajectories (Stanley and Lehman, 2015).

A fundamental challenge in NAS is that the evaluations of numerous candidate
architectures are prohibitively time-consuming (Zoph and Le, 2017; Real et
al., 2019). To address this, many performance predictors (White et al., 2021)
have been proposed recently, notably the emergence of training-free metrics
(Abdelfattah et al., 2021). While these metrics can provide a quick and cost-
effective way to estimate the performance of different architectures, their
use is not without challenges. One of the main arguments is that they may not
always correlate well with the final test accuracy (Abdelfattah et al., 2021).
Consequently, over-reliance on these metrics as the direct objective in NAS,
due to their insufficient informativeness about the performance of candidate
architectures, could potentially lead to bias and deception in the search
process (Krishnakumar et al., 2022; Ning et al., 2021). These inaccurate
performance objectives can misguide the search process, leading the search to
converge prematurely to bad local optima - architectures that seem effective
according to performance predictors but are not the best solutions in terms of
actual performance. Thus, the search process can neglect the exploration of
other potentially high-performing architectures that could exist elsewhere in
the search space (Lehman and Stanley, 2011; Gomes et al., 2015; Fister et al.,
2019).

Novelty Search (NS) has been proposed as an alternative approach that rewards
divergence in characteristic features or behaviors of solutions from those
previously explored in the search process, rather than the optimization of
performance objectives alone (Stanley and Lehman, 2015; Lehman and Stanley,
2011; Doncieux et al., 2019). NS has shown potential in various domain (Gomes
et al., 2013; Liapis et al., 2013), including NAS (Sinha and Chen, 2022b;
Zhang et al., 2020b, a). In NAS, the novelty score is calculated based on the
distinctive descriptors of each architecture in relation to others in the
current population, and possibly as well as explored architectures in the
previous generations stored in an archive. When a novelty score is pursued,
the search process is encouraged to perform more exploration, thereby
obtaining diverse solutions, potentially from simple to increasingly more
complex ones. The novelty method can lead to the discovery of a wider variety
of neural architectures, some of which may be more effective, that could be
overlooked by conventional search methods. This shift in focus from rigidly
pursuing performance objectives, which can lead to convergence in a single
region of search space, to promoting exploration and novelty, can help avoid
deception and premature convergence (Gomes et al., 2015; Lehman and Stanley,
2011; Fister et al., 2019).

In this study, we propose the Pareto Dominance-based Novelty Search for NAS
with Multiple Training-Free metrics (MTF-PDNS), which introduces a novelty
score that utilizes training-free performance and complexity metrics to
enhance evolutionary multi-objective NAS (Lu et al., 2020b, a). This score is
designed to integrate both novelty and fitness of architectures, guiding a
Genetic Algorithm (GA) as the primary objective. To complement this, we
maintain an elitist archive (Luong and Bosman, 2012), which preserves
training-free performance and complexity metrics of non-dominated
architectures. Our method only utilizes archives to calculate novelty scores
without directly optimizing the metrics. Moreover, we take into consideration
various aspects of neural network architectures, prioritizing not just
performance but also complexity, which makes it more applicable to real-world
scenarios. To validate our approach, we conduct extensive experiments across
widely-used NAS benchmarks, including NAS-Bench-101 (Ying et al., 2019), NAS-
Bench-201 (Dong and Yang, 2020), and NAS-Bench-1Shot1 (Zela et al., 2020). The
experimental results underscore the superiority of our method in the context
of Multi-Objective NAS (MONAS), indicating its ability to effectively navigate
the search space and efficiently explore a wide range of neural network
architectures.

##  2\. Preliminaries

###  2.1. Multi-objective NAS

Multi-Objective NAS (MONAS (Lu et al., 2020b, a)) ideally aims to find within
the architecture search space $\Omega$ a Pareto set
$\mathcal{P}_{S}\subset\Omega$ of neural network topologies that exhibit
optimal trade-offs regarding $m$ objectives. These objectives often compete
with each other, such as minimizing error while minimizing computational
resource usage, model complexity, or inference latency. Assuming minimization
for all objectives, the MONAS problem can be defined as follows:

(1)
$\min\mathbf{F}(\mathbf{x})=[f_{1}(\mathbf{x}),f_{2}(\mathbf{x}),\ldots,f_{m}(\mathbf{x})]:\Omega\rightarrow\mathbb{R}^{m},$

where $\Omega$ is the search space and $f_{i}(\mathbf{x})$ denotes the $i$-th
objective function to be minimized. Let $\mathbf{x},\mathbf{y}\in\Omega$ be
two architectures. We say that $\mathbf{x}$ Pareto dominates $\mathbf{y}$
(denoted as $\mathbf{x}\prec\mathbf{y}$) if:

(2) $\begin{cases}\forall i\in\\{1,\ldots,m\\},f_{i}(\mathbf{x})\leq
f_{i}(\mathbf{y})\\\ \exists
j\in\\{1,\ldots,m\\},f_{j}(\mathbf{x})<f_{j}(\mathbf{y})\end{cases}$

The first condition says that architecture $\mathbf{x}$ is no worse than
architecture $\mathbf{y}$ in all objectives, and the second condition says
that architecture $\mathbf{x}$ is strictly better than architecture
$\mathbf{y}$ in at least one objective. The Pareto set $\mathcal{P}_{S}$ of an
MONAS problem thus consists of all Pareto-optimal architectures
$\mathbf{x}\in\Omega$ such that there is no other architecture
$\mathbf{y}\in\Omega$ dominating $\mathbf{x}$:
$\mathcal{P}_{S}=\\{\mathbf{x}\in\Omega\mid\nexists\mathbf{y}\in\Omega,\mathbf{y}\prec\mathbf{x}\\}$.
The Pareto front $\mathcal{P}_{F}$ is defined as the set of vectors of
objective values of architectures in $\mathcal{P}_{S}$, representing all the
optimal trade-offs among the objectives:
$\mathcal{P}_{F}=\mathbf{F}(\mathcal{P}_{S})=\\{\mathbf{F}(\mathbf{x})~{}|~{}\mathbf{x}\in\mathcal{P}_{S}\\}$.
Instead of finding the entire Pareto set $\mathcal{P}_{S}$, in real-world
MONAS, it is often practical to find an approximation set $A$ containing
candidate architectures that do not Pareto dominate each other and
$\mathbf{F}(A)$ closely approximates $\mathcal{P}_{F}$ in the objective space.

Figure 1. Illustration of Pareto Dominance-based Novelty Search. In the
elitist archive update (yellow background), if we use descriptors derived from
training-based metrics to calculate novelty scores, the x-axis represents
validation error. In contrast, if we use descriptors derived from training-
free metrics, the x-axis represents training-free metrics as shown in the
figure.

###  2.2. Training-free metrics for NAS

Training-free metrics (Abdelfattah et al., 2021) are used to estimate the
quality of neural network architectures without having to firstly train them
to obtain proper network weight values. These metrics are useful in NAS as
they dramatically reduce the computational cost associated with evaluating
candidate architectures. In this section, we discuss three such metrics:
Synaptic Flow (synflow) (Tanaka et al., 2020), Jacobian Covariance (jacov)
(Mellor et al., 2020), and snip (Lee et al., 2019). Both synflow and snip are
originally proposed as metrics for network pruning, which is the process of
removing less important weights from a neural network in order to reduce its
complexity. However, they differ in how they determine the importance of
weights. The intuitions and calculations for these training-free metrics are
provided in the supplementary material.

Krishnakumar et al. (Krishnakumar et al., 2022) analyze the biases inherent in
training-free metrics on NAS benchmarks and indicate that training-free
metrics exhibit varying degrees of biases. For instance, synflow was found to
have a strong bias towards larger cell sizes on NAS-Bench-201, meaning its
preference for larger architectures. Similarly, both snip and synflow
demonstrate a high bias with respect to the number of architecture parameters.
Recognizing these biases is crucial for understanding the limitations of
training-free metrics and also for developing methods to reduce bias, which
can lead to improved performance in NAS (Krishnakumar et al., 2022).

Many studies have been conducted recently to effectively employ training-free
metrics for NAS. For example, FreeGEA (Cavagnero et al., 2023) combines
synflow, linear regions, and the number of skip layers as a single objective
to be optimized. In contrast, E-TF-MOENAS (Luong et al., 2024) optimizes
synflow, jacov, and the number of parameters (or FLOPs) simultaneously as
separate objectives. Abdelfattah et al. (Abdelfattah et al., 2021) propose a
voting mechanism utilizing all three metrics synflow, jacov, and snip. The
voting results are shown to achieve a strong correlation with network accuracy
on various NAS benchmarks. Using multiple training-free metrics is a suggested
way to increase NAS performance, while mitigating the bias of each training-
free metric (Krishnakumar et al., 2022). In this work, our proposed novelty
search approach also utilizes synflow, jacov, and snip simultaneously.
However, these metrics are used as character descriptors for calculating the
novelty score of an architecture, rather than being directly optimized as
performance objectives as in aforementioned approaches.

###  2.3. Novelty Search

Suppose we have a set of individuals
$P=\\{\mathbf{a}_{1},\mathbf{a}_{2},\ldots,\mathbf{a}_{N}\\}$, where each
individual $\mathbf{a}$ has a set of descriptors $\phi(\mathbf{a})$. The
novelty score $\eta(\mathbf{x})$ for an individual $\mathbf{x}$ can be
calculated as follows:

(3)
$\eta(\mathbf{x})=\frac{1}{N}\sum_{i=1}^{N}\delta(\phi(\mathbf{x}),\phi(\mathbf{a}_{i}))$

In this formula, $\delta$ represents a distance function (e.g., Euclidean
distance), which quantifies the difference between the descriptor set
$\phi(\mathbf{x})$ of individual $\mathbf{x}$ and those of each other
individual $\mathbf{a}_{i}$ in the set of individuals $P$. This aims to
encourage the algorithm’s exploration of less-visited parts of the descriptor
space, rewarding individuals with unique descriptors. In NAS, this approach
enhances the likelihood of identifying architectures that may be overlooked
when the exploration of the search space is driven directly by performance
metrics. However, designing a novelty score $\eta$ requires task-specific
knowledge as we must find a way to strike a balance between the novelty and
the quality of architectures.

Despite the potential, the application of NS in NAS has been explored in a
relatively limited number of studies. Zhang et al. (Zhang et al., 2020b)
proposed a mechanism based on NS to apply an architecture sampling controller
in one-shot NAS (Pham et al., 2018; Bender et al., 2018). The work of Sinha et
al. (Sinha and Chen, 2022b), on the other hand, utilized NS for both supernet
training and maintaining a diverse set of solutions during the search. They
employed the multi-objective evolutionary algorithm NSGA-II (Deb et al., 2002)
to maximize both novelty score and architecture fitness. This approach aims to
balance between exploration and the pursuit of high-performing architectures.
However, they did not consider the complexity of architectures despite
employing multi-objective optimization. Both of these studies calculate the
novelty score based on differences in architectural designs, but overlook
information about performance and complexity metrics. Moreover, they still
require training the supernets to predict the performance of candidate
architectures, which incurs significant computational costs.

##  3\. Methodology

In contrast to previous studies that primarily focus on architectural novelty
based on design attributes in Section 2.3, our method proposes a metric-based
novelty score that utilizes training-free performance and complexity metrics
for multi-objective NAS. We argue that diversity of obtained architectures in
terms of performance and complexity is more beneficial for decision makers
than diversity in terms of network design. In this section, we discuss in
detail how we calculate the novelty score and enhance the exploration of new
architectures while still maintaining the quality of the approximation front.

###  3.1. Pareto Dominance-based Novelty Search

Algorithm 1 MTF-PDNS

1: Initialize a population
$P=\\{\mathbf{x}_{1},\mathbf{x}_{2},\ldots,\mathbf{x}_{N}\\}$ of $N$
architectures

2: Initialize an empty elitist archive $\mathcal{A}$

3: for each architecture $\mathbf{x}_{i}$ in $P$ do

4: Evaluate $\mathbf{x}_{i}$ using training-free and complexity metrics

5: Update $\mathcal{A}$ based on the evaluation of $\mathbf{x}_{i}$

6: end for

7: while termination criteria not met do

8: Apply crossover and mutation on $P$ to create offspring architectures
$O=\\{\mathbf{y}_{1},\mathbf{y}_{2},\ldots,\mathbf{y}_{N}\\}$

9: for each architecture $\mathbf{y}_{i}$ in $O$ do

10: Evaluate $\mathbf{y}_{i}$ using training-free and complexity metrics

11: Update $\mathcal{A}$ based on the evaluation of $\mathbf{y}_{i}$

12: end for

13: for each architecture $\mathbf{x}$ in $P\cup O$ do

14: Compute novelty score $\eta(\mathbf{x})$

15: end for

16: Select architectures from $P\cup O$ based on $\eta(\mathbf{x})$

17: end while

18: return Elitist archive $\mathcal{A}$ as approximation front

Our method is illustrated in Algorithm 1. At the start of the algorithm, we
randomly initialize a population
$P=\\{\mathbf{x}_{1},\mathbf{x}_{2},\ldots,\mathbf{x}_{N}\\}$ of $N$
architectures for the genetic algorithm (line 1). Each architecture is then
assessed using three training-free metrics: synflow, jacov and snip, along
with a complexity metric (e.g., FLOPs or the number of parameters). An elitist
archive $\mathcal{A}$ is created (line 2) and is considered for update each
time a candidate architecture from $P$ is evaluated (lines 3-6).

An elitist archive $\mathcal{A}$ (Coello Coello et al., 2005) is a subset of
architectures that only contains non-dominated architectures from the entire
architecture set explored so far. It is often incorporated in multi-objective
optimization algorithms to keep track of the best solutions found during the
search process. Every time a new architecture $\mathbf{y}$ is generated in the
search process, we evaluate whether this new architecture $\mathbf{y}$ is
dominated by any existing architecture $\mathbf{x}$ in the elitist archive
$\mathcal{A}$. If $\mathbf{y}$ is not dominated by any architecture in
$\mathcal{A}$, it is then added to $\mathcal{A}$. Following this addition,
architectures $\mathbf{x}$ that are dominated by the newly added architecture
$\mathbf{y}$ are removed from $\mathcal{A}$. The procedure of updating elitist
archive $\mathcal{A}$ is detailed in the supplementary material. In our
method, the elitist archive $\mathcal{A}$ serves as a memory of the search
process, storing non-dominated architectures and serving as a component to
compute the novelty score. It is updated dynamically after each generation and
evaluation of new architectures, ensuring that the novelty scores are always
relative to the current state of the search process. This dynamic updating
mechanism intensifies the exploratory pressure toward novel regions within the
descriptor space (Lehman and Stanley, 2011).

In each generation, we apply crossover and mutation operations on parent
architectures $P$ to create a set of offspring architectures $O$ (line 8).
Similar to the initialization step, these offspring architectures are assessed
using three training-free metrics: synflow, jacov and snip, along with a
complexity metric (e.g., FLOPs or the number of parameters). The elitist
archive $\mathcal{A}$ is also updated based on these metrics of offspring
architectures (line 9-12).

The novelty score $\eta(\mathbf{x})$ for each architecture in both the parent
set $P$ and offspring set $O$ is calculated as the mean Euclidean distance
from the descriptor set of these architectures to the ones existing in the
elitist archive $\mathcal{A}$ (line 13-15). The descriptor set
$\phi(\mathbf{x})$ of architecture $\mathbf{x}$ includes three training-free
metrics (synflow, jacov, snip) and a complexity metric evaluated in previous
steps. It is important that these metrics should be normalized prior to the
calculations of novelty scores. This normalization is crucial because it
ensures that all metrics have equal weights, preventing the dominance of
certain metrics due to scale differences. Without normalization, metrics with
larger numerical ranges could dominate the novelty score, leading to biased
search results. Following the computation of the novelty scores, a selection
process is carried out to retain architectures from both parent set $P$ and
offspring set $O$ that exhibit higher novelty scores (line 16). At the end of
the algorithm, the final elitist archive $\mathcal{A}$ is returned as the
approximation set, serving as the result of our method (line 18). Figure 1
illustrates our PDNS framework.

Table 1. Summary results on NAS-Bench-101 and NAS-Bench-1Shot1. Underline results indicate which method is significantly better when using the same performance objective (p-value ¡ 0.01) | NAS-Bench-101 | NAS-Bench-1Shot1
---|---|---
Methods | $\text{IGD}^{+}\downarrow$ |  Hypervolume $\uparrow$ |  | Search cost
---
(hours) $\downarrow$
$\text{IGD}^{+}\downarrow$ |  Hypervolume $\uparrow$ |  | Search cost
---
(hours) $\downarrow$
MOENAS-synflow | $0.0160\pm{\scriptstyle 0.0055}^{-}$ | $1.0152\pm{\scriptstyle 0.0074}^{-}$ | $0.44$ | $0.0370\pm{\scriptstyle 0.0046}^{-}$ | $0.9989\pm{\scriptstyle 0.0154}^{-}$ | $0.52$
PDNS-synflow | $\underline{0.0126\pm{\scriptstyle 0.0027}^{-}}$ | $\underline{1.0223\pm{\scriptstyle 0.0036^{-}}}$ | $1.45$ | $0.0364\pm{\scriptstyle 0.0040}^{-}$ | $\underline{1.0102\pm{\scriptstyle 0.0095}^{-}}$ | $1.28$
MOENAS-jacov | $0.0339\pm{\scriptstyle 0.0082}^{-}$ | $0.9843\pm{\scriptstyle 0.0131}^{-}$ | $1.11$ | $0.0355\pm{\scriptstyle 0.0054}^{-}$ | $0.9806\pm{\scriptstyle 0.0061}^{-}$ | $0.91$
PDNS-jacov | $0.0312\pm{\scriptstyle 0.0072}^{-}$ | $0.9901\pm{\scriptstyle 0.0113}^{-}$ | $2.36$ | $0.0320\pm{\scriptstyle 0.0084}^{-}$ | $0.9865\pm{\scriptstyle 0.0112}^{-}$ | $2.27$
MOENAS-snip | $0.0648\pm{\scriptstyle 0.0149}^{-}$ | $0.9544\pm{\scriptstyle 0.0200}^{-}$ | $0.59$ | $0.0723\pm{\scriptstyle 0.0065}^{-}$ | $0.9539\pm{\scriptstyle 0.0138}^{-}$ | $0.59$
PDNS-snip | $\underline{0.0500\pm{\scriptstyle 0.0146}^{-}}$ | $\underline{0.9691\pm{\scriptstyle 0.0173}^{-}}$ | $1.94$ | $0.0740\pm{\scriptstyle 0.0072}^{-}$ | $0.9507\pm{\scriptstyle 0.0136}^{-}$ | $1.57$
MOENAS-valacc | $0.0052\pm{\scriptstyle 0.0017}^{-}$ | $1.0279\pm{\scriptstyle 0.0030}^{-}$ | $38.53$ | $0.0042\pm{\scriptstyle 0.0012}^{-}$ | $1.0276\pm{\scriptstyle 0.0032}^{-}$ | $30.66$
PDNS-valacc | $\underline{\mathbf{0.0040\pm{\scriptstyle 0.0006}^{+}}}$ | $\underline{\mathbf{1.0306\pm{\scriptstyle 0.0017}^{\approx}}}$ | $104.44$ | $\underline{\mathbf{0.0033\pm{\scriptstyle 0.0007}^{+}}}$ | $\underline{\mathbf{1.0299\pm{\scriptstyle 0.0023}^{\approx}}}$ | $90.75$
MTF-MOENAS | $0.0126\pm{\scriptstyle 0.0034}^{-}$ | $1.0261\pm{\scriptstyle 0.0045}^{-}$ | $0.94$ | $0.0123\pm{\scriptstyle 0.0045}^{-}$ | $1.0264\pm{\scriptstyle 0.0034}^{-}$ | $0.83$
MTF-PDNS | $\underline{0.0084\pm{\scriptstyle 0.0014}^{-}}$ | $\underline{\mathbf{1.0297\pm{\scriptstyle 0.0015}^{\approx}}}$ | $2.02$ | $0.0100\pm{\scriptstyle 0.0021}^{-}$ | $\underline{\mathbf{1.0295\pm{\scriptstyle 0.0015}^{\approx}}}$ | $1.56$
$+$ Denotes a method that delivers significantly better performance (p-value ¡
0.01).
$\approx$ Denotes a method that achieves performance comparable to the best-
performing method.
$-$ Denotes a method that delivers significantly worse performance (p-value ¡
0.01).

###  3.2. Novelty Score

We compute the novelty score of an architecture $\mathbf{x}$ as:

(4)
$\eta(\mathbf{x})=\frac{1}{|\mathcal{A}|}\sum_{i=1}^{|\mathcal{A}|}\|\phi(\mathbf{x})-\phi(\mathbf{a}_{i})\|,$

where $\|\phi(\mathbf{x})-\phi(\mathbf{a}_{i})\|$ represents the Euclidean
distance which quantifies the difference between the descriptor set
$\phi(\mathbf{x})$ of architecture $\mathbf{x}$ and the descriptor set
$\phi(\mathbf{a}_{i})$ of architecture $\mathbf{a}_{j}$ in the elitist archive
$\mathcal{A}$. As mentioned above, the descriptor set of an architecture
includes four values: synflow, jacov and snip, along with a complexity metric
(e.g., FLOPs or the number of parameters). As the novelty score is a measure
of how different an architecture $\mathbf{x}$ is from those $\mathbf{a}_{j}$
in the elitist archive $\mathcal{A}$, this encourages the exploration of a
wide range of architectures, thereby reducing the risk of converging
prematurely to local optima. However, such a naive approach may inadvertently
assign high novelty scores to architectures that perform poorly at both
performance and complexity metrics in the descriptor space. This could result
in the search process expanding substantial effort exploring regions that are
irrelevant to the task objectives (Gomes et al., 2015).

To address this issue, we propose the use of a sign function that adjusts the
novelty scores based on whether the architecture is included in the elitist
archive $\mathcal{A}$. Architectures that belong to the elitist archive
$\mathcal{A}$ can be assigned a positive novelty score, indicating that a
larger score corresponds to a higher novelty. However, for architectures not
included in the updated elitist archive $\mathcal{A}$, which typically
correspond to poor-performing and dominated architectures, we aim to limit
their survival to the next generation due to their potentially detrimental
effect on the search process. Hence, these architectures are assigned a
negative novelty score. This implies that a larger absolute value of these
negative novelty scores indicates poorer performance, effectively discouraging
the algorithm from retaining these architectures in subsequent generations.
When running the algorithm, we aim to maximize this novelty score. The
adjusted novelty score can be described as follows:

(5)
$\eta(\mathbf{x})=\begin{cases}\frac{1}{|\mathcal{A}|}\sum_{i=1}^{|\mathcal{A}|}\|\phi(\mathbf{x})-\phi(\mathbf{a}_{i})\|,&\text{if
}\mathbf{x}\in\mathcal{A}\\\
-\frac{1}{|\mathcal{A}|}\sum_{i=1}^{|\mathcal{A}|}\|\phi(\mathbf{x})-\phi(\mathbf{a}_{i})\|,&\text{if
}\mathbf{x}\notin\mathcal{A}\end{cases}$

By including both training-free performance metrics and complexity metrics in
the descriptor space $\phi(\mathbf{x})$, the novelty score takes into account
multiple conflicting metrics. The novelty score is also calculated based on
the current elitist archive $\mathcal{A}$, which means it adapts over time as
the archive evolves. This allows the algorithm to adjust its notion of
_novelty_ based on the architectures it has seen so far, enabling a more
dynamic and responsive search process. Moreover, the integration of novelty
and fitness can encourage the discovery of high-quality architectures, while
still preserving the diversity of architectures in the search process (Gomes
et al., 2015). Notably, our proposed novelty score also prioritizes assigning
higher novelty scores to non-dominated architectures that appear within
regions of low architectural density in our elitist archive. It promotes
diversity in the population by favoring solutions in less crowded niches. In
other words, this strategy encourages the algorithm to explore sparser areas,
similar to NSGA-II’s crowding distance principles (Deb et al., 2002).

##  4\. Experiments

###  4.1. Experimental settings

We conduct our experiments on the following NAS benchmarks: NAS-Bench-101
(Ying et al., 2019), which offers a comprehensive evaluation of 423,624
architectures on CIFAR-10; NAS-Bench-1Shot1 (Zela et al., 2020), an extension
of NAS-Bench-101 that includes around 363,648 architectures; and NAS-Bench-201
(Dong and Yang, 2020), comprising 15,625 architectures assessed across
multiple datasets, including CIFAR-10, CIFAR-100, and ImageNet16-120. These
NAS benchmarks provide performance information for each architecture, e.g.,
accuracy, number of parameters, FLOPs, training time, etc. To assess the
quality of the obtained approximation fronts, we employ the two quality
indicators: Inverted Generational Distance Plus (IGD+) (Ishibuchi et al.,
2015) and Hypervolume (Zitzler and Thiele, 1999). Further details on NAS
benchmarks and quality indicators can be found in the supplementary material.

When evaluating the training-free metrics for architectures in these NAS
benchmarks, we utilize the pre-computed scores and the recorded computing
times of the training-free metrics from (Abdelfattah et al., 2021) and
(Krishnakumar et al., 2022). Besides our main proposed method MTF-PDNS using
simultaneously synflow, jacov, and snip, we also experiment with other four
baseline versions of PDNS, each employing a different performance metric to
calculate the novelty score along with the complexity metric. Similarly, we
experiment with multiple versions of the multi-objective evolutionary
algorithm NSGA-II (Deb et al., 2002) for NAS (MOENAS) as baseline methods,
where each optimizes performance objectives in combination with a complexity
metric.

  * •

MOENAS-synflow, MOENAS-jacov, MOENAS-snip, together with MOENAS-valacc: These
methods employ synflow, jacov, snip or validation accuracy at epoch 12
respectively, as the single performance objective alongside the complexity
objective to be optimized with NSGA-II.

  * •

MTF-MOENAS: This method uses synflow, jacov, snip versus complexity metric as
four objectives to be optimized with NSGA-II.

  * •

PDNS-synflow, PDNS-jacov, PDNS-snip, and PDNS-valacc: These methods use
synflow, jacov, snip or validation accuracy at epoch 12 respectively as the
single performance metric, in conjunction with a complexity metric to
calculate the novelty score.

  * •

MTF-PDNS (ours): This method uses synflow, jacov, and snip versus a complexity
metric simultaneously as multiple criteria for computing the novelty score.

The PDNS-synflow/jacov/snip/valacc variants only optimize a single objective,
which is the novelty score, using the Genetic Algorithm (GA). The complexity
metrics are FLOPs for NAS-Bench-201, and the number of parameters for both
NAS-Bench-101 and NAS-Bench-1Shot1. PDNS employs two-point crossover and
uniform mutation with population size 20. Meanwhile, MOENAS is implemented
using pymoo framework (Blank and Deb, 2020) with default settings as: two-
point crossover, polynomial mutation, and population size 20. Both methods run
for 150 generations when applied to larger NAS benchmarks such as NAS-
Bench-101 and NAS-Bench-1Shot1. For the smaller benchmark NAS-Bench-201, the
number of generations is 50. Both MOENAS and PDNS utilize an elitist archive
to maintain a set of non-dominated architectures obtained so far during the
search. While the elitist archive in MOENAS serves solely to preserve the
approximation front, the elitist archive in PDNS is also used for novelty
score calculations. All experiments are conducted over 30 runs on a single
NVIDIA GeForce RTX 3050 Ti laptop GPU. Source codes are available at:
https://github.com/ELO-Lab/PDNS.

###  4.2. Qualify of Final Approximation Front

Table 2. Summary results on NAS-Bench-201. Underline results indicate which method is significantly better when using the same performance objective (p-value ¡ 0.01) | CIFAR-10 | CIFAR-100 | ImageNet16-120
---|---|---|---
Methods | $\text{IGD}^{+}\downarrow$ |  Hypervolume $\uparrow$ |  | Search cost
---
(hours) $\downarrow$
$\text{IGD}^{+}\downarrow$ |  Hypervolume $\uparrow$ |  | Search cost
---
(hours) $\downarrow$
$\text{IGD}^{+}\downarrow$ |  Hypervolume $\uparrow$ |  | Search cost
---
(hours) $\downarrow$
MOENAS-synflow | $0.0126\pm{\scriptstyle 0.0026}^{-}$ | $1.0226\pm{\scriptstyle 0.0043}^{-}$ | $0.13$ | $0.0178\pm{\scriptstyle 0.0034}^{-}$ | $0.7873\pm{\scriptstyle 0.0054}^{-}$ | $0.11$ | $0.0227\pm{\scriptstyle 0.0044}^{-}$ | $0.5080\pm{\scriptstyle 0.0063}^{-}$ | $0.18$
PDNS-synflow | $0.0140\pm{\scriptstyle 0.0029}^{-}$ | $1.0219\pm{\scriptstyle 0.0030}^{-}$ | $0.21$ | $0.0197\pm{\scriptstyle 0.0046}^{-}$ | $0.7836\pm{\scriptstyle 0.0057}^{-}$ | $0.18$ | $0.0226\pm{\scriptstyle 0.0056}^{-}$ | $0.5071\pm{\scriptstyle 0.0078}^{-}$ | $0.31$
MOENAS-jacov | $0.0220\pm{\scriptstyle 0.0098^{-}}$ | $1.0089\pm{\scriptstyle 0.0135}^{-}$ | $0.14$ | $\underline{0.0332\pm{\scriptstyle 0.0103}^{-}}$ | $\underline{0.7620\pm{\scriptstyle 0.0153}^{-}}$ | $0.15$ | $0.0428\pm{\scriptstyle 0.0171}^{-}$ | $0.4673\pm{\scriptstyle 0.0244}^{-}$ | $0.19$
PDNS-jacov | $0.0251\pm{\scriptstyle 0.0097}^{-}$ | $1.0044\pm{\scriptstyle 0.0130}^{-}$ | $0.23$ | $0.0501\pm{\scriptstyle 0.0191}^{-}$ | $0.7384\pm{\scriptstyle 0.0243}^{-}$ | $0.23$ | $0.0470\pm{\scriptstyle 0.0162}^{-}$ | $0.4612\pm{\scriptstyle 0.0233}^{-}$ | $0.29$
MOENAS-snip | $0.0569\pm{\scriptstyle 0.0126}^{-}$ | $0.9660\pm{\scriptstyle 0.0164}^{-}$ | $0.16$ | $0.1151\pm{\scriptstyle 0.0221}^{-}$ | $0.6635\pm{\scriptstyle 0.0279}^{-}$ | $0.16$ | $0.1541\pm{\scriptstyle 0.0332}^{-}$ | $0.3424\pm{\scriptstyle 0.0348}^{-}$ | $0.18$
PDNS-snip | $0.0630\pm{\scriptstyle 0.0073}^{-}$ | $0.9575\pm{\scriptstyle 0.0092}^{-}$ | $0.23$ | $0.1190\pm{\scriptstyle 0.0184}^{-}$ | $0.6568\pm{\scriptstyle 0.0226}^{-}$ | $0.24$ | $0.1653\pm{\scriptstyle 0.0209}^{-}$ | $0.3308\pm{\scriptstyle 0.0213}^{-}$ | $0.29$
MOENAS-valacc | $\mathbf{0.0063\pm{\scriptstyle 0.0016}^{\approx}}$ | $1.0286\pm{\scriptstyle 0.0016}^{-}$ | $21.62$ | $0.0198\pm{\scriptstyle 0.0091}^{-}$ | $0.7837\pm{\scriptstyle 0.0083}^{-}$ | $22.27$ | $0.0199\pm{\scriptstyle 0.0083}^{-}$ | $0.5099\pm{\scriptstyle 0.0070}^{-}$ | $69.80$
PDNS-valacc | $\mathbf{0.0063\pm{\scriptstyle 0.0015}^{\approx}}$ | $1.0283\pm{\scriptstyle 0.0017}^{-}$ | $35.81$ | $\underline{0.0142\pm{\scriptstyle 0.0037}^{-}}$ | $0.7875\pm{\scriptstyle 0.0061}^{-}$ | $38.51$ | $0.0173\pm{\scriptstyle 0.0055}^{-}$ | $0.5108\pm{\scriptstyle 0.0057}^{-}$ | $120.06$
MTF-MOENAS | $0.0080\pm{\scriptstyle 0.0020}^{-}$ | $1.0300\pm{\scriptstyle 0.0019}^{-}$ | $0.20$ | $0.0134\pm{\scriptstyle 0.0032}^{-}$ | $\mathbf{0.7939\pm{\scriptstyle 0.0047}^{\approx}}$ | $0.20$ | $0.0163\pm{\scriptstyle 0.0046}^{-}$ | $0.5141\pm{\scriptstyle 0.0053}^{-}$ | $0.23$
MTF-PDNS | $\underline{\mathbf{0.0058\pm{\scriptstyle 0.0015}^{\approx}}}$ | $\underline{\mathbf{1.0315\pm{\scriptstyle 0.0011}^{+}}}$ | $0.28$ | $\underline{\mathbf{0.0108\pm{\scriptstyle 0.0030}^{+}}}$ | $\mathbf{0.7965\pm{\scriptstyle 0.0031}^{\approx}}$ | $0.28$ | $\underline{\mathbf{0.0134\pm{\scriptstyle 0.0033}^{+}}}$ | $\underline{\mathbf{0.5180\pm{\scriptstyle 0.0037}^{+}}}$ | $0.32$
$+$ Denotes a method that delivers significantly better performance (p-value ¡
0.01).
$\approx$ Denotes a method that achieves performance comparable to the best-
performing method.
$-$ Denotes a method that delivers significantly worse performance (p-value ¡
0.01).

Our experiment results presented across various NAS benchmarks consistently
demonstrate the effectiveness of our proposed MTF-PDNS approach in terms of
the quality of the approximation front. On NAS-Bench-101 as shown in Table 1,
PDNS variants show a substantial increase in IGD+ and Hypervolume compared to
MOENAS variants, especially those employing a single metric like synflow,
snip, valacc. Notably, MTF-PDNS, which employs all three training-free
performance metrics (synflow, jacov, snip) and the complexity metric (the
number of parameters) exhibits comparable performance to the training-based
PDNS-valacc. MTF-PDNS achieves this result in a mere 2.02 GPU hours,
dramatically less than the 104.44 GPU hours required by PDNS-valacc. Besides,
the accuracy results of NAS-Bench-101 can be found in the supplementary
material.

On NAS-Bench-1Shot1, the advantage of PDNS over MOENAS was not as striking
when using a single training-free metric as shown in Table 1. However, we
observed substantial improvements in both IGD+ and Hypervolume when utilizing
valacc or combining all three training-free metrics in PDNS. These
improvements make PDNS-valacc and MTF-PDNS surpass MOENAS-valacc and MTF-
MOENAS, respectively. The usage of a sole training-free metric in this search
space may not establish a robust correlation with actual performance,
potentially causing deception and bias in the exploration during the novelty
search process. In other words, the metrics must be strong correlation enough
to strike a balance between exploring new architectures and efficiently
exploiting existing ones. This balance can be achieved by combining multiple
training-free metrics to calculate the novelty score as in MTF-PDNS. By
employing this mechanism, MTF-PDNS manages to achieve significantly better
IGD+ and Hypervolume metrics compared to MTF-MOENAS, which directly uses
training-free metrics as performance objectives. This improvement underscores
the utility of a multi-faceted assessment approach in finding high-performing
architectures, highlighting the capability of MTF-PDNS to navigate the
architectural design space more efficiently and effectively. Moreover, the
addition of more training-free metrics requires only a few extra seconds but
yields considerable benefits. Regarding the search cost, MTF-PDNS again
demonstrates its efficiency in this search space, achieving competitive
results with just 1.56 GPU hours, dramatically less than the 90.75 GPU hours
required by PDNS-valacc.

(a) CIFAR-10

(b) CIFAR-100

(c) ImageNet16-120

Figure 2. Distribution of operations in architectures on final approximation
fronts of MTF-MOENAS and MTF-PDNS on NAS-Bench-201. Figure 3. Comparison of
IGD+ (top) and Hypervolume (bottom) metrics with respect to GPU hours on NAS
benchmarks.

Table 2 presents the results in the small search space NAS-Bench-201. We find
that an increased exploration of architectures does not always lead to
enhanced search performance. Despite exploring more architectures, PDNS does
not always produce better results than MOENAS. This outcome occurs when the
novelty search is guided solely by a single training-free metric, which leads
to issues due to the biases of training-free metrics (discussed in Section
2.2). However, when multiple training-free metrics are incorporated, as is the
case of MTF-PDNS, we see a significant performance improvement in comparison
with MTF-MOENAS. This is similar to what we observe on NAS-Bench-101 and NAS-
Bench-1Shot1. Using more training-free metrics as descriptors to calculate the
novelty score leads to more informative evaluations and provides a more
comprehensive description of an architecture’s characteristics. MTF-PDNS also
incurs a relatively low search cost compared to other methods, achieving these
impressive results using about only 0.3 GPU hours across datasets.

Figure 2 illustrates the operational preferences in the design space explored
by MTF-MOENAS and MTF-PDNS within NAS-Bench-201. Table 2 shows that MTF-PDNS
achieves higher-quality approximation fronts compared to MTF-MOENAS. Notably,
the 3x3 convolution operation predominates in the architectures on the
approximation fronts obtained by MTF-PDNS, whereas the 1x1 convolution is more
prevalent in those from MTF-MOENAS on all datasets of NAS-Bench-201. This
observation suggests that favoring 3x3 convolution over 1x1 convolution could
enhance the quality of approximation fronts in the search process.

###  4.3. Efficiency and Stability

Figure 3 illustrates that the steeper curve of MTF-PDNS exhibits a faster
convergence rate compared to other methods across different NAS benchmarks.
While using the same number of evaluations as MOENAS-valacc and PDNS-valacc,
MTF-PDNS identifies high-quality approximation fronts at a quicker pace than
these training-based methods. This demonstrates the efficiency of MTF-PDNS in
the search process when using training-free metrics instead of using training-
based metrics. In addition, MTF-PDNS consistently surpasses MTF-MOENAS across
various NAS benchmarks in terms of GPU hours. MTF-PDNS consistently achieves
lower IGD+ and higher Hypervolume values compared to MTF-MOENAS during the
entire search process. Note that both methods utilize training-free metrics,
underscoring the effectiveness of the novelty-guided search mechanism of MTF-
PDNS.

A notable characteristic of MTF-PDNS is its stability shown in Figure 3. This
is evidenced by its steady curve with less fluctuation in IGD+ and
Hypervolume. Such stability indicates that MTF-PDNS is more reliable in
locating high-quality approximation fronts within just a limited number of GPU
hours. The reason behind this can be attributed to the increasing number of
architectures explored during the novelty search. As this number increases,
the combination of multiple metrics provides a more accurate calculation of
the novelty score. The combination of training-free metrics can also help to
circumvent the limitations associated with individual metrics, particularly
when they exhibit biases related to factors such as the cell size of
architectures or the number of parameters (Krishnakumar et al., 2022).
Consequently, it results in more reliable guidance for the exploration
process. This mechanism ensures that the search is effectively directed toward
new and promising regions of the architectural space, enhancing the likelihood
of discovering high-performing architectures that are different from the
existing ones.

Figure 4. Visual representation of architectures explored by MTF-MOENAS (top)
and MTF-PDNS (bottom) within the performance and complexity space on NAS
benchmarks. Circles with no edges and blurred represent the architectures that
are not explored by the corresponding search algorithm.

###  4.4. Transferability

Table 3. Test accuracy comparison for transfer learning tasks on NAS-Bench-201 |  | CIFAR-10
---
(direct)
| CIFAR-100
---
(transfer)
| ImageNet16-120
---
(transfer)
Evolution
REA (Real et al., 2019) | $93.92\pm{\scriptstyle 0.30}^{-}$ | $71.84\pm{\scriptstyle 0.99}^{-}$ | $45.54\pm{\scriptstyle 1.03}^{-}$
G-EA (Lopes et al., 2022) | $93.99\pm{\scriptstyle 0.23}^{-}$ | $72.36\pm{\scriptstyle 0.66}^{-}$ | $46.04\pm{\scriptstyle 0.67}^{-}$
EvNAS (Sinha and Chen, 2021) | $92.18\pm{\scriptstyle 1.11}^{-}$ | $66.74\pm{\scriptstyle 3.08}^{-}$ | $39.00\pm{\scriptstyle 0.44}^{-}$
Fast-ENAS (Peng et al., 2023) | $93.74\pm{\scriptstyle 0.22}^{-}$ | $72.00\pm{\scriptstyle 0.92}^{-}$ | $45.74\pm{\scriptstyle 0.80}^{-}$
SF-GOMENAS (Tran et al., 2023) | $\mathbf{94.22\pm{\scriptstyle 0.17}^{\approx}}$ | $\mathbf{72.76\pm{\scriptstyle 0.63}^{\approx}}$ | $46.16\pm{\scriptstyle 0.45}^{-}$
PRE-NAS (Peng et al., 2022) | $94.04\pm{\scriptstyle 0.34}^{-}$ | $72.02\pm{\scriptstyle 1.22}^{-}$ | $45.34\pm{\scriptstyle 1.03}^{-}$
pEvoNAS (Sinha and Chen, 2022a) | $93.63\pm{\scriptstyle 0.42}^{-}$ | $69.05\pm{\scriptstyle 1.99}^{-}$ | $39.98\pm{\scriptstyle 3.76}^{-}$
MOENAS-valacc${}^{\text{\textdagger}}$ | $93.86\pm{\scriptstyle 0.17}^{-}$ | $71.14\pm{\scriptstyle 0.48}^{-}$ | $45.11\pm{\scriptstyle 1.00}^{-}$
MTF-MOENAS${}^{*\text{\textdagger}}$ | $94.14\pm{\scriptstyle 0.22}^{-}$ | $\mathbf{72.75\pm{\scriptstyle 0.68}^{\approx}}$ | $\mathbf{46.51\pm{\scriptstyle 0.33}^{\approx}}$
Novelty Search
EN2NAS (Zhang et al., 2020b) | $93.36\pm{\scriptstyle 0.30}^{-}$ | N/A | N/A
NEvoNAS (Sinha and Chen, 2022c) | $93.50\pm{\scriptstyle 0.30}^{-}$ | $71.51\pm{\scriptstyle 0.52}^{-}$ | $45.30\pm{\scriptstyle 0.82}^{-}$
PDNS-valacc${}^{\text{\textdagger}}$ | $93.81\pm{\scriptstyle 0.27}^{-}$ | $71.00\pm{\scriptstyle 0.83}^{-}$ | $44.93\pm{\scriptstyle 1.08}^{-}$
MTF-PDNS (ours)${}^{*\text{\textdagger}}$ | $\mathbf{94.28\pm{\scriptstyle 0.13}^{\approx}}$ | $\mathbf{73.15\pm{\scriptstyle 0.53}^{\approx}}$ | $\mathbf{46.47\pm{\scriptstyle 0.28}^{\approx}}$
Optimal (in benchmark) | $\mathbf{94.37}$ | $\mathbf{73.51}$ | $\mathbf{47.31}$
* Training-Free | † Multi-Objective |
$+$ Denotes a method that delivers significantly better performance (p-value ¡
0.01).
$\approx$ Denotes a method that achieves performance comparable to the best-
performing method.
$-$ Denotes a method that delivers significantly worse performance (p-value ¡
0.01).

Table 3 compares the transferability of MTF-PDNS against other evolutionary
and novelty search approaches on NAS-Bench-201. The experiments are initially
conducted on CIFAR-10, and the architectures from the obtained approximation
fronts are then transferred to CIFAR-100 and ImgageNet16-120 for evaluation.
The results of transfer learning tasks are particularly crucial in real-world
scenarios where the ultimate goal is to apply the discovered architectures to
unseen tasks.

In terms of accuracy, MTF-PDNS archives comparable performance with SF-GOMENAS
(Tran et al., 2023) on CIFAR-10, CIFAR-100, and to MTF-MOENAS on CIFAR-100 and
ImageNet16-120 and surpasses all other methods listed in Table 3 in
identifying top-performing architectures. However, it is worth noting that SF-
GOMENAS is a training-based single-objective method. While it also employs
synflow to accelerate its solution variation, it still uses validation
accuracy as the objective, requiring a training procedure that increases the
search cost of SF-GOMEA. MTF-PDNS also achieves better performance compared to
NEvoNAS (Sinha and Chen, 2022c) and EN2NAS (Zhang et al., 2020b), other
methods that utilize Novelty Search for NAS. Despite its high performance,
MTF-PDNS utilizes completely training-free metrics in the search process,
maintaining a relatively low cost compared to training-based methods. The
results indicate that the best-performing architectures on the approximation
fronts obtained by MTF-PDNS exhibit the ability to generalize well across
different tasks. The IGD+ and Hypervolume results on transfer learning task
can be found in the supplementary material.

###  4.5. Architectural Coverage and Prioritization

Figure 4 illustrates the architectures explored by MTF-PDNS and MTF-MOENAS on
various NAS benchmarks. MTF-PDNS demonstrates its ability to cover a broader
range of architectures in the search space compared to MTF-MOENAS. Notably,
MTF-PDNS focuses on architectures in the high accuracy-low complexity area, as
evidenced by the color density in these regions. It indicates that MTF-PDNS
prioritizes not just any new architectures, but those that potentially expand
the approximation front. This characteristic becomes particularly evident in
larger search spaces like NAS-Bench-101 and NAS-Bench-1Shot1. The observed
pattern shows that our method enhances the novelty search process while
maintaining focus on exploration within valuable regions of the search space.
We also have additional experiments about the efficiency in architecture
exploration of MTF-PDNS and MTF-MOENAS in the supplementary material.

##  5\. Conclusions

In this work, we presented MTF-PDNS, the Pareto Dominance-based Novelty Search
with Multiple Training-Free metrics framework for NAS, leveraging the
strengths of training-free metrics and a novelty search approach. Our method
demonstrated substantial performance improvements across various NAS
benchmarks, often outperforming traditional NAS methods. The key strength of
MTF-PDNS lies in its novelty search approach, which prioritizes exploration
over exploitation. This approach allowed MTF-PDNS to explore a broader and
more diverse range of architectures, thereby avoiding premature convergence on
sub-optimal solutions. Moreover, our training-free approach also demonstrated
computational efficiency, incurring low computational costs despite the
expansive exploration of the search space. The combination of multiple
training-free and complexity metrics in MTF-PDNS provided a more holistic
assessment of novelty scores of network architectures, accounting for various
aspects simultaneously. Future works could further explore the potential of
combining other training-free metrics or designing other advanced novelty
search strategies.

###### Acknowledgements.

This research is funded by Vietnam National University HoChiMinh City (VNU-
HCM) under grant number C2024-26-05.

## References

  * (1)
  * Abdelfattah et al. (2021) Mohamed S. Abdelfattah, Abhinav Mehrotra, Lukasz Dudziak, and Nicholas Donald Lane. 2021.  Zero-Cost Proxies for Lightweight NAS. In _9th International Conference on Learning Representations, ICLR 2021, Virtual Event, Austria, May 3-7, 2021_. OpenReview.net.  https://openreview.net/forum?id=0cmMMy8J5q
  * Bender et al. (2018) Gabriel Bender, Pieter-Jan Kindermans, Barret Zoph, Vijay Vasudevan, and Quoc V. Le. 2018.  Understanding and Simplifying One-Shot Architecture Search. In _Proceedings of the 35th International Conference on Machine Learning, ICML 2018, Stockholmsmässan, Stockholm, Sweden, July 10-15, 2018_ _(Proceedings of Machine Learning Research, Vol. 80)_ , Jennifer G. Dy and Andreas Krause (Eds.). PMLR, 549–558.  http://proceedings.mlr.press/v80/bender18a.html
  * Blank and Deb (2020) Julian Blank and Kalyanmoy Deb. 2020.  Pymoo: Multi-Objective Optimization in Python.  _IEEE Access_ 8 (2020), 89497–89509.  https://doi.org/10.1109/ACCESS.2020.2990567
  * Cavagnero et al. (2023) Niccolò Cavagnero, Luca Robbiano, Barbara Caputo, and Giuseppe Averta. 2023.  FreeREA: Training-Free Evolution-based Architecture Search. In _IEEE/CVF Winter Conference on Applications of Computer Vision, WACV 2023, Waikoloa, HI, USA, January 2-7, 2023_. IEEE, 1493–1502.  https://doi.org/10.1109/WACV56688.2023.00154
  * Coello Coello et al. (2005) C. A. Coello Coello, G. Toscano Pulido, and E. Mezura Montes. 2005.  _Current and Future Research Trends in Evolutionary Multiobjective Optimization_.  Springer London, London, 213–231.  https://doi.org/10.1007/1-84628-117-2_15
  * Deb et al. (2002) Kalyanmoy Deb, Samir Agrawal, Amrit Pratap, and T. Meyarivan. 2002.  A fast and elitist multiobjective genetic algorithm: NSGA-II.  _IEEE Trans. Evol. Comput._ 6, 2 (2002), 182–197.  https://doi.org/10.1109/4235.996017
  * Doncieux et al. (2019) Stéphane Doncieux, Alban Laflaquière, and Alexandre Coninx. 2019.  Novelty search: a theoretical perspective. In _Proceedings of the Genetic and Evolutionary Computation Conference, GECCO 2019, Prague, Czech Republic, July 13-17, 2019_ , Anne Auger and Thomas Stützle (Eds.). ACM, 99–106.  https://doi.org/10.1145/3321707.3321752
  * Dong and Yang (2020) Xuanyi Dong and Yi Yang. 2020.  NAS-Bench-201: Extending the Scope of Reproducible Neural Architecture Search. In _8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020_. OpenReview.net.  https://openreview.net/forum?id=HJxyZkBKDr
  * Elsken et al. (2019) Thomas Elsken, Jan Hendrik Metzen, and Frank Hutter. 2019.  Neural architecture search: A survey.  _The Journal of Machine Learning Research_ 20, 1 (2019), 1997–2017.
  * Fister et al. (2019) Iztok Fister, Andrés Iglesias, Akemi Gálvez, Javier Del Ser, Eneko Osaba, Iztok Fister Jr., Matjaz Perc, and Mitja Slavinec. 2019.  Novelty search for global optimization.  _Appl. Math. Comput._ 347 (2019), 865–881.  https://doi.org/10.1016/J.AMC.2018.11.052
  * Gomes et al. (2015) Jorge C. Gomes, Pedro Mariano, and Anders Lyhne Christensen. 2015.  Devising Effective Novelty Search Algorithms: A Comprehensive Empirical Study. In _Proceedings of the Genetic and Evolutionary Computation Conference, GECCO 2015, Madrid, Spain, July 11-15, 2015_ , Sara Silva and Anna Isabel Esparcia-Alcázar (Eds.). ACM, 943–950.  https://doi.org/10.1145/2739480.2754736
  * Gomes et al. (2013) Jorge C. Gomes, Paulo Urbano, and Anders Lyhne Christensen. 2013.  Evolution of swarm robotics systems with novelty search.  _Swarm Intell._ 7, 2-3 (2013), 115–144.  https://doi.org/10.1007/s11721-013-0081-z
  * Ishibuchi et al. (2015) Hisao Ishibuchi, Hiroyuki Masuda, Yuki Tanigaki, and Yusuke Nojima. 2015.  Modified Distance Calculation in Generational Distance and Inverted Generational Distance. In _Evolutionary Multi-Criterion Optimization - 8th International Conference, EMO 2015, Guimarães, Portugal, March 29 -April 1, 2015. Proceedings, Part II_ _(Lecture Notes in Computer Science, Vol. 9019)_ , António Gaspar-Cunha, Carlos Henggeler Antunes, and Carlos A. Coello Coello (Eds.). Springer, 110–125.  https://doi.org/10.1007/978-3-319-15892-1_8
  * Krishnakumar et al. (2022) Arjun Krishnakumar, Colin White, Arber Zela, Renbo Tu, Mahmoud Safari, and Frank Hutter. 2022.  NAS-Bench-Suite-Zero: Accelerating Research on Zero Cost Proxies. In _NeurIPS_.  http://papers.nips.cc/paper_files/paper/2022/hash/b3835dd49b7d5bb062aecccc14d8a675-Abstract-Datasets_and_Benchmarks.html
  * Lee et al. (2019) Namhoon Lee, Thalaiyasingam Ajanthan, and Philip H. S. Torr. 2019.  Snip: single-Shot Network Pruning based on Connection sensitivity. In _7th International Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019_. OpenReview.net.  https://openreview.net/forum?id=B1VZqjAcYX
  * Lehman and Stanley (2011) Joel Lehman and Kenneth O. Stanley. 2011.  Abandoning Objectives: Evolution Through the Search for Novelty Alone.  _Evol. Comput._ 19, 2 (2011), 189–223.  https://doi.org/10.1162/EVCO_a_00025
  * Liapis et al. (2013) Antonios Liapis, Georgios N. Yannakakis, and Julian Togelius. 2013.  Enhancements to constrained novelty search: two-population novelty search for generating game content. In _Genetic and Evolutionary Computation Conference, GECCO ’13, Amsterdam, The Netherlands, July 6-10, 2013_ , Christian Blum and Enrique Alba (Eds.). ACM, 343–350.  https://doi.org/10.1145/2463372.2463416
  * Lopes et al. (2022) Vasco Lopes, Miguel Santos, Bruno Degardin, and Luís A. Alexandre. 2022.  Efficient guided evolution for neural architecture search. In _GECCO ’22: Genetic and Evolutionary Computation Conference, Companion Volume, Boston, Massachusetts, USA, July 9 - 13, 2022_ , Jonathan E. Fieldsend and Markus Wagner (Eds.). ACM, 655–658.  https://doi.org/10.1145/3520304.3528936
  * Lu et al. (2020a) Zhichao Lu, Kalyanmoy Deb, Erik D. Goodman, Wolfgang Banzhaf, and Vishnu Naresh Boddeti. 2020a.  NSGANetV2: Evolutionary Multi-objective Surrogate-Assisted Neural Architecture Search. In _Computer Vision - ECCV 2020 - 16th European Conference, Glasgow, UK, August 23-28, 2020, Proceedings, Part I_ _(Lecture Notes in Computer Science, Vol. 12346)_ , Andrea Vedaldi, Horst Bischof, Thomas Brox, and Jan-Michael Frahm (Eds.). Springer, 35–51.  https://doi.org/10.1007/978-3-030-58452-8_3
  * Lu et al. (2020b) Zhichao Lu, Ian Whalen, Yashesh D. Dhebar, Kalyanmoy Deb, Erik D. Goodman, Wolfgang Banzhaf, and Vishnu Naresh Boddeti. 2020b.  NSGA-Net: Neural Architecture Search using Multi-Objective Genetic Algorithm (Extended Abstract). In _Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence, IJCAI 2020_ , Christian Bessiere (Ed.). ijcai.org, 4750–4754.  https://doi.org/10.24963/ijcai.2020/659
  * Luong and Bosman (2012) Hoang N. Luong and Peter A. N. Bosman. 2012.  Elitist Archiving for Multi-Objective Evolutionary Algorithms: To Adapt or Not to Adapt. In _Parallel Problem Solving from Nature - PPSN XII - 12th International Conference, Taormina, Italy, September 1-5, 2012, Proceedings, Part II_ _(Lecture Notes in Computer Science, Vol. 7492)_ , Carlos A. Coello Coello, Vincenzo Cutello, Kalyanmoy Deb, Stephanie Forrest, Giuseppe Nicosia, and Mario Pavone (Eds.). Springer, 72–81.  https://doi.org/10.1007/978-3-642-32964-7_8
  * Luong et al. (2024) Ngoc Hoang Luong, Quan Minh Phan, An Vo, Tan Ngoc Pham, and Dzung Tri Bui. 2024.  Lightweight multi-objective evolutionary neural architecture search with low-cost proxy metrics.  _Information Sciences_ 655 (2024), 119856.  https://doi.org/10.1016/j.ins.2023.119856
  * Mellor et al. (2020) Joseph Charles Mellor, Jack Turner, Amos J. Storkey, and Elliot J. Crowley. 2020.  Neural Architecture Search without Training.  _CoRR_ abs/2006.04647 (2020).  arXiv:2006.04647 https://arxiv.org/abs/2006.04647
  * Ning et al. (2021) Xuefei Ning, Changcheng Tang, Wenshuo Li, Zixuan Zhou, Shuang Liang, Huazhong Yang, and Yu Wang. 2021.  Evaluating Efficient Performance Estimators of Neural Architectures. In _Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, NeurIPS 2021, December 6-14, 2021, virtual_ , Marc’Aurelio Ranzato, Alina Beygelzimer, Yann N. Dauphin, Percy Liang, and Jennifer Wortman Vaughan (Eds.). 12265–12277.  https://proceedings.neurips.cc/paper/2021/hash/65d90fc6d307590b14e9e1800d4e8eab-Abstract.html
  * Peng et al. (2022) Yameng Peng, Andy Song, Vic Ciesielski, Haytham M. Fayek, and Xiaojun Chang. 2022.  PRE-NAS: predictor-assisted evolutionary neural architecture search. In _GECCO ’22: Genetic and Evolutionary Computation Conference, Boston, Massachusetts, USA, July 9 - 13, 2022_ , Jonathan E. Fieldsend and Markus Wagner (Eds.). ACM, 1066–1074.  https://doi.org/10.1145/3512290.3528727
  * Peng et al. (2023) Yameng Peng, Andy Song, Vic Ciesielski, Haytham M. Fayek, and Xiaojun Chang. 2023.  Fast Evolutionary Neural Architecture Search by Contrastive Predictor with Linear Regions. In _Proceedings of the Genetic and Evolutionary Computation Conference, GECCO 2023, Lisbon, Portugal, July 15-19, 2023_ , Sara Silva and Luís Paquete (Eds.). ACM, 1257–1266.  https://doi.org/10.1145/3583131.3590452
  * Pham et al. (2018) Hieu Pham, Melody Y. Guan, Barret Zoph, Quoc V. Le, and Jeff Dean. 2018.  Efficient Neural Architecture Search via Parameter Sharing. In _Proceedings of the 35th International Conference on Machine Learning, ICML 2018, Stockholmsmässan, Stockholm, Sweden, July 10-15, 2018_ _(Proceedings of Machine Learning Research, Vol. 80)_ , Jennifer G. Dy and Andreas Krause (Eds.). PMLR, 4092–4101.  http://proceedings.mlr.press/v80/pham18a.html
  * Real et al. (2019) Esteban Real, Alok Aggarwal, Yanping Huang, and Quoc V. Le. 2019.  Regularized Evolution for Image Classifier Architecture Search. In _The Thirty-Third AAAI Conference on Artificial Intelligence, AAAI 2019, The Thirty-First Innovative Applications of Artificial Intelligence Conference, IAAI 2019, The Ninth AAAI Symposium on Educational Advances in Artificial Intelligence, EAAI 2019, Honolulu, Hawaii, USA, January 27 - February 1, 2019_. AAAI Press, USA, 4780–4789.  https://doi.org/10.1609/aaai.v33i01.33014780
  * Sinha and Chen (2021) Nilotpal Sinha and Kuan-Wen Chen. 2021.  Evolving neural architecture using one shot model. In _GECCO ’21: Genetic and Evolutionary Computation Conference, Lille, France, July 10-14, 2021_ , Francisco Chicano and Krzysztof Krawiec (Eds.). ACM, 910–918.  https://doi.org/10.1145/3449639.3459275
  * Sinha and Chen (2022a) Nilotpal Sinha and Kuan-Wen Chen. 2022a.  Neural architecture search using progressive evolution. In _GECCO ’22: Genetic and Evolutionary Computation Conference, Boston, Massachusetts, USA, July 9 - 13, 2022_ , Jonathan E. Fieldsend and Markus Wagner (Eds.). ACM, 1093–1101.  https://doi.org/10.1145/3512290.3528707
  * Sinha and Chen (2022b) Nilotpal Sinha and Kuan-Wen Chen. 2022b.  Novelty driven evolutionary neural architecture search. In _GECCO ’22: Genetic and Evolutionary Computation Conference, Companion Volume, Boston, Massachusetts, USA, July 9 - 13, 2022_ , Jonathan E. Fieldsend and Markus Wagner (Eds.). ACM, 671–674.  https://doi.org/10.1145/3520304.3528889
  * Sinha and Chen (2022c) Nilotpal Sinha and Kuan-Wen Chen. 2022c.  Novelty driven evolutionary neural architecture search. In _GECCO ’22: Genetic and Evolutionary Computation Conference, Companion Volume, Boston, Massachusetts, USA, July 9 - 13, 2022_ , Jonathan E. Fieldsend and Markus Wagner (Eds.). ACM, 671–674.  https://doi.org/10.1145/3520304.3528889
  * Stanley and Lehman (2015) Kenneth O. Stanley and Joel Lehman. 2015.  _Why Greatness Cannot Be Planned - The Myth of the Objective_.  Springer.  https://doi.org/10.1007/978-3-319-15524-1
  * Tanaka et al. (2020) Hidenori Tanaka, Daniel Kunin, Daniel L. K. Yamins, and Surya Ganguli. 2020.  Pruning neural networks without any data by iteratively conserving synaptic flow. In _Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual_ , Hugo Larochelle, Marc’Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan-Tien Lin (Eds.).
  * Tran et al. (2023) Khoa Huu Tran, Luc Truong, An Vo, and Ngoc Hoang Luong. 2023.  Accelerating Gene-pool Optimal Mixing Evolutionary Algorithm for Neural Architecture Search with Synaptic Flow. In _Companion Proceedings of the Conference on Genetic and Evolutionary Computation, GECCO 2023, Companion Volume, Lisbon, Portugal, July 15-19, 2023_ , Sara Silva and Luís Paquete (Eds.). ACM, 85–86.  https://doi.org/10.1145/3583133.3596438
  * White et al. (2023) Colin White, Mahmoud Safari, Rhea Sukthanker, Binxin Ru, Thomas Elsken, Arber Zela, Debadeepta Dey, and Frank Hutter. 2023.  Neural Architecture Search: Insights from 1000 Papers.  _CoRR_ abs/2301.08727 (2023).  https://doi.org/10.48550/arXiv.2301.08727 arXiv:2301.08727
  * White et al. (2021) Colin White, Arber Zela, Robin Ru, Yang Liu, and Frank Hutter. 2021.  How Powerful are Performance Predictors in Neural Architecture Search?. In _Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, NeurIPS 2021, December 6-14, 2021, virtual_ , Marc’Aurelio Ranzato, Alina Beygelzimer, Yann N. Dauphin, Percy Liang, and Jennifer Wortman Vaughan (Eds.). 28454–28469.  https://proceedings.neurips.cc/paper/2021/hash/ef575e8837d065a1683c022d2077d342-Abstract.html
  * Ying et al. (2019) Chris Ying, Aaron Klein, Eric Christiansen, Esteban Real, Kevin Murphy, and Frank Hutter. 2019.  NAS-Bench-101: Towards Reproducible Neural Architecture Search. In _Proceedings of the 36th International Conference on Machine Learning, ICML 2019, 9-15 June 2019, Long Beach, California, USA_ _(Proceedings of Machine Learning Research, Vol. 97)_ , Kamalika Chaudhuri and Ruslan Salakhutdinov (Eds.). PMLR, 7105–7114.  http://proceedings.mlr.press/v97/ying19a.html
  * Zela et al. (2020) Arber Zela, Julien Siems, and Frank Hutter. 2020.  NAS-Bench-1Shot1: Benchmarking and Dissecting One-shot Neural Architecture Search. In _8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020_. OpenReview.net.  https://openreview.net/forum?id=SJx9ngStPH
  * Zhang et al. (2020a) Miao Zhang, Huiqi Li, Shirui Pan, Xiaojun Chang, and Steven W. Su. 2020a.  Overcoming Multi-Model Forgetting in One-Shot NAS With Diversity Maximization. In _2020 IEEE/CVF Conference on Computer Vision and Pattern Recognition, CVPR 2020, Seattle, WA, USA, June 13-19, 2020_. Computer Vision Foundation / IEEE, 7806–7815.  https://doi.org/10.1109/CVPR42600.2020.00783
  * Zhang et al. (2020b) Miao Zhang, Huiqi Li, Shirui Pan, Taoping Liu, and Steven W. Su. 2020b.  One-Shot Neural Architecture Search via Novelty Driven Sampling. In _Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence, IJCAI 2020_ , Christian Bessiere (Ed.). ijcai.org, 3188–3194.  https://doi.org/10.24963/ijcai.2020/441
  * Zitzler and Thiele (1999) Eckart Zitzler and Lothar Thiele. 1999.  Multiobjective evolutionary algorithms: a comparative case study and the strength Pareto approach.  _IEEE Trans. Evol. Comput._ 3, 4 (1999), 257–271.  https://doi.org/10.1109/4235.797969
  * Zoph and Le (2017) Barret Zoph and Quoc V. Le. 2017.  Neural Architecture Search with Reinforcement Learning. In _5th International Conference on Learning Representations, ICLR 2017, Toulon, France, April 24-26, 2017, Conference Track Proceedings_. OpenReview.net.  https://openreview.net/forum?id=r1Ue8Hcxg


# Go-No go criteria for performing quantum chemistry calculations on quantum
computers

Thibaud Louvet  PHELIQS, Université Grenoble Alpes, CEA, Grenoble INP, IRIG,
Grenoble 38000, France  Thomas Ayral  Atos Quantum Laboratory, Les Clayes-
sous-Bois, France  Xavier Waintal  PHELIQS, Université Grenoble Alpes, CEA,
Grenoble INP, IRIG, Grenoble 38000, France

###### Abstract

Quantum chemistry is envisioned as an early and disruptive application where
quantum computers would provide a genuine advantage with respect to purely
classical approaches. In this work, we propose two criteria for evaluating the
potential of the two leading quantum approaches for this class of problems.
The first criterion applies to the Variational Quantum Eigensolver (VQE)
algorithm and sets an upper bound to the level of noise that can be tolerated
in quantum hardware as a function of the target precision and problem size. We
find a crippling effect of noise with an overall scaling of the precision that
is generically less favourable than in the corresponding classical algorithms.
This is due to the studied molecule being unrelated to the hardware dynamics,
hence its noise; conversely the hardware noise populates states of arbitrary
energy of the studied molecule. The second criterion applies to the Quantum
Phase Estimation (QPE) algorithm that is often presented as the go-to
replacement of VQE upon availability of (noiseless) fault-tolerant quantum
computers. QPE suffers from the phenomenon known as the orthogonality
catastrophe that generically leads to an exponentially small success
probability when the size of the problem grows. Our criterion allows one to
estimate quantitatively the importance of this phenomenon from the knowledge
of the variance of the energy of the input state used in the calculation.

There exists a hierarchy in the applications that have been proposed for
quantum computers, from the celebrated Shor algorithm [1] (exponentially
faster than its known classical counterparts) to Grover algorithm [2] (up to
quadratically faster than its classical counterparts [3] but less specialized)
to near-term algorithms such as the Variational Quantum Eigensolver (VQE) [4],
which have no a priori parametric advantage over their classical counterparts
but might have a practical one. This hierarchy ends with quantum (analog)
simulations, where one gives up on the quantum gate model, i.e. on
programmability. Going down this hierarchy, one gives up on the advantage
provided by the quantum computer in terms of the degree of generality of the
applications and arguably the expected provable speedup. In turn, the
requirements on the hardware become less drastic, perhaps allowing one to
obtain useful results without the need for a fault-tolerant approach [5].

This article focuses on one field that has been put forward as a possible
near-term application for quantum computers: quantum chemistry. Quantum
approaches to this problem have been blooming recently, with several good
reviews that analyze the various aspects of the algorithms [6, 7] or the
applicability of the approach to solve real problems in VQE [8, 9, 10, 11] or
in its fault-tolerant counterpart, the Quantum Phase Estimation (QPE)
algorithm [12, 13, 14]. Despite great expectations, it is a very difficult
exercise to extrapolate the existing hardware capabilities to estimate whether
a quantum advantage will be eventually reached. In this letter, we take a
somewhat reverse approach and derive necessary conditions to obtain such an
advantage, thereby defining constraints that the hardware must fulfill if an
advantage is to be obtained.

A criterion for Variational Quantum Eigensolving. We start with an analysis of
VQE and the level of quantum noise that it can sustain. The VQE approach is
very close in spirit to the classical algorithm of variational Monte-Carlo
(VMC) [15]. One constructs a variational anzatz
$|\Psi_{V}\rangle=U(\vec{\theta})|0\rangle$ by applying a quantum circuit
$U(\vec{\theta})$ to an initial state $|0\rangle$ of a system made of $n$
qubits. The variables $\vec{\theta}$ parametrize the ansatz. In a second step,
one estimates the energy $E_{V}=\langle\Psi_{V}|H|\Psi_{V}\rangle$ of the
molecule. Here $H$ is the Hamiltonian of the studied molecule, encoded in a
form suitable for qubits. The ground state of $H$ is $|\Psi_{0}\rangle$, with
a ground state energy $E_{0}$, and one seeks to find $E_{V}\geq E_{0}$ as
close to $E_{0}$ as possible. The energy estimation is performed by running
the circuit $N_{S}$ times until the statistical uncertainty of the measured
quantities $\eta_{S}\propto 1/\sqrt{N_{S}}$ is smaller than the desired
precision. Then the parameters $\vec{\theta}$ are updated in order to decrease
the variational energy $E_{V}$. The process is repeated until the energy has
reached convergence.

A central question for VQE is the ability of the algorithm to provide accurate
results despite the presence of hardware imperfections such as noise or
decoherence. Noise is known to lead to exponentially vanishing gradients [16]
(hence a more difficult optimization) and quite stringent lower bounds on the
lowest achievable variational energy [17]. Important efforts are on-going to
try and mitigate the effect of this noise [18, 19] but these techniques are
generically also plagued with an exponential complexity [20, 21, 21, 22, 23].
The effect of the noise in real hardware can be measured by the fidelity
$F=\langle\Psi_{V}|\rho|\Psi_{V}\rangle$. The fidelity expresses how the
density matrix $\rho$ of the quantum computer after state preparation differs
from the expected one, $|\Psi_{V}\rangle\langle\Psi_{V}|$. A fidelity smaller
than one implies that $\rho=F|\Psi_{V}\rangle\langle\Psi_{V}|+(1-F)\rho_{\rm
noise}$, where $\rho_{\rm noise}$ is the part of the density matrix that
results from decoherence. The resulting energy is given by $E=E_{V}+\Delta E$
with a noise induced error $\Delta E$ defined as

$\Delta E=(1-F)[E_{\rm noise}-E_{V}],$ (1)

with $E_{\rm noise}={\rm Tr}(\rho_{\rm noise}H)$. A large corpus of
experiments and theory [24], including the seminal ”quantum supremacy”
experiment by Google [25], indicates that the fidelity decays exponentially
with the total number of applied gates $N_{g}$,

$F\approx e^{-\epsilon N_{g}}$ (2)

where $\epsilon$ is the average error per gate. In the leading quantum
hardware, this error is dominated by the two-qubit gates for which
$\epsilon\leq 1\%$.

Figure 1: Hydrogen chain energy scales. Hartree-Fock ground state energy
$E_{HF}$ and thermalized energy $E_{\infty}$ per atom, for the ”STO-3G” ($2$
qubits per atom), ”6-31G” ($4$ qubits per atom) [26], ”cc-pVDZ” ($10$ qubits
per atom) and ”cc-pVTZ” basis ($28$ qubits per atom) [27]. For the ”STO-3G”
basis we have plotted the highest excited state energy $E_{max}$ up to $N=10$
(regime where exact diagonalization is possible). For all curves, the zero-
offset for energies per atom is $E_{0}(N=2)/2$, where $E_{0}(N=2)$ comes from
exact diagonalization of the H2 Hamiltonian in the ”STO-3G” basis.

We now argue that the energy scale $E_{\mathrm{noise}}-E_{V}$ generically
scales as the square of the number of electrons, a very unfavourable scaling.
Indeed, in general, the target Hamiltonian $H$ is very different from the
Hamiltonian that describes the hardware. Therefore, the sought-after
$|\Psi_{V}\rangle$ is generically a high-energy state of the hardware
Hamiltonian. Conversely, hardware noise shares no structure with the studied
molecule and it will typically populate eigenstates of $H$ of arbitrary large
energies. For instance, one of the simplest noise channels, the depolarizing
noise, maps $\rho\rightarrow(1-\epsilon)\rho+\epsilon I_{d}/2^{n}$, where
$I_{d}$ is the identity matrix. It follows that $E_{\rm noise}=E_{\infty}$ for
this model, where $E_{\infty}$ is the equilibrium energy of the Hamiltonian
$H$ at infinite temperature. The same energy scale would be found using local
Pauli errors which have the same fixed point[16].

A first consequence of the above discussion lies in the scaling of the noise-
induced error due to the long-range nature of the Coulomb interaction. Indeed,
the ground-state energy of a molecule is generically an extensive quantity,
i.e. it is proportional to the number $N$ of electrons in the system:
$E_{0}\propto N$. Likewise, any reasonable variational ansatz will share this
property $E_{V}\propto N$. The spectrum of $H$, however, generically contains
contributions from Coulomb interaction terms that scale quadratically in
$N^{2}$. For low energy states, these terms are not significant because the
electrons screen the nucleous electric field and no macroscopic dipole arises.
However in VQE, the Hamiltonian of the quantum hardware is distinct and
independent from the physical Hamiltonian so that noise can mix the target
states with arbitrary high energy states. For example, we can build an
extremely high energy state for a given molecule by piling all the electrons
on one atom and leaving the orbitals of the other atoms unoccupied. Such a
state has an energy that scales as $N^{2}$ (classical charging energy of a
capacitor). It follows that the error scales defavorably as

$E_{\rm noise}=aN+bN^{2}.$ (3)

This is very different from e.g. VMC that does not suffer from this problem
(unless a particularly ill-chosen variational ansatz is used). Interestingly,
quantum simulators (aka analog quantum computers) do not generically suffer
from this problem either. There, the Hamiltonian of the physical system (the
hardware) is supposed to match as closely as possible the Hamiltonian that one
wants to study. It follows that imperfections such as e.g. energy relaxation
are not necessarily problematic, they are part of the hardware and perhaps
have a counterpart in the problem that one wants to study. The quadratic
scaling of the VQE error is a direct consequence of its added programmability
with respect to an analog simulation.

Figure 2: (a) Sketch of the energy $E(\tau)$ versus imaginary time. The area
$\kappa$ under the energy curve directly provides the overlap
$\Omega=e^{-\kappa}$. We approximate $\kappa$ with the orange shaded area
$I_{\Omega}$ more easily accessible. (b), (c) and (d): Energy $E_{V}$ versus
optimization step in VQE simulation, the ”error bar” corresponds to the
standard deviation $\sigma_{V}$. (e), (f) and (g): Overlap $\Omega$ and
$e^{-I_{\Omega}}$ versus optimization step.

We now construct a quantitative criterion for using VQE on a given hardware
for a given molecule. A generally accepted minimum accuracy necessary for a
quantum chemistry calculation to be of real use is the so-called chemical
accuracy $\eta_{\rm chem}=1{\rm kcal/mol}\ \approx 1.6{\rm mHa}\approx 500K$.
The energy $E_{\rm noise}$, on the other hand, will have a typical value of
the order of 1 Ha or higher (the typical scale of the Hamiltonian matrix
element in the atomic orbitals). For instance for the $H_{2}$ molecule in a
minimum basis set of just two orbitals per atom (STO-3G), one gets
$E_{\infty}-E_{0}=1.02$ Ha. This energy quickly climbs to tens of Hartrees
when one uses larger basis sets, necessary for achieving chemical accuracy. We
can thus construct our first criterion: it simply reads $\Delta E\leq\eta_{\rm
chem}$, and translates [using Eq.(1) and (2)] into

$\epsilon\leq\frac{\eta_{\rm chem}}{(E_{\rm noise}-E_{0})N_{g}}.$ (4)

It follows that the error level must be very low, especially if an expressive
ansatz with a large number of gates is to be used, another necessary step
needed to reach chemical accuracy. What does this criterion imply in practice?
Let us consider a recent blind test benchmark on the benzene molecule [28].
Benzene is a non trivial calculation for classical approaches. Yet [28]
showcased that a variety of classical techniques arrived at chemical precision
using $30$ electrons distributed on $108$ orbitals. Using the UCC ansatz,
inspired by the successful coupled cluster approach used in quantum chemistry,
would require to include at least single, double and triple excitations
(actually quadruple would probably be needed too) which translates into $\sim
N^{6}$ gates. One arrives at a noise level $\epsilon\leq 10^{-12}$ or lower,
that is many orders of magnitude below the best existing quantum hardware.

To further illustrate the unfavourable behaviour of the noise-induced error,
we have computed the energy $E_{\infty}-E_{0}$ of a chain of hydrogen atoms in
various basis sets of increasing accuracy, using the PySCF package[29]. Figure
1 shows the energy per atom $E_{\infty}/N$ (counted from $E_{0}/N$, which at
this scale does not depend on $N$) for various standard basis sets of
increasing accuracy (typically only the largest one can reach chemical
accuracy). To set the energy scales into perspective the right axis shows the
energies in Kelvin and one quickly arrives at core sun level of temperature.
Also shown are the Hartree-Fock energy (empty squares) and the maximum energy
of $H$ for the minimum basis set STO-3G (blue stars). As soon as one steps
away from the minimum basis set and/or number of hydrogen atoms, one finds
that the energy $E_{\infty}$ becomes very large, which will lead to an
explosion of the noise-induced error and rule out any practical computation.

A last consequence of the noise-induced error is the statistical precision of
the calculation. In VQE, one does not measure the energy $E$ directly but
rather its different subterms separately from the one and two-body reduced
density matrix. It results that even if $|\Psi_{V}\rangle$ is close to the
actual ground state (hence the total energy has a low variance), these
subterms taken separately have large standard deviations ($|\Psi_{V}\rangle$
is not an eigenstate of any of them) of the order of $1Ha$ or larger. This
implies a large number of shots $N_{S}$ is needed to reach high precision. To
this problem, the noise adds a contribution to the variance of the order of
$(\Delta E)^{2}$, which will have a drastic impact on the measurement time
needed e.g. to implement any noise mitigation scheme. Note that classical
methods typically do not suffer from this problem. In a VMC calculation, the
statistical error $\eta_{S}$ is given by $\eta_{S}=\sigma_{V}/\sqrt{N_{S}}$
where $\sigma^{2}_{V}=\langle\Psi_{V}|H^{2}|\Psi_{V}\rangle-E_{V}^{2}$ is the
variance of the energy of the ansatz. Hence, when the ansatz is properly
chosen, it has a low variance so that one can reach high precision at an
affordable $N_{S}$.

Figure 3:  Scaling of the Hartree-Fock energy (a) and the energy variance (b)
versus number of atoms in an hydrogen chain. (c): Overlap index $I_{\Omega}$
versus energy error $|E-E_{0}|$ for the variational ansatz of the [30] data
set. The dashed line is a linear fit $I_{\Omega}\approx 27.8|E-E_{0}|$.

A criterion for Quantum Phase Estimation. We now turn to the second criterion
relevant for Quantum Phase Estimation (QPE) algorithm. QPE starts from a guess
input state $|\Psi_{V}\rangle$ and applies the quantum phase estimation
algorithm to project the state onto the eigenvectors of $e^{-iHt}$ i.e. the
eigenvectors of $H$, and extract the corresponding eigenenergy $E_{0}$. QPE is
much more demanding than VQE and it is assumed that one is in possession of a
hypothetical [31] (noiseless) fault tolerant quantum computer. The probability
to obtain the ground state $|\Psi_{0}\rangle$ of $H$ is proportional to the
overlap $\Omega$ of the initial input state with the ground state, i.e.
$\Omega=|\langle\Psi_{V}|\Psi_{0}\rangle|^{2}$. It is thus of prime importance
to be able to estimate what value of $\Omega$ one can hope for in quantum
chemistry in order to determine if QPE could become useful. In condensed
matter, the overlap between two slightly different states is usually believed
to decrease exponentially with system size, a phenomenon referred to as the
orthogonality catastrophe [32]. This phenomenon holds even for states that
share very similar energies. For instance, the difference of energy per
particle between superconducting aluminum and normal-metal aluminium is
extremely tiny $\sim(\Delta/E_{F})^{2}\approx 10^{-8}$ ($\Delta$:
superconducting gap, $E_{F}$: Fermi energy) yet the two states behave
drastically differently. In quantum chemistry, the situation has been studied
in less detail: Tubman et al. [33] looked at small molecules with small static
correlation and concluded that $\Omega$ could be kept to relatively high
values, while [34], which looked at more correlated molecules, gave indication
of a relatively fast decay of the overlap. We note that calculations on small
molecules may be artificially optimistic. For instance in a method such as
CCSD which spans a $N^{4}$ dimensional space, the crossover $N^{4}\approx
2^{N}$ happens for $N=16$. Hence, the ansatz is overexpressive for small $N$,
indicating that the exact ground state likely can be represented by the
variational ansatz, while the situation deteriorates abruptly as $N$
increases. Also, molecules with small static correlations are good targets for
classical calculations.

Below we show that $\Omega$ can actually be estimated from quantities
accessible in standard quantum chemistry calculations, therefore allowing one
to estimate the success probability that QPE would have on a perfect quantum
computer. Let us assume that the initial state $|\Psi_{V}\rangle$ fed to QPE
has been obtained using a variational computation like VQE. Then, we use a
theorem proved by one of us in [35] to estimate the overlap $\Omega$ of this
state with the ground state $|\Psi_{0}\rangle$. Let us consider the
wavefunction
$|\Psi(\tau)\rangle=\frac{1}{\sqrt{Z}}e^{-H\tau}|\Psi_{V}\rangle$, where the
factor $Z=\langle\Psi_{V}|e^{-2H\tau}|\Psi_{V}\rangle$ ensures normalization.
This wavefunction appears in various techniques (e.g. Diffusion Monte-Carlo or
Green function Monte-Carlo) that project the variational wavefunction onto the
groundstate since
$\lim_{\tau\rightarrow\infty}|\Psi(\tau)\rangle=|\Psi_{0}\rangle$. A typical
output of these methods is the energy
$E(\tau)=\langle\Psi(\tau)|H|\Psi(\tau)\rangle$ as a function of $\tau$ as
sketched in Fig. 2 (left panel). The success probability of PQE is simply
related to the area $\kappa$ under this curve as [35],

$\displaystyle\Omega=\exp(-\kappa),\mathrm{~{}with~{}}\kappa=\int\limits_{0}^{\infty}d\tau(E(\tau)-E_{0}).$
(5)

While the area $\kappa$ is not necessarily easy to compute, a good proxy can
be obtained by considering the area $I_{\Omega}$ of the dashed triangle in the
left panel of Fig. 2. This area can be calculated from the knowledge of the
variational energy $E_{V}=E(\tau=0)$, the energy variance of the variaitonal
ansatz $\sigma_{V}^{2}=-\partial_{\tau}E(\tau=0)$ and an estimate (that needs
not necessarily to be very accurate) of the ground state energy $E_{0}$:

$I_{\Omega}\equiv\frac{(E_{V}-E_{0})^{2}}{2\sigma^{2}}.$ (6)

We call $I_{\Omega}$ the ”overlap index” of the variational ansatz
$|\Psi_{V}\rangle$. The overlap index provides an estimate of the success
probability $\Omega$ as

$\Omega\approx e^{-I_{\Omega}},$ (7)

and the associated criterion is naturally $\Omega\sim 1$. This criterion
depends on the energy and variance of the ansatz and is totally independent on
the imaginary time evolution used for its derivation.

To corroborate the validity of this overlap estimation, we have performed VQE
simulations for several molecules, computing both the variational energy and
the variance. For these small systems, the exact ground state energy can be
calculated as well. This allows to compute the exact overlap $\Omega$ and
check if the estimate Eq.(7) holds. (On bigger systems, one would rely on
estimates such as those currently used in quantum chemistry where one
extrapolates from a sequence of increasingly accurate calculations (e.g. CCSD,
CCSDT and CCSDTQ calculations)). We use the myQLM-fermion package [36], a one-
layer UCC ansatz and a minimum basis set (STO-$3$g for H2 and H4 molecules;
the $6$-$31$G basis and active space selection to reduce the Hilbert space
dimension from $22$ to $4$ for LiH). The convergence of the results versus the
optimization step are shown on the right panels of Figure 2. Note that the
”error bars” in the upper panels stand for the variance of the variational
ansatz. In the lower panels, we observe a very good match between the right
and left-hand sides of Eq.(7), which shows that the overlap index can indeed
be used to estimate the overlap $\Omega$. This is an important point of this
second criterion: adding the calculation of the variance $\sigma_{V}^{2}$
provides, together with the energy, very valuable information and we argue
that variational calculations should report on the variance. Note that in the
H4 simulation, which uses $8$ qubits in contrast to H2 and LiH where the
number of qubits is only $4$, the convergence is much slower.

We end this letter by a discussion of the scaling that one may expect for
$\Omega$. A reasonable variational energy is an extensive quantity
$E_{V}\propto N$. Likewise, the variance is also likely to be extensive
$\sigma^{2}\propto N$ (this is true if the energy is roughly the sum of local
terms). It follows that the overlap index is generically an extensive quantity
$I_{\Omega}=\alpha N$, from which one concludes that the overlap decreases
exponentially $\Omega\approx e^{-\alpha N}$. This is the orthogonality
catastrophe in the context of variational calculations. To illustrate the
above statements, the top panels of Figure 3 show the Hartree-Fock energy
(left) and variance (right) of hydrogen chains of up to $N=128$ in the
STO-$3$G basis set. Both indeed scale linearly with $N$ as advertized. In a
slightly different context, a recent work [30] has aggregated a large data set
of energies and variances of variational ansatz of various condensed matter
systems of various sizes using various methods. The bottom panel of Figure 3
shows $I_{\Omega}$ versus $E_{V}-E_{0}$ for the data set of [30]. We find that
$I_{\Omega}$ is well fitted by a linear law $I_{\Omega}=C|E-E_{0}|$, with
$C=27.8\pm 0.1$. Since $|E-E_{0}|$ is an extensive quantity, this implies
again the exponential decay associated with the orthogonality catastrophe.

To conclude, we have proposed two criteria, one for VQE (noisy hardware) one
for QPE (fault tolerant hardware) that are easily accessible and provide
necessary conditions for the possibility of doing genuinely relevant chemistry
calculations on quantum hardware. Our preliminary estimates imply that this
possibility is unlikely with the approaches and technologies that are
currently pursued, unless important paradigm shifts take place.

## Acknowledgements

We acknowledge funding from the French ANR QPEG and the Plan France 2030
ANR-22-PETQ-0007 “EPIQ”.

## References

  * Shor [1994] P. Shor, Algorithms for quantum computation: discrete logarithms and factoring, in  _Proceedings 35th Annual Symposium on Foundations of Computer Science_ (1994) pp. 124–134.
  * Grover [1997] L. K. Grover, Quantum mechanics helps in searching for a needle in a haystack, Phys. Rev. Lett. 79, 325 (1997).
  * Stoudenmire and Waintal [2023] E. M. Stoudenmire and X. Waintal, Grover’s algorithm offers no quantum advantage (2023), arXiv:2303.11317 [quant-ph] .
  * 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, A variational eigenvalue solver on a photonic quantum processor, Nature Communications 5, 4213 (2014).
  * Ayral  _et al._ [2023a] T. Ayral, P. Besserve, D. Lacroix, and E. A. R. Guzman, Quantum computing with and for many-body physics (2023a), arXiv:2303.04850 [quant-ph] .
  * Bauer  _et al._ [2020] B. Bauer, S. Bravyi, M. Motta, and G. K.-L. Chan, Quantum algorithms for quantum chemistry and quantum materials science, Chemical Reviews 120, 12685 (2020), pMID: 33090772, https://doi.org/10.1021/acs.chemrev.9b00829 .
  * 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, The variational quantum eigensolver: A review of methods and best practices, Physics Reports 986, 1 (2022), the Variational Quantum Eigensolver: a review of methods and best practices.
  * Kühn  _et al._ [2019] M. Kühn, S. Zanker, P. Deglmann, M. Marthaler, and H. Weiß, Accuracy and resource estimations for quantum chemistry on a near-term quantum computer, Journal of Chemical Theory and Computation 15, 4764 (2019), pMID: 31403781, https://doi.org/10.1021/acs.jctc.9b00236 .
  * Elfving  _et al._ [2020] V. E. Elfving, B. W. Broer, M. Webber, J. Gavartin, M. D. Halls, K. P. Lorton, and A. Bochevarov, How will quantum computers provide an industrially relevant computational advantage in quantum chemistry? (2020), arXiv:2009.12472 [quant-ph] .
  * Cerezo  _et al._ [2021] M. Cerezo, A. Arrasmith, R. Babbush, S. C. Benjamin, S. Endo, K. Fujii, J. R. McClean, K. Mitarai, X. Yuan, L. Cincio, and P. J. Coles, Variational quantum algorithms, Nature Reviews Physics 3, 625 (2021).
  * Gonthier  _et al._ [2022] J. F. Gonthier, M. D. Radin, C. Buda, E. J. Doskocil, C. M. Abuan, and J. Romero, Measurements as a roadblock to near-term practical quantum advantage in chemistry: Resource analysis, Phys. Rev. Res. 4, 033154 (2022).
  * Wecker  _et al._ [2015] D. Wecker, M. B. Hastings, and M. Troyer, Progress towards practical quantum variational algorithms, Physical Review A 92, 042303 (2015), arXiv:1507.08969 .
  * von Burg  _et al._ [2021] V. von Burg, G. H. Low, T. Häner, D. S. Steiger, M. Reiher, M. Roetteler, and M. Troyer, Quantum computing enhanced computational catalysis, Phys. Rev. Res. 3, 033055 (2021).
  * Beverland  _et al._ [2022] M. E. Beverland, P. Murali, M. Troyer, K. M. Svore, T. Hoefler, V. Kliuchnikov, G. H. Low, M. Soeken, A. Sundaram, and A. Vaschillo, Assessing requirements to scale to practical quantum advantage (2022), arXiv:2211.07629 [quant-ph] .
  * Ceperley  _et al._ [1977] D. Ceperley, G. V. Chester, and M. H. Kalos, Monte carlo simulation of a many-fermion study, Phys. Rev. B 16, 3081 (1977).
  * Wang  _et al._ [2021] S. Wang, E. Fontana, M. Cerezo, K. Sharma, A. Sone, L. Cincio, and P. J. Coles, Noise-induced barren plateaus in variational quantum algorithms, Nature Communications 12, 6961 (2021), arXiv:2007.14384 .
  * Stilck França and García-Patrón [2021] D. Stilck França and R. García-Patrón, Limitations of optimization algorithms on noisy quantum devices, Nature Physics 17, 1221 (2021), arXiv:2009.05532 .
  * Grimsley  _et al._ [2019] H. R. Grimsley, S. E. Economou, E. Barnes, and N. J. Mayhall, An adaptive variational algorithm for exact molecular simulations on a quantum computer, Nature Communications 10, 3007 (2019), arXiv:arXiv:1812.11173v2 .
  * Endo  _et al._ [2021] S. Endo, Z. Cai, S. C. Benjamin, and X. Yuan, Hybrid Quantum-Classical Algorithms and Quantum Error Mitigation, Journal of the Physical Society of Japan 90, 032001 (2021), arXiv:2011.01382v1 .
  * Li and Benjamin [2017] Y. Li and S. C. Benjamin, Efficient Variational Quantum Simulator Incorporating Active Error Minimization, Physical Review X 7, 021050 (2017), arXiv:1611.09301 .
  * Temme  _et al._ [2017] K. Temme, S. Bravyi, and J. M. Gambetta, Error Mitigation for Short-Depth Quantum Circuits, Physical Review Letters 119, 180509 (2017), arXiv:1612.02058 .
  * Endo  _et al._ [2018] S. Endo, S. C. Benjamin, and Y. Li, Practical Quantum Error Mitigation for Near-Future Applications, Physical Review X 8, 031027 (2018), arXiv:1712.09271 .
  * Ferracin  _et al._ [2022] S. Ferracin, A. Hashim, J.-L. Ville, R. Naik, A. Carignan-Dugas, H. Qassim, A. Morvan, D. I. Santiago, I. Siddiqi, and J. J. Wallman, Efficiently improving the performance of noisy quantum computers,  , 1 (2022), arXiv:2201.10672 .
  * Ayral  _et al._ [2023b] T. Ayral, T. Louvet, Y. Zhou, C. Lambert, E. M. Stoudenmire, and X. Waintal, Density-matrix renormalization group algorithm for simulating quantum circuits with a finite fidelity, PRX Quantum 4, 020304 (2023b).
  * Arute  _et al._ [2020] 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, Hartree-fock on a superconducting qubit quantum computer, Science 369, 1084 (2020), https://www.science.org/doi/pdf/10.1126/science.abb9811 .
  * Ditchfield  _et al._ [1971] R. Ditchfield, W. J. Hehre, and J. A. Pople, Self‐consistent molecular‐orbital methods. ix. an extended gaussian‐type basis for molecular‐orbital studies of organic molecules, The Journal of Chemical Physics 54, 724 (1971), https://doi.org/10.1063/1.1674902 .
  * Dunning [1989] T. H. Dunning, Gaussian basis sets for use in correlated molecular calculations. i. the atoms boron through neon and hydrogen, The Journal of Chemical Physics 90, 1007 (1989), https://doi.org/10.1063/1.456153 .
  * Eriksen  _et al._ [2020] J. J. Eriksen, T. A. Anderson, J. E. Deustua, K. Ghanem, D. Hait, M. R. Hoffmann, S. Lee, D. S. Levine, I. Magoulas, J. Shen, N. M. Tubman, K. B. Whaley, E. Xu, Y. Yao, N. Zhang, A. Alavi, G. K.-L. Chan, M. Head-Gordon, W. Liu, P. Piecuch, S. Sharma, S. L. Ten-no, C. J. Umrigar, and J. Gauss, The ground state electronic energy of benzene, The Journal of Physical Chemistry Letters 11, 8922 (2020), pMID: 33022176, https://doi.org/10.1021/acs.jpclett.0c02621 .
  * Sun  _et al._ [2020] Q. Sun, X. Zhang, S. Banerjee, P. Bao, M. Barbry, N. S. Blunt, N. A. Bogdanov, G. H. Booth, J. Chen, Z.-H. Cui, J. J. Eriksen, Y. Gao, S. Guo, J. Hermann, M. R. Hermes, K. Koh, P. Koval, S. Lehtola, Z. Li, J. Liu, N. Mardirossian, J. D. McClain, M. Motta, B. Mussard, H. Q. Pham, A. Pulkin, W. Purwanto, P. J. Robinson, E. Ronca, E. R. Sayfutyarova, M. Scheurer, H. F. Schurkus, J. E. T. Smith, C. Sun, S.-N. Sun, S. Upadhyay, L. K. Wagner, X. Wang, A. White, J. D. Whitfield, M. J. Williamson, S. Wouters, J. Yang, J. M. Yu, T. Zhu, T. C. Berkelbach, S. Sharma, A. Y. Sokolov, and G. K.-L. Chan, Recent developments in the PySCF program package, The Journal of Chemical Physics 153, 10.1063/5.0006074 (2020), 024109, https://pubs.aip.org/aip/jcp/article-pdf/doi/10.1063/5.0006074/16722275/024109_1_online.pdf .
  * Wu  _et al._ [2023] D. Wu, R. Rossi, F. Vicentini, N. Astrakhantsev, F. Becca, X. Cao, J. Carrasquilla, F. Ferrari, A. Georges, M. Hibat-Allah, M. Imada, A. M. Läuchli, G. Mazzola, A. Mezzacapo, A. Millis, J. R. Moreno, T. Neupert, Y. Nomura, J. Nys, O. Parcollet, R. Pohle, I. Romero, M. Schmid, J. M. Silvester, S. Sorella, L. F. Tocchio, L. Wang, S. R. White, A. Wietek, Q. Yang, Y. Yang, S. Zhang, and G. Carleo, Variational benchmarks for quantum many-body problems (2023).
  * Waintal [2019] X. Waintal, What determines the ultimate precision of a quantum computer, Phys. Rev. A 99, 042318 (2019).
  * Anderson [1967] P. W. Anderson, Infrared catastrophe in fermi gases with local scattering potentials, Phys. Rev. Lett. 18, 1049 (1967).
  * Tubman  _et al._ [2018] N. M. Tubman, C. Mejuto-Zaera, J. M. Epstein, D. Hait, D. S. Levine, W. Huggins, Z. Jiang, J. R. McClean, R. Babbush, M. Head-Gordon, and K. B. Whaley, Postponing the orthogonality catastrophe: efficient state preparation for electronic structure simulations on quantum devices (2018), arXiv:1809.05523 [quant-ph] .
  * Lee  _et al._ [2022] S. Lee, J. Lee, H. Zhai, Y. Tong, A. M. Dalzell, A. Kumar, P. Helms, J. Gray, Z.-H. Cui, W. Liu, M. Kastoryano, R. Babbush, J. Preskill, D. R. Reichman, E. T. Campbell, E. F. Valeev, L. Lin, and G. K.-L. Chan, Is there evidence for exponential quantum advantage in quantum chemistry? (2022).
  * Mora and Waintal [2007] C. Mora and X. Waintal, Variational wave functions and their overlap with the ground state, Physical review letters 99, 030403 (2007).
  * Haidar  _et al._ [2022] M. Haidar, M. J. Rančić, T. Ayral, Y. Maday, and J.-P. Piquemal, Open source variational quantum eigensolver extension of the quantum learning machine (qlm) for quantum chemistry (2022).