#  An entanglement-based protocol for simultaneous reciprocal information
exchange between 2 players

Theodore Andronikos1 and Alla Sirokofskich2

1 Department of Informatics, Ionian University,
7 Tsirigoti Square, 49100 Corfu, Greece;
<EMAIL_ADDRESS>
2 Department of History and Philosophy of Sciences,
National and Kapodistrian University of Athens,
Athens 15771, Greece;
<EMAIL_ADDRESS>
###### Abstract

Let us consider a situation where two information brokers, whose currency is,
of course, information, need to reciprocally exchange information. The two
brokers, being somewhat distrustful, would like a third, mutually trusted,
entity to be involved in the exchange process so as to guarantee the
successful completion of the transaction, and also verify that it indeed took
place. Can this be done in such a way that both brokers receive their
information simultaneously and securely, and without the trusted intermediary
ending up knowing the exchanged information? This work presents and rigorously
analyzes a new quantum entanglement-based protocol that provides a solution to
the above problem. The proposed protocol is aptly named entanglement-based
reciprocal simultaneous information exchange protocol. Its security is
ultimately based on the assumption of the existence of a third trusted party.
Although, the reciprocal information flow is between our two information
brokers, the third entity plays a crucial role in mediating this process,
being a guarantor and a verifier. The phenomenon of quantum entanglement is
the cornerstone of this protocol, as it makes possible its implementation even
when all entities are spatially separated, and ensuring that, upon completion,
the trusted third party remains oblivious of the actual information that was
exchanged.

Keywords:: Quantum cryptography, quantum entanglement, Bell states, GHZ
states, secure information exchange.

##  1 Introduction

Living in an era where privacy and security are fundamental and inherent
rights in everyone’s professional and social life, has undoubtedly motivated
the enormous research effort to design and implement robust security
algorithms, techniques, and protocols. It would seem that there are at least
two major research directions aspiring to achieve this goal.

The first, known by the umbrella term post-quantum cryptography [1, 2, 3, 4],
could be perceived as the natural evolution of our present situation, where
security relies on carefully chosen computationally hard problems. The
efficiency and reliability of this approach has been practically confirmed
thus far, and offers the additional advantage that implementation-wise it is
compatible with the existing infrastructure.

There is however reason for concern, as the computational difficult has not
actually been mathematically proven, but is rather empirically accepted
because of the absence of efficient algorithms. Probably, even more worrying
is the fact that when one steps out of the confines of conventional, or
classical, computation, discovers that quantum algorithms have been developed
by Peter Shor and Lov Grover [5, 6], that may compromise the security afforded
by conventional means. The second direction, quantum cryptography, advocates
the embrace of the unconventional, in particular the quantum, realm and relies
on the laws of nature, at least as we understand them today, to achieve
uncompromising security.

On this front, there are many reasons to be optimistic lately, with signs of
accelerated progress. The impressive breakthrough of the $100$ qubit barrier
by IBM’s $127$ qubit processor Eagle [7] has been, almost immediately,
followed by the more recent $433$ qubit quantum processor named Osprey [8].
Therefore, it is now more important than ever before to address the problem of
secure communication [9], and quantum cryptography seems the most promising
approach for the job. Clever use of the fundamental properties of quantum
mechanics offers undisputed advantages that not only they guarantee the
adequate protection of critical information, but also ensure the efficient and
secure transmission of information, e.g., via the use of entanglement, as
first suggested by Ekert [10]. In his 1991 influential paper, Ekert proved
that key distribution is possible with the use of EPR pairs. Immediately
afterwards, research in this field produced a plethora of entanglement-based
protocols for quantum key distribution [11, 12, 13, 14, 15, 16, 17]. Quantum
cryptographic protocols have the potential to enhance the security not only of
established applications, but also of new and emerging technologies, such as
cloud computing, cloud storage [18, 19] or blockchain [20]. Considerable
progress has been recorded in the development of algorithm and protocols [21,
22, 23, 24, 25, 26], accompanied by experimental demonstrations in real-life
situations [27, 28, 29, 30].

This work studies the following problem within the broader context of quantum
information and cryptography. We envision a setting where information is the
real currency, and in such a setting, two information brokers want to
reciprocally exchange information. In their profession, trust can not be taken
for granted. Hence, they would like a third party that is mutually trusted by
both, to mediate the whole process and guaranteed the honest implementation of
the agreed upon protocol. This third party must have a pivotal role, in the
sense that without its participation it will be impossible to complete the
exchange. Another important benefit of the presence of the trusted
intermediary is that it can serve as a referee to verify that this transaction
took place, if such a need arises in the future, e.g., if one or both of the
information brokers ever need such a proof. This scheme should work even when
all parties involved are spatially separated, and, most importantly, designed
so carefully that the trusted intermediary does not end up in possession of
the exchanged information. In the rest of this paper we present a quantum
protocol that provides a solution to this problem, satisfying all the
previously set requirements, in the form of a game.

It is almost some kind of tradition to use games in quantum cryptography; from
the very beginning [31] to the more recent [16, 17]. The pedagogical aspect of
games often makes expositions of difficult and technical concepts much more
accessible, even entertaining. Quantum games, ever since their initial
inception in 1999 [32, 33], have offered motivation and additional insight
because quite often quantum strategies seem to achieve better results than
classical ones [34, 35, 36]. The famous Prisoners’ Dilemma game provides such
the most prominent example [33, 37], which also applies to other abstract
quantum games [38]. The quantization of many classical systems can even apply
to political structures, as was shown in [39]. To be fair, the quantum setting
is not the only unconventional venue that has been pursued. The biological
realm has also received its share of attention (see [40, 41, 42]). By drawing
inspiration from the biological domain, it is often possible to outperform
classical strategies in games such as the Prisoners’ Dilemma [43, 44, 45, 46,
47].

To motivate the forthcoming presentation of the protocol we give a real-life
example where the ability to have such an efficient and secure three-party
information exchange protocol, complying with the specifications previously
outline, is beneficial or even necessary.

######  Example 1.1 (The undercover agents).

This example should be seen as a proof of concept for more intricate real-life
situations. Let us suppose that Bob and Charlie are two undercover agents
working for a law enforcement agency. Information is critical for the success
of their mission. Bob is desperately in need of some piece of information that
knows Charlie has. He also knows that in their line of work the only real
currency is information. So, he is ready to offer Charlie another piece of
information that he believes will prove useful to Charlie. Bob and Charlie are
not friends, just colleagues, and they do not fully trust each other, but they
both trust their boss, Alice. Alice would be the ideal intermediary because
she trusted by both agents, so she should be involved in the process of
information exchange. Moreover, based on her involvement, Alice would be able
to remember this secret transaction and vouch for her agents in case one, or
both, of them would need in the future to prove that this particular
information exchange took place, e.g., if their missions failed. At the end of
the exchange process, Alice, should not have become aware of the contents of
the information that was exchanged because both agents want to protect their
informants. Finally, Alice stays at the headquarters, whereas Bob and Charlie
work undercover in different parts of town, so it would be safer and more
prudent if they did not meet in person at all. How can they complete this
task? $\triangleleft$

Contribution. This paper presents a quantum protocol that solves efficiently
and securely the problem of reciprocal information exchange between two
information brokers. Its novelty is twofold: (i) in the integral use
entanglement, and (ii) in the inclusion of a third party to supervise and
facilitate the exchange process. Entanglement, one of the hallmarks of the
quantum world, allows the simultaneous transmission of information by the two
players, enhances the security of the operation, and also enables the
spatially distributed execution of the protocol. There many practical
situations, as briefly sketched in the previous example, where the presence of
an intermediary would be required. The important observation here is that a
trusted intermediary does not compromise the security of the procedure, and,
after the completion of the protocol, remains oblivious of the actual
information that was exchanged between the two players, i.e., there is no
information leak whatsoever.

### Organization

The structure of this paper is the following. Section 1 contains an
introduction to the subject and contains related references. Section 2 gives a
succinct reminder on entangled GHZ states. Section 3 provides a formal and
detailed exposition of the quantum protocol, and, finally, Section 4 contains
a summary and a brief discussion on some of the finer points of this protocol.

##  2 Preliminaries

Many quantum protocols can be described as game between well-known fictional
players, commonly referred to as Alice, Bob, Charlie, who, while being
spatially separated, are attempting to send and/or receive information
securely. Typically, secure communication can be established via a combination
of classical pairwise authenticated channels with pairwise quantum channels.
Usually, the process of transmitting secret information takes place through
the quantum channel using a multitude of different techniques, and,
subsequently, in order to complete the process, a message is exchanged through
a classical public channel. During this phase, an adversary who is mostly
referred to as Eve, may appear and attempt to track this communication and
steal any information possible. If such an eventuality, the major advantage of
quantum cryptography over its classical counterpart is that during the
transmission of information through the quantum channel, the communicating
players are protected due to certain fundamental principles of quantum
mechanics, such as the no-cloning theorem [48], entanglement monogamy, etc.

Entanglement constitutes the fundamental basis of most quantum protocols,
including the one proposed in this work, and possibly the de facto future of
quantum cryptography, due to its numerous applications in the entire field. It
is one of the fundamental principles of quantum mechanics and can be described
mathematically as the linear combination of two or more product states. The
Bell states are specific quantum states of two qubits, sometimes called an EPR
pair, that represent the simplest examples of quantum entanglement. The
entanglement of three or more qubits is referred to as a GHZ state. The
fundamental idea of quantum entanglement in its simplest form is that it is
possible for quantum particles to be entangled together and when a property is
measured in one particle, it can be observed on the other particles
instantaneously.

Contemporary quantum computers based on the circuit model can readily produce
general states involving $n$ entangled qubits, which are denoted by
$\ket{GHZ_{n}}$. Implementing such a circuit requires $n$ qubits, one Hadamard
gate that is applied to the first qubit, and $n-1$ CNOT gates. We refer the
interested reader to [49] for a practical methodology that can be utilized to
construct efficient GHZ circuits, in the sense that it just takes $\lg n$
steps to produce the $\ket{GHZ_{n}}$ state. For the proposed protocol
$\ket{GHZ_{3}}$ triplets suffice. A typical circuit capable of generating the
$\ket{GHZ_{3}}$ state is given in Figure 1. The circuit was designed using the
IBM Quantum Composer [50]. The dotted lines are not part of the circuit; they
just serve to provide a visual aid in order to distinguish “time slices.”
Figure 2, also taken from the IBM Quantum Composer, depict the state vector
description of the $\ket{GHZ_{3}}$ state.

Figure 1: The above quantum circuit can entangle 3 qubits in the
$\ket{GHZ_{3}}=\frac{\ket{0}\ket{0}\ket{0}+\ket{1}\ket{1}\ket{1}}{\sqrt{2}}$
state. Any $\ket{GHZ_{n}}$ state can be produced in an analogous manner.

Figure 2: The above figure depicts the state vector description of the
$\ket{GHZ_{3}}$ state.

The mathematical description of the $\ket{GHZ_{3}}$ state is given below.

$\displaystyle\ket{GHZ_{3}}=\frac{1}{\sqrt{2}}\left(\ket{0}_{A}\ket{0}_{B}\ket{0}_{C}+\ket{1}_{A}\ket{1}_{B}\ket{1}_{C}\right)\
.$ (2.1)

Our protocol requires not just a single $\ket{GHZ_{3}}$ triplet, but $n$ such
triplets. The state of a composite system comprised of $n$ $\ket{GHZ_{3}}$
triplets is given by the next formula (for details we refer to [17] and [51]).

$\displaystyle\ket{GHZ_{3}}^{\otimes
n}=\frac{1}{\sqrt{2^{n}}}\sum_{\mathbf{x}\in\\{0,1\\}^{n}}\ket{\mathbf{x}}_{A}\ket{\mathbf{x}}_{B}\ket{\mathbf{x}}_{C}\
.$ (2.2)

In (2.2), ${\mathbf{x}\in\\{0,1\\}^{n}}$ ranges through all the $2^{n}$ basis
kets, $\ket{\mathbf{x}}_{A}$, $\ket{\mathbf{x}}_{B}$ and
$\ket{\mathbf{x}}_{C}$ correspond to the contents of Alice, Bob and Charlie’s
input registers, respectively.

##  3 The protocol for simultaneous reciprocal information exchange between 2
players

$n$ qubits$n$ qubits $n$ qubits$n$ qubits THE QUANTUM CHANNELS Two quantum
channels are required; one between Alice and Bob, and another between Alice
and Charlie, where Alice, Bob and Charlie are pairwise spatially separated.
Alice creates $n$ triplets in the $\ket{GHZ_{3}}$ state. From each triplet,
Alice keeps one qubit and sends through the quantum channels the other two to
Bob and Charlie, one to each of them. Charlie Alice (Source of the
$\ket{GHZ_{3}}$ triples) Bob Figure 3: This figure shows Alice, Bob and
Charlie, who are spatially separated, and the two quantum channels, one
between Alice and Bob and the other between Alice and Charlie. Alice produces
$n$ triplets of photons entangled in the $\ket{GHZ_{3}}$ state. From each
triplet Alice keeps one for herself, sends the second to Bob, and the third to
Charlie through the corresponding quantum channels.

In this section we present the entanglement-based protocol for simultaneous
reciprocal information exchange between 2 players, or ESR for short. The ESR
protocol is designed so as to enable two players, named Bob and Charlie, who
are perceived as information brokers, to exchange information simultaneously
and reciprocally. The process is mediated by Alice, who plays the mutually
trusted intermediary. All our three protagonists are assumed to be spatially
separated. The main idea is to achieve this task by using an appropriate
number (which we denote by $n$) of maximally entangled $\ket{GHZ_{3}}$
triplets. These are created by Alice, trusted by both Bob and Charlie, who
evenly distributes all triplets among herself, Bob and Charlie, using two
corresponding pairwise quantum channels. This results in each player having
precisely one qubit from every triplet. Alice’s role is crucial not only to
the successful completion of the protocol, but also as a possible witness that
the information exchange really took place. It is very important to point out
that, despite being an integral part of the exchange, Alice does not end up
knowing anything. The protocol can be conceptually divided in two parts, a
quantum and a classical part, taking place through the quantum and the public
classical channels, respectively.

###  3.1 The quantum part of the protocol

The game effectively begins after Alice, Bob and Charlie have populated their
output registers, denoted by AOR, BOR and COR, respectively, with their $n$
qubits. The whole setting is depicted in Figure 3. The protocol itself can be
implemented with the distributed quantum circuit of Figure 4. Although this
circuit is distributed, since the players’ local circuits are spatially
separated, it is in fact one composite system because their input registers
are strongly correlated due to the presence of entanglement. The notation
employed in the circuit of Figure 4 is explained in Table 1.

$n$ qubits$n$ qubits$n$ qubits$n$ qubits $n$ qubits$n$ qubits$n$ qubits$n$
qubits$CIR$$COR$$\ket{1}$$BIR$$BOR$$\ket{1}$$AIR$HHU${}_{f_{C}}$U${}_{f_{B}}$H⊗nH⊗nH⊗n$\ket{\mathbf{c}}$$\ket{\mathbf{b}}$$\ket{\mathbf{a}}$$\ket{\psi_{0}}$$\ket{\psi_{1}}$$\ket{\psi_{2}}$$\ket{\psi_{3}}$$\ket{\psi_{4}}$Charlie
Bob Creates $n$ $\ket{GHZ_{3}}$ tripletsAlice  Figure 4: This figure is an
abstract visualization of the quantum circuits employed by Alice, Bob and
Charlie. Although they are spatially separated, they are correlated, due to
the phenomenon of entanglement. Thus, they form a composite system, whose
temporal evolution is given by the state vectors $\ket{\psi_{0}}$,
$\ket{\psi_{1}}$, $\ket{\psi_{2}}$, $\ket{\psi_{3}}$ and $\ket{\psi_{4}}$.

$n$ qubits$n$ qubits$n$ qubits$n$ qubits Table 1: This table contains the
notations and abbreviations that are used in Figure 4. Notations and
Abbreviations Symbolism  Explanation $n$ The number of qubits in each input
register AIR  Alice’s $n$-qubit Input Register BIR  Bob’s $n$-qubit Input
Register BOR  Bob’s single qubit Output Register CIR  Charlie’s $n$-qubit
Input Register COR  Charlie’s single qubit Output Register

The rigorous mathematical analysis of the ESR information exchange protocol
invokes a couple of standard relations from the literature, typically found in
most textbooks, like [52] and [53]):

$\displaystyle H\ket{1}$
$\displaystyle=\frac{1}{\sqrt{2}}\left(\ket{0}-\ket{1}\right)=\ket{-}\
,\quad\text{and}$ (3.1) $\displaystyle H^{\otimes n}\ket{\mathbf{x}}$
$\displaystyle=\frac{1}{\sqrt{2^{n}}}\sum_{\mathbf{z}\in\\{0,1\\}^{n}}(-1)^{\mathbf{z\cdot
x}}\ket{\mathbf{z}}\ .$ (3.2)

In equation (3.2) we have adhered to the typical convention of writing the
contents of quantum registers in boldface, e.g.,
$\ket{\mathbf{x}}=\ket{x_{n-1}}\dots\ket{x_{0}}$, for some $n\geq 1$.
Moreover, the notation $\mathbf{z\cdot x}$ stands for the _inner product
modulo_ $2$, which, assuming that
$\ket{\mathbf{z}}=\ket{z_{n-1}}\dots\ket{z_{0}}$, is defined as

$\displaystyle\mathbf{z\cdot x}=z_{n-1}x_{n-1}\oplus\dots\oplus z_{0}x_{0}\ .$
(3.3)

Let us assume that $\mathbf{i}_{B}$ is the bit vector that represents the
information that Bob possesses and intends to exchange with Charlie, and,
symmetrically, that $\mathbf{i}_{C}$ is the bit vector corresponding to the
information that Charlie possesses and intends to exchange with Bob. We define
the _auxiliary information bit vectors_ $\widetilde{\mathbf{i}_{B}}$ and
$\widetilde{\mathbf{i}_{C}}$ as follows, where the notation $|\cdot|$ denotes
the length, i.e., number of bits, of the enclosed bit vector:

$\displaystyle\widetilde{\mathbf{i}_{B}}$ $\displaystyle=\mathbf{i}_{B}\
\underbrace{0\ \cdots\ 0}_{|\mathbf{i}_{C}|\rm\ times}\ ,\quad\text{and}$
(3.4) $\displaystyle\widetilde{\mathbf{i}_{C}}$ $\displaystyle=\underbrace{0\
\cdots\ 0}_{|\mathbf{i}_{B}|\rm\ times}\ \mathbf{i}_{C}\ .$ (3.5)

We define the _aggregated information bit vector_ $\mathbf{i}$ as the
concatenation of $\mathbf{i}_{B}$ and $\mathbf{i}_{C}$:

$\displaystyle\mathbf{i}=\mathbf{i}_{B}\ \mathbf{i}_{C}\ ,$ (3.6)

and we set

$\displaystyle
n=|\mathbf{i}|=|\widetilde{\mathbf{i}_{B}}|=|\widetilde{\mathbf{i}_{C}}|=|\mathbf{i}_{B}|+|\mathbf{i}_{C}|\
.$ (3.7)

We use the boldface $\mathbf{0}$ to abbreviate the zero bit vector of length
$n$. Of course, we assume that $n$ is common knowledge to all three players.
In effect, this can be easily achieved if Bob and Charlie share though the
public channel the lengths $|\mathbf{i}_{B}|$ and $|\mathbf{i}_{C}|$ of their
respective information bit vectors. This poses no danger whatsoever, as
sharing the length does not reveal the contents of the secret information. The
preceding discussion also implies that

$\displaystyle\mathbf{i}=\widetilde{\mathbf{i}_{B}}\oplus\widetilde{\mathbf{i}_{C}}\
.$ (3.8)

The initial state of the circuit of Figure 4 is denoted by $\ket{\psi_{0}}$.
In view of (2.2), $\ket{\psi_{0}}$ is given by

$\displaystyle\ket{\psi_{0}}=\frac{1}{\sqrt{2^{n}}}\sum_{\mathbf{x}\in\\{0,1\\}^{n}}\ket{\mathbf{x}}_{A}\ket{1}_{B}\ket{\mathbf{x}}_{B}\ket{1}_{C}\ket{\mathbf{x}}_{C}\
.$ (3.9)

As is the trend nowadays, we stick to the Qiskit [54] way of ordering the
qubits, in which the most significant is the bottom qubit and the least
significant the top. Furthermore, we rely on the subscripts $A$, $B$ and $C$
in order to designate Alice, Bob and Charlie’s registers, respectively.

At the end of the first phase, Bob and Charlie have applied the Hadamard
transform to their output registers and the resulting state has become
$\ket{\psi_{1}}$:

$\displaystyle\ket{\psi_{1}}\overset{(\ref{eq:Ket -
Definition})}{=}\frac{1}{\sqrt{2^{n}}}\sum_{\mathbf{x}\in\\{0,1\\}^{n}}\ket{\mathbf{x}}_{A}\ket{-}_{B}\ket{\mathbf{x}}_{B}\ket{-}_{C}\ket{\mathbf{x}}_{C}\
.$ (3.10)

It is during the second phase that Bob and Charlie simultaneously encode the
information they intend to exchange within the state of the quantum circuit.
They do so by acting with their unitary transforms $U_{f_{B}}$ and $U_{f_{C}}$
on both their output and input registers. The unitary transforms $U_{f_{A}}$
and $U_{f_{B}}$ are constructed using the functions $f_{B}(\mathbf{x})$ and
$f_{C}(\mathbf{x})$, respectively, according to the usual scheme

$\displaystyle U_{f_{B}}$
$\displaystyle:\ket{y}_{B}\ket{\mathbf{x}}_{B}\rightarrow\ket{y\oplus
f_{B}(\mathbf{x})}_{B}\ket{\mathbf{x}}_{B}\ ,\quad\text{and}$ (3.11)
$\displaystyle U_{f_{C}}$
$\displaystyle:\ket{y}_{C}\ket{\mathbf{x}}_{C}\rightarrow\ket{y\oplus
f_{C}(\mathbf{x})}_{C}\ket{\mathbf{x}}_{C}\ .$ (3.12)

The functions $f_{B}(\mathbf{x})$ and $f_{C}(\mathbf{x})$ are quite
straightforward, relying on Bob and Charlie’s auxiliary information bit
vectors $\widetilde{\mathbf{i}_{B}}$ and $\widetilde{\mathbf{i}_{C}}$,
respectively, according to the formulas (3.13) and (3.14) presented below.

$\displaystyle f_{B}(\mathbf{x})$
$\displaystyle=\widetilde{\mathbf{i}_{B}}\cdot\mathbf{x}\ ,\quad\text{and}$
(3.13) $\displaystyle f_{C}(\mathbf{x})$
$\displaystyle=\widetilde{\mathbf{i}_{C}}\cdot\mathbf{x}\ .$ (3.14)

Therefore, (3.11) and (3.12) can be explicitly written as

$\displaystyle U_{f_{B}}$
$\displaystyle:\ket{-}_{B}\ket{\mathbf{x}}_{B}\rightarrow(-1)^{\widetilde{\mathbf{i}_{B}}\cdot\mathbf{x}}\ket{-}_{B}\ket{\mathbf{x}}_{B}\
,\quad\text{and}$ (3.15) $\displaystyle U_{f_{C}}$
$\displaystyle:\ket{-}_{C}\ket{\mathbf{x}}_{C}\rightarrow(-1)^{\widetilde{\mathbf{i}_{C}}\cdot\mathbf{x}}\ket{-}_{C}\ket{\mathbf{x}}_{C}\
.$ (3.16)

In view of the above calculations, at the end of the second phase the state of
the quantum circuit has become $\ket{\psi_{2}}$:

$\displaystyle\ket{\psi_{2}}$ $\displaystyle\
=\frac{1}{\sqrt{2^{n}}}\sum_{\mathbf{x}\in\\{0,1\\}^{n}}\ket{\mathbf{x}}_{A}(-1)^{\widetilde{\mathbf{i}_{B}}\cdot\mathbf{x}}\ket{-}_{B}\ket{\mathbf{x}}_{B}(-1)^{\widetilde{\mathbf{i}_{C}}\cdot\mathbf{x}}\ket{-}_{C}\ket{\mathbf{x}}_{C}$
$\displaystyle\
=\frac{1}{\sqrt{2^{n}}}\sum_{\mathbf{x}\in\\{0,1\\}^{n}}(-1)^{(\widetilde{\mathbf{i}_{B}}\oplus\widetilde{\mathbf{i}_{C}})\cdot\mathbf{x}}\ket{\mathbf{x}}_{A}\ket{-}_{B}\ket{\mathbf{x}}_{B}\ket{-}_{C}\ket{\mathbf{x}}_{C}$
$\displaystyle\overset{(\ref{eq:Aggregated Information Vector Length as Mod
$2$
Sum})}{=}\frac{1}{\sqrt{2^{n}}}\sum_{\mathbf{x}\in\\{0,1\\}^{n}}(-1)^{\mathbf{i}\cdot\mathbf{x}}\ket{\mathbf{x}}_{A}\ket{-}_{B}\ket{\mathbf{x}}_{B}\ket{-}_{C}\ket{\mathbf{x}}_{C}\
.$ (3.17)

As the third phase unfolds, Alice, Bob and Charlie apply their $n$-fold
Hadamard transform to their input registers, driving the quantum circuit to
the next state $\ket{\psi_{3}}$.

$\displaystyle\ket{\psi_{3}}$
$\displaystyle=\frac{1}{\sqrt{2^{n}}}\sum_{\mathbf{x}\in\\{0,1\\}^{n}}(-1)^{\mathbf{i}\cdot\mathbf{x}}H^{\otimes
n}\ket{\mathbf{x}}_{A}\ket{-}_{B}H^{\otimes
n}\ket{\mathbf{x}}_{B}\ket{-}_{C}H^{\otimes n}\ket{\mathbf{x}}_{C}$
$\displaystyle\overset{(\ref{eq:Hadamard n-Fold Ket
x})}{=}\frac{1}{\sqrt{2^{n}}}\sum_{\mathbf{x}\in\\{0,1\\}^{n}}(-1)^{\mathbf{i}\cdot\mathbf{x}}\left(\frac{1}{\sqrt{2^{n}}}\sum_{\mathbf{a}\in\\{0,1\\}^{n}}(-1)^{\mathbf{a}\cdot\mathbf{x}}\ket{\mathbf{a}}_{A}\right)$
$\displaystyle\hskip
60.4621pt\ket{-}_{B}\left(\frac{1}{\sqrt{2^{n}}}\sum_{\mathbf{b}\in\\{0,1\\}^{n}}(-1)^{\mathbf{b}\cdot\mathbf{x}}\ket{\mathbf{b}}_{B}\right)$
$\displaystyle\hskip
60.88887pt\ket{-}_{C}\left(\frac{1}{\sqrt{2^{n}}}\sum_{\mathbf{c}\in\\{0,1\\}^{n}}(-1)^{\mathbf{c}\cdot\mathbf{x}}\ket{\mathbf{c}}_{C}\right)$
$\displaystyle=\frac{1}{2^{2n}}\sum_{\mathbf{x}\in\\{0,1\\}^{n}}\sum_{\mathbf{a}\in\\{0,1\\}^{n}}\sum_{\mathbf{b}\in\\{0,1\\}^{n}}\sum_{\mathbf{c}\in\\{0,1\\}^{n}}(-1)^{(\mathbf{i}\oplus\mathbf{a}\oplus\mathbf{b}\oplus\mathbf{c})\cdot\mathbf{x}}\ket{\mathbf{a}}_{A}\ket{-}_{B}\ket{\mathbf{b}}_{B}\ket{-}_{C}\ket{\mathbf{b}}_{C}$
$\displaystyle=\frac{1}{2^{2n}}\sum_{\mathbf{a}\in\\{0,1\\}^{n}}\sum_{\mathbf{b}\in\\{0,1\\}^{n}}\sum_{\mathbf{c}\in\\{0,1\\}^{n}}\sum_{\mathbf{x}\in\\{0,1\\}^{n}}(-1)^{(\mathbf{i}\oplus\mathbf{a}\oplus\mathbf{b}\oplus\mathbf{c})\cdot\mathbf{x}}\ket{\mathbf{a}}_{A}\ket{-}_{B}\ket{\mathbf{b}}_{B}\ket{-}_{C}\ket{\mathbf{b}}_{C}\
.$ (3.18)

We can express (3.1) in a more intelligible form by invoking a useful property
of the inner product modulo $2$. Whenever $\mathbf{c}$ is a fixed element of
$\\{0,1\\}^{n}$, but different from $\mathbf{0}$, then for half of the
elements $\mathbf{x}\in\\{0,1\\}^{n}$, $\mathbf{c}\cdot\mathbf{x}$ is $0$ and
for the other half, $\mathbf{c}\cdot\mathbf{x}$ is $1$. However, when
$\mathbf{c}=\mathbf{0}$, then for all $\mathbf{x}\in\\{0,1\\}^{n}$, $\
\mathbf{c}\cdot\mathbf{x}=0$. For a more detailed analysis on this point we
refer to [51]. Therefore, if

$\displaystyle\mathbf{a}\oplus\mathbf{b}\oplus\mathbf{c}=\mathbf{i}\ ,$ (3.19)

the sum
$\sum_{\mathbf{x}\in\\{0,1\\}^{n}}(-1)^{(\mathbf{i}\oplus\mathbf{a}\oplus\mathbf{b}\oplus\mathbf{c})\cdot\mathbf{x}}\ket{\mathbf{a}}_{A}\ket{-}_{B}\ket{\mathbf{b}}_{B}\ket{-}_{C}\ket{\mathbf{b}}_{C}$
is equal to $2^{n}$ $\ket{\mathbf{a}}_{A}$ $\ket{-}_{B}\ket{\mathbf{b}}_{B}$
$\ket{-}_{C}\ket{\mathbf{b}}_{C}$, whereas if
$\mathbf{a}\oplus\mathbf{b}\oplus\mathbf{c}\neq\mathbf{i}$, the sum reduces to
$0$. Ergo, $\ket{\psi_{3}}$ can be written simpler as

$\displaystyle\ket{\psi_{3}}=\frac{1}{2^{n}}\sum_{\mathbf{a}\in\\{0,1\\}^{n}}\sum_{\mathbf{b}\in\\{0,1\\}^{n}}\sum_{\mathbf{c}\in\\{0,1\\}^{n}}\ket{\mathbf{a}}_{A}\ket{-}_{B}\ket{\mathbf{b}}_{B}\ket{-}_{C}\ket{\mathbf{b}}_{C}\
,\quad\text{where}\quad\mathbf{a}\oplus\mathbf{b}\oplus\mathbf{c}=\mathbf{i}\
.$ (3.20)

We call relation (3.19) the Fundamental Correlation Property that intertwines
the contents of Alice, Bob and Charlie’s input registers. The intuition behind
this property is that the entanglement between their input registers in the
initialization of the quantum circuit, has caused this specific dependency
that disallows the contents of the input registers from varying independently
of its other.

The final measurement of their input registers by Alice, Bob and Charlie,
drives the quantum circuit into its final state $\ket{\psi_{4}}$.

$\displaystyle\ket{\psi_{4}}=\ket{\mathbf{a}}_{A}\ket{-}_{B}\ket{\mathbf{b}}_{B}\ket{-}_{C}\ket{\mathbf{b}}_{C}\
,\quad\text{for some}\quad\mathbf{a},\mathbf{b},\mathbf{c}\in\\{0,1\\}^{n}\ ,$
(3.21)

where $\mathbf{a},\mathbf{b}$ and $\mathbf{c}$ are correlated via (3.19). One
may regard the final contents $\mathbf{a}$ and $\mathbf{b}$ of Alice and Bob’s
input registers random, but in that case the final contents $\mathbf{c}$ of
Charlie’s input register are completely determined. Symmetrically, one may
regard the final contents $\mathbf{b}$ and $\mathbf{c}$ of Bob and Charlie’s
input register random, in which case the final contents $\mathbf{a}$ of
Alice’s input register are completely determined, and so on.

###  3.2 The classical part of the protocol

$n$ qubits$n$ qubits$n$ qubits$n$
qubits$\mathbf{a}_{C}$$\mathbf{a}_{B}$$\mathbf{b}_{B}$$\mathbf{c}_{C}$ $n$
qubits$n$ qubits$n$ qubits$n$
qubits$\mathbf{a}_{C}$$\mathbf{a}_{B}$$\mathbf{b}_{B}$$\mathbf{c}_{C}$ THE
CLASSICAL CHANNELS Alice uses two classical channels, the first between
herself and Bob, and the second between herself and Charlie, to send them the
contents of her input register. Bob and Charlie use a third classical channel
to exchange information. Charlie Alice (Source of the $\ket{GHZ_{3}}$ triples)
Bob Figure 5: This figure shows Alice, Bob and Charlie, who are spatially
separated, and their three classical channels, the first between Alice and
Bob, the second between Alice and Charlie, and the third between Bob and
Charlie.

To complete the ESR information exchange protocol one final step remains, and
this step takes place in the classical public channels. We may write the
contents of the players’ input registers as follows:

$\displaystyle\mathbf{a}$ $\displaystyle=\mathbf{a}_{B}\ \mathbf{a}_{C},$
$\displaystyle\text{where}\ |\mathbf{a}_{B}|=|\mathbf{i}_{B}|\ $
$\displaystyle\text{and}\ |\mathbf{a}_{C}|=|\mathbf{i}_{C}|$ (3.22)
$\displaystyle\mathbf{b}$ $\displaystyle=\mathbf{b}_{B}\ \mathbf{b}_{C},$
$\displaystyle\text{where}\ |\mathbf{b}_{B}|=|\mathbf{i}_{B}|\ $
$\displaystyle\text{and}\ |\mathbf{b}_{C}|=|\mathbf{i}_{C}|\ ,\quad\text{and}$
(3.23) $\displaystyle\mathbf{c}$ $\displaystyle=\mathbf{c}_{B}\
\mathbf{c}_{C},$ $\displaystyle\text{where}\
|\mathbf{c}_{B}|=|\mathbf{i}_{B}|\ $ $\displaystyle\text{and}\
|\mathbf{c}_{C}|=|\mathbf{i}_{C}|\ .$ (3.24)

The previous formulas, allow us to refine equation (3.19) into two independent
parts, the first regarding the information bit vector $\mathbf{i}_{B}$ that
Bob intends to communicate to Charlie, and the second regarding the
information bit vector $\mathbf{i}_{C}$, that Charlie intends to communicate
to Bob.

$\displaystyle\mathbf{a}_{B}\oplus\mathbf{b}_{B}\oplus\mathbf{c}_{B}$
$\displaystyle=\mathbf{i}_{B}\ ,\quad\text{and}$ (3.25)
$\displaystyle\mathbf{a}_{C}\oplus\mathbf{b}_{C}\oplus\mathbf{c}_{C}$
$\displaystyle=\mathbf{i}_{C}\ .$ (3.26)

The above relations (3.25) and (3.26) dictate what remains to be done in the
final classical part of the ESR information exchange protocol so that Bob and
Charlie receive the intended information.

  * •

Alice must use two classical public channels to communicate with Bob and
Charlie. Specifically, she must send through these channels the information
bit vectors $\mathbf{a}_{C}$ and $\mathbf{a}_{B}$ to Bob and Charlie,
respectively.

  * •

Bob and Charlie must use a third classical channel to communicate with each
other. This communication must take place with caution. They must not reveal
the entire contents of their input registers because then Alice, and any other
adversary for that matter, will be able to piece together the secret
information $\mathbf{i}_{B}$ and $\mathbf{i}_{C}$. They must transmit only the
absolutely necessary information for the successful completion of the
exchange. This means that Bob must send to Charlie only the information vector
$\mathbf{b}_{B}$ and not the whole contents $\mathbf{b}$ of his input
register. Reciprocally, Charlie must send to Bob only the information vector
$\mathbf{c}_{C}$ and not the whole contents $\mathbf{c}$ of his input
register.

After the communications outlined above have taken place, the ESR protocol is
concluded. Bob knows $\mathbf{a}_{C}$, $\mathbf{c}_{C}$, and, of course the
contents of his input register, and can discover the secret information
$\mathbf{i}_{C}$, according to equation (3.26). Symmetrically, Charlie, being
in possession of $\mathbf{a}_{B}$, $\mathbf{b}_{B}$, can reconstruct
$\mathbf{i}_{B}$, as equation (3.25) asserts. Alice, despite her critical
contribution in the implementation of the protocol, lacks the necessary
information, namely $\mathbf{b}_{C}$ and $\mathbf{c}_{B}$, which has not been
made public. Thus, she is no position to uncover either $\mathbf{i}_{B}$, or
$\mathbf{i}_{C}$.

##  4 Discussion and conclusions

This work proposed the ESR protocol for the simultaneous reciprocal exchange
of secret information between Bob and Charlie. The whole process is mediated
by Alice, who is assumed to be a trusted intermediary. Alice is necessary for
the completion of the ESR protocol because without the contents of her input
register, the information can be reconstructed. Although her contribution is
absolutely essential, proper execution of the last classical part of the
protocol ensures that she gains no insight whatsoever about the information
that was exchanged. Moreover, since Alice is assumed to be a player that is
mutually trusted by both Bob and Charlie, her involvement does not compromise
the security of the protocol.

$n$ qubits$n$ qubits$n$ qubits$n$
qubits$\mathbf{a}_{C}$$\mathbf{a}_{B}$$\mathbf{b}_{B}$$\mathbf{c}_{C}$$n$
qubits$n$ qubits $n$ qubits$n$ qubits$n$ qubits$n$
qubits$\mathbf{a}_{C}$$\mathbf{a}_{B}$$\mathbf{b}_{B}$$\mathbf{c}_{C}$$n$
qubits$n$
qubits$CIR$$COR$$\ket{1}$$BIR$$BOR$$\ket{1}$HHU${}_{f_{C}}$U${}_{f_{B}}$H⊗nH⊗n$\ket{\mathbf{c}}$$\ket{\mathbf{b}}$$\ket{\psi_{0}}$$\ket{\psi_{1}}$$\ket{\psi_{2}}$$\ket{\psi_{3}}$$\ket{\psi_{4}}$Charlie
Bob $n$ $\ket{\Phi^{+}}$ pairs source  Figure 6: This figure outlines a
distributed quantum circuit, where only Bob and Charlie are present. Again
both are correlated, due to the phenomenon of entanglement. Thus, they form a
composite system, whose temporal evolution is given by the state vectors
$\ket{\psi_{0}}$, $\ket{\psi_{1}}$, $\ket{\psi_{2}}$, $\ket{\psi_{3}}$ and
$\ket{\psi_{4}}$.

Of course, one can easily envision a protocol for information exchange between
Bob and Charlie that does not involve Alice at all. The ESR protocol can be
easily simplified to function without the presence of Alice, using for
instance the quantum circuit shown in Figure 6. In such a case, instead of
entangled triplets, it would be necessary to employ entangled pairs, e.g., EPR
pairs in the Bell $\ket{\Phi^{+}}$ state:

$\displaystyle\ket{\Phi^{+}}=\frac{\ket{0}_{B}\ket{0}_{C}+\ket{1}_{B}\ket{1}_{C}}{\sqrt{2}}\
.$ (4.1)

Such an approach would certainly require a somewhat simpler quantum circuit
for the production of the EPR pairs. Furthermore, the whole mathematical
description of the protocol would be considerably easier. Nonetheless one
would still have to address the requirement for a trusted source to produce
and distribute that $n$ $\ket{\Phi^{+}}$ pairs to Bob and Charlie.

However, it is our belief that, as we have advocated in the Introduction,
there are many real-life situations where having a third party witnessing and
verifying that such a transaction has indeed occurred can be beneficial, or
even necessary. Ergo, it seems prudent to able to account for this
eventuality, particularly in view of the fact that the third party not only is
trusted, but it does not gain knowledge of the secret information that was
exchanged.

## References

  * [1] L. Chen, L. Chen, S. Jordan, Y.-K. Liu, D. Moody, R. Peralta, R. Perlner, and D. Smith-Tone, Report on post-quantum cryptography, vol. 12.  US Department of Commerce, National Institute of Standards and Technology, 2016.
  * [2] G. Alagic, G. Alagic, J. Alperin-Sheriff, D. Apon, D. Cooper, Q. Dang, Y.-K. Liu, C. Miller, D. Moody, R. Peralta, et al., Status report on the first round of the NIST post-quantum cryptography standardization process.  US Department of Commerce, National Institute of Standards and Technology …, 2019.
  * [3] G. Alagic, J. Alperin-Sheriff, D. Apon, D. Cooper, Q. Dang, J. Kelsey, Y.-K. Liu, C. Miller, D. Moody, R. Peralta, et al., “Status report on the second round of the nist post-quantum cryptography standardization process,” US Department of Commerce, NIST, 2020.
  * [4] G. Alagic, D. Apon, D. Cooper, Q. Dang, T. Dang, J. Kelsey, J. Lichtinger, C. Miller, D. Moody, R. Peralta, et al., “Status report on the third round of the nist post-quantum cryptography standardization process,” National Institute of Standards and Technology, Gaithersburg, 2022.
  * [5] P. Shor, “Algorithms for quantum computation: discrete logarithms and factoring,” in Proceedings 35th Annual Symposium on Foundations of Computer Science, IEEE Comput. Soc. Press, 1994.
  * [6] L. Grover, “A fast quantum mechanical algorithm for database search,” in Proc. of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing, 1996, 1996.
  * [7] J. Chow, O. Dial, and J. Gambetta, “IBM Quantum breaks the 100-qubit processor barrier.” https://research.ibm.com/blog/127-qubit-quantum-processor-eagle, 2021.  Accessed: 2022-04-03.
  * [8] I. Newsroom, “IBM unveils 400 qubit-plus quantum processor.” https://newsroom.ibm.com/2022-11-09-IBM-Unveils-400-Qubit-Plus-Quantum-Processor-and-Next-Generation-IBM-Quantum-System-Two, 2022\.  Accessed: 2022-04-03.
  * [9] V. Chamola, A. Jolfaei, V. Chanana, P. Parashari, and V. Hassija, “Information security in the post quantum era for 5g and beyond networks: Threats to existing cryptography, and post-quantum cryptography,” Computer Communications, vol. 176, pp. 99–118, 2021.
  * [10] A. K. Ekert, “Quantum cryptography based on bell’s theorem,” Physical Review Letters, vol. 67, no. 6, pp. 661–663, 1991.
  * [11] C. H. Bennett, G. Brassard, and N. D. Mermin, “Quantum cryptography without bell’s theorem,” Physical Review Letters, vol. 68, no. 5, pp. 557–559, 1992.
  * [12] N. Gisin, G. Ribordy, H. Zbinden, D. Stucki, N. Brunner, and V. Scarani, “Towards practical and fast quantum cryptography,” arXiv preprint quant-ph/0411022, 2004.
  * [13] K. Inoue, E. Waks, and Y. Yamamoto, “Differential phase shift quantum key distribution,” Physical review letters, vol. 89, no. 3, p. 037902, 2002\.
  * [14] J.-Y. Guan, Z. Cao, Y. Liu, G.-L. Shen-Tu, J. S. Pelc, M. Fejer, C.-Z. Peng, X. Ma, Q. Zhang, and J.-W. Pan, “Experimental passive round-robin differential phase-shift quantum key distribution,” Physical review letters, vol. 114, no. 18, p. 180502, 2015.
  * [15] E. Waks, H. Takesue, and Y. Yamamoto, “Security of differential-phase-shift quantum key distribution against individual attacks,” Physical Review A, vol. 73, no. 1, p. 012344, 2006.
  * [16] M. Ampatzis and T. Andronikos, “QKD based on symmetric entangled bernstein-vazirani,” Entropy, vol. 23, no. 7, p. 870, 2021.
  * [17] M. Ampatzis and T. Andronikos, “A symmetric extensible protocol for quantum secret sharing,” Symmetry, vol. 14, no. 8, p. 1692, 2022.
  * [18] V. Attasena, J. Darmont, and N. Harbi, “Secret sharing for cloud data security: a survey,” The VLDB Journal, vol. 26, no. 5, pp. 657–681, 2017\.
  * [19] T. Ermakova and B. Fabian, “Secret sharing for health data in multi-provider clouds,” in 2013 IEEE 15th conference on business informatics, pp. 93–100, IEEE, 2013.
  * [20] J. Cha, S. K. Singh, T. W. Kim, and J. H. Park, “Blockchain-empowered cloud architecture based on secret sharing for smart city,” Journal of Information Security and Applications, vol. 57, p. 102686, 2021.
  * [21] A. Karlsson, M. Koashi, and N. Imoto, “Quantum entanglement for secret sharing and secret splitting,” Physical Review A, vol. 59, no. 1, p. 162, 1999\.
  * [22] A. D. Smith, “Quantum secret sharing for general access structures,” arXiv preprint quant-ph/0001087, 2000.
  * [23] D. Gottesman, “Theory of quantum secret sharing,” Physical Review A, vol. 61, no. 4, p. 042311, 2000.
  * [24] B. Fortescue and G. Gour, “Reducing the quantum communication cost of quantum secret sharing,” IEEE transactions on information theory, vol. 58, no. 10, pp. 6659–6666, 2012.
  * [25] H. Qin, W. K. Tang, and R. Tso, “Hierarchical quantum secret sharing based on special high-dimensional entangled state,” IEEE Journal of Selected Topics in Quantum Electronics, vol. 26, no. 3, pp. 1–6, 2020.
  * [26] K. Senthoor and P. K. Sarvepalli, “Theory of communication efficient quantum secret sharing,” IEEE Transactions on Information Theory, 2022.
  * [27] Y. Fu, H.-L. Yin, T.-Y. Chen, and Z.-B. Chen, “Long-distance measurement-device-independent multiparty quantum communication,” Physical review letters, vol. 114, no. 9, p. 090501, 2015.
  * [28] X. Wu, Y. Wang, and D. Huang, “Passive continuous-variable quantum secret sharing using a thermal source,” Physical Review A, vol. 101, no. 2, p. 022301, 2020.
  * [29] W. P. Grice and B. Qi, “Quantum secret sharing using weak coherent states,” Physical Review A, vol. 100, no. 2, p. 022339, 2019.
  * [30] J. Gu, Y.-M. Xie, W.-B. Liu, Y. Fu, H.-L. Yin, and Z.-B. Chen, “Secure quantum secret sharing without signal disturbance monitoring,” Optics Express, vol. 29, no. 20, pp. 32244–32255, 2021.
  * [31] C. H. Bennett and G. Brassard, “Quantum cryptography: Public key distribution and coin tossing,” in Proceedings of the IEEE International Conference on Computers, Systems, and Signal Processing, pp. 175–179, IEEE Computer Society Press, 1984.
  * [32] D. A. Meyer, “Quantum strategies,” Physical Review Letters, vol. 82, no. 5, p. 1052, 1999.
  * [33] J. Eisert, M. Wilkens, and M. Lewenstein, “Quantum games and quantum strategies,” Physical Review Letters, vol. 83, no. 15, p. 3077, 1999.
  * [34] T. Andronikos, A. Sirokofskich, K. Kastampolidou, M. Varvouzou, K. Giannakis, and A. Singh, “Finite automata capturing winning sequences for all possible variants of the PQ penny flip game,” Mathematics, vol. 6, p. 20, Feb 2018\.
  * [35] T. Andronikos and A. Sirokofskich, “The connection between the PQ penny flip game and the dihedral groups,” Mathematics, vol. 9, no. 10, p. 1115, 2021\.
  * [36] T. Andronikos, “Conditions that enable a player to surely win in sequential quantum games,” Quantum Information Processing, vol. 21, no. 7, 2022.
  * [37] K. Giannakis, G. Theocharopoulou, C. Papalitsas, S. Fanarioti, and T. Andronikos, “Quantum conditional strategies and automata for prisoners’ dilemmata under the EWL scheme,” Applied Sciences, vol. 9, p. 2635, Jun 2019.
  * [38] K. Giannakis, C. Papalitsas, K. Kastampolidou, A. Singh, and T. Andronikos, “Dominant strategies of quantum games on quantum periodic automata,” Computation, vol. 3, pp. 586–599, nov 2015.
  * [39] T. Andronikos and M. Stefanidakis, “A two-party quantum parliament,” Algorithms, vol. 15, no. 2, p. 62, 2022.
  * [40] G. Theocharopoulou, K. Giannakis, C. Papalitsas, S. Fanarioti, and T. Andronikos, “Elements of game theory in a bio-inspired model of computation,” in 2019 10th International Conference on Information, Intelligence, Systems and Applications (IISA), pp. 1–4, IEEE, jul 2019.
  * [41] K. Kastampolidou, M. N. Nikiforos, and T. Andronikos, “A brief survey of the prisoners’ dilemma game and its potential use in biology,” in Advances in Experimental Medicine and Biology, pp. 315–322, Springer International Publishing, 2020.
  * [42] D. Kostadimas, K. Kastampolidou, and T. Andronikos, “Correlation of biological and computer viruses through evolutionary game theory,” in 2021 16th International Workshop on Semantic and Social Media Adaptation & Personalization (SMAP), IEEE, 2021.
  * [43] K. Kastampolidou and T. Andronikos, “A survey of evolutionary games in biology,” in Advances in Experimental Medicine and Biology, pp. 253–261, Springer International Publishing, 2020.
  * [44] K. Kastampolidou and T. Andronikos, “Microbes and the games they play,” in GeNeDis 2020, pp. 265–271, Springer International Publishing, 2021.
  * [45] K. Kastampolidou and T. Andronikos, “Game theory and other unconventional approaches to biological systems,” in Handbook of Computational Neurodegeneration, pp. 1–18, Springer International Publishing, 2021.
  * [46] C. Papalitsas, K. Kastampolidou, and T. Andronikos, “Nature and quantum-inspired procedures – a short literature review,” in GeNeDis 2020, pp. 129–133, Springer International Publishing, 2021.
  * [47] S. Adam, P. Karastathis, D. Kostadimas, K. Kastampolidou, and T. Andronikos, “Protein misfolding and neurodegenerative diseases: A game theory perspective,” in Handbook of Computational Neurodegeneration, pp. 1–12, Springer International Publishing, 2023.
  * [48] W. K. Wootters and W. H. Zurek, “A single quantum cannot be cloned,” Nature, vol. 299, no. 5886, pp. 802–803, 1982.
  * [49] D. Cruz, R. Fournier, F. Gremion, A. Jeannerot, K. Komagata, T. Tosic, J. Thiesbrummel, C. L. Chan, N. Macris, M.-A. Dupertuis, and C. Javerzac-Galy, “Efficient quantum algorithms for GHZ and w states, and implementation on the IBM quantum computer,” Advanced Quantum Technologies, vol. 2, no. 5-6, p. 1900015, 2019.
  * [50] IBM, “IBM Quantum Composer.” https://quantum-computing.ibm.com/composer.  Accessed: 2022-04-03.
  * [51] M. Ampatzis and T. Andronikos, “Quantum secret aggregation utilizing a network of agents,” Cryptography, vol. 7, no. 1, p. 5, 2023.
  * [52] M. A. Nielsen and I. L. Chuang, Quantum computation and quantum information.  Cambridge University Press, 2010.
  * [53] N. Mermin, Quantum Computer Science: An Introduction.  Cambridge University Press, 2007.
  * [54] Qiskit, “Qiskit open-source quantum development.” https://qiskit.org.  Accessed: 2022-04-03.


# GPT-Neo for commonsense reasoning - a theoretical and practical lens

Rohan Kashyap  9632145522 ,  Vivek Kashyap  and  Narendra C.P  narendracp@bit-
bangalore.edu.in Bangalore Institute of TechnologyBangaloreIndia

(2023)

###### Abstract.

Recent work has demonstrated substantial gains in pre-training large-language
models (LLMs) followed by supervised fine-tuning on the downstream task. In
this paper, we evaluate the performance of the GPT-neo model using $6$
commonsense reasoning benchmark tasks. We aim to examine the performance of
smaller models using the GPT-neo models against several larger model baselines
such as GPT-$3$, Llama-$2$, MPT and Falcon. Upon fine-tuning with the
appropriate set of hyperparameters, our model achieves competitive accuracy on
several tasks. We also investigate and substantiate our results using
attention-head visualization to better understand the model performance.
Finally, we conduct various robustness tests using various methods to gauge
the model performance under numerous settings.

Transformers

††copyright: acmcopyright††journalyear: 2023††doi:
10.1145/1122445.1122455††journal: TOG††journalvolume: 37††journalnumber:
4††article: 111††publicationmonth: 3††ccs: Neural Networks Large Language
models††ccs: Reasoning

##  1\. Introduction

Commonsense reasoning encompasses a central role in neural language
understanding. Recent years has seen the rise of large language models (LLMs),
such as the GPT-$3$ (b10, ), T5 (b30, ), Falcon (b47, ) and Llama (b25, ; b26,
). Autoregressive language models pretrained on large corpus of self-
supervised data using Reinforcement Learning with Human Feedback (RHLF)
results in model alignment with respect to human preferences on numerous
tasks. Advances in natural language processing tasks such as reading
comprehension, question answering and inductive reasoning demonstrate the
effectiveness of these huge pre-trained models on numerous downstream tasks,
and methods such as instructive fine-tuning (b16, ) and chain-of-thought
prompting (b15, ) have shown excellent few-shot learning capabilities.

In particular, (b15, ) demonstrates the ability of LLMs for multiple-step
reasoning on complex arithmetic and symbolic reasoning tasks as an emergent
property i.e., a series of intermediate reasoning steps lead the model to the
final output known as chain-of-thought-prompting. The parametric count of
these models typically ranges from a few million to billions, the performance
of which follows strict scaling laws (b14, ), with the larger models being
more sample efficient and only mildly prone to overfitting.

The transformer architecture has achieved immense success in NLP, generative
modeling (b2, ; b10, ) and reinforcement learning tasks. The self-attention
mechanism is the central idea of the transformer which help capture long-term
dependencies, and can thus learn coherent patterns and capture the
compositional relationships between them given as:

$Attention(Q,K,V)=softmax(QK^{T}/d_{k})V$

where $Q,K,V$ represents the input query, key and value matrix and $d_{k}$
denotes the key dimension respectively. Thus, they produce cohesive and
plausible text when adequately tuned to the right temperature ($0\leq T\leq
1$) during model inference and trained for several epochs ($>20$). This
challenges the LMs ability to extrapolate and draw useful information from the
training data to gain knowledge about the physical world to generate the
correct answers. We believe that the statistical patterns implicitly present
in the pre-trained text corpus is known to provide the model with a few innate
priors and experience and is a possible explanation for its performance on
few-shot learning methods such as the GPT-$3$ model (b10, ; b13, ).

In regard to commonsense and arithmetic reasoning tasks (b24, ; b28, ; b29, )
large-language models (LLMs) such as GPT-3, Flacon, Llama achieve excellent
performance on these tasks while fails to achieve good generalization as the
model size is decreased. This leads to misrepresentation of knowledge and
factual data in LMs.

###  1.1. Contribution

In this regard, we evaluate the GPT-neo model in a relatively low-parameter
regime, and subsequently, we gauge its performance in comparison to other
baselines with larger model size. Our main contribution in this paper is as
follows:

  * •

We investigate the generalization capabilities of the GPT-neo model through
the commonsense reasoning lens. In particular, we employ a supervised learning
objective discussion and test the model on a suite of $6$ tasks, namely Piqa,
Winogrande, Hellaswag, Storycloze, BoolQ and OpenBookQA.

  * •

We conduct adequate comparisons with competitive baselines such as GPT-$3$,
Llama and Falcon for all our tasks in both zero-shot setting and fine-tuning
methods.

  * •

We also conduct extensive robustness tests and visualisations to assess its
ability for in-context learning and examine the overfitting concerns in
Section $3$ & $4$ respectively.

Our main goal is not to demonstrate state-of-the-art results but to show that
the GPT-neo model is competitive with its counterpart, such as the GPT-$3$
model, even though it is much smaller by a factor of $64x$.

##  2\. Can LLMs Reason?

As discussed in (b53, ; b54, ), reasoning encompasses the ability of LMs for
deduction, induction, abduction, analogy, commonsense and systematic methods
for rational problem solving in multi-steps of inference. This enables the
model with abstraction \- allowing for the model to generalize to unseen test
examples.

While LLMs are not trained explicitly to reason, it is more often an emergent
behaviour where the model mimics true reasoning abilities through less robust
and generalizable mechanism - such as memorization or pattern matching using
the contexts seen in the training data.

For example, (b55, ) examines the in-context performance of GPT-$3$ on
arithmetic tasks. They assess the model performance as a function of the
frequency of the test samples in the training set. They observe that the model
performs significantly lower for numbers not present in the training data and
that thus lack the general ability to perform arithmetic. In addition, they
demonstrate that superior performance on these tasks is rely largely on
memorization and mimics reasoning-like abilities by matching patterns present
in the pre-training data.

Similarly, to test the memorization hypothesis, (b56, ) construct
”counterfactual tasks” to assess if LMs perform faithful reasoning on
commonsense and arithmetic tasks. Their results reveal degradation in
performance on several counterfactual tasks and they attribute this gap to
overfitting and absence of generalization, even though it requires the same
reasoning ability as the original task.

##  3\. MODEL GENERALIZATION

(b3, ) defines generalization as the sensitivity to abstract analogies and
thus requires a series of intermediate reasoning steps for complex downstream
tasks. It involves adapting to novel situations by converting past experience
into future skills. In this regard, neural networks are long known to perform
well as function approximators on smooth (continuous) data manifolds without
any discontinuities using gradient descent methods. Thus, this paper is an
attempt in this direction to explore at least a few of these intuitive
questions by resorting to the commonsense reasoning benchmark as a standard of
measure in all our experiments.

It is believed that the success of LLMs is mainly due to in-context learning:
the ability to predict later tokens is easier because the auto-regressive
model can now utilize the data present in-context i.e., the earlier tokens in
the input data ($x_{i-1}$) itself (b35, ) and induction heads: mainly prefix
matching (similar to skip-grams) and thus increases the logits of attended
tokens (b36, ). This is known to drive meta-learning and the models ability to
extract useful information from earlier context allowing information to move
forward to attention heads in the subsequent layers.

In a recent work, (b48, ) investigate the trajectory of the training process
in masked language models (MLMs) to understand the phase transitions and
specialised attention heads for emergent behaviour at different points in
training. In particular, they introduce Syntactic Attention Structure to
examine the learning of complex linguistic phenomenon in MLMs which leads to
model interpretability.

Likewise, (b49, ) introduce distributional simplicity bias that identify the
features of the training data that influence the network. They argue that
neural networks learn higher order statistics and correlations only later in
the training process which deviates from the general conception of model
progression from linear to non-linear functions during stochastic gradient
descent training.

(b32, ) study in-context learning using selection algorithms of LLMs on
various generation tasks for multiple input sequences without explicit
prompting of the right task. This also allows for meta-learning and adapting
the parameter initialization within few epochs of fine-tuning on downstream
tasks.

It is observed that as the model size increases, the network can learn
concepts that they pass on to downstream tasks and thus generalise to unseen
instances than those seen during training through transfer learning as
discussed in (b10, ; b14, ; b22, ). However, (b19, ) postulate the model-wise
double descent phenomenon where, as we increase the model size the performance
first decreases i.e., a U-like behaviour and then increases on the test data.
The former behaviour is expected because of the classical bias-variance
tradeoff from statistical learning theory given as:

$MSE=bias^{2}+variance$

where $MSE$ is the mean-squared error. Thus, larger models exhibit lower bias
with higher variance. Therefore, as the model size increases beyond a certain
threshold called the over-parameterization regime, we expect the
generalization error on the test dataset to increase while (b19, ) argues that
neural networks exhibit the opposite i.e., the generalization error decreases
with increase in model complexity.

(b23, ) examined the the models robustness with increasing capacity under
projected-gradient descent adversarial examples. They observed that as beyond
a certain point as we increase the size of the network there is a sharp
transition in the model behaviour with steady increase in the training
accuracy under strong adversaries.

Likewise, (b20, ) observes that in the over-parameterization regime i.e., when
the model complexity is large enough to cause zero training error leads to a
decrease in the average test error and the performance of the worst group
error i.e., the minority samples. The best worst-group error was observed for
model with in the underparametrized regime with non-zero training error. This
is attributed to the memorization of the minority samples in the training set
and thus leads to poor generalization on unseen examples.

One way to test GPT-neo’s ability in the fine-tuning phase with limited
dataset constraints is through simple commonsense reasoning tasks, which
requires recognizing a novel pattern that is unlikely to have occurred during
pre-training and thus adapting quickly to the given task.

We demonstrate the effectiveness of our approach on a diverse array of tasks
for natural language understanding. The results show that the model leverages
the feature representations learned during unsupervised pre-training for
larger performance gains during downstream tasks.

Figure 1. Input format for GPT-neo architecture for multiple-choice task.
Start and delim indicates the start and delimiter token respectively.

Winogrande |  The trophy doesn’t fit into the brown suitcase because the __ is too large.
---|---
|  Choice 1. Trophy Choice 2. Suitcase
Piqa |  To make a tomato sauce taste more like a pizza sauce,
|  Choice 1. Mix extra paprika into the sauce to brighten the flavor.
|  Choice 2. Mix a little bit of sugar into the sauce to sweeten it.
HellaSwag |  Making a cake: Several cake pops are shown on a display. A woman and girl are shown making
|  Choice 1. Bake them, then frost and decorate.
|  Choice 2. Taste them as they place them on plates.
|  Choice 3. Put the frosting on the cake as they pan it.
|  Choice 4. Come out and begin decorating the cake as well.
StoryCloze |  I was walking to my house after riding the school bus. When I arrived at the front, I tried to open
|  the door. The door was locked. When I tried to look for my keys, I couldn’t
find them anywhere.
|  Choice 1. I then found my spare key and entered.
|  Choice 2. I was locked out and had to move to a new home.
BoolQ |  In Australia, each state has its own constitution. Each state constitution preceded the
|  Constitution of Australia as constitutions of the then separate British
colonies, but all the states
|  ceded powers to the Parliament of Australia as part of federation in 1901.
|  Question: Does each Australian state have its own constitution?
|  Answer: True
OpenBookQA |  Context: A stem is used to store water by some plants.
|  Question: Stems are to flowers as
|  Choice 1. Dogs are to cats.
|  Choice 2. Cows are to cud.
|  Choice 3. Bees are to pollen.
|  Choice 4. Silos are to grains.

Table 1. An example is specified for each of the tasks used for evaluating the
GPT-neo model with the correct answer choice indicated using the bold mark.

###  3.1. Related Work

Recent work on evaluation of LLMs for commonsense natural language inference
has garnered significant attention for larger models under zero-shot and few-
shot settings. (b40, ) conduct a comprehensive examination on four commonsense
benchmark tasks. Similarly, (b43, ) study LLMs under zero-shot settings and
strong supervision, where they assess the model performance under various
design choices such as input format and score function to better understand
scaling laws of large models on NLI tasks.

(b44, ) examine the proficiency of language models for transfer learning
capabilities on downstream tasks using intermediate pre-training and adapter-
based methods. Similarly, (b45, ) introduces a weak supervision method for
incorporating prompts into answer choices for effective knowledge transfer
using a question-answering format i.e., using noisy predictions to get final
predictions on commonsense benchmark tasks.

In contrast, our work is focused on assessing the performance of smaller
language models against larger models and we also conduct numerous robustness
tests and visualisation to investigate the discrepancy between these models as
the size increases.

Our choice for evaluation of the GPT-neo model is motivated by the use of
local and linear self-attention (b37, ), Mixture of Experts (MoE) (b38, ) and
axial positional embeddings (b39, ) in the model architecture which aids in
better in-context learning and also lesser computational overhead while
training on TPUs.

##  4\. Dataset

Commonsense tasks provide a way to understand the model’s capability to
interpret complex structural patterns that are not explicitly mentioned in the
input text and are not part of the pre-trained data. The commonsense reasoning
ability of large pre-trained models largely depends on the dataset quality and
requires high levels of abstract reasoning capabilities to solve these tasks
(b34, ; b35, ). These tasks include reading-comprehension, question-answering,
sentence completion and classification. For multiple-choice tasks, we
concatenate the context, question, and answer choice for each example to
obtain $k$ different such sentences ($k$ choices) and pass it as input to the
model as shown in Figure 1. We compute each choice’s probability and the
softmax scores from their logit values.

For our experiments, we consider six diverse standard commonsense reasoning
benchmark datasets (see Table 1) and examine how well the model adapts to each
of these tasks.

For example, in the sentence, ”The corner table in a restaurant ordered a
beer. The waiter served them the drink”. Humans can quickly establish that it
is the people at the corner table that ordered the beer, and them refers to
the people and not the corner table because we humans have a hard-coded notion
of what people are. On the other hand, language models cannot quickly capture
such implicit information or knowledge and hence fall back significantly on
these tasks. Although relatively trivial for humans, these tasks are extremely
hard for machines that merely rely on statistical patterns without proper
understanding and abstraction capabilities. This paper shows that popular
approaches to large-scale language pre-training, while highly successful on
many abstract tasks, fall short when a physical world model is required.

###  4.1. Winogrande

Winogrande (b4, ) is inspired by the ”Winograd Schema Challenge” with
increased task complexity. It consists of constructing two identical questions
with two answer choices such that it includes a trigger word which flips the
corresponding answer questions. The task is to find a suitable entity for the
pronoun. The training set consists of $44$k examples. Ex: ”The Trophy doesn’t
fit into the brown suitcase because the $trophy^{*}/suitcase$ is too large”.
Here, predicting what blank requires the inference regarding the relative size
of the trophy and the suitcase.

###  4.2. Piqa

PIQA (b6, ) (Physical Interaction Question Answering) dataset is used to
evaluate language representations and their knowledge about our physical
world. This dataset describes how an object is built, used, or operated, which
requires physical reasoning capabilities to select the right choice. It
consists of over $16k$ training question-answering pairs, with an additional
$2k$ and $3k$ validation and test examples respectively. As shown in Table 1,
the prediction of right choice as ”mix extra paprika into the sauce to
brighten the flavor”, requires in-context learning and establishing coherent
relations between tomato sauce, paprika and the pizza sauce.

###  4.3. StoryCloze

Story Cloze (b7, ) dataset involves selecting a plausible ending to a long
story which is framed as a multiple-choice question consisting of $2$ answer
choices. It consists of $4k$ examples, which are based on everyday events of
daily life. It helps evaluate the extent to which the model learns causal and
temporal relations between different entities within the given context.

###  4.4. HellaSwag

HellaSwag (b8, ) is a commonsense natural language inference task with a data
format similar to the Swag dataset but of higher quality. The hellaswag
dataset involves picking the best ending for a story. For each input question,
the model is presented with the context from a caption and four choices to
predict a what might happen next in a coherent way. It contains a total of
$50k$ sentences with an average length of $230$-word tokens.

###  4.5. BoolQ

BoolQ is a question-answering dataset with yes/no answer choices containing
$16k$ examples. Each example consists of a reading comprehension, question and
an answer, with the title as additional context. The task entails various
inferences to be drawn from the passage to find the correct answer choice,
since the questions are generated in unprompted and unconstrained setting. In
Table 1, inferring the answer choice requires establishing adequate casual
relations between the consitution of australia and the federation act in 1901.

###  4.6. OpennBookQA

OpenBookQA is an advanced question-answering task used for commonsense NLI and
consists of a $6k$ examples. It is modeled as an open-book exam where each
example consists of a set of elementary science facts (context), a question
and $4$ answer choices. As shown in Table 1, predicting the right choice
requires a deeper understanding of the input text comprehension and a general
commonsense knowledge to logically connect the facts presented as context and
establish the analogy as ”silos are to grains”.

##  5\. Model

The GPT-neo model was released by Eleuther AI. The GPT-neo model is a
transformer-based decoder-only autoregressive language model that uses a
causal self-attention mechanism to learn contextual representations of
individual word tokens. The GPT-neo was pre-trained using the standard
language modeling objective: next token prediction using causal self-
attention. The objective is to maximize the log-likelihood of the data given
as:

$L(\theta)=\sum_{i}\log p(x_{i}|x_{i-1},...,x_{2},x{1};\theta)$

where $p$ the conditional probability of $x_{i}$ given its context
$\left\\{x_{i}\right\\}_{i=1}^{i-1}$ which is modeled using the GPT-neo model
with parameters $\theta$. The model is trained using gradient descent method.

The GPT-neo model is similar to the GPT-$3$ model but with key differences. It
was pre-trained using on the Pile dataset (b1, ) with consists of a diverse
collection of $22$ high-quality datasets derived from numerous sources and
with a similar performance boost compared to the GPT-$3$ models pre-trained on
the common crawl dataset as the model size increases. This includes several
datasets such as the books$3$, Pile-CC and DM-Mathematics and shows
significant gains when fine-tuned on downstream tasks.

Figure 2. GPT-neo architecture for multiple-choice task.

We adapt the model parameters to the supervised learning task. Let
$\mathcal{C}=\left\\{x_{i},y_{i}\right\\}_{i=1}^{m}$ denote the set of $m$
training examples. The objective is to maximize the conditional probability
$P(y|x)$ over the entire training set given as:

$l(\mathcal{C})=\sum_{(x,y)}\log P\left(y\mid x^{1},\ldots,x^{m}\right)$

First, the input tokens are passed through the model to obtain the final
transformer block’s activation $h_{l}$ and is then fed to a linear classifier
to get model predictions $P_{i}$ given as:

$\displaystyle h_{0}$ $\displaystyle=AW_{e}+W_{ps}$ $\displaystyle h_{l}$
$\displaystyle=\operatorname{transformer}\\_\text{block
}\left(h_{l-1}\right)\forall i\in[1,n]$ $\displaystyle P(i)$
$\displaystyle=\operatorname{softmax}\left(h_{n}W_{e}^{T}\right)$

where $A$ is the context vector for tokens, $W_{e}$ is the embedding matrix
and $W_{ps}$ is the positional-encoding matrix. We are primarily interested in
evaluating: (1) the accuracy and (2) the cross-entropy loss on the test
dataset given as:

$\mathcal{L}=-\sum_{i=1}^{d}y_{i}\log\hat{y_{i}}$

where $y_{i}$ and $\hat{y_{i}}$ correspond to the true and predicted class
labels respectively. We also examine the model robustness under adversarial
attacks at sentence-level and visualize the attention maps in Section 3 and 4
respectively.

##  6\. Baselines

We compare the performance of the GPT-neo model with several model baselines.
The GPT-3 model is our primary choice since it offers similar choices in model
sizes ($125$M, $350$M, $1.5$B & $2.7$B) for comparison against the GPT-neo
model. We evaluate the GPT-$3$ model under zero-shot and few-shot settings for
all our tasks and utilize the standard hyperparameters as discussed in (b10,
).

We also assess the model performance against a family of pre-trained LLMs such
as MPT ($7$B), Falcon ($7$B), Llama ($7$B & $13$B) and GPT-J ($6$B) in both
zero-shot setting and discriminative fine-tuning for adequate model
comparisons. We also utilize bidirectional language models such as BERT-base
($110$M) and BERT-large ($340$M) and report its accuracy scores for all our
tasks as shown in Table 2 $\&$ 5.

Method M | MPT | Falcon | Llama-1 | Llama-2 | Fairseq | GPT-3 Zero Shot | GPT-3 Few Shot | GPT-J | BERT | BERT-L | GPT-Neo
---|---|---|---|---|---|---|---|---|---|---|---
| 7B | 7B | 7B | 13B | 7B | 13B | 125M | 1.3B | 2.7B | 13B | 125M | 350M | 1.3B | 2.7B | 13B | 125M | 350M | 1.3B | 2.7B | 13B | 6B | 110M | 340M | 125M | 350M | 1.3B | 2.7B
Piqa | 79.3 | 75.4 | 78.1 | 80.0 | 78.0 | 80.3 | 66.1 | 72.3 | 75.0 | 75.6 | 63.5 | 69.1 | 74.1 | 74.6 | 78.4 | 62.3 | 68.1 | 73.2 | 74.9 | 78.6 | 76.1 | 66.1 | 65.9 | 62.0 | 64.0 | 69.1 | 71.1
BoolQ | 74.9 | 66.5 | 74.5 | 77.1 | 76.9 | 80.6 | 55.9 | 57.6 | 60.2 | 64.1 | 48.6 | 59.8 | 61.4 | 66.5 | 65.7 | 42.9 | 59.4 | 63.7 | 69.2 | 69.1 | 71.1 | 76.2 | 61.9 | 42.6 | 46.7 | 53.7 | 59.3
Hellaswag | 75.9 | 73.7 | 75.4 | 71.2 | 76.9 | 79.6 | 29.1 | 43.7 | 48.4 | 54.4 | 32.7 | 41.7 | 54.1 | 62.1 | 69.0 | 32.4 | 42.7 | 53.4 | 61.3 | 70.5 | 65.7 | 39.4 | 45.1 | 28.1 | 30.1 | 38.6 | 41.6
Winogrande | 67.9 | 65.8 | 69.1 | 72.0 | 68.2 | 71.7 | 50.0 | 60.2 | 61.5 | 66.5 | 51.9 | 51.1 | 56.5 | 61.8 | 68.0 | 50.2 | 51.5 | 58.1 | 61.5 | 67 | 63.3 | 60.2 | 62.9 | 50.0 | 51.1 | 54.0 | 55.5
Storycloze | 82.9 | 80.3 | 81.1 | - | 82.6 | - | 65.0 | 70.9 | 75.8 | 76.2 | 62.3 | 66.5 | 72.4 | 74.2 | 74.1 | 61.5 | 68.2 | 75.1 | 79.2 | 82.3 | 55.3 | 65.4 | 80.5 | 45.6 | 51.0 | 54.7 | 59.2
OpenBookQA | 50.4 | 51.6 | 56.1 | 55.3 | 57.4 | 56.0 | 34.0 | 48.9 | 48.5 | 54.1 | 31.6 | 40.2 | 45.8 | 51.0 | 54.9 | 36.0 | 42.6 | 49.5 | 54.2 | 59.8 | 50.2 | 52.1 | 61.4 | 35.5 | 39.2 | 42.2 | 46.3

Table 2. Test accuracy for commonsense reasoning tasks using the GPT-neo model
and model baselines. The best performer across all methods is denoted using
the bold mark (excluding model size $\geq 6$B parameters). For ease of
comparison, we color the second best performer with  blue color.

##  7\. Experimental Setting

In this section, we give a general overview of the training procedure used for
fine-tuning both GPT-neo and the baseline models. We perform all our model
fine-tuning using Google Cloud TPU- VMs using the TPU-V8 accelerators. We use
the JAX framework for model training and evaluation and obtain significant
training speed boost-up using vmaps and pmaps for vectorisation and
parallelisation on multiple devices. We train the models for $7$ epochs and
use a fixed random seed throughout our experiments. We also add a dropout of
$0.2$ for regularization. We use the byte pair encoding (BPE) tokenization
scheme with a vocab size of $50257$ tokens.

For all our tasks, we use the adafactor optimizer with a learning rate of
$2e-5$ to $3e-7$ and do not use gradient clipping. We use a linear learning
rate decay schedule with warm-up over $0.1\%$ of training, and the value
annealed $3e-7$. We slightly deviate from the standard approach used in
GPT-$3$, where we use the maximum length of the input tokens for padding the
input sequences. This does not affect the model performance and also results
in a reduced memory footprint on the TPU accelerators.

We use a batch size ($k$) of $32$ i.e., $4$ examples on each device. Also
through experiments on various batch sizes ranging from $k=[8,16,32]$ and
conclude that the $32$ version outperforms significantly when experimented for
each of our datasets.

Parameter | Value
---|---
$n_{heads}$ | $16$
$n_{layers}$ | $24$
$d_{model}$ | $768$
$n_{linear}$ | $2048$
$d_{vocab}$ | $50257$
Table 3. Training Parameters used for GPT-neo model training.

In this section, we assess GPT-neo’s performance on a suite of commonsense
reasoning benchmark tasks that involve sentence completion, mulitpl-choice
natural language inference, using the setting discussed in Section 7. We also
report the model scores for baselines (Section 6) to ensure comparisons across
numerous model sizes.

Figure 3 compares the performance gap of the GPT-neo model against random
baselines for all our tasks. The random baseline is the GPT-neo model without
discriminative fine-tuning where the probability of choosing the correct
answer choice is given as $p(y|x)=1/k$ where $k$ is the number of choices.

##  8\. Results

Figure 3. Performance comparison of GPT-neo model and Random baselines for
each of our task.

In the following section, we present our results across for all the tasks
discussed in Section 4. Please note that we exclude the results for the $13$B
parameter model in the following discussion, as our largest model is of size
$2.7$B parameters. However, the results for the $13$B parameter model are
presented in Table 2 for reference.

###  8.1. Winogrande

We evaluate our results on the Winogrande test dataset and obtain an accuracy
of $55.5\%$ which is competitive with the GPT-$3$ model. We also observe that
the model accuracy shows improved performance with an $5.5\%$ increase in
accuracy as the size increases from $125$M to $2.7$B model parameters.
However, we observe that the GPT-$3$ few-shot and BERT-large model achieve the
Top-$2$ accuracy of $61.8\%$ and $62.9\%$ respectively (excluding models $\geq
6$B), which is attributed to their large model size.

###  8.2. Piqa

Here, we achieve an accuracy of $71.1\%$ upon fine-tuning, which is only
slightly lower than the GPT-3 few-shot and the Fairseq model by $4\%$. We
observe that the model is competitive with both the Fairseq and GPT-3 model as
the model size is increased and achieves a performance drop of $4\%$ and $8\%$
with respect to the Falcon and the MPT model respectively.

###  8.3. HellaSwag

We obtain an accuracy of $41.6\%$ on the Hellaswag dataset which is our worst
performance among all the tasks. The GPT-$3$ model significantly outperform
our model by $19\%$ in both the zero-shot and few-shot setting. For model size
of $13$B, Llama-$1$ and Llama-$2$ obtain excellent results with a model best
accuracy of $79.6\%$ which is $9\%$ higher than the GPT-$3$ few-shot results.

###  8.4. StoryCloze

On the StoryCloze dataset, our model achieves an accuracy of $59.2\%$. In
contrast to HellaSwag, the GPT-$3$ model outperforms the GPT-neo model by a
margin of $15-18\%$, even when considering both the $125$M and $350$M
versions. Surprisingly enough the Fairseq model demonstrates better
performance compared to the GPT-$3$ few-shot model for model sizes of $125$M
and $350$M. However, GPT-$3$ excels in performance as its model size scales
beyond $1$B parameters, achieving the highest accuracy of $82.3\%$ in the few-
shot setting.

###  8.5. BoolQ

On this task, GPT-neo achieves an accuracy rate of $59.3\%$, while Llama-$2$
attains a significantly higher accuracy rate of $80.6\%$. While the model’s
performance remains competitive compared to the GPT-$3$ few-shot model with
$125$M parameters, exhibiting only a marginal difference of $0.3\%$, it
becomes evident that as model size increases, GPT-$3$ rapidly adapts to the
task, showcasing a substantial $17.5\%$ performance improvement when
transitioning from the $125$M to the $350$M model. In contrast, GPT-neo
demonstrates a comparatively modest increase of $4.5\%$ over the same
transition.

###  8.6. OpenBookQA

We obtain an accuracy of $46.3\%$ on our largest model which is comparable
with the Fairseq model but the GPT-$3$ model is still better by $8\%$ in the
few-shot setting. We also observe that BERT-large which contains just $340$M
parameters obtains the highest accuracy of $61.4\%$ among all the models.
Larger models such as MPT and Falcon obtain accuracy of $50.4\%$ and $51.6\%$
which is higher than the GPT-neo model by only $4\%$. The attention head
visualization for the example presented in Table 1 is discussed in Section 10.

We also report the mean accuracy scores for all the models reported in Table 5
with model size greater size $20$B parameters. Since, these models are
computational expensive and results in memory-overhead, we do not perform
these supervised fine-tuning for models $\geq 20$B parameters, but report
their scores from the literature (b10, ; b26, ; b27, ; b42, ; b45, ). We also
include our original GPT-neo results from Table 2 for comparisons with larger
models. As expected the performance exhibits a significant and consistent
improvement as the model size increases across all benchmark tasks.

##  9\. Robustness Test

Figure 4. Reframed sentences-we construct additional samples by modifying the
original sentence or its answer choice, which is used to test the model during
inference time.

(b22, ) examine a universal law of robustness where they state that to truly
memorize the dataset (in the sense of low training error i.e.,
$L_{train}<<\epsilon$, where $\epsilon\rightarrow 0$) and to do so robustly
(measured using the Lipschitz 111A function $f:R^{d}\rightarrow R$ is
$L$-Lipschitz with respect to the norm $\|.\|$ if $\forall x,y\in
R^{d},|f(x)-f(y)|/\|x-y\|\leq L$.  constant $L$), requires that:

$p\geq nd$

where $p$ is the number of model parameters, $n$ is the number of high-
dimensional data points and $d$ is the ambient input dimension respectively.
This is called dramatic overparametrization.

We are mainly interested in evaluating if our results are robust to the
possibility that one of our assumptions might not be accurate. We perform the
robustness test on a few examples to examine GPT-neo ability to learn the
right semantics at token-level.

We follow the conventional dual text instance method as discussed in (b12, ;
b42, ) by constructing a distorted sentence using the original test sample and
thus inferring the robustness measure.Note that we perform the robustness
tests for both these examples in-context i.e., predictions at the sentence-
level. Each task involves the addition of noise into the original sentences by
means of addition, deletion and replacing of adequate word tokens and then
predict the similarity scores between both these sentences with respect to the
input context.

Method M | Piqa | BoolQ | HellaSwag | Storycloze | Winogrande
---|---|---|---|---|---
Addition | 90 | 81 | 81 | 94 | 74
Subtraction | 80 | 62 | 63 | 85 | 62
Replace | 92 | 71 | 84 | 93 | 75
Swap | 96 | 67 | 66 | 91 | 67

Table 4. Estimation accuracy (in %) for robustness tests across all the tasks.

Dataset M | MPT | Falcon | Llama-1 | Llama-2 | GPT-3 | GPT-Neo X | GPT-Neo | Human
---|---|---|---|---|---|---|---|---
| 30B | 40B | 33B | 65B | 70B | 175B | 20B | 2.7B |
Piqa | 81.9 | 82.4 | 82.3 | 82.8 | 82.8 | 82.3 | 78 | 72.14 | 94.09
BoolQ | 79.0 | 83.1 | 83.1 | 85.3 | 85.0 | 77.5 | - | 57.3 | 90.0
Hellaswag | 79.9 | 83.6 | 82.8 | 84.2 | 85.3 | 79.3 | 71.2 | 42.73 | 95.6
Winogrande | 71 | 76.9 | 76 | 77 | 80.2 | 77.7 | 66.5 | 56.5 | 94.1
OpenBookQA | 52.0 | 56.6 | 58.6 | 60.2 | 60.2 | 65.4 | 32.6 | 56.5 | 92.0
Storycloze | - | - | - | - | - | 87.7 | - | - | 91.5

Table 5. Performance comparison of Large language models ($\geq 20$B) from the
literature. We follow similar convention as that in Table 2.

For each of the robustness task, we create $100$ test samples using random
sampling from the test dataset and forming a pair of coherent test sentences,
testing for consistent results (defined as $\%$ of test samples with accurate
predictions on both the original and distorted sentences) across all the
instances, and report their mean accuracy scores in Table 4.

The goal of this task is to ascertain accurate predictions of the answer
choice that corresponds to the original sentence when the distorted sentence
maintains logical coherence, while allowing a random selection otherwise such
as the subtraction task. We test the model’s capabilities on four tasks given
as follows:

  1. (1)

Addition: Addition of words to its sentences, such that they are semantically
equivalent, and is required to output the same answer choice for both the
sentences.

  2. (2)

Subtraction: The polarity of the sentence is reversed to negate its semantic
meaning, wherein the sentences contradict each other while the answers choices
for both the original and new sentence remains the same.

  3. (3)

Swap: The role of each noun swapped with one another and is expected to pick
the right choices by contextual inference by identifying the roles of each
noun respectively.

  4. (4)

Replace: We replace its word tokens so that they are logically coherent and
should output the right choice depending on the context presented in the
sentence.

Figure 5. Samples used for measuring the robustness of the GPT-neo models
using various methods such as addition, subtraction, swapping, and replacing.
We use two sentences here to indicate the original (first row) and distorted
(second row) samples, and the model accurately predicts the positive sentence
and as correct or incorrect predictions for the negative sentence.

In Table 4, we present the mean estimation accuracy of the robustness test for
various datasets. The reported accuracies correspond to the predictions
obtained using the GPT-neo model in a zero-shot setting without further fine-
tuning on the additional distorted test samples. The Piqa and Storycloze
dataset performs consistently well when tested under different settings on all
our tasks with accurate predictions. However, Hellaswag demonstrated strong
performance in two specific tasks i.e., add and replace while exhibits a
considerable drop in accuracy for the remaining tasks.

Likewise the performance on Boolq and Winograde dataset is somewhat degraded,
with some overfitting concerns and its inability to adapt to the given
context. A closer inspection of the incorrect responses reveals that the model
frequently struggles to infer contextual meanings and at times is insensitive
to such changes for both positive and negative sentences. Overall, GPT-neo
displays reasonable proficiency when probed at various zero-shot settings for
atleast a few of these tasks. 222We do not report robustness test scores on
the OpenBookQA dataset because plausible modifications to the original
sentence was not possible while preserving the semantics with respect to the
answer choices.

##  10\. Visualization

Figure 6. Attention head for GPT-neo model Layer $6$ for the example in the
HellsSwag dataset as discussed in Table 1.

In this section, we visualise the attention pattern using the GPT-neo model
for sentence completion tasks using the source and destination token. We
visualise the overall attention pattern and individual attention heads for a
few examples as shown in Figure 6 $\&$ 7. We are mainly interested in
understanding in-context learning and induction heads i.e., a composition of
attention heads that work together to copy patterns. It is observed that the
lower layers of transformer models capture global token dependencies across
multiple tokens which enables the transfer of relevant information across
layers and thus predict the correct answer choice (b50, ; b51, ).

Figure 7. Attention head for GPT-neo model Layer $6$ for the example in the
OpenBookQA dataset as discussed in Table 1.

In Figure 6 $\&$ 7, we observe previous token attention heads that simply
attend back to the preceding token and also first token heads that fall back
to the first token and do nothing as discussed in (b50, ). In comparison, we
also find specialized attention heads i.e., the pattern is diagonal while most
heads have no clear identifiable structure. In Figure 8, we demonstrate an
interesting hook in the attention pattern activation for the relevant head as
discussed in (b52, ).

Figure 8. Attention hook for GPT-based LLMs as demonstrated in (b52, ).

##  11\. Limitation

Although, we conduct the examination of the GPT-neo model, we understand that
we comparisons are not exhaustive in terms of datasets considered and the
ablation studies for understanding the model performance using robustness
tests. Likewise, due to limited computational resource availability, we were
unable to perform extended model training for for more epochs and supervised
fine-tuning on large models in particular for the Storycloze dataset. In our
subsequent work, we hope to extend this further to probe smaller models for a
larger class of datasets with interpretable results. We hope our work provides
some preliminary motivation and understanding on the impact of smaller models
in the purview of larger models.

##  12\. Conclusion

In this work, we illustrate the commonsense reasoning capabilities of the GPT-
neo model on a suite of $6$ diverse tasks. Furthermore, we incorporated
various model baselines for comparative analysis and have demonstrated that
the GPT-neo model delivers competitive performance on several tasks as the
model size is increased. We also investigated the model using attention head
visualization and conducted robustness tests to better understand the model
performance under various settings.

##  13\. Acknowledgments

We thank the anonymous reviewers for their review and suggestions.

## References

  * (1) Gao, Leo, et al. ”The pile: An 800gb dataset of diverse text for language modeling.” arXiv preprint arXiv:2101.00027 (2020).
  * (2) Vaswani, Ashish, et al. ”Attention is all you need.” Advances in neural information processing systems 30 (2017).
  * (3) Chollet, François. ”On the measure of intelligence.” arXiv preprint arXiv:1911.01547 (2019).
  * (4) Sakaguchi, Keisuke, et al. ”Winogrande: An adversarial winograd schema challenge at scale.” Communications of the ACM 64.9 (2021): 99-106.
  * (5) Rajani, Nazneen Fatema, et al. ”Explain yourself! leveraging language models for commonsense reasoning.” arXiv preprint arXiv:1906.02361 (2019).
  * (6) Bisk, Yonatan, et al. ”Piqa: Reasoning about physical commonsense in natural language.” Proceedings of the AAAI conference on artificial intelligence. Vol. 34. No. 05. 2020.
  * (7) Mostafazadeh, Nasrin, et al. ”A corpus and evaluation framework for deeper understanding of commonsense stories.” arXiv preprint arXiv:1604.01696 (2016).
  * (8) Zellers, Rowan, et al. ”HellaSwag: Can a machine really finish your sentence?.” arXiv preprint arXiv:1905.07830 (2019).
  * (9) Huang, Lifu, et al. ”Cosmos QA: Machine reading comprehension with contextual commonsense reasoning.” arXiv preprint arXiv:1909.00277 (2019).
  * (10) Brown, Tom, et al. ”Language models are few-shot learners.” Advances in neural information processing systems 33 (2020): 1877-1901.
  * (11) Devlin, Jacob, et al. ”Bert: Pre-training of deep bidirectional transformers for language understanding.” arXiv preprint arXiv:1810.04805 (2018).
  * (12) Zhou, Xuhui, et al. ”Evaluating commonsense in pre-trained language models.” Proceedings of the AAAI Conference on Artificial Intelligence. Vol. 34. No. 05. 2020.
  * (13) Radford, Alec, et al. ”Language models are unsupervised multitask learners.” OpenAI blog 1.8 (2019): 9.
  * (14) Kaplan, Jared, et al. ”Scaling laws for neural language models.” arXiv preprint arXiv:2001.08361 (2020).
  * (15) Wei, Jason, et al. ”Chain of thought prompting elicits reasoning in large language models.” arXiv preprint arXiv:2201.11903 (2022).
  * (16) Wei, Jason, et al. ”Finetuned language models are zero-shot learners.” arXiv preprint arXiv:2109.01652 (2021).
  * (17) Reed, Scott, et al. ”A generalist agent.” arXiv preprint arXiv:2205.06175 (2022).
  * (18) Frei, Spencer, Niladri S. Chatterji, and Peter Bartlett. ”Benign overfitting without linearity: Neural network classifiers trained by gradient descent for noisy linear data.” Conference on Learning Theory. PMLR, 2022.
  * (19) Nakkiran, Preetum, et al. ”Deep double descent: Where bigger models and more data hurt.” Journal of Statistical Mechanics: Theory and Experiment 2021.12 (2021): 124003.
  * (20) Sagawa, Shiori, et al. ”An investigation of why overparameterization exacerbates spurious correlations.” International Conference on Machine Learning. PMLR, 2020.
  * (21) Liu, Ruibo, et al. ”Mind’s Eye: Grounded Language Model Reasoning through Simulation.” arXiv preprint arXiv:2210.05359 (2022).
  * (22) Bubeck, Sébastien, and Mark Sellke. ”A universal law of robustness via isoperimetry.” Advances in Neural Information Processing Systems 34 (2021): 28811-28822.
  * (23) Madry, Aleksander, et al. ”Towards deep learning models resistant to adversarial attacks.” arXiv preprint arXiv:1706.06083 (2017).
  * (24) Cobbe, Karl, et al. ”Training verifiers to solve math word problems.” arXiv preprint arXiv:2110.14168 (2021).
  * (25) Touvron, Hugo, et al. ”Llama: Open and efficient foundation language models.” arXiv preprint arXiv:2302.13971 (2023).
  * (26) Touvron, Hugo, et al. ”Llama 2: Open foundation and fine-tuned chat models.” arXiv preprint arXiv:2307.09288 (2023).
  * (27) Ott, Myle, et al. ”fairseq: A fast, extensible toolkit for sequence modeling.” arXiv preprint arXiv:1904.01038 (2019).
  * (28) Talmor, Alon, et al. ”Commonsenseqa 2.0: Exposing the limits of ai through gamification.” arXiv preprint arXiv:2201.05320 (2022).
  * (29) Geva, Mor, et al. ”Did aristotle use a laptop? a question answering benchmark with implicit reasoning strategies.” Transactions of the Association for Computational Linguistics 9 (2021): 346-361.
  * (30) Raffel, Colin, et al. ”Exploring the limits of transfer learning with a unified text-to-text transformer.” The Journal of Machine Learning Research 21.1 (2020): 5485-5551.
  * (31) Poggio, Tomaso, et al. ”Why and when can deep-but not shallow-networks avoid the curse of dimensionality: a review.” International Journal of Automation and Computing 14.5 (2017): 503-519.
  * (32) Bai, Yu, Fan Chen, Huan Wang, Caiming Xiong, and Song Mei. ”Transformers as Statisticians: Provable In-Context Learning with In-Context Algorithm Selection.” arXiv preprint arXiv:2306.04637 (2023).
  * (33) Allen-Zhu, Zeyuan, and Yuanzhi Li. ”Physics of Language Models: Part 1, Context-Free Grammar.” arXiv preprint arXiv:2305.13673 (2023).
  * (34) Arora, Sanjeev, and Anirudh Goyal. ”A theory for emergence of complex skills in language models.” arXiv preprint arXiv:2307.15936 (2023).
  * (35) Von Oswald, Johannes, et al. ”Transformers learn in-context by gradient descent.” International Conference on Machine Learning. PMLR, 2023.
  * (36) Olsson, Catherine, et al. ”In-context learning and induction heads.” arXiv preprint arXiv:2209.11895 (2022).
  * (37) Beltagy, Iz, Matthew E. Peters, and Arman Cohan. ”Longformer: The long-document transformer.” arXiv preprint arXiv:2004.05150 (2020).
  * (38) Shazeer, Noam, et al. ”Outrageously large neural networks: The sparsely-gated mixture-of-experts layer.” arXiv preprint arXiv:1701.06538 (2017).
  * (39) Ho, Jonathan, et al. ”Axial attention in multidimensional transformers.” arXiv preprint arXiv:1912.12180 (2019).
  * (40) Zellers, Rowan, et al. ”Swag: A large-scale adversarial dataset for grounded commonsense inference.” arXiv preprint arXiv:1808.05326 (2018).
  * (41) Madaan, Aman, et al. ”Language models of code are few-shot commonsense learners.” arXiv preprint arXiv:2210.07128 (2022).
  * (42) Zhou, Xuhui, et al. ”Evaluating commonsense in pre-trained language models.” Proceedings of the AAAI conference on artificial intelligence. Vol. 34. No. 05. 2020.
  * (43) Li, Xiang Lorraine, et al. ”A systematic investigation of commonsense knowledge in large language models.” Proceedings of the 2022 Conference on Empirical Methods in Natural Language Processing. 2022.
  * (44) Poth, Clifton, et al. ”What to pre-train on? efficient intermediate task selection.” arXiv preprint arXiv:2104.08247 (2021).
  * (45) Arora, Simran, et al. ”Ask me anything: A simple strategy for prompting language models.” arXiv preprint arXiv:2210.02441 (2022).
  * (46) Chung, Hyung Won, et al. ”Scaling instruction-finetuned language models.” arXiv preprint arXiv:2210.11416 (2022).
  * (47) Penedo, Guilherme, et al. ”The RefinedWeb dataset for Falcon LLM: outperforming curated corpora with web data, and web data only.” arXiv preprint arXiv:2306.01116 (2023).
  * (48) Angelica Chen, et al. ”Sudden Drops in the Loss: Syntax Acquisition, Phase Transitions, and Simplicity Bias in MLMs.” arXiv:2309.07311 (2023).
  * (49) Refinetti, Maria, Alessandro Ingrosso, and Sebastian Goldt. ”Neural networks trained with SGD learn distributions of increasing complexity.” International Conference on Machine Learning. PMLR, 2023.
  * (50) Olsson, Catherine, et al. ”In-context learning and induction heads.” arXiv preprint arXiv:2209.11895 (2022).
  * (51) Elhage, Nelson, et al. ”A mathematical framework for transformer circuits.” Transformer Circuits Thread 1 (2021).
  * (52) Nanda, Neel. ”Transformerlens, 2022b.” https://github.com/neelnanda-io/TransformerLens.
  * (53) Mitchell, Melanie, and David C. Krakauer. ”The debate over understanding in AI’s large language models.” Proceedings of the National Academy of Sciences 120.13 (2023).
  * (54) Mitchell, Melanie. ”How do we know how smart AI systems are?.” Science 381.6654 (2023).
  * (55) Razeghi, Yasaman, et al. ”Impact of pretraining term frequencies on few-shot numerical reasoning.” Findings of the Association for Computational Linguistics: EMNLP 2022. 2022.
  * (56) Wu, Zhaofeng, et al. ”Reasoning or reciting? exploring the capabilities and limitations of language models through counterfactual tasks.” arXiv preprint arXiv:2307.02477 (2023).
  * (57) Huang, Jie, and Kevin Chen-Chuan Chang. ”Towards reasoning in large language models: A survey.” arXiv preprint arXiv:2212.10403 (2022).