# Mitigating Noise-Induced Gradient Vanishing in Variational Quantum Algorithm
Training

Anbang Wu
Department of Computer Science
University of California, Santa Barbara
<EMAIL_ADDRESS>
&Gushu Li
Department of Electrical & Computer Engineering
University of California, Santa Barbara
<EMAIL_ADDRESS>
Yufei Ding
Department of Computer Science
University of California, Santa Barbara
<EMAIL_ADDRESS>
Yuan Xie
Department of Electrical & Computer Engineering
University of California, Santa Barbara
<EMAIL_ADDRESS>

###### Abstract

Variational quantum algorithms are expected to demonstrate the advantage of
quantum computing on near-term noisy quantum computers. However, training such
variational quantum algorithms suffers from gradient vanishing as the size of
the algorithm increases. Previous work cannot handle the gradient vanishing
induced by the inevitable noise effects on realistic quantum hardware. In this
paper, we propose a novel training scheme to mitigate such noise-induced
gradient vanishing. We first introduce a new cost function of which the
gradients are significantly augmented by employing traceless observables in
truncated subspace. We then prove that the same minimum can be reached by
optimizing the original cost function with the gradients from the new cost
function. Experiments show that our new training scheme is highly effective
for major variational quantum algorithms of various tasks.

##  1 Introduction

The recent development of quantum hardware has been able to demonstrate the
‘quantum supremacy’ [1] against classical computers on a specific application
[2]. However, a quantum algorithm that is of practical usage and can
demonstrate the advantage of quantum computing on near-term noisy quantum
hardware platforms is still unclear. Variational Quantum Algorithm (VQA) [3]
is one of the leading candidates because it has a relatively moderate
requirement for the number of qubits and the depth of computation and it has
demonstrated the ability of error tolerance. Several VQAs have been
experimentally implemented on existing quantum computers for various problems,
e.g., optimization [4, 5], chemistry simulation [6, 7].

VQA can be considered as the quantum analogy of classical machine learning
[3]. It has two key components. The first one, usually referred to as ‘ansatz’
in the quantum computing community, is a quantum program with some tunable
parameters $\bm{\theta}$. This program will convert an input state $\rho$ to
an output state $\rho(\bm{\theta})$. The second component is the observable
$O$, a Hermitian operator in the Hilbert space of the quantum system. The
observable is constructed based on the target problem so that its smallest
eigenvalue, together with the corresponding eigenstate, is the solution to the
target problem. On a quantum computer, we can measure the value of
${\mathrm{Tr}}(\rho(\bm{\theta})O)$, which is the expectation of the
observable $O$ with respect to the final state of the parameterized quantum
program. VQA then employs a classical optimizer (e.g., gradient descent) to
optimize the parameters $\bm{\theta}$ and minimize the cost function
${\mathrm{Tr}}(\rho(\bm{\theta})O)$, which is similar to training a model in
classical machine learning. After we reach the minimal
${\mathrm{Tr}}(\rho(\bm{\theta})O)$,
$\min_{\theta}\\{{\mathrm{Tr}}(\rho(\bm{\theta})O)\\}$ becomes the smallest
eigenvalue ($\rho(\bm{\theta})$ is naturally the corresponding eigenstate) and
a solution to the target problem is found.

One of the critical challenges in training a VQA is the gradient vanishing,
i.e., the partial derivatives of the cost function
${\mathrm{Tr}}(\rho(\bm{\theta})O)$ with respect to its parameters are
exponentially small as the system size increases [8, 9]. Inspired by the
related techniques in classical neural network training, several techniques
[10, 11, 12, 13, 14, 15, 16, 17, 18] have been proposed to efficiently
suppress the gradient exponential decay in the noise-free scenario.

However, all these techniques mentioned above ignores the noise effects.
Different from classical computers which are usually digital with extremely
small error rates, noise effects are inevitable on the analog near-term
quantum devices. A recent study points out that the noise effect itself can
cause gradient vanishing by concentrating the cost function landscape around a
specific value [9]. Such noise-induced gradient vanishing, which is not yet
considered in existing gradient vanishing mitigation techniques, will make the
training of VQAs extremely difficult and hinder solving practical problems
with VQAs [9]. It is crucial to mitigate the noise-induced gradient vanishing
in VQA training before we can achieve quantum advantage with VQA.

In this paper, we focus on mitigating the noise-induced gradient vanishing
through a key insight that the observables in major VQAs are only active in a
small subspace. This property comes from the symmetry in the cost function
[19, 20, 21] and such symmetry is shown to be general in major VQAs for
realistic problems [22, 23, 24]. Some noise effects, when they lead to a
measurement result outside the subspace, can be eliminated to reduce the noise
effects and the noise-induced gradient vanishing can be mitigated in this
process. Besides, we notice that the trivial measurement result (i.e., the
measurement with respect to the identity component in the observable) will
aggravate the noise-induced gradient vanishing. Thus, the noise-induced
gradient vanishing can be alleviated by disabling trivial measurements.

To this end, we propose a novel training scheme with two cost functions. The
first cost function $C_{1}$ is the vanilla cost in a subspace while the second
function $C_{2}$ is crafted by making the observables traceless (i.e., the
observable without identity component [25]). Such a design can remove a
constant dominating term in the observable and amplify the variation with
respect to the parameters. Besides, gradient induced by measurement results
outside the subspace will be omitted owing to the use of subspace.
Theoretically, we prove that the gradient of $C_{2}$ is augmented
exponentially comparing with that of the vanilla cost $C_{1}$. We also show
that the same minimum value can be reached when optimizing the vanilla $C_{1}$
with the augmented gradient from $C_{2}$.

We evaluate our training scheme by simulating the noisy VQA training on major
VQAs and various tasks. The results show that the magnitudes of the gradients
of $C_{2}$ are $58.4\times$ larger on average compared with that of $C_{1}$.
For combinatorial optimization tasks, with the subspace derived from the
symmetries of graph structures, our training scheme can increase the
probability of measuring the correct output by $87.7\%$ compared with the
conventional setup with the vanilla cost function. For chemistry simulation
tasks, with the subspace derived from the particle conservation law, the
fidelity of the simulated quantum state is $68.1\%$ larger than that of the
conventional setup.

Our major contributions can be summarized as follows:

  1. 1.

We propose the first training scheme that can counter the unavoidable noise-
induced gradient vanishing in VQA training on near-term quantum computers.

  2. 2.

We design a new cost function of truncated subspace with traceless observables
and theoretically prove that the gradients can be augmented exponentially
without changing the minimum value found in the optimization.

  3. 3.

Our experiments show that our new training scheme outperforms conventional
gradient descent training with significantly larger gradients, faster
convergence, and better VQA results.

###  1.1 Related Work

VQA can be considered as the quantum analog of the successful neural-network-
based classical machine learning methods. It has demonstrated potential
applicability in optimization [26, 27], classification [28, 29], chemistry
simulation [30, 31], etc.

One of the key challenges in VQA training is the gradient vanishing problem.
[8, 32] observed that gradients experience an exponential decay with respect
to the qubit numbers on deep VQA circuits. [9] further revealed that the
gradient barren plateaus can also be induced by local device noises. Empirical
studies [13, 33] provides numerical evidence of the gradient vanishing
phenomenon of VQAs in both noise-free and noisy settings.

Some of the techniques that are proposed for gradient vanishing mitigation in
classical neural networks can possibly be migrated to VQA since most VQA
circuits have multiple layers with tunable parameters. These techniques
include parameter initialization [10], pre-training [11], layer-wise training
[12], changing optimizer [13], and variational quantum circuit architecture
design [14, 15, 16, 17]. In addition, [18] proposed to employ local
observables in the cost function for better VQA trainability. All these works
only consider the noise-free gradient vanishing [8, 32]. However, the noise
effects, which do not exist in classical neural networks, are inevitable in
the near term. The techniques mentioned above cannot counter the noise-induced
gradient vanishing [9]. In contrast, this paper tackles this problem by
suppressing the dominated trivial measurement as well as noise effects outside
the active space of the optimization target. The gradient can then be
significantly augmented, leading to better VQA trainability.

##  2 Preliminary

In this section, we introduce necessary backgrounds to help understand the
proposed gradient vanishing mitigation techniques.

###  2.1 Quantum Computing Basics

The basic information processing unit in quantum computing is a qubit.
Different from a classical bit which can be either 0 or 1 exclusively, the
state of a qubit, usually denoted by $\ket{\psi}$, is a unit vector in a
2-dimensional Hilbert space ${\mathcal{H}}_{2}=\\{a\ket{0}+b\ket{1}\\}$ where
$a,b\in\mathbb{C}$ and $\absolutevalue{a}^{2}+\absolutevalue{b}^{2}=1$. The
state space of $n$ qubits is the tensor product of the state spaces of the $n$
qubits, $\bigotimes^{n}{\mathcal{H}}_{2}={\mathcal{H}}_{2^{n}}$, a
$2^{n}$-dimensional Hilbert space. Sometimes the exact state is not known but
we know it can be in one of a set of pure states $\ket{\psi_{i}}$ with
respective probability $p_{i}$ and $\sum_{i}p_{i}=1$. We define a density
operator $\rho=\sum_{i}p_{i}{|\psi_{i}\rangle\langle\psi_{i}|}$ to represent
such a mixed state ($\bra{\psi}$ is the complex conjugate of $\ket{\psi}$).

There are two major types of operations applied to a quantum system. The first
one is the unitary transformation which can be represented as a unitary
operator $U$ in the state space where $UU^{\dagger}=I$ and $I$ is the identity
operator. A state vector $\ket{\psi}$ and a density operator $\rho$ will be
changed to $U\ket{\psi}$ and $U\rho U^{\dagger}$, respectively, after a
unitary transformation. Measurement can extract information from a quantum
system. What can be measured from a quantum system is defined by an observable
$O$ which must be a Hermitian operator (a Hermitian operator $H$ is self-
adjoint and $H=H^{\dagger}$). In practice, we can measure the expectation
value of an observable $O$ and it can be calculated by $\bra{\psi}O\ket{\psi}$
or ${\mathrm{Tr}}(\rho O)$ for a state vector $\ket{\psi}$ or density operator
$\rho$. One Hermitian operator can be decomposed into an array of weighted
Pauli strings, which is defined as follows.

######  Definition 2.1 (Pauli representation).

The Pauli representation of $2^{n}$-dimensional Hermitian matrix $H$ is
defined as,
$H=\sum_{i}\eta^{i}\sigma_{n}^{i}=\frac{{\mathrm{Tr}}(H)}{2^{n}}\sigma_{n}^{0}+\bm{\eta}\cdot\bm{\sigma}_{n}$,
where $\sigma_{n}^{0}=\mathbbm{1}^{\otimes n}$,
$\sigma_{n}^{i}\in\\{\mathbbm{1},\sigma_{X},\sigma_{Y},\sigma_{Z}\\}^{\otimes
n}\backslash\\{\mathbbm{1}^{\otimes n}\\}$. $\mathbbm{1}$ is the 2-dimensional
identity matrix; $\sigma_{X}$, $\sigma_{Y}$ and $\sigma_{Z}$ are Pauli
matrices, ${\mathrm{Tr}}(H)$ is the trace of $H$. $\sigma_{n}^{i}$ is often
called Pauli string. $2^{n}\bm{\eta}={\mathrm{Tr}}(H\bm{\sigma}_{n})$ is often
called Pauli coefficient of $H$. A Pauli string together with its Pauli
coefficient is referred to as a Pauli term.

######  Definition 2.2 (Rank of observable).

The rank of an observable $O$ is defined to be the number of non-zero Pauli
coefficients in its Pauli representation.

###  2.2 Variational Quantum Algorithms

Variational quantum algorithm [3] is a leading candidate that can potentially
demonstrate the advantage of quantum computing. Variational quantum circuit
(VQC) is the core component of variational quantum algorithms. An n-qubit VQC
$\mathcal{U}_{n}^{L}$ consists of L layers, and can be decomposed into a
sequence of unitary transformations as
$\mathcal{U}_{n}^{L}=\mathcal{U}_{L}(\bm{\theta}_{L})\circ\cdots\circ\mathcal{U}_{2}(\bm{\theta}_{2})\circ\mathcal{U}_{1}(\bm{\theta}_{1})$,
where $\mathcal{U}_{l}(\bm{\theta}_{l})$ is a super operator defined as
$\mathcal{U}_{l}(\bm{\theta}_{l})(\rho)=U_{l}(\bm{\theta}_{l})\rho
U_{l}(\bm{\theta}_{l})^{\dagger}$. And

$\displaystyle U_{l}(\bm{\theta}_{l})$
$\displaystyle=\exp\\{-i\,{\textstyle\sum}_{j}(\theta_{lj}H_{lj}+R_{lj})\\}\,.$
(1)

Here $\bm{\theta}_{l}=\\{\theta_{lj}\\}$ are continuous parameters, both
$H_{lj}$ and $R_{lj}$ are $2^{n}$-dimensional Hermitian matrices.

######  Definition 2.3 (Local Pauli channel).

The Local Pauli Channel $\mathcal{P}$ defined on a single-qubit state $\rho$
can be expressed as
$\mathcal{P}(\rho)=\sum_{i}q_{i}\sigma_{i}\rho\sigma_{i}+(1-\sum_{i}q_{i})\rho$,
where $i\in\\{X,Y,Z\\}$.

In this paper, we consider the noise model based on the local Pauli channel,
and the noisy n-qubit VQC model expressed as
$\widetilde{\mathcal{U}}_{n}^{L}=\widetilde{\mathcal{U}}_{L}(\bm{\theta}_{L})\circ\cdots\circ\widetilde{\mathcal{U}}_{2}(\bm{\theta}_{2})\circ\widetilde{\mathcal{U}}_{1}(\bm{\theta}_{1})$,
where $\widetilde{\mathcal{U}}_{l}(\bm{\theta}_{l})=\mathcal{P}^{\otimes
n}\circ\mathcal{U}_{l}(\bm{\theta}_{l})$ is the the unitary operation
distorted by noise. We refer to the state outputted by channel
$\widetilde{\mathcal{U}}_{l}$ as $\rho_{l}$. Specifically, the final output
state of $\widetilde{\mathcal{U}}_{n}^{L}$ is referred to as $\rho_{L}$.
Quantum state $\rho_{l}$ is also a Hermitian matrix, and its Pauli
representation can be expressed as
$\rho_{l}=\frac{1}{2^{n}}\Big{(}\mathbbm{1}^{\otimes
n}+\bm{a}^{l}\cdot\bm{\sigma}_{n}\Big{)}$, where
$a_{i}^{l}={\mathrm{Tr}}(\rho_{l}\,\sigma_{n}^{i})$.

In the following, we introduce the cost function of the n-qubit local noisy
circuit, and calculate its gradient with the Pauli representation language.

######  Definition 2.4 (Cost function of the local noisy circuit).

Given an observable $O$ and its eigendecomposition
$O=\sum_{i}\lambda_{i}{|i\rangle\langle i|}$, the cost function $C_{0}$ is
defined as $C_{0}={\mathrm{Tr}}(\rho_{L}O)=\sum_{i}\lambda_{i}p_{i}$, where
$p_{i}$ is the probability of $\rho_{L}$ being in the quantum state
${|i\rangle\langle i|}$.

######  Proposition 2.1 (Gradient of cost function $C_{0}$ [9]).

For any parameter $\theta$ in the variational quantum circuit, we have
$\partial_{\theta}C_{0}=\bm{g}^{L}_{\theta}\cdot\bm{w}$, where $2^{n}\bm{w}$
is the Pauli coefficient of observable $O$, $\bm{g}^{L}_{\theta}$ is the Pauli
coefficient of $\partial_{\theta}\rho_{L}$. If without ambiguity, we will use
$\bm{g}^{L}$ instead of $\bm{g}^{L}_{\theta}$ for simplicity.

To be convenient, we use a single parameter
$q=\max\\{1-2q_{Y}-2q_{Z},1-2q_{X}-2q_{Z},1-2q_{X}-2q_{Y}\\}$ to denote the
noise strength of a local Pauli channel. We then introduce the gradient
vanishing problem of VQA induced by the local Pauli error channel.

######  Lemma 2.1 (Gradient vanishing of the Pauli coefficient [9]).

Let $\theta_{lm}$ be the $m$-th element of parameter $\bm{\theta}_{l}$,
$\bm{g}^{L}_{lm}$ be the Pauli coefficient of
$\partial_{\theta_{lm}}\rho_{L}$. Then

$\displaystyle\norm{\bm{g}_{lm}^{L}}_{\infty}\leq\norm{\bm{g}_{lm}^{L}}_{2}\leq\sqrt{2^{n+1}-2}N_{lm}\norm{\bm{\eta}_{lm}}_{\infty}q^{L+1}\,,$
(2)

where $2^{n}\bm{\eta}_{lm}$ is the Pauli coefficient of $H_{lm}$ defined in
Equ (1) and $N_{lm}$ is the number of non-zero elements of $\bm{\eta}_{lm}$.

The following lemma reveals the effect of the local noisy Pauli channel on the
Pauli coefficient of a quantum state.

######  Lemma 2.2 (Noise-induced exponential decay of Pauli coefficient [9]).

Let $\bm{a}^{l}$ denote the Pauli coefficient of the quantum state $\rho_{l}$.
Then $\|\bm{a}^{l}\|_{\infty}\leq\|\bm{a}^{l}\|_{2}\leq q^{l}\sqrt{2^{n}-1}$.

(a) Cost function $C_{0}$

(b) Cost function $C_{1}$

(c) Cost function $C_{2}$

Figure 1: A schematic diagram for $C_{0}$, $C_{1}$, $C_{2}$. $C_{2}$ has
larger gradient than $C_{0}$ and $C_{2}$ while it is singular.

##  3 Augmented Gradient in Truncated Subspace

In this section, we will show how to construct a cost function in a truncated
subspace. We first define two new cost functions $C_{1}$ and $C_{2}$ in a
truncated subspace. The $C_{1}$ cost function will still have a small gradient
but it is not singular near its minimum. The $C_{2}$ cost function will have a
large gradient and can be easily optimized with gradient descent but it is
singular near its minimum, as shown in Figure 1. We will show that the minimum
value point of $C_{2}$ is also a local minimum of $C_{1}$ and we can optimize
$C_{1}$ with the gradient of $C_{2}$.

###  3.1 Cost Function Definitions

An observable (Hermitian operator) $O$ can always be decomposed into
$O=\sum_{\lambda_{i}\neq 0}\lambda_{i}{|i\rangle\langle i|}$. The states in
the summation terms span a subspace $S$ in the overall Hilbert space. We first
define a cost function $C_{1}$ in this subspace.

######  Definition 3.1 (Cost function of truncated subspace).

Given a subspace $S$, an observable $O$ and its eigendecomposition
$O=\sum_{i}\lambda_{i}{|i\rangle\langle i|}$, the cost in this subspace is
$C_{1}=\frac{\sum_{i\in S}\lambda_{i}p_{i}}{\sum_{i\in S}p_{i}}$, where
$p_{i}$ the measured probability of state $\ket{i}$. The denominator is for
normalization.

The cost function form in Definition 3.1 is not suitable for gradient
analysis. We define an equivalent form of the cost function of truncated space
in terms of observables.

######  Proposition 3.1 (Truncated cost function with observables).

A cost function of truncated measurement $C_{1}=\frac{\sum_{i\in
S}\lambda_{i}p_{i}}{\sum_{i\in S}p_{i}}$ can also be expressed with two
observables:

$C_{1}=\frac{{\mathrm{Tr}}(\rho_{L}O_{1})}{{\mathrm{Tr}}(\rho_{L}O_{2})}\,,$
(3)

where $O_{1}=\sum\limits_{i\in S}\lambda_{i}|i\rangle\langle i|$,
$O_{2}=\sum\limits_{i\in S}|i\rangle\langle i|$.

Proof. Notice that ${\mathrm{Tr}}(\rho_{L}O_{1})=\sum_{i\in
S}\lambda_{i}p_{i}$, ${\mathrm{Tr}}(\rho_{L}O_{1})=\sum_{i\in S}p_{i}$. ∎

######  Example 3.1 (Measurement result truncation).

Suppose the observable is $O_{1}=0.8{|00\rangle\langle
00|}+0.2{|11\rangle\langle 11|}$. The quantum state produced by the
variational quantum circuit is $\rho=0.7{|00\rangle\langle
00|}+0.26{|11\rangle\langle 11|}+0.04{|01\rangle\langle 01|}$. Measuring this
state may give the result ‘01’ with a probability $0.04$. We can discard this
result since it is not in the subspace defined by $O_{1}$ and will not
contribute to the cost function.

The Pauli representations of $O_{1}$ and $O_{2}$ are very useful for gradient
analysis. We introduce them in the following:
$O_{1}=\frac{{\mathrm{Tr}}(O_{1})}{2^{n}}\mathbbm{1}^{\otimes
n}+\bm{w}_{1}\cdot\bm{\sigma}_{n}$,
$O_{2}=\frac{{\mathrm{Tr}}(O_{2})}{2^{n}}\mathbbm{1}^{\otimes
n}+\bm{w}_{2}\cdot\bm{\sigma}_{n}$.

Similar to the cost function $C_{0}$, the gradient of cost function $C_{1}$
decays exponentially as the number of layers increases, as depicted in
Proposition 3.2, because $C_{1}$ will converge to
$\frac{{\mathrm{Tr}}(O_{1})}{{\mathrm{Tr}}(O_{2})}$ as the number of layers
$L$ increases [9].

######  Proposition 3.2 (Gradient of $C_{1}$).

$\forall\rho_{L}$ s.t.
$\absolutevalue{{\mathrm{Tr}}(O_{2}\rho_{L})}\geq\absolutevalue{\frac{{\mathrm{Tr}}(O_{2})}{2^{n}}}$,
the gradient of $C_{1}$ will decay exponentially w.r.t the circuit depth $L$
as, $\partial_{\theta_{lm}}C_{1}\leq\sqrt{2^{n+1}-2}hq^{L+1}$, where
$h=(\frac{\|\bm{w}_{1}\|_{2}}{k_{2}}+\max\limits_{i\in
S}\lambda_{i}\frac{\|\bm{w}_{2}\|_{2}}{k_{2}^{2}})N_{lm}\|\bm{\eta}_{lm}\|_{\infty}$,
$k_{2}=\frac{{\mathrm{Tr}}(O_{2})}{2^{n}}$, $\bm{\eta}_{lm}$ and $N_{lm}$ are
previously defined in Lemma 2.2.

Proof. Postponed to Appendix A. ∎

We observe that gradient vanishing is caused by the first term of the Pauli
representation of the observables in the cost function. We quantitatively
evaluate this effect in the following proposition.

######  Proposition 3.3 (Dominating term in the observable).

$C_{1}=\frac{\frac{{\mathrm{Tr}}(O_{1})}{2^{n}}+\bm{a}^{L}\cdot\bm{w}_{1}}{\frac{{\mathrm{Tr}}(O_{2})}{2^{n}}+\bm{a}^{L}\cdot\bm{w}_{2}}\,,$

where $\bm{a}^{L}$ is the Pauli coefficient of $\rho_{L}$. As $L\to\infty$, if
$\bm{a}^{L}\to 0$ and $\frac{\partial\bm{a}^{L}}{\partial\theta}\to 0$ , then
$\partial_{\theta}C_{1}\to 0$.

Proof. Postponed to Appendix A. ∎

The Pauli representations of $O_{1}$ and $O_{2}$ have dominated term
$\frac{{\mathrm{Tr}}(O_{1})}{2^{n}}\mathbbm{1}^{\otimes n}$ and
$\frac{{\mathrm{Tr}}(O_{2})}{2^{n}}\mathbbm{1}^{\otimes n}$, respectively.
These two dominated terms will mask the effect of other Pauli terms, making
gradient vanishing quickly. However, by eliminating the dominated term, we can
amplify the effect of other Pauli terms and thus mitigate the gradient
vanishing. Therefore, we define a new cost function of truncated space with
dominated terms eliminated.

######  Definition 3.2 (Truncated cost function with traceless observables).

A cost function of truncated measurement with traceless observables is defined
as
$C_{2}=\frac{{\mathrm{Tr}}(\rho_{L}O_{1}^{\prime})}{{\mathrm{Tr}}(\rho_{L}O_{2}^{\prime})}$,
where
$O^{\prime}_{1}=O_{1}-\frac{{\mathrm{Tr}}(O_{1})}{2^{n}}\mathbbm{1}^{\otimes
n}$,
$O^{\prime}_{2}=O_{2}-\frac{{\mathrm{Tr}}(O_{2})}{2^{n}}\mathbbm{1}^{\otimes
n}$.

###  3.2 Augmented Gradient

After removing the first term in the Pauli representation of the observable,
the new observables ($O^{\prime}_{1}$, $O^{\prime}_{2}$) become traceless
(${\mathrm{Tr}}(O^{\prime}_{1})={\mathrm{Tr}}(O^{\prime}_{2})=0$). We first
give the gradient of this new cost function with traceless observables in the
following proposition:

######  Proposition 3.4 (Gradient of $C_{2}$).

The gradient of truncated cost function with traceless observables is

$\displaystyle\partial_{\theta}C_{2}=\frac{\bm{g}^{L}\cdot\bm{w_{1}}}{\bm{a}^{L}\cdot\bm{w_{2}}}-\frac{{\mathrm{Tr}}(\rho_{L}O_{1}^{\prime})}{{\mathrm{Tr}}(\rho_{L}O_{2}^{\prime})}\frac{\bm{g}^{L}\cdot\bm{w_{2}}}{\bm{a}^{L}\cdot\bm{w_{2}}}\,,$
(4)

where $\bm{g}^{L}$ is the Pauli coefficient of $\partial_{\theta}\rho_{L}$,
$\bm{a}^{L}$ is the Pauli coefficient of $\rho_{L}$.

Proof. Postponed to Appendix B. ∎

Then we compare the gradient of the original cost function $C_{1}$ and that of
the new cost function $C_{2}$ with traceless observables. In the following
theorem, we will show that the gradient of $C_{2}$ is much larger than that of
$C_{1}$ .

######  Theorem 3.1 (Mitigating gradient vanishing).

Assume $L_{0}$ is the minimal integer s.t.
$q^{L_{0}}\sqrt{2^{n}-1}\norm{\bm{w}_{2}}_{2}(1+\epsilon)\leq\absolutevalue{\frac{{\mathrm{Tr}}(O_{2})}{2^{n}}}$,
then for $L>2L_{0}+1$, we have
$\absolutevalue{\partial_{\theta_{lm}}C_{2}}\geq\frac{s}{q^{L+1}}\absolutevalue{\partial_{\theta_{lm}}C_{1}}-1$,
where
$s=\min{\\{\frac{\epsilon^{2}k_{2}^{2}}{(1+\epsilon)^{2}\sqrt{2^{n+1}-2}N_{lm}\norm{\bm{\eta}_{lm}}_{\infty}\norm{\bm{w}_{1}k_{2}-\bm{w}_{2}k_{1})}_{2}},}(\frac{\absolutevalue{k_{2}}}{q^{L_{0}}\sqrt{2^{n}-1}\norm{\bm{w}_{2}}_{2}}-q^{L_{0}+1})^{2}\\}$,
$\epsilon$ is an arbitrarily small positive number,
$k_{1}=\frac{{\mathrm{Tr}}(O_{1})}{2^{n}}$,
$k_{2}=\frac{{\mathrm{Tr}}(O_{2})}{2^{n}}$, $\bm{\eta}_{lm}$ and $N_{lm}$ are
previously defined in Lemma 2.2.

Proof. Postponed to Appendix B. ∎

###  3.3 Bypassing the Singularity

However, the cost function $C_{2}$ has a major drawback that it is singular
around its minimum value point. We show its singularity in Proposition 3.5.

######  Proposition 3.5 (Singularity of $C_{2}$).

If $\max\limits_{i\in S}p_{i}=\sum\limits_{i\in
S}p_{i}=\frac{{\mathrm{Tr}}(O_{2})}{2^{n}}$, the cost function $C_{2}$ is
singular and has the two following properties: (a) The global minimum of
$C_{2}$ is negative infinity; (b) The gradient of $C_{2}$ will become
infinitely large.

Proof. Postponed to Appendix C. ∎

We may not want to directly optimize $C_{2}$ due to its singularity but we
will show that we can use the gradient of $C_{2}$ to optimize $C_{1}$. In the
following theorem, we reveal the connection between the minimum value points
of $C_{1}$ and $C_{2}$. That is, the minimum value point of $C_{2}$ is also a
minimum value point of $C_{1}$.

######  Theorem 3.2 (Optimizing $C_{1}$ with gradient from $C_{2}$).

Assume the minimum value of $C_{1}$ be the $C_{1}^{*}$. If there is an
iterative algorithm $\mathcal{P}$ that optimize $C_{2}$ with a sequence of
parameters $\\{\bm{\theta}_{1},\bm{\theta}_{2},\cdots\\}$, then
$\forall\epsilon>0$, $\exists n_{0}\in\mathbb{N}$, s.t. $\forall n>n_{0}$,
$|C_{1}(\bm{\theta}_{n})-C_{1}^{*}|<\epsilon$ where $\bm{\theta}_{n}$ is the
parameter at the $n$-th iteration of $\mathcal{P}$.

Proof. Postponed to Appendix C. ∎

Another benefit of optimizing $C_{1}$ rather than $C_{2}$ is that, the
optimization process may terminate earlier for the cost function $C_{1}$
because $C_{1}$ has a large minimum value point space:

######  Proposition 3.6 (Solution space of $C_{1}$).

The solution space of problem $\min\limits_{\ket{\psi}}C_{1}$ is of dimension
$2^{n}-\dim S+1$.

Proof. Postponed to Appendix C. ∎

Without loss of generality, we assume the minimum eigenvalue in the subspace
$S$ is negative. In the following, we introduce a refined version of $C_{2}$
that has better properties in practical optimization.

Avoiding singularity of $C_{2}$: To avoid the singularity of $C_{2}$’s
gradient, we will add a threshold value to the denominator of $C_{2}$ as,
$C_{2}=\frac{{\mathrm{Tr}}(\rho_{L}O_{1}^{\prime})}{{\mathrm{Tr}}(\rho_{L}O_{2}^{\prime})+\alpha}$,
where $\alpha$ is an adjustable positive hyper-parameter.

Penalize $C_{2}$’s gradient: To avoid leaving the subspace $S$, we will add a
penalty term to the numerator of $C_{2}$ as,
$C_{2}=\frac{{\mathrm{Tr}}(\rho_{L}O_{1}^{\prime})+\beta}{{\mathrm{Tr}}(\rho_{L}O_{2}^{\prime})+\alpha}$,
where $\beta$ is an adjustable positive hyper-parameter.

##  4 Evaluation

In this section, we evaluate the proposed gradient mitigation scheme over
various VQA tasks.

###  4.1 Experimental Setup

Benchmarks: We select six different VQA benchmarks of two major types. The
first three benchmarks solve three different combinatorial optimization
problems, the graph max-cut problem (MC), the vertex cover problem (VC), and
the traveling salesman problem (TSP), using the QAOA algorithm [26]. The
second three benchmarks simulate the ground state of three chemical molecules,
${\rm H_{2}}$, ${\rm LiH}$, and ${\rm BeH_{2}}$, using the VQE algorithm [30].
Both QAOA and VQE are essentially VQA. The information (numbers of qubits and
parameters) of the circuits in these benchmarks are listed in Table 1. We
illustrate the graphs of the three combinatorial optimization problems and the
molecule configurations (atoms and bond lengths) in the ‘Description’ column.

Figure 2: Gradient norm of $C_{1}$ and $C_{2}$ on QAOA and VQE tasks

The symmetry comes from the domain knowledge of the real VQA applications and
it is widespread. For VQE application, such symmetry comes from the property
of the simulated physical system governed by the physics laws. For example,
suppose we are simulating a chemical system with 2 electrons on 3 orbitals. We
will have 3 qubits representing the 3 orbitals and the qubit state 1 means the
orbital is occupied by an electron. A subspace S could be
$span\\{|110\rangle,|101\rangle,|011\rangle\\}$ (the space spanned by basis
states with two 1’s in the bit string). This is because the number of
electrons is preserved in chemical simulation and 1 electron state (e.g.,
$|011\rangle$) or 3 electron state ($|111\rangle$) are not valid states. For
QAOA, the symmetry can come from the underlying graph structure of the problem
as well as the qubit encoding scheme of the problem. We recommend a good
reference “Classical symmetries and qaoa” (https://arxiv.org/abs/2012.04713
(https://arxiv.org/abs/2012.04713)) which discusses the symmetries for QAOA.
We have explained more details in Section 4.1 about how to find the symmetries
in the benchmarks.

Encoding and symmetries: For VQE tasks, we adopt the commonly used
Jordan–Wigner transformation [34] and different basis states represent
different numbers of electrons. The symmetries of VQE tasks come from the fact
that the number of electrons is conserved in chemical simulation. The subspace
is spanned by basis states corresponding to the correct number of electrons
simulated. The symmetries of QAOA tasks come from the graph structure. For MC,
we use 4 qubits $\\{q_{3},q_{2},q_{1},q_{0}\\}$ to represent each graph node,
and quantum state $\ket{1}$ ($\ket{0}$) means this node is selected in the
first partition (resp. the second partition). Since it does not matter if the
orders of the two partitions are exchanged, we can always assume
$q_{0}=\ket{1}$. For VC, the encoding scheme is similar to that of MC. We use
$q_{2}$ to represent the rightmost node, $q_{3}$ to represent the uppermost
node. Since $q_{2}$ and $q_{3}$ are nodes of reflection symmetry, we do not to
need have both qubits being $\ket{1}$ for the VC task. Thus, we can always
assume $q_{2}=0$. For TSP, we use 6 qubits
$\\{q_{5},q_{4},q_{3},q_{2},q_{1},q_{0}\\}$ to encode node numbers, i.e., 2
qubits per node. The graph of TSP has a cyclic symmetry, thus we can always
assume $q_{1}q_{0}=\ket{00}$. Our subspaces are derived from these symmetries.

Table 1: Benchmarks

Name | QAOA-MC | QAOA-VC | QAOA-TSP | VQE-${\rm H_{2}}$ | VQE-${\rm LiH}$ | VQE-${\rm BeH_{2}}$
---|---|---|---|---|---|---
# of Qubits | 4 | 4 | 6 | 4 | 6 | 8
# of Param. | 20 | 20 | 30 | 20 | 30 | 40
Description |  |  |  |  |  |

Gradient estimation: The eigendecomposition of an observable, which exists but
usually not available, is used only in our theoretical analysis. When applying
our technique in practice, we can obtain ${\mathrm{Tr}}(\rho_{L}O_{1})$ via
measurement. ${\mathrm{Tr}}(\rho_{L}O_{2})$ can be estimated by accumulating
the probability of states satisfying certain symmetries associated with the
adopted subspace. Thus, we can compute $C_{1}$ or $C_{2}$ without
eigendecomposition in evaluation. The gradients can then be calculated with
the central difference method.

Metrics: We evaluate the values of the cost functions and the norms of the
gradients during the training procedures to show the effect of our gradient
vanishing mitigation technique. For QAOA tasks, we also include the Success
Rate, which is the probability of obtaining the correct answer in the final
measurement. A higher successful rate is more desirable. For VQE tasks, we use
Fidelity to measure the “closeness” of the ground state found in our VQE
training and the true ground state of the target molecule. The fidelity $F$ of
quantum states $\ket{\psi_{1}}$, $\ket{\psi_{2}}$ is defined by
$F(\ket{\psi_{1}},\ket{\psi_{2}})=\big{|}\bra{\psi_{1}}\ket{\psi_{2}}\big{|}^{2}$
and
$F(\ket{\psi_{1}},\ket{\psi_{2}})=1\Leftrightarrow\ket{\psi_{1}}=\ket{\psi_{2}}$.
When $F$ is closer to 1, the state found in VQA is closer to the true ground
state.

To understand the quality of the learned parameters, we propose another metric
called Parameter Quality. For QAOA tasks, the parameter quality refers to the
success rate of noise-free simulation using the parameters obtained from noisy
simulation. For VQE tasks, the parameter quality refers to the fidelity
between the state generated from noise-free simulation with the trained
parameters and the correct eigenstate of the minimal eigenvalue.

Ansatz selection: Our work is ansatz-independent since our propositions and
theorems do not make any assumptions about the ansatz form. In this paper, we
use hardware efficient ansatz (HEA) constructed by Qiskit for all experiments
since HEA is the most widely used ansatz form in experiments due to its
relatively small computation resource requirement.

Noise setting: In this paper, we only consider local Pauli noise. For 4-qubit
benchmarks, the noise rate is set to be $q_{X}=q_{Y}=q_{Z}=0.03$. For 6-qubit
and 8-qubit benchmarks, the noise rate is set to be $q_{X}=q_{Y}=q_{Z}=0.01$.
With this noise setting, our results on 10-20 circuit depth (later in this
session) can already demonstrate the advantage of our method. We expect that
our method can be more effective on larger-size ansatzes according to Theorem
3.1.

Implementation: All cost functions and experiments are implemented on IBM’s
Qiskit framework [35]. For VQE experiments, we use Qiskit Chemistry and PySCF
[36] to generate the Hamiltonian of the simulated molecules. For QAOA
experiments, we use Qiskit Optimization to generate the Hamiltonian of the
simulated combinatoric optimization problems. The parameters are optimized
with the gradient descent algorithm. We perform all simulations based on IBM’s
Qiskit noisy simulation infrastructure (version 0.7.2). We perform all
experiments on a server with a 6-core Intel E5-2603v4 CPU and 32GB of RAM. We
use a linear decay for the learning rate. The gradient is truncated if its
$\infty$-norm is larger than certain threshold value.

###  4.2 Results

Figure 3: The optimization results with $C_{1}$ and $C_{2}$

Augmented gradient: We first compare the norm of the gradients from both
$C_{1}$ and $C_{2}$. As shown in Figure 2, $C_{2}$ has a much larger gradient
in nature compared with $C_{1}$ under the same noise level and this result is
consistent with Theorem 3.1. The gradient norms of $C_{2}$ are about 141x,
5.7x, and 2.1x higher on average than that of $C_{1}$ for QAOA tasks MAXCUT,
VC, and TSP, respectively. For VQE tasks, the gradient norms of $C_{2}$ are
about 21.7x, 2462.3x, and 3.7x higher on average than that of $C_{1}$ for the
simulation of $\rm H_{2}$, $\rm LiH$, and $\rm BeH_{2}$, respectively. The
singularity of $C_{2}$ can also be observed since the gradient of $C_{2}$ can
be very large (as discussed in Proposition 3.5).

Table 2: Results for QAOA and VQE tasks.

Benchmark | Success rate | Parameter Quality | Benchmark | Fidelity | Parameter Quality
---|---|---|---|---|---
Name | $C_{1}$ | $C_{2}$ | $C_{1}$ | $C_{2}$ | Name | $C_{1}$ | $C_{2}$ | $C_{1}$ | $C_{2}$
QAOA-MC | 0.3544 | 0.5380 | 0.4480 | 0.9156 | VQE-${\rm H_{2}}$ | 0.2100 | 0.4503 | 0.0242 | 0.8753
QAOA-VC | 0.1587 | 0.4757 | 0.1203 | 0.9570 | VQE-${\rm LiH}$ | 0.3980 | 0.8568 | 0.3633 | 0.8705
QAOA-TSP | 0.2252 | 0.3718 | 0.6156 | 0.8974 | VQE-${\rm BeH_{2}}$ | 0.1681 | 0.2083 | 0.4108 | 0.5457

Overall improvement: We then compare the overall optimization results of using
$C_{1}$ and $C_{2}$. In general, optimizations using the gradient from $C_{2}$
can converge to a better minimum. The upper half of Figure 3 shows the
optimization results with cost function $C_{1}$ and $C_{2}$ on different QAOA
tasks. Compared with using the gradient from $C_{1}$, $C_{2}$’s gradient
increases the success rates significantly as shown in Table 2: from 35.4% to
53.8% for the MC task, and from 15.9% to 47.6% for the VC task, from 22.5% to
37.2% for the TSP task, respectively. The parameter quality of using $C_{2}$
is also improved significantly as shown in Table 2: from 44.8% to 91.6% for
the MC task, and from 12.03% to 95.7% for the VC task, from 61.6% to 89.7% for
the TSP task.

The lower half of Figure 3 shows the optimization results with cost function
$C_{1}$ and $C_{2}$ on different VQE tasks and it can be observed that using
gradients $C_{2}$ can converge to a better ground state. The final state
fidelity improvement of using $C_{2}$ is shown in Table 2: from 0.21 to 0.45
for the $\rm H_{2}$ molecule, from 0.398 to 0.857 for the $\rm LiH$ molecule,
from 0.168 to 0.208 for the $\rm BeH_{2}$ molecule. $C_{2}$ promotes the
parameter quality significantly (Table 2): from 0.024 to 0.875 for the $\rm
H_{2}$ molecule, from 0.363 to 0.870 for the $\rm LiH$ molecule, from 0.411 to
0.546 for the $\rm BeH_{2}$ molecule.

In summary, VQAs with cost function $C_{2}$ show significant improvement over
original VQAs using the vanilla cost $C_{1}$ and our optimization scheme in
Theorem 3.2 is very effective. Sometimes using the gradient from $C_{1}$
cannot even optimize (e.g., QAOA-VC, VQE-LiH) because the gradient is mainly
caused by the noise, and the gradient descent direction is random. However,
the gradient from $C_{2}$ is significantly augmented and is able to point out
the correct descent direction. This can help VQA converge faster and mitigate
part of the noise effects.

##  5 Discussion

This paper studies mitigating the noise-induced gradient vanishing in VQA
training through a novel training scheme. By identifying and eliminating the
dominant term in the Pauli representation of an observable, we construct a new
cost function that has significantly larger gradients without changing the
minimum found in the gradient descent. The advantages of our training approach
are not only proved in theory but also demonstrated in practice. The
techniques proposed in this paper can mitigate one major obstacle in VQA
training of larger sizes and thus help with a future demonstration of quantum
advantage using VQAs. Several future research directions are briefly discussed
as follows:

Beyond the cost function: In this paper, we aim to mitigate the noise effects
on the gradient and augment the gradient norm significantly through a new cost
function $C_{2}$. A VQA has several components other than the cost function,
e.g., ansatz architecture, optimizer algorithm, parameter initialization. It
is worth exploring how we can improve these components to reduce the noise-
induced gradient vanishing.

More about the subspace: We present a general result on the benefit of using
subspace. However, one VQA task may have multiple symmetries, leading to
completely different subspace selections. For example, there are two
symmetries in the TSP task. One symmetry is the so-called cyclic symmetry as
any node can be the starting point. Another symmetry is that the same node
encoding cannot be repeated. The subspace selection principles can be
investigated to maximize the benefit with respect to the VQA performance.

##  6 Conclusion

This paper presents a novel training scheme to mitigate the inevitable noise-
induced gradient vanishing in VQA training. We show that, by introducing a new
cost function with a traceless observable in a truncated subspace, the
gradient can be augmented significantly. We also prove that the same minimum
value point can be found when optimizing the vanilla cost function with the
augmented gradients from the new cost. Experiments show that our new training
scheme is applicable to major VQAs with various tasks. The techniques proposed
in this paper can alleviate the gradient vanishing obstacle on the road to
demonstrating quantum advantages on near-term quantum computers.

## References

  * [1] John Preskill.  Quantum computing and the entanglement frontier.  arXiv preprint arXiv:1203.5813, 2012.
  * [2] Frank Arute, Kunal Arya, Ryan Babbush, Dave Bacon, Joseph C Bardin, Rami Barends, Rupak Biswas, Sergio Boixo, Fernando GSL Brandao, David A Buell, et al.  Quantum supremacy using a programmable superconducting processor.  Nature, 574(7779):505–510, 2019.
  * [3] M. Cerezo, Andrew Arrasmith, Ryan Babbush, Simon C. Benjamin, Suguru Endo, Keisuke Fujii, Jarrod R. McClean, Kosuke Mitarai, Xiao Yuan, Lukasz Cincio, and Patrick J. Coles.  Variational quantum algorithms, 2020.
  * [4] Frank Arute, Kunal Arya, Ryan Babbush, Dave Bacon, Joseph C Bardin, Rami Barends, Sergio Boixo, Michael Broughton, Bob B Buckley, David A Buell, et al.  Quantum approximate optimization of non-planar graph problems on a planar superconducting processor.  arXiv preprint arXiv:2004.04197, 2020.
  * [5] G. Pagano, A. Bapat, Pascal Becker, K. S. Collins, A. De, P. W. Hess, H. B. Kaplan, A. Kyprianidis, W. Tan, C. Baldwin, L. Brady, A. Deshpande, F. Liu, S. Jordan, A. V. Gorshkov, and C. Monroe.  Quantum approximate optimization of the long-range ising model with a trapped-ion quantum simulator.  Proceedings of the National Academy of Sciences of the United States of America, 117:25396 – 25401, 2020.
  * [6] F. Arute, K. Arya, R. Babbush, D. Bacon, Joseph C. Bardin, R. Barends, S. Boixo, M. Broughton, B. Buckley, David A. Buell, B. Burkett, N. Bushnell, Y. Chen, Zhiqiang Chen, B. Chiaro, R. Collins, W. Courtney, Sean Demura, A. Dunsworth, E. Farhi, A. Fowler, B. Foxen, C. Gidney, M. Giustina, R. Graff, Steve Habegger, Matthew P. Harrigan, A. Ho, S. Hong, T. Huang, William J. Huggins, L. Ioffe, S. V. Isakov, E. Jeffrey, Z. Jiang, C. Jones, D. Kafri, K. Kechedzhi, J. Kelly, S. Kim, P. Klimov, A. Korotkov, F. Kostritsa, D. Landhuis, P. Laptev, Mike Lindmark, E. Lucero, O. Martin, J. M. Martinis, J. McClean, M. McEwen, A. Megrant, X. Mi, M. Mohseni, Wojciech Mruczkiewicz, J. Mutus, O. Naaman, M. Neeley, C. Neill, H. Neven, M. Y. Niu, T. E. O’brien, E. Ostby, A. Petukhov, Harald Putterman, C. Quintana, P. Roushan, N. Rubin, D. Sank, K. Satzinger, V. Smelyanskiy, D. Strain, Kevin J. Sung, M. Szalay, Tyler Y Takeshita, A. Vainsencher, T. White, N. Wiebe, Z. Yao, P. Yeh, and Adam Zalcman.  Hartree-fock on a superconducting qubit quantum computer.  Science, 369:1084 – 1089, 2020.
  * [7] Abhinav Kandala, A. Mezzacapo, K. Temme, Maika Takita, M. Brink, J. Chow, and J. Gambetta.  Hardware-efficient variational quantum eigensolver for small molecules and quantum magnets.  Nature, 549:242–246, 2017.
  * [8] Jarrod R McClean, Sergio Boixo, Vadim N Smelyanskiy, Ryan Babbush, and Hartmut Neven.  Barren plateaus in quantum neural network training landscapes.  Nature communications, 9(1):1–6, 2018.
  * [9] Samson Wang, Enrico Fontana, Marco Cerezo, Kunal Sharma, Akira Sone, Lukasz Cincio, and Patrick J Coles.  Noise-induced barren plateaus in variational quantum algorithms.  arXiv preprint arXiv:2007.14384, 2020.
  * [10] E. Grant, L. Wossnig, M. Ostaszewski, and Marcello Benedetti.  An initialization strategy for addressing barren plateaus in parametrized quantum circuits.  arXiv: Quantum Physics, 2019.
  * [11] Guillaume Verdon, M. Broughton, J. McClean, Kevin J. Sung, R. Babbush, Z. Jiang, H. Neven, and M. Mohseni.  Learning to learn with quantum neural networks via classical neural networks.  ArXiv, abs/1907.05415, 2019.
  * [12] A. Skolik, J. McClean, M. Mohseni, P. V. D. Smagt, and M. Leib.  Layerwise learning for quantum neural networks.  ArXiv, abs/2006.14904, 2020.
  * [13] J. Kubler, A. Arrasmith, L. Cincio, and Patrick J. Coles.  An adaptive optimizer for measurement-frugal variational algorithms.  arXiv: Quantum Physics, 2019.
  * [14] Kaining Zhang, Min-Hsiu Hsieh, L. Liu, and D. Tao.  Toward trainability of quantum neural networks.  arXiv: Quantum Physics, 2020.
  * [15] T. Volkoff and Patrick J. Coles.  Large gradients via correlation in random parameterized quantum circuits.  arXiv: Quantum Physics, 2020.
  * [16] Arthur Pesah, M. Cerezo, Samson Wang, T. Volkoff, A. Sornborger, and Patrick J. Coles.  Absence of barren plateaus in quantum convolutional neural networks.  ArXiv, abs/2011.02966, 2020.
  * [17] Yuxuan Du, T. Huang, Shan You, Min-Hsiu Hsieh, and Dacheng Tao.  Quantum circuit architecture search: error mitigation and trainability enhancement for variational quantum solvers.  ArXiv, abs/2010.10217, 2020.
  * [18] Marco Cerezo, Akira Sone, Tyler Volkoff, Lukasz Cincio, and Patrick J Coles.  Cost-function-dependent barren plateaus in shallow quantum neural networks.  arXiv preprint arXiv:2001.00550, 2020.
  * [19] R. Sagastizabal, X. Bonet-Monroig, M. Singh, M. A. Rol, C. C. Bultink, X. Fu, C. Price, V. P. Ostroukh, N. Muthusubramanian, A. Bruno, M. Beekman, N. Haider, T. E. O’brien, and L. DiCarlo.  Error mitigation by symmetry verification on a variational quantum eigensolver.  arXiv: Quantum Physics, 2019.
  * [20] Bryan T. Gard, L. Zhu, G. Barron, Nicholas J Mayhall, S. Economou, and Edwin Barnes.  Efficient symmetry-preserving state preparation circuits for the variational quantum eigensolver algorithm.  npj Quantum Information, 6:1–9, 2019.
  * [21] X. Bonet-Monroig, R. Sagastizabal, M. Singh, and T. O’Brien.  Low-cost error mitigation by symmetry verification.  Physical Review A, 98, 2018.
  * [22] Ruslan Shaydulin, Stuart Hadfield, Tad Hogg, and Ilya Safro.  Classical symmetries and qaoa.  ArXiv, abs/2012.04713, 2020.
  * [23] Z. Wang, Stuart Hadfield, Z. Jiang, and E. Rieffel.  The quantum approximation optimization algorithm for maxcut: A fermionic view.  arXiv: Quantum Physics, 2017.
  * [24] S. Bravyi, Alexander Kliesch, R. Koenig, and E. Tang.  Obstacles to state preparation and variational optimization from symmetry protection.  arXiv: Quantum Physics, 2019.
  * [25] Michael A Nielsen and Isaac Chuang.  Quantum computation and quantum information, 2002.
  * [26] Edward Farhi, Jeffrey Goldstone, and Sam Gutmann.  A quantum approximate optimization algorithm.  arXiv preprint arXiv:1411.4028, 2014.
  * [27] Nikolaj Moll, Panagiotis Barkoutsos, Lev S Bishop, Jerry M Chow, Andrew Cross, Daniel J Egger, Stefan Filipp, Andreas Fuhrer, Jay M Gambetta, Marc Ganzhorn, et al.  Quantum optimization using variational algorithms on near-term quantum devices.  Quantum Science and Technology, 3(3):030503, 2018.
  * [28] Edward Farhi and Hartmut Neven.  Classification with quantum neural networks on near term processors, 2018\.
  * [29] Maria Schuld, Alex Bocharov, Krysta M. Svore, and Nathan Wiebe.  Circuit-centric quantum classifiers.  Physical Review A, 101(3), Mar 2020.
  * [30] Alberto Peruzzo, Jarrod McClean, Peter Shadbolt, Man-Hong Yung, Xiao-Qi Zhou, Peter J Love, Alán Aspuru-Guzik, and Jeremy L O’brien.  A variational eigenvalue solver on a photonic quantum processor.  Nature communications, 5:4213, 2014.
  * [31] Abhinav Kandala, Antonio Mezzacapo, Kristan Temme, Maika Takita, Markus Brink, Jerry M Chow, and Jay M Gambetta.  Hardware-efficient variational quantum eigensolver for small molecules and quantum magnets.  Nature, 549(7671):242–246, 2017.
  * [32] Kunal Sharma, Marco Cerezo, Lukasz Cincio, and Patrick J Coles.  Trainability of dissipative perceptron-based quantum neural networks.  arXiv preprint arXiv:2005.12458, 2020.
  * [33] Cheng Xue, Zhaoyun Chen, Yuchun Wu, and G. Guo.  Effects of quantum noise on quantum approximate optimization algorithm.  arXiv: Quantum Physics, 2019.
  * [34] P. Jordán and E. Wigner.  Über das paulische äquivalenzverbot.  Zeitschrift für Physik, 47:631–651, 1928.
  * [35] Héctor Abraham, AduOffei, Rochisha Agarwal, Ismail Yunus Akhalwaya, Gadi Aleksandrowicz, Thomas Alexander, Matthew Amy, Eli Arbel, Arijit02, Abraham Asfaw, Artur Avkhadiev, Carlos Azaustre, AzizNgoueya, Abhik Banerjee, Aman Bansal, Panagiotis Barkoutsos, Ashish Barnawal, George Barron, George S. Barron, Luciano Bello, Yael Ben-Haim, Daniel Bevenius, Arjun Bhobe, Lev S. Bishop, Carsten Blank, Sorin Bolos, Samuel Bosch, Brandon, Sergey Bravyi, Bryce-Fuller, David Bucher, Artemiy Burov, Fran Cabrera, Padraic Calpin, Lauren Capelluto, Jorge Carballo, Ginés Carrascal, Adrian Chen, Chun-Fu Chen, Edward Chen, Jielun (Chris) Chen, Richard Chen, Jerry M. Chow, Spencer Churchill, Christian Claus, Christian Clauss, Romilly Cocking, Filipe Correa, Abigail J. Cross, Andrew W. Cross, Simon Cross, Juan Cruz-Benito, Chris Culver, Antonio D. Córcoles-Gonzales, Sean Dague, Tareq El Dandachi, Marcus Daniels, Matthieu Dartiailh, DavideFrr, Abdón Rodríguez Davila, Anton Dekusar, Delton Ding, Jun Doi, Eric Drechsler, Drew, Eugene Dumitrescu, Karel Dumon, Ivan Duran, Kareem EL-Safty, Eric Eastman, Grant Eberle, Pieter Eendebak, Daniel Egger, Mark Everitt, Paco Martín Fernández, Axel Hernández Ferrera, Romain Fouilland, FranckChevallier, Albert Frisch, Andreas Fuhrer, Bryce Fuller, MELVIN GEORGE, Julien Gacon, Borja Godoy Gago, Claudio Gambella, Jay M. Gambetta, Adhisha Gammanpila, Luis Garcia, Tanya Garg, Shelly Garion, Austin Gilliam, Aditya Giridharan, Juan Gomez-Mosquera, Gonzalo, Salvador de la Puente González, Jesse Gorzinski, Ian Gould, Donny Greenberg, Dmitry Grinko, Wen Guan, John A. Gunnels, Mikael Haglund, Isabel Haide, Ikko Hamamura, Omar Costa Hamido, Frank Harkins, Vojtech Havlicek, Joe Hellmers, Łukasz Herok, Stefan Hillmich, Hiroshi Horii, Connor Howington, Shaohan Hu, Wei Hu, Junye Huang, Rolf Huisman, Haruki Imai, Takashi Imamichi, Kazuaki Ishizaki, Raban Iten, Toshinari Itoko, JamesSeaward, Ali Javadi, Ali Javadi-Abhari, Wahaj Javed, Jessica, Madhav Jivrajani, Kiran Johns, Scott Johnstun, Jonathan-Shoemaker, Vismai K, Tal Kachmann, Akshay Kale, Naoki Kanazawa, Kang-Bae, Anton Karazeev, Paul Kassebaum, Josh Kelso, Spencer King, Knabberjoe, Yuri Kobayashi, Arseny Kovyrshin, Rajiv Krishnakumar, Vivek Krishnan, Kevin Krsulich, Prasad Kumkar, Gawel Kus, Ryan LaRose, Enrique Lacal, Raphaël Lambert, John Lapeyre, Joe Latone, Scott Lawrence, Christina Lee, Gushu Li, Dennis Liu, Peng Liu, Yunho Maeng, Kahan Majmudar, Aleksei Malyshev, Joshua Manela, Jakub Marecek, Manoel Marques, Dmitri Maslov, Dolph Mathews, Atsushi Matsuo, Douglas T. McClure, Cameron McGarry, David McKay, Dan McPherson, Srujan Meesala, Thomas Metcalfe, Martin Mevissen, Andrew Meyer, Antonio Mezzacapo, Rohit Midha, Zlatko Minev, Abby Mitchell, Nikolaj Moll, Jhon Montanez, Gabriel Monteiro, Michael Duane Mooring, Renier Morales, Niall Moran, Mario Motta, MrF, Prakash Murali, Jan Müggenburg, David Nadlinger, Ken Nakanishi, Giacomo Nannicini, Paul Nation, Edwin Navarro, Yehuda Naveh, Scott Wyman Neagle, Patrick Neuweiler, Johan Nicander, Pradeep Niroula, Hassi Norlen, NuoWenLei, Lee James O’Riordan, Oluwatobi Ogunbayo, Pauline Ollitrault, Raul Otaolea, Steven Oud, Dan Padilha, Hanhee Paik, Soham Pal, Yuchen Pang, Vincent R. Pascuzzi, Simone Perriello, Anna Phan, Francesco Piro, Marco Pistoia, Christophe Piveteau, Pierre Pocreau, Alejandro Pozas-iKerstjens, Milos Prokop, Viktor Prutyanov, Daniel Puzzuoli, Jesús Pérez, Quintiii, Rafey Iqbal Rahman, Arun Raja, Nipun Ramagiri, Anirudh Rao, Rudy Raymond, Rafael Martín-Cuevas Redondo, Max Reuter, Julia Rice, Matt Riedemann, Marcello La Rocca, Diego M. Rodríguez, RohithKarur, Max Rossmannek, Mingi Ryu, Tharrmashastha SAPV, SamFerracin, Martin Sandberg, Hirmay Sandesara, Ritvik Sapra, Hayk Sargsyan, Aniruddha Sarkar, Ninad Sathaye, Bruno Schmitt, Chris Schnabel, Zachary Schoenfeld, Travis L. Scholten, Eddie Schoute, Joachim Schwarm, Ismael Faro Sertage, Kanav Setia, Nathan Shammah, Yunong Shi, Adenilton Silva, Andrea Simonetto, Nick Singstock, Yukio Siraichi, Iskandar Sitdikov, Seyon Sivarajah, Magnus Berg Sletfjerding, John A. Smolin, Mathias Soeken, Igor Olegovich Sokolov, Igor Sokolov, SooluThomas, Starfish, Dominik Steenken, Matt Stypulkoski, Shaojun Sun, Kevin J. Sung, Hitomi Takahashi, Tanvesh Takawale, Ivano Tavernelli, Charles Taylor, Pete Taylour, Soolu Thomas, Mathieu Tillet, Maddy Tod, Miroslav Tomasik, Enrique de la Torre, Kenso Trabing, Matthew Treinish, TrishaPe, Davindra Tulsi, Wes Turner, Yotam Vaknin, Carmen Recio Valcarce, Francois Varchon, Almudena Carrera Vazquez, Victor Villar, Desiree Vogt-Lee, Christophe Vuillot, James Weaver, Johannes Weidenfeller, Rafal Wieczorek, Jonathan A. Wildstrom, Erick Winston, Jack J. Woehr, Stefan Woerner, Ryan Woo, Christopher J. Wood, Ryan Wood, Stephen Wood, Steve Wood, James Wootton, Daniyar Yeralin, David Yonge-Mallo, Richard Young, Jessie Yu, Christopher Zachow, Laura Zdanski, Helena Zhang, Christa Zoufal, Zoufalc, a kapila, a matsuo, bcamorrison, brandhsn, nick bronn, brosand, chlorophyll zz, csseifms, dekel.meirom, dekelmeirom, dekool, dime10, drholmie, dtrenev, ehchen, elfrocampeador, faisaldebouni, fanizzamarco, gabrieleagl, gadial, galeinston, georgios ts, gruu, hhorii, hykavitha, jagunther, jliu45, jscott2, kanejess, klinvill, krutik2966, kurarrr, lerongil, ma5x, merav aharoni, michelle4654, ordmoj, sagar pahwa, rmoyard, saswati qiskit, scottkelso, sethmerkel, shaashwat, sternparky, strickroman, sumitpuri, tigerjack, toural, tsura crisaldo, vvilpas, welien, willhbang, yang.luh, yotamvakninibm, and Mantas Čepulkovskis.  Qiskit: An open-source framework for quantum computing, 2019.
  * [36] Qiming Sun, Timothy C. Berkelbach, Nick S. Blunt, George H. Booth, Sheng Guo, Zhendong Li, Junzi Liu, James D. McClain, Elvira R. Sayfutyarova, Sandeep Sharma, Sebastian Wouters, and Garnet Kin-Lic Chan.  Pyscf: the python-based simulations of chemistry framework, 2017.

##  Appendix A Gradient Vanishing of C1

In the following, we will follow the notations defined in previous sections.

We first prove that the derivative of a quantum state with respect to the
parameters in a variational quantum circuit is a traceless operator under the
local Pauli channel noise model.

######  Lemma A.1 (Traceless derivative of the quantum state).

For a variational circuit with local Pauli channel noise model,
$\partial_{\theta}\rho_{L}$ is a traceless operator, i.e.,
${\mathrm{Tr}}(\partial_{\theta}\rho_{L})=0$.

###### Proof.

Assume $\bm{a}^{L}$ is the Pauli coefficient of $\rho_{L}$. Since
$\rho_{L}=\frac{1}{2^{n}}(\mathbbm{1}^{\otimes
n}+\bm{a}^{L}\cdot\bm{\sigma}_{n}$), we have

$\displaystyle\partial_{\theta}\rho_{L}=\frac{1}{2^{n}}\frac{\partial\bm{a}^{L}}{\partial\theta}\cdot\bm{\sigma}_{n}$
(5)

Thus,
${\mathrm{Tr}}(\partial_{\theta}\rho_{L})={\mathrm{Tr}}(\frac{1}{2^{n}}\frac{\partial\bm{a}^{L}}{\partial\theta}\cdot\bm{\sigma}_{n})=0$.
∎

Similar to the original cost function $C_{0}$, the gradient of cost function
$C_{1}$ decays exponentially as the number of layers increases, as depicted in
Proposition 3.2, because $C_{1}$ will converge to
$\frac{{\mathrm{Tr}}(O_{1})}{{\mathrm{Tr}}(O_{2})}$ as the number of layers
$L$ increases [9].

Proposition 3.2 (Gradient of $C_{1}$). $\forall\rho_{L}$ s.t.
$\absolutevalue{{\mathrm{Tr}}(O_{2}\rho_{L})}\geq\absolutevalue{\frac{{\mathrm{Tr}}(O_{2})}{2^{n}}}$,
the gradient of $C_{1}$ will decay exponentially with respect to the circuit
depth $L$:

$\partial_{\theta_{lm}}C_{1}\leq\sqrt{2^{n+1}-2}hq^{L+1}$

where $h=(\frac{\|\bm{w}_{1}\|_{2}}{k_{2}}+\max\limits_{i\in
S}\lambda_{i}\frac{\|\bm{w}_{2}\|_{2}}{k_{2}^{2}})N_{lm}\|\bm{\eta}_{lm}\|_{\infty}$,
$k_{2}=\frac{{\mathrm{Tr}}(O_{2})}{2^{n}}$, $\bm{\eta}_{lm}$ and $N_{lm}$ are
previously defined in Lemma 2.2.

###### Proof.

Let $\theta=\theta_{lm}$. Using Lemma A.1, we have
$\partial_{\theta}\rho_{L}=\frac{1}{2^{n}}\bm{g}^{L}\cdot\bm{\sigma}_{n}$,
where $\bm{g}^{L}=\frac{\partial\bm{a}^{L}}{\partial\theta}$ is the Pauli
coefficient of $\partial_{\theta}\rho_{L}$. Then

$\displaystyle\partial_{\theta}C_{1}$
$\displaystyle=\frac{{\mathrm{Tr}}(O_{1}\partial_{\theta}\rho_{L})}{{\mathrm{Tr}}(O_{2}\rho_{L})}-\frac{{\mathrm{Tr}}(O_{1}\rho_{L})}{{\mathrm{Tr}}(O_{2}\rho_{L})}\frac{{\mathrm{Tr}}(O_{2}\partial_{\theta}\rho_{L})}{{\mathrm{Tr}}(O_{2}\rho_{L})}$
$\displaystyle=\frac{{\mathrm{Tr}}((\frac{{\mathrm{Tr}}(O_{1})}{2^{n}}\mathbbm{1}^{\otimes
n}+\bm{w}_{1}\cdot\bm{\sigma}_{n})(\frac{1}{2^{n}}\bm{g}^{L}\cdot\bm{\sigma}_{n}))}{{\mathrm{Tr}}(O_{2}\rho_{L})}-\frac{{\mathrm{Tr}}(O_{1}\rho_{L})}{{\mathrm{Tr}}(O_{2}\rho_{L})}\frac{{\mathrm{Tr}}((\frac{{\mathrm{Tr}}(O_{2})}{2^{n}}\mathbbm{1}^{\otimes
n}+\bm{w}_{2}\cdot\bm{\sigma}_{n})(\frac{1}{2^{n}}\bm{g}^{L}\cdot\bm{\sigma}_{n}))}{{\mathrm{Tr}}(O_{2}\rho_{L})}$
$\displaystyle=\frac{\bm{w}_{1}\cdot\bm{g}^{L}}{{\mathrm{Tr}}(O_{2}\rho_{L})}-\frac{{\mathrm{Tr}}(O_{1}\rho_{L})}{{\mathrm{Tr}}(O_{2}\rho_{L})}\frac{\bm{w}_{2}\cdot\bm{g}^{L}}{{\mathrm{Tr}}(O_{2}\rho_{L})},$

Then, we have

$\displaystyle\lvert\partial_{\theta}C_{1}\rvert$
$\displaystyle\leq\left|\frac{\bm{w}_{1}\cdot\bm{g}^{L}}{{\mathrm{Tr}}(O_{2}\rho_{L})}\right|+\left|\frac{{\mathrm{Tr}}(O_{1}\rho_{L})}{{\mathrm{Tr}}(O_{2}\rho_{L})}\frac{\bm{w}_{2}\cdot\bm{g}^{L}}{{\mathrm{Tr}}(O_{2}\rho_{L})}\right|$
$\displaystyle\leq|\frac{\bm{w}_{1}\cdot\bm{g}^{L}}{k_{2}}|+\max\limits_{i\in
S}\lambda_{i}|\frac{1}{k_{2}}\frac{\bm{w}_{2}\cdot\bm{g}^{L}}{k_{2}}|$
$\displaystyle\leq\frac{1}{k_{2}}\norm{\bm{w}_{1}}_{2}\norm{\bm{g}^{L}}_{2}+\frac{1}{k_{2}^{2}}\max_{i\in
S}\lambda_{i}\norm{\bm{w}_{2}}_{2}\norm{\bm{g}^{L}}_{2}$

where $k_{2}=\absolutevalue{\frac{{\mathrm{Tr}}(O_{2})}{2^{n}}}$. With Lemma
2.1, we have

$\displaystyle\lvert\partial_{\theta}C_{1}\rvert\leq(\frac{1}{k_{2}}\norm{\bm{w}_{1}}_{2}+\frac{1}{k_{2}^{2}}\max_{i\in
S}\lambda_{i}\norm{\bm{w}_{2}}_{2})\sqrt{2^{n+1}-2}N_{lm}\norm{\bm{\eta}_{lm}}_{\infty}q^{L+1}$

Let $h=(\frac{\|\bm{w}_{1}\|_{2}}{k_{2}}+\max\limits_{i\in
S}\lambda_{i}\frac{\|\bm{w}_{2}\|_{2}}{k_{2}^{2}})N_{lm}\|\bm{\eta}_{lm}\|_{\infty}$.
Then we have $\partial_{\theta_{lm}}C_{1}\leq\sqrt{2^{n+1}-2}hq^{L+1}$.

∎

Proposition 3.3 (Dominating Term in the Observable).

$C_{1}=\frac{\frac{{\mathrm{Tr}}(O_{1})}{2^{n}}+\bm{a}^{L}\cdot\bm{w}_{1}}{\frac{{\mathrm{Tr}}(O_{2})}{2^{n}}+\bm{a}^{L}\cdot\bm{w}_{2}}$

where $\bm{a}^{L}$ is the Pauli coefficient of $\rho_{L}$. If $\bm{a}^{L}\to
0$ and $\frac{\partial\bm{a}^{L}}{\partial\theta}\to 0$ as $L\to\infty$, then

$\displaystyle\operatornamewithlimits{lim}_{L\to\infty}\partial_{\theta}C_{1}=0$

###### Proof.

${\mathrm{Tr}}(\rho_{L}O_{1})={\mathrm{Tr}}(\frac{1}{2^{n}}(\mathbbm{1}^{\otimes
n}+\bm{a}^{L}\cdot\bm{\sigma}_{n})(\frac{{\mathrm{Tr}}(O_{1})}{2^{n}}\mathbbm{1}^{\otimes
n}+\bm{w}_{1}\cdot\bm{\sigma}_{n}))=\frac{{\mathrm{Tr}}(O_{1})}{2^{n}}+\bm{a}^{L}\cdot\bm{w}_{1}$.
Likewise,
${\mathrm{Tr}}(\rho_{L}O_{2})=\frac{{\mathrm{Tr}}(O_{2})}{2^{n}}+\bm{a}^{L}\cdot\bm{w}_{2}$.
We have

$C_{1}=\frac{{\mathrm{Tr}}(\rho_{L}O_{1})}{{\mathrm{Tr}}(\rho_{L}O_{2})}=\frac{\frac{{\mathrm{Tr}}(O_{1})}{2^{n}}+\bm{a}^{L}\cdot\bm{w}_{1}}{\frac{{\mathrm{Tr}}(O_{2})}{2^{n}}+\bm{a}^{L}\cdot\bm{w}_{2}},$

where $\bm{a}^{L}\to 0$ and $\frac{\partial\bm{a}^{L}}{\partial\theta}\to 0$
as $L\to\infty$ by Lemma 2.2 and Lemma 2.1. Thus,

$\partial_{\theta}C_{1}=\frac{(\frac{\partial\bm{a}^{L}}{\partial\theta}\cdot\bm{w}_{1})(\frac{{\mathrm{Tr}}(O_{2})}{2^{n}}+\bm{a}^{L}\cdot\bm{w}_{2})-(\frac{\partial\bm{a}^{L}}{\partial\theta}\cdot\bm{w}_{2})(\frac{{\mathrm{Tr}}(O_{1})}{2^{n}}+\bm{a}^{L}\cdot\bm{w}_{1})}{(\frac{{\mathrm{Tr}}(O_{2})}{2^{n}}+\bm{a}^{L}\cdot\bm{w}_{2})^{2}}\longrightarrow
0$

as $L\to\infty$.

∎

##  Appendix B Gradient Vanishing Mitigation by C2

Observable $O_{1}$ has dominated term
$\frac{{\mathrm{Tr}}(O_{1})}{2^{n}}\mathbbm{1}^{\otimes n}$ which will mask
the effect of other Pauli terms, making gradient vanishing quickly. However,
by eliminating the dominated term, we can amplify the effect of other Pauli
terms and thus mitigate the gradient vanishing.

Proposition 3.4 (Gradient of $C_{2}$). The gradient of truncated cost function
with traceless observables is

$\displaystyle\partial_{\theta}C_{2}=\frac{\bm{g}^{L}\cdot\bm{w_{1}}}{\bm{a}^{L}\cdot\bm{w_{2}}}-\frac{{\mathrm{Tr}}(\rho_{L}O_{1}^{\prime})}{{\mathrm{Tr}}(\rho_{L}O_{2}^{\prime})}\frac{\bm{g}^{L}\cdot\bm{w_{2}}}{\bm{a}^{L}\cdot\bm{w_{2}}}$
(6)

where $\bm{g}^{L}$ is the Pauli coefficient of $\partial_{\theta}\rho_{L}$,
$\bm{a}^{L}$ is the Pauli coefficient of $\rho_{L}$.

###### Proof.

With the derivative rule, we can get

$\partial_{\theta}C_{2}=\frac{{\mathrm{Tr}}(O_{1}^{\prime}\partial_{\theta}\rho_{L})}{{\mathrm{Tr}}(\rho_{L}O_{2}^{\prime})}-\frac{{\mathrm{Tr}}(\rho_{L}O_{1}^{\prime})}{{\mathrm{Tr}}(\rho_{L}O_{2}^{\prime})}\frac{{\mathrm{Tr}}(O_{2}^{\prime}\partial_{\theta}\rho_{L})}{{\mathrm{Tr}}(\rho_{L}O_{2}^{\prime})}$

On the other hand,
${\mathrm{Tr}}(O_{1}^{\prime}\partial_{\theta}\rho_{L})={\mathrm{Tr}}((\bm{w}_{1}\cdot\bm{\sigma}_{n})\frac{1}{2^{n}}(\bm{g}^{L}\cdot\bm{\sigma}_{n}))=\bm{g}^{L}\cdot\bm{w}_{1}$.
Likewise,
${\mathrm{Tr}}(O_{2}^{\prime}\partial_{\theta}\rho_{L})=\bm{g}^{L}\cdot\bm{w}_{2}$.
And
${\mathrm{Tr}}(\rho_{L}O_{2}^{\prime})={\mathrm{Tr}}((\bm{w}_{2}\cdot\bm{\sigma}_{n})\frac{1}{2^{n}}(\mathbbm{1}^{\otimes
n}+\bm{a}^{L}\cdot\bm{\sigma}_{n}))=\bm{a}^{L}\cdot\bm{w}_{2}$. Substitute
these equities into the above derivative expression, we can get the desired
gradient expression. ∎

In the following theorem, we will show that the gradient of $C_{2}$ is much
larger than that of $C_{1}$.

Theorem 3.1 (Mitigating Gradient Vanishing). Assume $L_{0}$ is the minimal
integer s.t.
$q^{L_{0}}\sqrt{2^{n}-1}\norm{\bm{w}_{2}}_{2}(1+\epsilon)\leq\absolutevalue{\frac{{\mathrm{Tr}}(O_{2})}{2^{n}}}$,
then for $L>2L_{0}+1$, we have

$\displaystyle\absolutevalue{\partial_{\theta_{lm}}C_{2}}\geq\frac{s}{q^{L+1}}\absolutevalue{\partial_{\theta_{lm}}C_{1}}-1,$

where
$s=\min{\\{\frac{\epsilon^{2}k_{2}^{2}}{(1+\epsilon)^{2}\sqrt{2^{n+1}-2}N_{lm}\norm{\bm{\eta}_{lm}}_{\infty}\norm{\bm{w}_{1}k_{2}-\bm{w}_{2}k_{1})}_{2}},}(\frac{\absolutevalue{k_{2}}}{q^{L_{0}}\sqrt{2^{n}-1}\norm{\bm{w}_{2}}_{2}}-q^{L_{0}+1})^{2}\\}$,
$\epsilon$ is an arbitrarily small positive number,
$k_{1}=\frac{{\mathrm{Tr}}(O_{1})}{2^{n}}$,
$k_{2}=\frac{{\mathrm{Tr}}(O_{2})}{2^{n}}$, $\bm{\eta}_{lm}$ and $N_{lm}$ are
previously defined in Lemma 2.2.

###### Proof.

Let $\theta=\theta_{lm}$. From Proposition 3.4, we have:

$\displaystyle\partial_{\theta}C_{2}$
$\displaystyle=\frac{\bm{g}^{L}\cdot\bm{w}_{1}}{\bm{a}^{L}\cdot\bm{w}_{2}}-\frac{{\mathrm{Tr}}(\rho_{L}O_{1}^{\prime})}{{\mathrm{Tr}}(\rho_{L}O_{2}^{\prime})}\frac{\bm{g}^{L}\cdot\bm{w}_{2}}{\bm{a}^{L}\cdot\bm{w}_{2}}$
$\displaystyle=\frac{\bm{g}^{L}\cdot(\bm{w}_{1}(\bm{a}^{L}\cdot\bm{w}_{2})-\bm{w}_{2}(\bm{a}^{L}\cdot\bm{w}_{1}))}{(\bm{a}^{L}\cdot\bm{w}_{2})^{2}}$
$\displaystyle=\frac{\bm{g}^{L}\cdot(\bm{a}^{L}\times(\bm{w}_{1}\times\bm{w}_{2}))}{(\bm{a}^{L}\cdot\bm{w}_{2})^{2}}$

Let $k_{1}=\frac{{\mathrm{Tr}}(O_{1})}{2^{n}}$,
$k_{2}=\frac{{\mathrm{Tr}}(O_{2})}{2^{n}}$, then

$\displaystyle\partial_{\theta}C_{1}$
$\displaystyle=\frac{\bm{g}^{L}\cdot\bm{w}_{1}}{k_{2}+\bm{a}^{L}\cdot\bm{w}_{2}}-\frac{{\mathrm{Tr}}(\rho_{L}O_{1})}{{\mathrm{Tr}}(\rho_{L}O_{2})}\frac{\bm{g}^{L}\cdot\bm{w}_{2}}{k_{2}+\bm{a}^{L}\cdot\bm{w}_{2}}$
$\displaystyle=\frac{\bm{g}^{L}\cdot(\bm{w}_{1}(k_{2}+\bm{a}^{L}\cdot\bm{w}_{2})-\bm{w}_{2}(k_{1}+\bm{a}^{L}\cdot\bm{w}_{1}))}{(k_{2}+\bm{a}^{L}\cdot\bm{w}_{2})^{2}}$
$\displaystyle=\frac{\bm{g}^{L}\cdot(\bm{a}^{L}\times(\bm{w}_{1}\times\bm{w}_{2}))}{(k_{2}+\bm{a}^{L}\cdot\bm{w}_{2})^{2}}+\frac{\bm{g}^{L}\cdot(\bm{w}_{1}k_{2}-\bm{w}_{2}k_{1})}{(k_{2}+\bm{a}^{L}\cdot\bm{w}_{2})^{2}}$
$\displaystyle=\partial_{\theta}C_{2}\frac{(\bm{a}^{L}\cdot\bm{w}_{2})^{2}}{(k_{2}+\bm{a}^{L}\cdot\bm{w}_{2})^{2}}+\frac{\bm{g}^{L}\cdot(\bm{w}_{1}k_{2}-\bm{w}_{2}k_{1})}{(k_{2}+\bm{a}^{L}\cdot\bm{w}_{2})^{2}}$

Let
$h=\max\\{\frac{(\bm{a}^{L}\cdot\bm{w}_{2})^{2}}{(k_{2}+\bm{a}^{L}\cdot\bm{w}_{2})^{2}},\frac{\absolutevalue{\bm{g}^{L}\cdot(\bm{w}_{1}k_{2}-\bm{w}_{2}k_{1})}}{(k_{2}+\bm{a}^{L}\cdot\bm{w}_{2})^{2}}\\}$.
Then,

$\displaystyle\absolutevalue{\partial_{\theta}C_{1}}\leq\absolutevalue{\partial_{\theta}C_{2}}\frac{(\bm{a}^{L}\cdot\bm{w}_{2})^{2}}{(k_{2}+\bm{a}^{L}\cdot\bm{w}_{2})^{2}}+\frac{\absolutevalue{\bm{g}^{L}\cdot(\bm{w}_{1}k_{2}-\bm{w}_{2}k_{1})}}{(k_{2}+\bm{a}^{L}\cdot\bm{w}_{2})^{2}}\leq
h(\absolutevalue{\partial_{\theta}C_{2}}+1)$

By Lemma 2.2, we have
$\absolutevalue{\bm{a}^{L_{0}}\cdot\bm{w}_{2}}(1+\epsilon)\leq
q^{L_{0}}\sqrt{2^{n}-1}\norm{\bm{w}_{2}}_{2}(1+\epsilon)\leq\absolutevalue{k_{2}}$.
In the following, we consider two cases:
Case (1):
$(\bm{a}^{L}\cdot\bm{w}_{2})^{2}>\absolutevalue{\bm{g}^{L}\cdot(\bm{w}_{1}k_{2}-\bm{w}_{2}k_{1})}$.
Then

$\displaystyle\frac{1}{h}$
$\displaystyle=\frac{(k_{2}+\bm{a}^{L}\cdot\bm{w}_{2})^{2}}{(\bm{a}^{L}\cdot\bm{w}_{2})^{2}}=(1+\frac{k_{2}}{\bm{a}^{L}\cdot\bm{w}_{2}})^{2}$
$\displaystyle\geq(\absolutevalue{\frac{k_{2}}{\bm{a}^{L}\cdot\bm{w}_{2}}}-1)^{2}\geq(\frac{\absolutevalue{k_{2}}}{q^{L}\sqrt{2^{n}-1}\norm{\bm{w}_{2}}_{2}}-1)^{2}$
$\displaystyle\geq\frac{1}{q^{2L-2L_{0}}}(\frac{\absolutevalue{k_{2}}}{q^{L_{0}}\sqrt{2^{n}-1}\norm{\bm{w}_{2}}_{2}}-q^{L-L_{0}})^{2}$
$\displaystyle\geq\frac{1}{q^{L+1}}(\frac{\absolutevalue{k_{2}}}{q^{L_{0}}\sqrt{2^{n}-1}\norm{\bm{w}_{2}}_{2}}-q^{L_{0}+1})^{2}$

Case (2):
$(\bm{a}^{L}\cdot\bm{w}_{2})^{2}<\absolutevalue{\bm{g}^{L}\cdot(\bm{w}_{1}k_{2}-\bm{w}_{2}k_{1})}$.
Then,

$\displaystyle\frac{1}{h}$
$\displaystyle=\frac{(k_{2}+\bm{a}^{L}\cdot\bm{w}_{2})^{2}}{\absolutevalue{\bm{g}^{L}\cdot(\bm{w}_{1}k_{2}-\bm{w}_{2}k_{1})}}\geq\frac{(\absolutevalue{k_{2}}-\absolutevalue{\bm{a}^{L}\cdot\bm{w}_{2}})^{2}}{\absolutevalue{\bm{g}^{L}\cdot(\bm{w}_{1}k_{2}-\bm{w}_{2}k_{1})}}$
$\displaystyle\geq\frac{\epsilon^{2}k_{2}^{2}}{(1+\epsilon)^{2}\absolutevalue{\bm{g}^{L}\cdot(\bm{w}_{1}k_{2}-\bm{w}_{2}k_{1})}}$
$\displaystyle\geq\frac{1}{q^{L+1}}\frac{\epsilon^{2}k_{2}^{2}}{(1+\epsilon)^{2}\sqrt{2^{n+1}-2}N_{lm}\norm{\bm{\eta}_{lm}}_{\infty}\norm{\bm{w}_{1}k_{2}-\bm{w}_{2}k_{1})}_{2}}$

Let
$s=\min\\{(\frac{\absolutevalue{k_{2}}}{q^{L_{0}}\sqrt{2^{n}-1}\norm{\bm{w}_{2}}_{2}}-q^{L_{0}+1})^{2},\frac{\epsilon^{2}k_{2}^{2}}{(1+\epsilon)^{2}\sqrt{2^{n+1}-2}N_{lm}\norm{\bm{\eta}_{lm}}_{\infty}\norm{\bm{w}_{1}k_{2}-\bm{w}_{2}k_{1})}_{2}}\\}$,
then we have

$\displaystyle\absolutevalue{\partial_{\theta}C_{2}}+1$
$\displaystyle\geq\frac{1}{h}\absolutevalue{\partial_{\theta}C_{1}}\geq\frac{s}{q^{L+1}}\absolutevalue{\partial_{\theta}C_{1}}$

∎

##  Appendix C Surrogate Gradient for C1

However, the cost function $C_{2}$ has a major drawback that it is singular
around its minimum value point. We show its singularity in Proposition 3.5.

Proposition 3.5 (Singularity of $C_{2}$). If $\max\limits_{i\in
S}p_{i}=\sum\limits_{i\in S}p_{i}=\frac{{\mathrm{Tr}}(O_{2})}{2^{n}}$, the
cost function $C_{2}$ is singular and has the two following properties:

  * •

The global minimum of $C_{2}$ is negative infinity

  * •

The gradient of $C_{2}$ will become infinitely large

###### Proof.

Let
$g(\rho_{L},O_{1},O_{2})=C_{2}=\frac{{\mathrm{Tr}}(\rho_{L}O_{1})-\frac{{\mathrm{Tr}}(O_{1})}{2^{n}}}{{\mathrm{Tr}}(\rho_{L}O_{2})-\frac{{\mathrm{Tr}}(O_{2})}{2^{n}}}$,
$k_{1}=\frac{{\mathrm{Tr}}(O_{1})}{2^{n}}$,
$k_{2}=\frac{{\mathrm{Tr}}(O_{2})}{2^{n}}>0$.
Notice that $g(\rho,kO_{1},O_{2})$ is linear w.r.t $O_{1}$, i.e.
$g(\rho,kO_{1},O_{2})=kg(\rho,O_{1},O_{2})$, then we can rewrite
$g(\rho,O_{1},O_{2})$:

$g(\rho,O_{1},O_{2})=\frac{1}{k_{21}}\frac{{\mathrm{Tr}}(\rho_{L}k_{21}O_{1})-k_{2}}{{\mathrm{Tr}}(\rho_{L}O_{2})-k_{2}}$

where $k_{21}=\frac{k_{2}}{k_{1}}$.
To find the minimum of $g(\rho,O_{1},O_{2})$, we could adopt a two-dimensional
method:
(1) For a given constant $k_{2}<m$, $g_{c}(m,O_{1},O_{2})=\min
g(\rho,O_{1},O_{2})$ s.t. $\sum_{j\in S}p_{j}=m$.
(2) Find $\min_{m}g_{c}(m,O_{1},O_{2})$.
For task (1), the minimum of $g(\rho,O_{1},O_{2})=\frac{\sum_{i\in
S}p_{i}\lambda_{i}-k_{1}}{\sum_{i\in S}p_{i}-k_{2}}$ is achieved when
$p_{i}=m$ where $i=\text{arg}\min\limits_{j\in S}\lambda_{j}$. Thus, $g_{c}$
consists of values
$g_{c}(m,O_{1},O_{2})=\frac{1}{k_{21}}\frac{mk_{21}\lambda_{i}-k_{2}}{m-k_{2}}=\lambda_{i}+\frac{(\lambda_{i}-\frac{1}{k_{21}})k_{2}}{m-k_{2}}$.
Since $\lambda_{i}<\frac{1}{k_{21}}$, the minimum value of $g_{c}$ (task (2))
is negative infinity. And, the gradient of $g_{c}$ at point $m=k_{2}+0_{+}$ is
$+\infty$.

∎

We may not want to directly optimize $C_{2}$ due to its singularity but we
will show that we can use the gradient of $C_{2}$ to optimize $C_{1}$. In the
following theorem, we reveal the connection between the minimum value points
of $C_{1}$ and $C_{2}$. That is, each minimum values point of $C_{2}$ is also
a minimum value point of $C_{1}$.

Theorem 3.2 (Optimizing $C_{1}$ with gradient from $C_{2}$). Assume the
minimum value of $C_{1}$ be the $C_{1}^{*}$. If there is an iterative
algorithm $\mathcal{P}$ that optimize $C_{2}$ with a sequence of parameters
$\\{\bm{\theta}_{1},\bm{\theta}_{2},\cdots\\}$, then $\forall\epsilon>0$,
$\exists n_{0}$, s.t. $\forall n>n_{0}$,
$|C_{1}(\bm{\theta}_{n})-C_{1}^{*}|<\epsilon$ where $\bm{\theta}_{n}$ is the
parameter at the $n$-th iteration of $\mathcal{P}$.

###### Proof.

Assume $\bm{\theta}^{*}_{1}$ is the minimum point found by $\mathcal{P}$ with
initial condition $\sum_{i\in S}p_{i}>\frac{{\mathrm{Tr}}(O_{2})}{2^{n}}$.
Then, as indicated in the proof of the Proposition 3.5, we have
$p_{i}(\bm{\theta}^{*}_{1})=\sum_{j\in S}p_{j}$ and
$p_{j}(\bm{\theta}^{*}_{1})=0$ if $j\in S$ and $j\neq i$, where
$i=\text{arg}\min\limits_{j\in S}\lambda_{j}$. Thus,
$C_{1}(\bm{\theta}^{*}_{1})=C_{1}^{*}=\min\limits_{j\in S}\lambda_{j}$.

Since $C_{1}$ is continuous, thus, $\forall\epsilon>0$, $\exists\delta>0$,
s.t.
$|C_{1}(\bm{\theta}_{n})-C_{1}(\bm{\theta}^{*}_{1})|=|C_{1}(\bm{\theta}_{n})-C_{1}^{*}|<\epsilon$
as long as $\|\bm{\theta}_{n}-\bm{\theta}^{*}_{1}\|<\delta$.
On the other hand, $C_{2}$ is optimized by $\mathcal{P}$ iteratively, thus
$\forall\delta>0$, with the algorithm $\mathcal{P}$, exists $n_{0}$, s.t.
$\forall n>n_{0}$, $\|\bm{\theta}_{n}-\bm{\theta}^{*}_{1}\|<\delta$. This
completes the proof.
∎

Another benefit of optimizing $C_{1}$ rather than $C_{2}$ is that, the
optimization process may terminated earlier cost function $C_{1}$ because
$C_{1}$ has a large minimum value point space as revealed by Proposition 3.6.

Propositon 3.6 (Solution space of $C_{1}$). The solution space of problem
$\min\limits_{\ket{\psi}}C_{1}$ is of dimension $2^{n}-\dim S+1$.

###### Proof.

We denote the minimum eigenvalue in subspace $S$ by $\lambda_{\min}^{S}$. Then

$\displaystyle C_{1}=\frac{\sum_{i\in S}p_{i}\lambda_{i}}{\sum_{i\in
S}p_{i}}\geq\lambda_{\min}^{S}$ (7)

Let $i=\text{arg}\min\limits_{j\in S}\lambda_{j}$.The minimum value of $C_{1}$
is achieved only when $p_{j}=0$, $\forall j\in S,j\neq i$.
Thus, any solution of the form
$\sum_{j\in\bar{S}}a_{j}|j\rangle+p_{i}|i\rangle$ is the minimum point of
$C_{1}$, as long as $p_{i}>0$.
Thus, the solution space of problem $\min C_{1}$ is of dimension $2^{n}-\dim
S+1$.
∎


# Exploring Demonstration Ensembling for In-context Learning

Muhammad Khalifa , Lajanugen Logeswaran†, Moontae Lee†‡,
Honglak Lee∗†, Lu Wang∗
University of Michigan∗, LG AI Research†, University of Illinois at Chicago‡
Correspondence to<EMAIL_ADDRESS>
###### Abstract

In-context learning (ICL) operates by showing language models (LMs) examples
of input-output pairs for a given task, i.e., demonstrations. The standard
approach for ICL is to prompt the LM with concatenated demonstrations followed
by the test input. This approach suffers from some issues. First,
concatenation offers almost no control over the contribution of each demo to
the model prediction. This can be sub-optimal when some demonstrations are
irrelevant to the test example. Second, due to the input length limit of some
transformer models, it might be infeasible to fit many examples into the
context, especially when dealing with long-input tasks. In this work, we
explore Demonstration Ensembling (DENSE) as an alternative to simple
concatenation. DENSE predicts outputs using subsets (i.e., buckets) of the
demonstrations and then combines the output probabilities resulting from each
subset to produce the final prediction. We study different ensembling methods
using GPT-j (Wang & Komatsuzaki, 2021) and experiment on 12 language tasks.
Our experiments show weighted max ensembling to outperform vanilla
concatenation by as large as 2.4 average points.111Code available at
https://github.com/mukhal/icl-ensembling.

##  1 Introduction

Large-scale language model (LM) pre-training on large corpora is currently
dominating the NLP scene. One impressive aspect of such large language models
(LLMs) is their capability to do in-context learning (Brown et al., 2020) by
conditioning the model on a few examples (i.e., demonstrations) of the desired
task and then asking the LM to predict the label for a given input.

The standard approach for feeding in-context demonstrations (demos, for short)
to the LM is by concatenating the task examples (Brown et al., 2020; Min et
al., 2022c; Lu et al., 2022). While simple, concatenation suffers from a few
drawbacks. First, it provides no control over each demo’s contribution to the
model’s output, which is left to the attention weights to decide. Second, the
concatenation of demos can easily use up the context window of transformer-
based models, especially when we have access to many demonstrations or when
dealing with lengthy inputs. Lastly, it has been shown that LLMs are sensitive
to the ordering of the demonstrations Zhao et al. (2021); Lu et al. (2022),
and a long chain of concatenated demos can indeed exacerbate this problem.

In this work, we explore an alternative to the concatenation approach, which
is to prompt the model with demonstrations in an ensembling approach. In
particular, we partition the examples into non-empty subsets or buckets and
then combine the predictions obtained from each bucket to obtain the final
prediction. We investigate three different ensembling methods to combine the
predictions from different buckets including a clustering-based approach to
partition the examples. Experiments on 7 different language tasks show that
ensembling can outperform the standard concatenation approach.

##  2 Related Work

This work is related to work that aims to improve few-shot learning with LLMs
(Min et al., 2022b; Rubin et al., 2022; Lu et al., 2022). For instance, Perez
et al. (2021) try to find optimal prompts using techniques such as cross-
validation and minimum description length. Min et al. (2022a) applied
demonstration ensembling for text classification in a limited setting. This
paper, on the other hand, explores the more generalized ensembling setting
with different bucket sizes and different types of tasks. Wang et al. (2022)
explore rationale-augmented ensembles, where different in-context
demonstrations are augmented with LM-generated rationales. Different from our
work, the ensembling is done over the rationales in the examples, while we
ensemble the examples themselves. Qin & Eisner (2021) trained mixtures of soft
prompts for knowledge extraction from language models. Our prior work (Khalifa
et al., 2022) also explored demonstration ensembling to in-context learn to
rerank document paths for multi-hop question answering.

##  3 Demonstration Ensembling

Figure 1: In-context learning with six demonstrations. Left: The standard
concat-based approach for feeding the examples (Brown et al., 2020). Right:
Ensembling with three buckets of size two each. For a given label $y$, the
probability $\tilde{p}_{i}(y|x)$ is computed using the $i$-th bucket. All
probabilities are ensembled to give the final probability $p(y|x)$.

We assume a list of $n$ demonstrations
$\mathcal{D}=\langle(x_{1},y_{1}),..,(x_{n},y_{n})\rangle$, where $x_{i}$ and
$y_{i}$ are the demonstration input and ground-truth output or label,
respectively. We now formalize our approach for demonstration ensembling.

###  3.1 Bucket Allocation

DENSE allocates the $n$ demos in $\mathcal{D}$ to $b$ non-empty buckets
$\\{\mathcal{B}_{0},\mathcal{B}_{1},...,\mathcal{B}_{b-1}\\}$. More precisely,
if each bucket has $\gamma$ demos, then $\mathcal{B}_{i}$ is assigned the
demos $\mathcal{D}_{\gamma i:\gamma(i+1)-1}$. We predict a set of
probabilities of a label $y$ by separately conditioning the LM on the
different buckets along with the test input $x$. Formally, for bucket
$\mathcal{B}_{i}$, we predict $\tilde{p}_{i}(y|x)$ as:

$\begin{split}\tilde{p}_{i}(y|x)&=P_{LM}(y|\mathcal{B}_{i},x)\\\ \end{split}$

The aggregate probability of the label $y$ is proportional to the output of an
ensembling operator $\Phi$ that combines different bucket probabilities:

$P(y|x)\propto\Phi(y|\tilde{p}_{0}(y|x),\ldots,\tilde{p}_{B-1}(y|x),x)$ (1)

Where $\Phi$ is a function that takes in the probabilities
$\tilde{p}_{0}(y|x),\ldots,\tilde{p}_{B-1}(y|x)$ and the test example $x$, and
computes a (possibly unnormalized) probability of the output label $y$. For
brevity, we will just use $\Phi(y|x)$ from now on.

###  3.2 Ensembling Method

We assume each bucket $\mathcal{B}_{i}$ has a normalized importance weight
$w_{i}$ assigned to it where $\sum_{i=0}^{b}w_{i}=1$. One form of $\Phi$ is
the product operator in which $P(y|x)$ corresponds to a product-of-experts
(Hinton, 2002):

$\Phi^{\operatorname{PoE}}(y|x)=\prod_{i=0}^{b}\tilde{p}_{i}(y|x)^{w_{i}}$ (2)

In addition, we can explore a mixture-of-experts formulation:

$\Phi^{\operatorname{MoE}}(y|x)=\sum_{i=0}^{b}w_{i}\tilde{p}_{i}(y|x)$ (3)

We also explore max ensembling, which uses the most confident prediction
probability across different buckets:

$\Phi^{\operatorname{max}}(y|x)=\max_{j}{w_{j}\tilde{p}_{j}(y|x)}$ (4)

###  3.3 Bucket Weighting

Inspired by recent work (Gao et al., 2021; Liu et al., 2022) that has shown
that demonstrations that are more similar to the input perform better than
distant ones, we weigh each bucket using the average of the similarity of its
examples with the input $x$:

$w_{i}=\frac{1}{|\mathcal{B}_{i}|}\sum_{(x_{j},y_{j})\in\mathcal{B}_{i}}\text{cos}(x_{j}^{e},x^{e})$
(5)

where cos is the cosine similarity and $x^{e}$ is the embedding of the $x$.

###  3.4 Clustering Demonstrations

While the bucket construction approach explained in Section 3.1 constructs
buckets arbitrarily based on the order of the demos in $\mathcal{D}$, one
heuristic is to use similarity information between demos to construct buckets.
We experiment with k-means clustering (Hartigan & Wong, 1979) to construct
buckets. More precisely, we apply k-means over vector representations of the
demonstrations to obtain $b$ clusters and then use each cluster as a
bucket.222Note that in this case, not all buckets will have the same number of
demos. Each bucket can operate as a semantically coherent expert. We refer to
this approach as similar-together bucket allocation.

Figure 2: 6-shot (Left) and 10-shot (Right) performance of different
ensembling methods and concatenation. Metrics are averaged over three seeds of
demos, 12 datasets, and different numbers of buckets. (Un)weighted indicates
whether we use similarity with the input examples to weigh the contribution of
each ensemble. Similar-together bins and Diverse buckets are achieved through
k-means clustering as explained in 3.4

As opposed to maximizing the similarity between the demos within a given
bucket, instead, we can maximize dissimilarity to achieve diverse buckets. To
do that, we use K-means to cluster demos into $\lfloor n/b\rfloor$ clusters,
each with $b$ demos.333We assume $n$ is always divisible by $b$ for
simplicity. Then, we construct $b$ buckets by picking a unique demo from each
cluster.444Here, we use a constrained version of k-means (Bradley et al.,
2000) to make sure we get exactly $b$ demos in each k-means cluster. Having
diverse buckets might result in a prediction that is less biased towards a
certain category of demonstrations. We refer to this approach as diverse
bucket allocation.

Besides yielding better bucket allocation, clustering makes bucket assignment
less sensitive with respect to the demonstration order in $\mathcal{D}$. As a
result, it can greatly reduce the sensitivity to the order of the demos
studied in previous work (Zhao et al., 2021; Lu et al., 2022).

##  4 Experiments and Results

###  4.1 Experimental Setup

#### Data.

We experiment with 12 datasets in total. Details on the datasets, metrics
used, and the number of evaluation examples can be found in Appendix A.

#### Baselines.

We compare ensembling to two concatenation-based settings. Concat is the
standard approach for ICL, which concatenates the demonstrations in an
arbitrary order, and Concat-sort which sorts the demos based on similarity
with the input (i.e., more similar demos come later). Concat-sort uses
similarity with the input, allowing for a fair comparison with the weighted
ensembling methods.

#### Model.

For all the experiments, we use GPT-j (6B) (Wang & Komatsuzaki, 2021). To
compute embeddings of examples for similarity calculations, we use a fine-
tuned 6-layer MiniLM (Wang et al., 2020).555https://huggingface.co/sentence-
transformers/all-MiniLM-L6-v2. Our experimental setup is detailed in Appendix
B.

#### Number of demonstrations and bucket count.

We experiment with number of examples $n=6,10$. For $n=6$, we use ensembling
with bucket counts $b=2,3,6$, and for $n=10$, we set $b=2,5,10$. We note that
the concat method in Brown et al. (2020) is a special case of ensembling with
$b=1$.

Figure 3: 6-shot (Left) and 10-shot (Right) performance with different bucket
count $b$. We show performance with weighted MoE, PoE, and Max ensembling.
Performance is averaged over 7 tasks and over 3 different seeds of demos.

###  4.2 Comparing Ensembling Methods

Figure 2 compares the performance of the concat approach against various
ensembling methods and in the 6- and 10-shot cases. We observe that unweighted
(i.e. $w_{i}=\frac{1}{b}$ for all $i$), PoE, MoE, and max ensembling
outperform the concat baseline. Precisely, max ensembling outperforms concat
by 0.8 average points in the 6-shot setting while MoE outperforms it by 0.6 in
the 10-shot setting. However, unweighted ensembling underperforms the concat-
sort baseline.

Furthermore, weighing the buckets based on the similarity with inputs boosts
the ensembling performance in all cases. In the 6-shot case, weighted max
ensembling outperforms concat and concat-sort by 2.4 and 1.2, respectively. In
the 10-shot setting, weighted max ensembling outperforms concat and concat-
sort by 1.9 and 0.75 respectively.

Lastly, we study the effect of bucket allocation based on clustering the
demonstrations, where similar-together clustering gives a consistent boost to
weighted ensembling methods in the 6-shot case. However, we do not have
conclusive evidence as to which clustering strategy is best. We find the
performance of the clustering strategy to vary depending on the task and the
total number of demonstrations. For instance, diverse always outperforms
similar-together allocation in the 10-shot case, which is not the case for the
6-shot setting. This is likely because having more demos allows for more
diverse buckets. We leave it to future work to explore different methods of
bucket allocation. Figure 4 in Appendix C shows per-task improvement obtained
by ensembling.

###  4.3 Buckets Count

Here we study what role the bucket count $b$ plays in the performance of
ensembling. Figure 3 shows the effect of changing the bucket count on the
performance. Using a small $b$ seems to perform worse across the board.
Interestingly, the performance improves as $b$ increases for all ensembling
methods in the 6-shot setting.

##  5 Conclusion

In this work, we explore an alternative to the popular in-context learning
paradigm where examples are concatenated and provided to a language model. We
show through experiments on 12 language tasks that ensembling, where examples
are partitioned into buckets and a final prediction is made by combining
predictions from each bucket, yields better performance over concatenation. In
particular, we find that max ensembling performs best compared to product-of-
experts and mixture-of-experts. In addition, we analyze the effect of varying
different aspects of ensembling such as the number of buckets and bucket
construction strategies.

## References

  * Barbieri et al. (2020) Francesco Barbieri, José Camacho-Collados, Luis Espinosa Anke, and Leonardo Neves.  Tweeteval: Unified benchmark and comparative evaluation for tweet classification.  In Trevor Cohn, Yulan He, and Yang Liu (eds.), _Findings of the Association for Computational Linguistics: EMNLP 2020, Online Event, 16-20 November 2020_ , volume EMNLP 2020 of _Findings of ACL_ , pp. 1644–1650. Association for Computational Linguistics, 2020.  doi: 10.18653/v1/2020.findings-emnlp.148.  URL https://doi.org/10.18653/v1/2020.findings-emnlp.148.
  * Bradley et al. (2000) Paul S Bradley, Kristin P Bennett, and Ayhan Demiriz.  Constrained k-means clustering.  _Microsoft Research, Redmond_ , 20(0):0, 2000\.
  * Brown et al. (2020) Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al.  Language models are few-shot learners.  _Advances in neural information processing systems_ , 33:1877–1901, 2020.
  * Chen et al. (2019) Michael Chen, Mike D’Arcy, Alisa Liu, Jared Fernandez, and Doug Downey.  CODAH: An adversarially-authored question answering dataset for common sense.  In _Proceedings of the 3rd Workshop on Evaluating Vector Space Representations for NLP_ , pp. 63–69, Minneapolis, USA, June 2019. Association for Computational Linguistics.  doi: 10.18653/v1/W19-2008.  URL https://aclanthology.org/W19-2008.
  * Clark et al. (2018) Peter Clark, Isaac Cowhey, Oren Etzioni, Tushar Khot, Ashish Sabharwal, Carissa Schoenick, and Oyvind Tafjord.  Think you have solved question answering? try arc, the ai2 reasoning challenge.  _arXiv preprint arXiv:1803.05457_ , 2018.
  * De Gibert et al. (2018) Ona De Gibert, Naiara Perez, Aitor García-Pablos, and Montse Cuadros.  Hate speech dataset from a white supremacy forum.  _arXiv preprint arXiv:1809.04444_ , 2018.
  * Diggelmann et al. (2020) Thomas Diggelmann, Jordan Boyd-Graber, Jannis Bulian, Massimiliano Ciaramita, and Markus Leippold.  Climate-fever: A dataset for verification of real-world climate claims.  _arXiv preprint arXiv:2012.00614_ , 2020.
  * Dolan & Brockett (2005) Bill Dolan and Chris Brockett.  Automatically constructing a corpus of sentential paraphrases.  In _Third International Workshop on Paraphrasing (IWP2005)_ , 2005\.
  * Gao et al. (2021) Tianyu Gao, Adam Fisch, and Danqi Chen.  Making pre-trained language models better few-shot learners.  In _Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference on Natural Language Processing (Volume 1: Long Papers)_ , pp. 3816–3830, Online, August 2021. Association for Computational Linguistics.  doi: 10.18653/v1/2021.acl-long.295.  URL https://aclanthology.org/2021.acl-long.295.
  * Hartigan & Wong (1979) John A Hartigan and Manchek A Wong.  Algorithm as 136: A k-means clustering algorithm.  _Journal of the royal statistical society. series c (applied statistics)_ , 28(1):100–108, 1979.
  * Hinton (2002) Geoffrey E Hinton.  Training products of experts by minimizing contrastive divergence.  _Neural computation_ , 14(8):1771–1800, 2002\.
  * Khalifa et al. (2022) Muhammad Khalifa, Lajanugen Logeswaran, Moontae Lee, Honglak Lee, and Lu Wang.  Lepus: Prompt-based unsupervised multi-hop reranking for open-domain qa.  _arXiv preprint arXiv:2205.12650_ , 2022.
  * Levesque et al. (2012) Hector Levesque, Ernest Davis, and Leora Morgenstern.  The winograd schema challenge.  In _Thirteenth international conference on the principles of knowledge representation and reasoning_ , 2012.
  * Liu et al. (2022) Jiachang Liu, Dinghan Shen, Yizhe Zhang, Bill Dolan, Lawrence Carin, and Weizhu Chen.  What makes good in-context examples for gpt-3?  In Eneko Agirre, Marianna Apidianaki, and Ivan Vulic (eds.), _Proceedings of Deep Learning Inside Out: The 3rd Workshop on Knowledge Extraction and Integration for Deep Learning Architectures, DeeLIO@ACL 2022, Dublin, Ireland and Online, May 27, 2022_ , pp. 100–114. Association for Computational Linguistics, 2022.  doi: 10.18653/v1/2022.deelio-1.10.  URL https://doi.org/10.18653/v1/2022.deelio-1.10.
  * Lu et al. (2022) Yao Lu, Max Bartolo, Alastair Moore, Sebastian Riedel, and Pontus Stenetorp.  Fantastically ordered prompts and where to find them: Overcoming few-shot prompt order sensitivity.  In Smaranda Muresan, Preslav Nakov, and Aline Villavicencio (eds.), _Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), ACL 2022, Dublin, Ireland, May 22-27, 2022_ , pp. 8086–8098. Association for Computational Linguistics, 2022.  URL https://aclanthology.org/2022.acl-long.556.
  * Marelli et al. (2014) Marco Marelli, Stefano Menini, Marco Baroni, Luisa Bentivogli, Raffaella Bernardi, Roberto Zamparelli, et al.  A sick cure for the evaluation of compositional distributional semantic models.  In _Lrec_ , pp. 216–223. Reykjavik, 2014.
  * McCreery et al. (2020) Clara H McCreery, Namit Katariya, Anitha Kannan, Manish Chablani, and Xavier Amatriain.  Effective transfer learning for identifying similar questions: matching user questions to covid-19 faqs.  In _Proceedings of the 26th ACM SIGKDD international conference on knowledge discovery & data mining_, pp. 3458–3465, 2020.
  * Mihaylov et al. (2018) Todor Mihaylov, Peter Clark, Tushar Khot, and Ashish Sabharwal.  Can a suit of armor conduct electricity? A new dataset for open book question answering.  In Ellen Riloff, David Chiang, Julia Hockenmaier, and Jun’ichi Tsujii (eds.), _Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing, Brussels, Belgium, October 31 - November 4, 2018_ , pp. 2381–2391. Association for Computational Linguistics, 2018.  doi: 10.18653/v1/d18-1260.  URL https://doi.org/10.18653/v1/d18-1260.
  * Min et al. (2022a) Sewon Min, Mike Lewis, Hannaneh Hajishirzi, and Luke Zettlemoyer.  Noisy channel language model prompting for few-shot text classification.  In Smaranda Muresan, Preslav Nakov, and Aline Villavicencio (eds.), _Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), ACL 2022, Dublin, Ireland, May 22-27, 2022_ , pp. 5316–5330. Association for Computational Linguistics, 2022a.  URL https://aclanthology.org/2022.acl-long.365.
  * Min et al. (2022b) Sewon Min, Mike Lewis, Luke Zettlemoyer, and Hannaneh Hajishirzi.  Metaicl: Learning to learn in context.  In Marine Carpuat, Marie-Catherine de Marneffe, and Iván Vladimir Meza Ruíz (eds.), _Proceedings of the 2022 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, NAACL 2022, Seattle, WA, United States, July 10-15, 2022_ , pp. 2791–2809. Association for Computational Linguistics, 2022b.  doi: 10.18653/v1/2022.naacl-main.201.  URL https://doi.org/10.18653/v1/2022.naacl-main.201.
  * Min et al. (2022c) Sewon Min, Xinxi Lyu, Ari Holtzman, Mikel Artetxe, Mike Lewis, Hannaneh Hajishirzi, and Luke Zettlemoyer.  Rethinking the role of demonstrations: What makes in-context learning work?  In _EMNLP_ , 2022c.
  * Perez et al. (2021) Ethan Perez, Douwe Kiela, and Kyunghyun Cho.  True few-shot learning with language models.  _Advances in neural information processing systems_ , 34:11054–11070, 2021.
  * Qin & Eisner (2021) Guanghui Qin and Jason Eisner.  Learning how to ask: Querying lms with mixtures of soft prompts.  In Kristina Toutanova, Anna Rumshisky, Luke Zettlemoyer, Dilek Hakkani-Tür, Iz Beltagy, Steven Bethard, Ryan Cotterell, Tanmoy Chakraborty, and Yichao Zhou (eds.), _Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, NAACL-HLT 2021, Online, June 6-11, 2021_ , pp. 5203–5212. Association for Computational Linguistics, 2021\.  doi: 10.18653/v1/2021.naacl-main.410.  URL https://doi.org/10.18653/v1/2021.naacl-main.410.
  * Rubin et al. (2022) Ohad Rubin, Jonathan Herzig, and Jonathan Berant.  Learning to retrieve prompts for in-context learning.  In Marine Carpuat, Marie-Catherine de Marneffe, and Iván Vladimir Meza Ruíz (eds.), _Proceedings of the 2022 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, NAACL 2022, Seattle, WA, United States, July 10-15, 2022_ , pp. 2655–2671. Association for Computational Linguistics, 2022\.  doi: 10.18653/v1/2022.naacl-main.191.  URL https://doi.org/10.18653/v1/2022.naacl-main.191.
  * Socher et al. (2013) Richard Socher, Alex Perelygin, Jean Wu, Jason Chuang, Christopher D Manning, Andrew Y Ng, and Christopher Potts.  Recursive deep models for semantic compositionality over a sentiment treebank.  In _Proceedings of the 2013 conference on empirical methods in natural language processing_ , pp. 1631–1642, 2013.
  * Tafjord et al. (2019) Oyvind Tafjord, Peter Clark, Matt Gardner, Wen-tau Yih, and Ashish Sabharwal.  Quarel: A dataset and models for answering questions about qualitative relationships.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 33, pp. 7063–7071, 2019.
  * Wang & Komatsuzaki (2021) Ben Wang and Aran Komatsuzaki.  Gpt-j-6b: A 6 billion parameter autoregressive language model, 2021.
  * Wang et al. (2020) Wenhui Wang, Furu Wei, Li Dong, Hangbo Bao, Nan Yang, and Ming Zhou.  Minilm: Deep self-attention distillation for task-agnostic compression of pre-trained transformers.  _Advances in Neural Information Processing Systems_ , 33:5776–5788, 2020.
  * Wang et al. (2022) Xuezhi Wang, Jason Wei, Dale Schuurmans, Quoc Le, Ed Chi, and Denny Zhou.  Rationale-augmented ensembles in language models.  _arXiv preprint arXiv:2207.00747_ , 2022.
  * Zhao et al. (2021) Zihao Zhao, Eric Wallace, Shi Feng, Dan Klein, and Sameer Singh.  Calibrate before use: Improving few-shot performance of language models.  In Marina Meila and Tong Zhang (eds.), _Proceedings of the 38th International Conference on Machine Learning, ICML 2021, 18-24 July 2021, Virtual Event_ , volume 139 of _Proceedings of Machine Learning Research_ , pp. 12697–12706. PMLR, 2021.  URL http://proceedings.mlr.press/v139/zhao21c.html.

##  Appendix A Datasets

Dataset | Task | Metric | # Eval
---|---|---|---
Glue-SST2 (Socher et al., 2013) | sentiment analysis | macro F1 | 872
Medical questions pairs (McCreery et al., 2020) | paraphrase detection | macro F1 | 610
Glue-MRPC Levesque et al. (2012) | paraphrase detection | macro F1 | 408
Climate Fever (Diggelmann et al., 2020) | fact verification | macro F1 | 307
SICK (Marelli et al., 2014) | NLI | macro F1 | 495
Glue-WNLI Dolan & Brockett (2005) | NLI | macro F1 | 71
Hate speech18 De Gibert et al. (2018) | hate speech detection | macro F1 | 2141
TweetEval-stance (feminism) (Barbieri et al., 2020) | stance detection | macro F1 | 67
OpenbookQA Mihaylov et al. (2018) | question answering | accuracy | 500
ARC Clark et al. (2018) | question answering | accuracy | 299
QUAREL Tafjord et al. (2019) | question answering | accuracy | 278
CODAH Chen et al. (2019) | sentence completion | accuracy | 556
Table 1: Datasets, tasks, metrics, and the number of evaluation examples for
each dataset.

##  Appendix B Experimental Setup

We run few-shot inference using fp16 half-precision. All experiments are run
on a workstation with 4 Nvidia A100 GPUs with a batch size of 16. We use the
GPT-j checkpoint provided by
Huggingface.666https://huggingface.co/EleutherAI/gpt-j-6B/tree/float16 For
clustering, we use the K-means implementation provided by
sklearn.777https://scikit-
learn.org/stable/modules/generated/sklearn.cluster.KMeans.html For constrained
K-means, we use this implementation.888https://github.com/joshlk/k-means-
constrained

##  Appendix C Detailed Results

Figure 4 shows relative improvement obtained by different weighted ensembling
approaches over the concatenation approach.

Figure 4: Relative performance improvement resulting from different ensembling
methods shown per task. The improvement is aggregated over a different number
of examples $6,10$, different numbers of buckets, and different seeds.