# Truthful Mechanisms for Secure Communication in Wireless Cooperative System

Jun Deng, Rongqing Zhang, , Lingyang Song, ,
Zhu Han, and Bingli Jiao,
Part of this work has been published in INFOCOM WKSHPS 2011 as given in
[1].Jun Deng, Rongqing Zhang, Lingyang Song and Bingli Jiao are with State Key
Laboratory of Advanced Optical Communication Systems and Networks, School of
Electronics Engineering and Computer Science, Peking University, Beijing,
China (email: {dengjun, rongqing.zhang, lingyang.song, jiaobl}@pku.edu.cn).
Zhu Han is with Electrical and Computer Engineering Department, University of
Houston, Houston, USA (email: zhan@uh.edu).

###### Abstract

To ensure security in data transmission is one of the most important issues
for wireless relay networks, and physical layer security is an attractive
alternative solution to address this issue. In this paper, we consider a
cooperative network, consisting of one source node, one destination node, one
eavesdropper node, and a number of relay nodes. Specifically, the source may
select several relays to help forward the signal to the corresponding
destination to achieve the best security performance. However, the relays may
have the incentive not to report their true private channel information in
order to get more chances to be selected and gain more payoff from the source.
We propose a Vickey-Clark-Grove (VCG) based mechanism and an
Arrow-d’Aspremont-Gerard-Varet (AGV) based mechanism into the investigated
relay network to solve this cheating problem. In these two different
mechanisms, we design different “transfer payment” functions to the payoff of
each selected relay and prove that each relay gets its maximum (expected)
payoff when it truthfully reveals its private channel information to the
source. And then, an optimal secrecy rate of the network can be achieved.
After discussing and comparing the VCG and AGV mechanisms, we prove that the
AGV mechanism can achieve all of the basic qualifications (incentive
compatibility, individual rationality and budget balance) for our system.
Moreover, we discuss the optimal quantity of relays that the source node
should select. Simulation results verify efficiency and fairness of the VCG
and AGV mechanisms, and consolidate these conclusions.

###### Index Terms:

Physical layer security, truth-telling, AGV, VCG

##  I Introduction

Security is one of the most important issues in wireless communications due to
the broadcast nature of wireless radio channels. In recent years, besides the
traditional cryptographic mechanisms, information-theoretic-based physical
layer security has been developing fast. The concept of “wiretap channel” was
first introduced by Wyner [2], who showed that perfect secrecy of transmitted
data from the source to the legitimate receiver is achievable in degraded
broadcast channels. In follow-up work, Leung-Yan-Cheong and Hellman further
determined the secrecy capacity in the Gaussian wire-tap channel [3]. Later,
Csiszar and Komer extended Wyner’s work to non-degraded broadcast channels and
found an expression of secrecy capacity [4].

When considering a wireless relay network, realization of secrecy capacity is
much more complicated. In [5], the authors studied the secrecy capacity of a
relay channel with orthogonal components in the presence of a passive
eavesdropper node. In [6, 7], the authors demonstrated that cooperation among
relay nodes can dramatically improve the physical layer security in a given
wireless relay network, And in [8, 9, 10], the authors investigated the
physical layer security with friendly jammer in the relay networks. In the
related work mentioned above, the channel state information (CSI) is assumed
to be known at both the transmitter and the receiver. All these schemes are
assumed under true channel information reported by relay nodes, and the
optimal solutions in these works will not hold anymore if the fake channel
information is reported. However, in practice, the relay node always measures
its own channel gains and distributes the information to others through a
control channel. There is no guarantee that it reveals its private information
honestly. Hence, the most critical problem is how to select efficient relay
nodes to optimize the total secrecy rate in the network, while some selfish
relays may report false information to the source to increase their own
utilities. In [11], the reputation methods are designed to achieve this goal.
However, all these methods require a delicate and complex “detection scheme”
to monitor and capture the liar nodes. It needs a lot of signal consumption
like an independent entity called “Trust Manager” to runs on each node.
Besides, it also demands large amount of data like “REP_MESSAGE”,“REP_VAL” to
record the intermediate variable in the process. Moreover, this method
requires long time of observation because of low speed of convergence. It
might be impractical to use these reputation based scheme in cooperative relay
network.

In recent years, the game theory is widely applied into wireless and
communication networks to solve resource allocation problems[12, 13, 14, 15,
16, 17]. In the area of mechanism design, a field in the game theory studying
solution concepts for a class of private information games, a game designer is
interested in the game’s outcome and wants to motivate the players to disclose
their private information by designing the payoff structure [18, 19, 20]. For
example, the well-known VCG (Vickrey-Clarke-Groves) mechanism [21, 22, 23] is
a dominant-strategy mechanism, which can achieve ex-post incentive
compatibility (truth-telling is a dominant strategy for every player in the
game). However, it cannot implement the budget balance of the game [24, 25],
which costs extra payment from the players and decrease their payoffs. Thus,
it cannot be properly used in the relay network we focus on. Compared with the
VCG mechanism, the AGV (Arrow-d’Aspremont-Gerard-Varet) mechanism [26, 27] can
also solve the truth-telling problem. It is an incentive efficient mechanism
that can maximize the expected total payoff of all the players in the game.
Additionally it achieves the budget balance under a weaker participation
requirement [28, 29].

In this paper, we mainly focus on a relay network, in which all the channels
are orthogonal and each relay’s private channel information is unknown by
others. Under these conditions, we apply the ideas of the VCG and AGV
mechanism and prove that the transfer function can meet the basic requirements
of the wireless relay networks and help achieve the truth-telling target. We
find and prove that the unique Bayesian Nash Equilibrium [28] is achieved when
all the relays in the network reveal the truth. The incentive to report false
information will lead to a loss in each relay node’s own (expected) payment.
In other words, the competing relay nodes are enforced to obey the selection
criterion and cooperate with each other honestly. Furthermore, there is no
extra cost paid in the system when applying the AGV mechanism while the VCG
mechanism can not. Since the AGV mechanism is budget balanced, which means the
total transfer payment of all relay nodes equals zero. Simulation results show
that the relay nodes can maximize their utilities when they all report their
true channel information. Any cheating to the source leads to certain loss in
the total secrecy rate as well as the payoff of relays themselves. We also
observe that the optimal choice for the system is based on the relays’ channel
information, but in a majority of cases selecting only one relay node for
transmitting data can attain the largest secrecy rate of the system. In
addition, we prove with simulations that the best strategy for each relay node
under this payoff structure is to improve its own channel condition to enlarge
its secrecy rate and always report the truth to the source.

The remainder of this paper is organized as follows. In Section II, the system
model for a relay network is presented. In Section III, we elaborate on the
basic definition and qualifications of the mechanism design, and discuss the
VCG mechanism and AGV mechanism. In Section IV, we demonstrate the mechanism
solutions to enforce relays reveal the true private information, and analyze
these mechanism solutions. Simulation results are shown in Section V, and the
conclusions are drawn in Section VI.

##  II System Model

Figure 1: System model for relay network with eavesdropper.

Considering a general cooperative network shown in Fig. 1. It consists of one
source node, one destination node, one eavesdropper node, and $I$ relay nodes,
which are denoted by $S$, $D$, $E$, and $R_{i}$, $i=1,2,\ldots,I$,
respectively. This cooperative network is conducted in two phases. In phase 1,
the source node broadcasts a signal $x$ to the destination node and all the
relay nodes, where only $N$ $(N\leq I)$ nodes can decode this signal correctly
due to their different geographical conditions. In phase 2, the source node
decides which nodes of those $N$ relays to forword information to the
destination node. The destination node combines messages from the source and
relays, according to the reported channel gains of both relay-destination and
relay-eavesdropper links. During the whole process, eavesdropper node wiretaps
the messages from the source node and the relay nodes. We assume the
orthogonal channel having the same bandwidth $W$. The source node hopes to
gain the highest secrecy rate by properly selecting some efficient relay nodes
based on their reported channel information. We denote the number of selected
relay nodes by $K$ $(K\leq N)$ and the set of $K$ relay nodes by
$\mathcal{K}$.

In the first phase, the received signal $y_{s,d}$, $y_{s,r_{i}}$, and
$y_{s,e}$ at destination node $D$, relays $R_{i}$, and eavesdropper $E$,
respectively, can be expressed as

$\displaystyle y_{s,d}=\sqrt{P_{s}}h_{s,d}x+n_{s,d},$ (1)

and

$\displaystyle y_{s,r_{i}}=\sqrt{P_{s}}h_{s,r_{i}}x+n_{s,r_{i}},$ (2)

and

$\displaystyle y_{s,e}=\sqrt{P_{s}}h_{s,e}x+n_{s,e},$ (3)

where $P_{s}$ represents the transmit power to the destination node from the
source node, $x$ is the unit-energy information symbol transmitted by the
source in phase 1, $h_{s,d}$, $h_{s,r_{i}}$, and $h_{s,e}$ are the channel
gains from $S$ to $D$, $R_{i}$ and $E$ respectively. $n_{s,d}$, $n_{s,r_{i}}$
and $n_{s,e}$ represent the noise at destination node, relay nodes and
eavesdropper node.

In the second phase, the received signal from the $i$-th relay node
$(R_{i}\in\mathcal{K})$ to the destination node and eavesdropper node can be
expressed as

$\displaystyle y_{r_{i},d}=\sqrt{P_{r_{i}}}h_{r_{i},d}x+n_{r_{i},d},$ (4)

and

$\displaystyle y_{r_{i},e}=\sqrt{P_{r_{i}}}h_{r_{i},e}x+n_{r_{i},e},$ (5)

respectively, where $P_{r_{i}}$ denotes the transmit power of relay node
$R_{i}$ under the power constraint $P_{r_{i}}\leq P_{max}$, $h_{r_{i},d}$ is
the channel gain between $R_{i}$ and $D$, and $h_{r_{i},e}$ is the channel
gain between $R_{i}$ and $E$. We assume that channel gain contains both the
path loss and the Rayleigh fading factor. Without loss of generality, we also
assume that all the links have the same noise power which is denoted by
${\sigma^{2}}$. The decode-and-forward (DF) protocol is used for relaying.

The direct transmission signal-to-noise-ratios (SNR) at the destination node
and eavesdropper from the source are
$\mbox{SNR}_{s,d}=\frac{P_{s}h_{s,d}^{2}}{\sigma^{2}},$ and
$\mbox{SNR}_{s,e}=\frac{P_{s}h_{s,e}^{2}}{\sigma^{2}},$ respectively. The SNR
at the destination node and eavesdropper node from relays are
$\mbox{SNR}_{r_{i},d}=\frac{{P_{r_{i}}h_{r_{i},d}^{2}}}{{\sigma^{2}}},$ and
$\mbox{SNR}_{r_{i},e}=\frac{{P_{r_{i}}h_{r_{i},e}^{2}}}{{\sigma^{2}}}.$
Therefore, the channel rate for relay $R_{i}$ to destination $D$ is

$\displaystyle C_{i,d}=W\log_{2}\left(1+\mbox{SNR}_{r_{i},d}\right).$ (6)

Similarly, the channel rate for relay $R_{i}$ to eavesdropper $E$ is

$\displaystyle C_{i,e}=W\log_{2}(1+\mbox{SNR}_{r_{i},e}).$ (7)

Then, the secrecy rate achieved by $R_{i}$ can be defined as [31]

$\displaystyle{C_{i,s}}={\left({{C_{i,d}}-{C_{i,e}}}\right)^{+}}={\left[{W{{\log}_{2}}\left({\frac{{1+\frac{{{P_{{r_{i}}}}h_{{r_{i}},d}^{2}}}{{{\sigma^{2}}}}}}{{1+\frac{{{P_{{r_{i}}}}h_{{r_{i}},e}^{2}}}{{{\sigma^{2}}}}}}}\right)}\right]^{+}},$
(8)

where $(x)^{+}=\max\\{x,0\\}$.

Besides, the secrecy rate assuming maximal ratio combining (MRC) at the
destination and the eavesdropper can be written as

$\displaystyle
C_{d,sys}=W\log_{2}\left(1+\mbox{SNR}_{s,d}+\sum\limits_{i\in\mathcal{K}}{\mbox{SNR}_{r_{i},d}}\right)$
(9)

and

$\displaystyle
C_{e,sys}=W\log_{2}\left(1+\mbox{SNR}_{s,e}+\sum\limits_{i\in\mathcal{K}}{\mbox{SNR}_{r_{i},e}}\right),$
(10)

respectively, such that the total secrecy rate attained by the system is

$\displaystyle{C_{s,sys}}$
$\displaystyle=\left({C_{d,sys}}-{C_{e,sys}}\right)^{+}$
$\displaystyle=W{\log_{2}}\left(1+\mbox{SNR}_{s,d}+\sum\limits_{i\in\mathcal{K}}{\mbox{SNR}_{r_{i},d}}\right)$
$\displaystyle-W{\log_{2}}\left(1+\mbox{SNR}_{s,e}+\sum\limits_{i\in\mathcal{K}}{\mbox{SNR}_{{r_{i}},e}}\right)$
(11)
$\displaystyle=W{\log_{2}}\left(\frac{{1+\mbox{SNR}_{s,d}+\sum\limits_{i\in\mathcal{K}}{\mbox{SNR}_{r_{i},d}}}}{1+\mbox{SNR}_{s,e}+\sum\limits_{i\in\mathcal{K}}{\mbox{SNR}_{{r_{i}},e}}}\right).$

##  III Mechanism Design

In this paper, we use mechanism design as the framework to create an efficient
way to prevent relay nodes from cheating in the process of selection. This
section provides an overview of essential concepts in mechanism design, the
VCG mechanism and AGV mechanism.

###  III-A Basic Definitions and Qualifications

Consider a public system consisting of $I$ agents, ${1,2,\ldots I}$. Each
agent $i\in\\{1,2\ldots I\\}$ has its private information
${\theta_{i}}\in{\Theta_{i}}$, which is known by itself only. A social choice
function $F$ is defined as

$\displaystyle
F:{\Theta_{1}}\times{\Theta_{2}}\times\ldots\times{\Theta_{I}}\to O,$

where $O$ stands for a set of possible outcomes.

A mechanism $\mathcal{M}$ is represented by the tuple
$(F,t_{1},\ldots,t_{I})$, where $t_{i}$ is the transfer payment of agent $i$
when the social choice is $F$. The utility of agent $i$:
$v_{i}\left[F\left({{\hat{\theta}}_{i}},{{\hat{\theta}}_{-i}}\right),\theta_{i}\right]$
depends on the outcome
$o=F\left({{\hat{\theta}}_{i}},{{\hat{\theta}}_{-i}}\right)$ and the true
information of agent $i$: $\theta_{i}$, where ${\hat{\theta}}_{i}$ denotes the
reported information of agent $i$, as opposed to ${\theta_{i}}$. Similarly,
${\hat{\theta}}_{-i}=\\{{\hat{\theta}_{1},\ldots,\hat{\theta}_{i-1},\hat{\theta}_{i+1},\ldots,\hat{\theta}_{I}}\\}$
is the reported information of all other agents. So the total payoff or
welfare of agent $i$ can be written as the following function:

$\displaystyle{u_{i}}\left({{\hat{\theta}}_{i}},{{\hat{\theta}}_{-i}},{\theta_{i}}\right)=v_{i}\left[F\left({{\hat{\theta}}_{i}},{{\hat{\theta}}_{-i}}\right),{\theta_{i}}\right]+{t_{i}}\left({{\hat{\theta}}_{i}},{{\hat{\theta}}_{-i}}\right).$
(12)

The objective of mechanism $\mathcal{M}$ is to choose a desirable set of
transfer payments $t_{i}$. Thus, each agent in the mechanism will achieve its
maximum payoffs. In the following, we define some properties for the
mechanism.

_Definition 1_ : A mechanism is _incentive compatible (IC)_ if the truth-
telling is the best strategy for the agents: ${\hat{\theta}}_{i}=\theta_{i}$,
which means that agents have no incentives to reveal false information. The
dominant-strategy IC is defined as

$\displaystyle{u_{i}}\left({\theta_{i}},{{\hat{\theta}}_{-i}},{\theta_{i}}\right)\geq{u_{i}}\left({{\hat{\theta}}_{i}},{{\hat{\theta}}_{-i}},{\theta_{i}}\right),\;\;\;\forall{{\hat{\theta}}_{i}},{\theta_{i}}\in{\Theta_{i}},{{\hat{\theta}}_{-i}}\in{\Theta_{-i}}.$
(13)

_Definition 2_ : In an _individual rational (IR)_ mechanism, rational agents
are expected to gain a higher utility from actively participating in the
mechanism than from avoiding it. Especially, in the dominant strategy IR can
be expressed as

$\displaystyle{u_{i}}\left({\hat{\theta}_{i}},{\hat{\theta}_{-i}},{\theta_{i}}\right)\geq
0,\;\forall{\theta_{i}}\in{\Theta_{i}}.$ (14)

A mechanism that is both incentive-compatible and individual rational is said
to be _strategy-proof_.

_Definition 3_ : In a _budget balanced (BB)_ mechanism, the sum of all agents
transfer payments is zero, which implies that there is no transfer payment
paid from the mechanism designer to the agents or the other way around. The BB
is defined as

$\displaystyle\sum\limits_{i=1}^{I}{{t_{i}}\left({{\hat{\theta}}_{i}},{{\hat{\theta}}_{-i}}\right)}=0,\;\forall{\theta_{i}}\in{\Theta_{i}}.$
(15)

###  III-B VCG Mechanism

Groves introduced a group of mechanisms which satisfy IC and IR. The Groves
mechanisms are characterized by the following transfer payment function:

$\displaystyle{t_{i}}\left({{\hat{\theta}}_{i}},{{\hat{\theta}}_{-i}}\right)=\sum\limits_{j\neq
i}^{I}{{v_{j}}\left[F\left({{\hat{\theta}}_{j}},{{\hat{\theta}}_{-j}}\right),{{\hat{\theta}}_{j}}\right]}-{\tau_{i}}\left({{\hat{\theta}}_{-i}}\right),$
(16)

where $\tau_{i}(.)$ can be any function of ${\hat{\theta}}_{i}$. The VCG
mechanism is an important special case of the Groves mechanisms for which

$\displaystyle{\tau_{i}}\left({{\hat{\theta}}_{-i}}\right)=\sum\limits_{j\neq
i}^{I}{{v_{j}}\left[{F^{*}}\left({{\hat{\theta}}_{j}},{{\hat{\theta}}_{-j}}\right),{{\hat{\theta}}_{j}}\right]},$
(17)

where ${{F^{*}}\left({{\hat{\theta}}_{j}},{{\hat{\theta}}_{-j}}\right)}$ is
the outcome of the mechanism when agent $i$ withdraws from the mechanism.
Thus, in the VCG mechanism agent $i$ could attain payoff as

$\displaystyle{u_{i}}\left({{\hat{\theta}}_{i}},{{\hat{\theta}}_{-i}},{\theta_{i}}\right)$
$\displaystyle={v_{i}}\left[F\left({{\hat{\theta}}_{i}},{{\hat{\theta}}_{-i}}\right),{\theta_{i}}\right]+{t_{i}}\left({{\hat{\theta}}_{i}},{{\hat{\theta}}_{-i}}\right)$
$\displaystyle={v_{i}}\left[F\left({{\hat{\theta}}_{i}},{{\hat{\theta}}_{-i}}\right),{\theta_{i}}\right]+\sum\limits_{j\neq
i}^{I}{{v_{j}}\left[F\left({{\hat{\theta}}_{j}},{{\hat{\theta}}_{-j}}\right),{{\hat{\theta}}_{j}}\right]}$
$\displaystyle-\sum\limits_{j\neq
i}^{I}{{v_{j}}\left[{F^{*}}\left({{\hat{\theta}}_{j}},{{\hat{\theta}}_{-j}}\right),{{\hat{\theta}}_{j}}\right]}.$
(18)

As will be proved in the next section, the VCG mechanism can satisfy both the
incentive compatibility and individual rationality of each agent. However, the
VCG mechanism is not budget-balanced and requires a third party agent to
mediate between mechanism designer and agents.

###  III-C AGV Mechanism

The AGV mechanism, an extension of the Groves mechanism, is possible to
achieve IC, IR and BB. It is an “expected form” of the Groves mechanism and
its transfer payment function is defined as

$\displaystyle{t_{i}}\left({{\hat{\theta}}_{i}},{{\hat{\theta}}_{-i}}\right)={E_{{\theta_{-i}}}}\left\\{\sum\limits_{j\neq
i}^{I}{v_{j}}\left[F\left({{\hat{\theta}}_{j}},{{\hat{\theta}}_{-j}}\right),{{\hat{\theta}}_{j}}\right]\right\\}-{\tau_{i}}\left({{\hat{\theta}}_{-i}}\right).$
(19)

The first term of $t_{i}$ is the expected total utility of agents $j\neq i$
when agent $i$ reports its information ${\hat{\theta}}_{i}$ with the
assumption that other agents report the truth. It is the function of agent
$i$’s report information only, exclusive of the actual strategies of agents
$j\neq i$, which making the AGV mechanism different from the VCG mechanism.

In the AGV mechanism it is possible to design the $\tau_{i}(.)$ to satisfy BB.
Let

$\displaystyle{\Phi_{i}}\left({{\hat{\theta}}_{i}}\right)={E_{{\theta_{-i}}}}\left\\{\sum\limits_{j\neq
i}^{I}{v_{j}}\left[F\left({{\hat{\theta}}_{j}},{{\hat{\theta}}_{-j}}\right),{{\hat{\theta}}_{j}}\right]\right\\}$
(20)

and

$\displaystyle{\tau_{i}}\left({{\hat{\theta}}_{-i}}\right)=\frac{{-\sum\limits_{j\neq
i}^{I}{{\Phi_{j}}\left({{\hat{\theta}}_{j}}\right)}}}{{I-1}},$ (21)

then budget balance can be achieved because each agent also pays an equal
share of total transfer payments distributed to the other agents, none of
which depends on its own report information. We will prove this property in
the following section.

##  IV Mechanism Solutions

In this section, we first describe how mechanism design is applied in the
relay system and prove that there is no equilibrium achieved if no transfer
payment is introduced to relay nodes. Then, we show the practical mapping from
the utility, transfer payment, and payoff of the VCG mechanism and AGV
mechanism to the wireless cooperative network. Finally, we will compare and
analyze the difference between two mechanisms.

###  IV-A Mechanism Implementation

In the network, each relay node reports its own channel information
$(h_{r_{i},d},h_{r_{i},e})$ to the source node which can be seen as different
agents report their own private information to mechanism designer. Assume
$\left\\{\left({{\tilde{h}}_{{r_{1}},d}},{{\tilde{h}}_{{r_{1}},e}}\right),\left({{\tilde{h}}_{{r_{2}},d}},{{\tilde{h}}_{{r_{2}},e}}\right),\ldots,\left({{\tilde{h}}_{{r_{K}},d}},{{\tilde{h}}_{{r_{K}},e}}\right)\right\\}$
is a realization of channel gains at one time slot, and relay nodes report
their information
$\left\\{\left(\hat{h}_{r_{1},d},\hat{h}_{r_{1},e}\right)\right.,$
$\left(\hat{h}_{r_{2},d},\hat{h}_{r_{2},e}\right),$ $\ldots,$
$\left.\left(\hat{h}_{r_{K},d},\hat{h}_{r_{K},e}\right)\right\\}$ to the
source node. Though the information may not be true, the source node will
still select relay nodes based on them. Define $R_{i}$’s private channel
information as
$\tilde{g}_{i}=\left\\{\tilde{h}_{r_{i},d},\tilde{h}_{r_{i},e}\right\\}$.
Thus, according to (8), the secrecy rate of relay $i$ depends on
$\tilde{g}_{i}$. The source node will choose $K$ relay nodes for transmitting
according to the relay’s reported information $\hat{g}$. The principle of
source node is to find the $K$ relays to maximize the secrecy rates. The
outcome function can be stated as

$\displaystyle
F({\bf{\hat{g}}})=\arg\max\sum\limits_{{R_{i}}\in\mathcal{K}}^{K}{{C_{i,s}}({{\hat{g}}_{i}})}.$
(22)

We define $\pi$ as the price per unit of secrecy rate achieved by the relay.
The relays in the network are assumed to be rational and fair-minded, which
means that although they are selfish, none is malicious. The object of relay
is to make itself chosen for transmitting so that it can gain payoff. Due to
the channel orthogonality, the _utility_ of $R_{i}$ can be expressed as

$\displaystyle{D_{i}}=\left\\{{\begin{array}[]{*{20}{c}}{\pi{C_{i,s}},\;\;\;\;\;\;\;\;\;\;\;\;{R_{i}}\in{\cal
K}},\\\ {0,\;\;\;\;\;\;\;\;\;\;\;\;\;\;\mbox{otherwise}.}\\\
\end{array}}\right.$ (25)

The total _payoff (utility)_ from the system can also be expressed as

$\displaystyle D=\sum\limits_{i=1}^{K}{{D_{i}}}.$ (26)

We assume that the channel information is the private information of each
relay, and thus, the source is unable to know whether the reported information
is true or not. Since only the relay nodes selected by the source for secure
data transmission can get the payoff, they will not report their true
information to the source in order to win greater opportunity to be selected.
In this situation, it can cause unfairness in selection and damage the
expected payoff of those unselected. It can also decrease the total payoff
paid by the system which can be expressed as $\hat{D}\leq\tilde{D},$ where
$\hat{D}$ represents the total the total payoff calculated according to the
information reported by the relay nodes. $\tilde{D}$ represents the total
payoff when all the relay nodes report the truth. These results can sabotage
the reliability of the system and eavesdropper can easily sniff the
transmitted messages.

Firstly, we prove that no equilibrium can be achieved under this condition.

Proposition 1: Assuming that $R_{i}$ does not know other relay’s channel
information, respectively, secrecy rate. But it knows that each relay obeys a
certain probability density function defined as
$p\left({{\tilde{C}}_{j,s}}\right)\left(0\leq{{\tilde{C}}_{j,s}}<\infty,j\neq
i\right)$. Then, $R_{i}$ has an incentive tendency to exaggerate its
${{\hat{C}}_{i,s}}$ to $\infty$ to get the maximum expected payoff.

###### Proof:

$R_{i}$’s expected payoff can be also be expressed as

$\displaystyle{D_{i}}({{\hat{g}}_{i}})=\pi{{\tilde{C}}_{i,s}}{\rm{P}}({R_{i}}\in\mathcal{K}),$
(27)

where $P\left(R_{i}\in\mathcal{K}\right)$ represents the probability of
$R_{i}$ when being chosen. Considering the principle of choosing relay,
$P\left(R_{i}\in\mathcal{K}\right)\propto{\hat{C}_{i,s}}$ and when
$\hat{C}_{i,s}\to\infty$, $P\left(R_{i}\in\mathcal{K}\right)\to 1$, so that
$R_{i}$ gets its maximum payoff at infinity. This indicates that every relay
node has the incentive to exaggerate its channel information to the source,
and thus, there is no equilibrium achieved under this kind of payoff
allocation. ∎

###  IV-B VCG-based Mechanism Solution

In order to prevent relay nodes from reporting distorted channel information,
we propose an effective self-enforcing truth-telling mechanism to solve this
problem. By using the VCG-based mechanism, the honest relay nodes gain the
maximum payoff, as any cheating in the process will lead to decrease in
payoff. Like the VCG mechanism, we introduced this transfer payment of $R_{i}$
as

$\displaystyle{t_{i}}\left({{\hat{g}}_{i}},{{\hat{g}}_{-i}}\right)=\sum\limits_{j\neq
i}^{K}{{D_{j}}({{\hat{g}}_{j}})}-\sum\limits_{j\neq
i}^{K}{D_{j}^{*}({{\hat{g}}_{j}})},$ (28)

where $D_{j}^{*}(.)$ denotes the utility of $R_{j}$ when $R_{i}$ does not
participate in the system. So the total payoff of $R_{i}$ is:

$\displaystyle{U_{i}}\left({{\hat{g}}_{i}}\right)$
$\displaystyle={D_{i}}({{\hat{g}}_{i}})+{t_{i}}({{\hat{g}}_{i}},{{\hat{g}}_{-i}})$
$\displaystyle={D_{i}}({{\hat{g}}_{i}})+\sum\limits_{j\neq
i}^{N}{{D_{j}}({{\hat{g}}_{j}})}-\sum\limits_{j\neq
i}^{K}{D_{j}^{*}({{\hat{g}}_{j}})}$ (29)
$\displaystyle=\sum\limits_{j}^{K}{{D_{j}}({{\hat{g}}_{j}})}-\sum\limits_{j\neq
i}^{K}{D_{j}^{*}({{\hat{g}}_{j}}).}$

If one relay node claims a higher $\hat{h}_{r_{i},d}$ or a lower
$\hat{h}_{r_{i},e}$ than the reality to make its secrecy rate larger, it may
get more chances to be selected by the source node, but also will pay a higher
transfer payoff to those unselected. On the contrary, if one relay node
reports a lower secrecy rate than reality, it will receive the compensation
from other relay nodes at the cost of less chances to be selected. By adding
this transfer function, we will discuss some properties of this VCG-based
mechanism as follows.

Proposition 2: By using the VCG transfer function (28) to balance the payoff
allocation, relay node $R_{i}$ can gain its largest payoff when it reports the
true private channel information.

###### Proof:

We can see from (IV-B) that the payoff of each relay $R_{i}$ is the total
utility of all relays $\sum_{j}^{K}{{D_{j}}({{\hat{g}}_{j}})}$ when relay
participates in the system, minuses the total utility of all other relays
$\sum_{j\neq i}^{K}{D_{j}^{*}({{\hat{g}}_{j}})}$ when relay $i$ withdraws from
the system. It is obvious that relay $i$ cannot influence the value of
$\sum_{j\neq i}^{K}{D_{j}^{*}({{\hat{g}}_{j}})}$. Therefore, in order to
maximize its own payoff, relay $i$ seeks to maximize the total utility of the
system. According to our relay selection principle, the total utility of all
relays depends on the chosen $K$ relay’s true channel information. If and only
if each relay reports the true information $(\hat{g}_{i}=\tilde{g}_{i})$, the
total utility is maximized. Hence, the payoff of $R_{i}$ is maximized. ∎

Proposition 3: Every rational relay node in the system takes part in the VCG-
based mechanism for its own benefit.

###### Proof:

It is easy to show that $\sum_{j}^{K}{{D_{j}}({{\hat{g}}_{j}})}\geq\sum_{j\neq
i}^{K}{D_{j}^{*}({{\hat{g}}_{j}})}$ when the IC achieved
$(\hat{g}_{i}=\tilde{g}_{i})$, and the equality holds when $R_{i}$ is not
selected ($D_{i}=0$). Therefore, for each relay $R_{i}$ , $U_{i}(g_{i})\geq 0$
and participating into the system is an optimal choice for a rational relay. ∎

Proposition 4: By applying the VCG-based mechanism in our system, we cannot
achieve the BB condition: the total transfer payments
$\sum_{i=1}^{N}{{t_{i}}}<0$, which means that we need the mechanism designer
or a third party to pay parts of the payoff.

###### Proof:

There are two cases of $R_{i}$:

  * •

It is not selected by the source node (${R_{i}}\notin\mathcal{K}$), then
obviously: ${t_{i}}\left({{\hat{g}}_{i}},{{\hat{g}}_{-i}}\right)=\sum_{j\neq
i}^{K}{{D_{j}}({{\hat{g}}_{j}})}-\sum_{j\neq
i}^{K}{D_{j}^{*}({{\hat{g}}_{j}})}=0$.

  * •

It is selected by the source node $(R_{i}\in\mathcal{K})$, then
${t_{i}}({{\hat{g}}_{i}},{{\hat{g}}_{-i}})=\sum_{j\neq
i}^{K}{{D_{j}}({{\hat{g}}_{j}})}-\sum_{j\neq
i}^{K}{D_{j}^{*}({{\hat{g}}_{j}})}<0$. Because of the withdrawal of $R_{i}$,
another relay node with a lower secrecy rate will be selected and its utility
$D^{*}$ will get bigger.

Combine these two cases together: $K$ relay nodes will receive negative
transfer payment that makes the total transfer payments
$\sum_{i=1}^{K}{{t_{i}}}<0$. Hence, the BB is not satisfied in the VCG-based
mechanism. ∎

###  IV-C AGV-based Mechanism Solution

From the discussions above we can know that the VCG-based mechanism can
enforce every relay node to tell the true private channel information, which
can effectively solve the cheating problem in our system. However, as the
mechanism designer, we need to pay some extra payments to the system because
the VCG-based mechanism fails the condition of BB. To compensate for this
loss, we improve the VCG-based mechanism to the AGV-based one.

In the AGV-based mechanism, we change the transfer payment of $R_{i}$ as

$\displaystyle{t_{i}}({{\hat{g}}_{i}},{{\hat{g}}_{-i}})={\Phi_{i}}({{\hat{g}}_{i}})-\frac{1}{{K-1}}\sum\limits_{j\neq
i}^{K}{{\Phi_{j}}({{\hat{g}}_{j}})}$ (30)

where

$\displaystyle{\Phi_{i}}\left({{\hat{g}}_{i}}\right)$
$\displaystyle={E_{{\hat{g}_{-i}}}}\left[\sum\limits_{j=1,j\neq
i}^{K}{D_{j}}({{\hat{g}}_{j}})\right]$ $\displaystyle=\sum\limits_{j=1,j\neq
i}^{K}{{E_{{\hat{g}_{-i}}}}\left[{D_{j}}({{\hat{g}}_{j}})\right]}$ (31)

represents the sum of the other relay nodes’ expected utilities given the
reported information $\hat{g}_{i}$.

Like in the VCG-based mechanism, we can prove that only if the relay nodes
reveal the true channel information, they can obtain the maximum payoff in the
AGV-based mechanism. There is only one equilibrium under this kind of payoff
allocation.

Proposition 5: By using the AGV-based mechanism, the relay node $R_{i}$ can
gain its largest expected payoff when it reports its true private channel
information to the source node.

###### Proof:

Without loss of generality, we consider the expected payoff of $R_{1}$. Since
$R_{1}$ only knows its own channel information, we can calculate the payoff
according to the transfer payment function (30) as

$\displaystyle
E[{U_{1}}({{\hat{g}}_{1}})]=E[{D_{1}}({{\hat{g}}_{1}})+{t_{1}}({{\hat{g}}_{1}},{{\hat{g}}_{-1}})]$
$\displaystyle=E[{D_{1}}({{\hat{g}}_{1}})]+{E_{{{\hat{g}}_{-1}}}}\left[\sum\limits_{j\neq
1}^{K}{D_{j}}({{\hat{g}}_{1}})\right]-\frac{1}{{K-1}}\sum\limits_{j\neq
1}^{K}{{\Phi_{j}}({{\hat{g}}_{j}})}$
$\displaystyle=E\left[\sum\limits_{j=1}^{K}{D_{j}}({{\hat{g}}_{j}})\right]-\frac{1}{{K-1}}\sum\limits_{j\neq
1}^{K}{{\Phi_{j}}({{\hat{g}}_{j}})}.$ (32)

We can see that there are two terms in the right side of (IV-C). The first one
represents the total expected payoff when $R_{1}$ reports $\hat{g}_{1}$ as its
channel information (the expectation is calculated by $R_{1}$ itself). Since
the other term being independent of $\tilde{g}_{1}$, only the first term
decides the expected payoff of $R_{1}$. As we have shown above, the total
payoff is based on the real secrecy rate. Only when the $K$ relays with top
$K$ secrecy rate are selected, the total payoff will be maximized. Any
cheating leads to a decrease in all relays’ total payoff, and therefore, the
expectation $E[U_{1}(\hat{g}_{1})]$ can get the maximum when $R_{1}$ reports
its true channel information. Similarly, each relay node in the network has an
incentive to report its true channel information
$({{\hat{g}}_{i}}={{\tilde{g}}_{i}})$. Thus, the equilibrium is achieved under
this condition. ∎

Proposition 6: Each relay node could gain a positive expected payoff in the
AGV-based mechanism, which ensures that every relay would like to take part in
this mechanism.

###### Proof:

From (30) and (IV-C) it is easy to derive $R_{i}$’s expected payoff:

$\displaystyle E[{U_{i}}({{\hat{g}}_{i}})]$
$\displaystyle=E\left[\sum\limits_{j=1}^{K}{D({{\hat{g}}_{j}})}\right]-\frac{1}{{K-1}}\sum\limits_{j\neq
i}^{K}{\sum\limits_{k\neq j}^{K}{{E_{-k}}[{D_{k}}({{\hat{g}}_{j}})]}}$
$\displaystyle=E\left[\sum\limits_{j=1}^{K}{D({{\hat{g}}_{j}})}\right]-\frac{1}{{K-1}}\left\\{(K-1)\sum\limits_{j=1}^{K}{E[{D_{j}}({{\hat{g}}_{j}})]}\right.$
$\displaystyle-\left.\sum\limits_{k\neq
i}^{K}{{E_{-k}}[{D_{k}}({{\hat{g}}_{i}})]}\right\\}$ (33)
$\displaystyle=\frac{1}{{K-1}}{E_{-j}}\left[\sum\limits_{j\neq
i}^{K}{{D_{j}}({{\hat{g}}_{i}})}\right].$

According to (27), $D_{i}>0$ if $R_{i}$ is selected and $D_{i}=0$ if not.
Since among all the relay nodes there are always some nodes being selected,
the right side of the equation above ${E_{-j}}\left[\sum\nolimits_{j\neq
i}^{N}{{D_{j}}({{\hat{g}}_{i}})}\right]>0$. Therefore, $R_{i}$ can gain a
payoff more than 0, and thus, the IR is satisfied. ∎

Proposition 7: In the AGV-based mechanism, the system can achieve budget
balance, which means that we, as the mechanism designer, will not pay any
extra payment to the system.

###### Proof:

If we calculate the total transfer payment of all relays, we could get

$\displaystyle\sum\limits_{i=1}^{N}{{t_{i}}({{\hat{g}}_{i}},{{\hat{g}}_{-i}})}$
$\displaystyle=\sum\limits_{i=1}^{N}{{\Phi_{i}}({{\hat{g}}_{i}})}-\frac{1}{{N-1}}\sum\limits_{i=1}^{N}{\sum\limits_{j=1,j\neq
i}^{N}{{\Phi_{j}}({{\hat{g}}_{j}})}}$
$\displaystyle=\sum\limits_{i=1}^{N}{{\Phi_{i}}({{\hat{g}}_{i}})}-\sum\limits_{j=1}^{N}{{\Phi_{j}}({{\hat{g}}_{j}})}=0.$
(34)

This implies that the proposed transfer function can realize a payment
reallocation among the relay nodes, and no extra payment is required to be
paid by the system or by the relay nodes. ∎

###  IV-D The Value of K

In the discussion above, we assumed that the value of $K$ is fixed and the
source node always choose $K$ relays for cooperating. However, it is easy to
see that different $K$ can lead to different results in the total secrecy rate
of the network. So we did some research to figure out the optimal amount $K$
of relays the source node should select.

In our system model, the total secrecy attained of the system is (II). By
using the AGV mechanism, each relay reports the truth. Now we assume each
relay’s reported information is $\mbox{SNR}_{r_{i},d}$ and
$\mbox{SNR}_{r_{i},e}$. Let
$k_{i}=\frac{\mbox{SNR}_{r_{i},d}}{\mbox{SNR}_{r_{i},e}}$. Sort $k_{i}$ in
descending order, and get $k_{(1)}\geq k_{(2)}\geq\ldots\geq
k_{(N)},k_{(i)}\in\\{k_{1},k_{2},\ldots,k_{N}\\}$. Obviously, the relay which
has a larger $C_{i,s}$ also has a larger $k_{i}$ according to (8). We denote
that $R_{(1)}$ is the best relay which has the largest secrecy rate, $R_{(2)}$
is the second best, and so forth. Then the optimal selection strategy of the
source node is described as below:

1\. Select $R_{(1)}$ for transmitting. Let $i=1$ and calculate
$\Psi_{1}=\frac{1+\mbox{SNR}_{s,d}+\mbox{SNR}_{r_{(1)},d}}{1+\mbox{SNR}_{s,e}+\mbox{SNR}_{r_{(1)},e}}$.

2\. For $i<N$, if $\Psi_{i}<k_{(i+1)}$, proceed step 3 and if $\Psi_{i}\geq
k_{(i+1)}$, skip to step 4.

3\. Select $R_{(i+1)}$ and calculate
${\Psi_{i+1}}=\frac{{1+{\rm{SN}}{{\rm{R}}_{s,d}}+\sum\nolimits_{j=1}^{i+1}{{\rm{SN}}{{\rm{R}}_{{r_{(j)}},d}}}}}{{1+{\rm{SN}}{{\rm{R}}_{s,e}}+\sum\nolimits_{j=1}^{i+1}{{\rm{SN}}{{\rm{R}}_{{r_{(j)}},e}}}}}$.
Then let $i=i+1$ and go back to step 2.

4\. Let $K$ = i and stop.

Proposition 8: The system can attain the largest secrecy rate by selecting $K$
relays for transmitting data, where $K$ is decided by the process above.

###### Proof:

By the selection strategy of the source described above, it is easy to prove
that $\Psi_{K}$ is the maximum among
$\left\\{\Psi_{1},\Psi_{2},\ldots,\Psi_{N}\right\\}$. According to (II), the
total secrecy rate of the network when selecting $i$ relays can be expressed
as $C_{s,sys}(i)=W\log_{2}\Psi_{i}$. When $i=K$, $\Psi_{K}$ can get the
maximum, and obviously $C_{s,sys}(K)$ is the largest. Therefore, it is the
best choice for the source to select $K$ relays in the system. ∎

In many cases, because of the geographic conditions, the direct transmission
is very weak compared with relay transmission which means that the selected
relay has a
$\mbox{SNR}_{r_{i},d}>\mbox{SNR}_{r_{i},e}\gg\mbox{SNR}_{s,d}>\mbox{SNR}_{s,e}$.
So
$\mbox{SNR}_{r_{i},d}\gg(1+\mbox{SNR}_{s,d}),\mbox{SNR}_{r_{i},e}\gg(1+\mbox{SNR}_{s,e})$
and $\Psi_{1}\approx k_{(1)}>k_{(2)}$. Thus, $K=1$ is the best choice, which
means the source should only select one best relay for transmitting data. More
than one relay node would lead to a decrease in the total secrecy rate of the
system.

##  V Simulation Results

In this section, we provide simulation results of the wireless relay system in
the VCG-based mechanism and AGV-based mechanism, respectively. Specifically,
to simplify the calculation and simulation, we assume that each relay node
first calculates its own secrecy rate according to its channel information,
and then reports it to the source. Without considering the process of
calculating $\pi C_{i,s}$, we assign random values $x_{i}$ to indicate $\pi
C_{i,s}(i=1,2,\ldots,N)$, which not affect the “outcome” or source’s selection
result. Furthermore, we assume that though $R_{i}$ does not know other relays’
channel information, it knows that every reported value obeys the probability
density function: $e^{-x_{i}}$
$\left(x_{i}\in[0,\infty)\;\mbox{and}\;\int_{0}^{+\infty}{e^{-x_{i}}dx_{i}}=1\right)$.

Firstly, we consider a system with $N=4$ relay nodes and from which the source
node chooses $K=2$ relays. A random sample of these relay nodes’ secrecy rates
is obtained as ${[1.0132,0.6091,0.3885,1.3210]}$ and the price per unit of
secrecy rate $\pi=1$ is assumed.

Figure 2: Payoff of $R_{i}$ when different secrecy rates are reported in the
VCG-based mechanism.

Fig. 2 shows the variation of $R_{i}$’s payoff when the reported values change
in the VCG-based mechanism. Given that the other three nodes are honest,
$R_{i}(i=1,2,3,4)$ can get its maximum payoff while reporting the truth. From
Fig. 2 we can observe that when they all tell the truth, the larger the true
value of secrecy rate of one relay node is, the more the payoff it gains. For
example, $R_{4}$ has the largest secrecy rate ($\tilde{C}_{4,s}=1.3210$) and
its payoff is the largest up to $0.5822$ when it reports the true value. It is
higher than the other three relay nodes’ payoff even though it is not as much
as $\pi C_{4,s}=1.3210$, which is paid by the destination node because of the
transfer payment.

Figure 3: Transfer payment of $R_{1}$ when different secrecy rates are
reported in the VCG-based mechanism.

In Fig. 3 we demonstrate the transfer payment of each relay they calculate
from their own angles when they report different secrecy rates. As is evident
in the figure, each relay has the same transfer payment curve. This is because
we assume each relay only knows the other relays report secrecy rates obey the
negative exponential distribution. So the difference of the utility of the
others relays whether the relay participates the mechanism or not is the same
for each relay. We can also see that they are all monotone decreasing because
the larger the reported value is, the more transfer payoff should be paid to
others. Besides, as the reported secrecy rate continuously increases, the
transfer payoff will tend to a fixed value. It is because this very large
reported value will always be larger than the others, the “outcome” or
source’s selection will be fixed whether this relay node is in this system or
not. So the transfer payment will be a fixed value when the reported value
becomes very large. The curve of $R_{i}$’s payoff in Fig. 2 is the same
reason.

Figure 4: Expected payoff of $R_{i}$ when different secrecy rates are reported
in the AGV-based mechanism. Figure 5: Expected transfer payment of $R_{i}$
when different secrecy rates are reported in the AGV-based mechanism. Figure
6: Expected payoff of $R_{1}$ with variable true secrecy rate when different
secrecy rates are reported in the AGV-based mechanism.

Fig. 4 and Fig. 5 show the results when we use the AGV-based mechanism in the
system. In Fig. 4, four curves show the expected payoff of $R_{1}$-$R_{4}$. It
is obvious to see that each relay maximizes its payoff when they report the
true secrecy rate. Compared with Fig. 2, we can see each relay’s payoff is
higher in the AGV-based mechanism than that in the VCG-based mechanism. It
means that the AGV-based mechanism can maximize all the relay nodes payoff
which is more attractive for relay node to attend. From Fig. 5 we also find
that $R_{1}$’s and $R_{4}$’s transfer payoffs are negative while the other
two’s are positive when they tell the truth. This is because $R_{1}$ and
$R_{4}$ are actually selected by the source node and need to pay the transfer
payment while $R_{2}$ and $R_{3}$ are not. By using the AGV-based mechanism,
the relay nodes with smaller secrecy rate will get compensations from those
with larger ones. It can balance the payment allocation of the system and
benefit those in worse physical conditions. Furthermore, we calculate the
expected transfer payoff of $R_{i}$ when they all report the truth:
$t_{1}=-0.1247$, $t_{2}=0.1570$, $t_{3}=0.2831$, $t_{4}=-0.3154$ and
$t_{1}+t_{2}+t_{3}+t_{4}=0$, which is in accord with the equation (27). Hence
the system is budget balanced and no extra payment is paid into or out of the
network. In conclusion, we can confirm that the AGV-based mechanism is more
compatible for our system than the VCG-based mechanism. Moreover, we show the
payoff of $R_{1}$ with changing secrecy rate when it reports different secrecy
rate in Fig. 6. It is obvious that no matter what true secrecy rate of $R_{1}$
is, $R_{1}$ always gains its maximum payoff when it reports its own true
secrecy rate.

Figure 7: Effectiveness of the reported secrecy of $R_{1}$ on the expected
payoff at different $K$ in the AGV-based mechanism. Figure 8: Effectiveness of
the reported secrecy of $R_{1}$ on the expected transfer payment at different
$K$ in the AGV-based mechanism.

In addition, we analyze the effects of the reported secrecy rate versus the
value of $K$ in the AGV-based mechanism. As an example, we set the relay node
$R_{1}$ be the interested one and its secrecy rate is $1.0132$. In Fig. 7, we
observe that the relay node $R_{1}$ achieve the maximum expected payoffs when
it reports the true secrecy rate with different $K$. When $K$ equals to $1$,
the payoff of the relay node $R_{1}$ is the lowest. And the larger the
reported value, the smaller the expected payoff shows. When $K$ equals $2$ and
$3$, the expected payoff becomes a fixed value as the reported secrecy rate
continuously increases. Because the transfer payment is a part of the total
payoff, the change of the expected payoff can be translated by the transfer
payment, which is shown in Fig. 8. When $K$ equals to $1$ and this relay
reports a larger secrecy rate, the expected transfer payment is a small and
negative value. So the expected payoff of the relay node is minor. When $K$
equals to $2$ and $3$, the slope of the curves becomes smoother as the
reported value increases. This shows the change trend of the relay node’s
payoff from the other point of view. Meanwhile, it implies that the transfer
payoff is helpful to control the payoff for fairness among relay nodes.

Figure 9: System secrecy rate at different $K$ at bad SNR in the AGV-based
mechanism.

Finally, we focus on the effect of the value of $K$ on the total system
secrecy. Here we assume $W=\ln 2$ then $C_{s,sys}(K)=\ln(\Psi(k))$. Let $N=6$,
the direct transmission SNR to destination and eavesdropper are $9.64$dB and
$5.47$dB, respectively, and given two random samples for $R_{i}$’s report
information ($\mbox{SNR}_{r_{i},d}$ and $\mbox{SNR}_{r_{i},e}$). In one sample
we assume each value has the same order of magnitude with $1$
$(1\mbox{dB}<\mbox{SNR}<10\mbox{dB}):\mbox{SNR}_{r_{i},d}=\\{6.1734,$
$7.9489,$ $9.7429,$ $7.1886,$ $6.3783,$ $7.3411\\},(\mbox{dB})$;
$\mbox{SNR}_{r_{i},e}=\\{3.7700,$ $0.9927,$ $5.6543,$ $4.3645,$ $0.6273,$
$6.1954\\},(\mbox{dB})$. In the other sample we assume each value has the same
order of magnitude with $10$
$(10\mbox{dB}<\mbox{SNR}<20\mbox{dB}):\mbox{SNR}_{r_{i},d}=\\{16.173,$
$17.948,$ $19.742,$ $17.188,$ $16.378,$ $17.341\\},(\mbox{dB});$
$\mbox{SNR}_{r_{i},e}=\\{13.770,$ $10.992,$ $15.654,$ $14.364,$ $10.627,$
$16.1954\\},(\mbox{dB})$. Similarly, we do this simulation with another group
data of high SNR and low SNR as follows: $\mbox{SNR}_{r_{i},d}=\\{8.8149,$
$5.6809,$ $9.3701,$ $8.5822,$ $3.3896,$ $10.000\\},(\mbox{dB})$;
$\mbox{SNR}_{r_{i},e}$ $=\\{3.7700,$ $0.9927,$ $5.6543,$ $4.3645,$ $0.6273,$
$6.1954\\},(\mbox{dB})$; $\mbox{SNR}_{r_{i},d}$ $=\\{$$16.173,$ $17.948,$
$19.742,$ $17.188,$ $16.378,$ $17.341\\},(\mbox{dB})$; and
$\mbox{SNR}_{r_{i},e}=\\{$$15.227,$ $12.164,$ $14.522,$ $13.278,$ $12.746,$
$13.648\\},(\mbox{dB})$. The simulation result is showed in Fig. 9, and we can
observe that in the low SNR situation, $C_{s,sys}$ is maximized when the
source select 2 and 3 relays, respectively. Thus, they attain the maximum
secrecy at $K=2$ and $K=3$. However, in the high SNR situation showed in Fig.
9, when all of the channel conditions are better, the best choice for the
system is to choose only one relay $(K=1)$ for transmitting. All these results
are based on the fact that all relays will reveal their true channel
information which is ensured by the AGV mechanism.

##  VI Conclusions

In this paper, we discussed and applied the ideas of mechanism design into the
wireless relay network to guarantee the strategy-proof during the process of
relay selection when considering secure data transmission. We proved that by
using the VCG mechanism and AGV mechanism, each relay node gets its maximum
payoff only when it reveals its true channel information, and any deviation
from the truth will lead to a loss in its own (expect) payoff as well as the
total secrecy rate. We compared these two mechanisms and illustrated that the
AGV mechanism is more compatible for our system when taking the budget balance
constraint into consideration. We proved that the strategy-proof and budget
balance of the system can be achieved in the AGV mechanism, which makes our
model more practical in reality. Simulation results verified these
conclusions. Moreover, we proposed and proved the best choice for the source
node in deciding how many relays it should select to get the maximum secrecy
rate of the network. In good channel conditions with higher SNR, it is better
to select only one relay for transmitting data.

## References

  * [1] S. Liu, R. Zhang, L. Song, Z. Han and B. Jiao, “Enforce truth-telling in wireless relay networks for secure communication,” in _Proc. IEEE INFOCOM WKSHPS_ , pp. 1071–1075, Shanghai, Apr. 2011.
  * [2] A. Wyner, “The wire-tap channel,” _Bell Syst. Tech. J._ , vol. 54, no. 8, pp. 1355–1387, Jul. 1975.
  * [3] S. K. Leung-Yan-Cheong and M. E. Hellman, “The Gaussian wire-tap channel,” _IEEE Transactions on Information Theory_ , vol. 24, no. 4, pp. 451–456, Jul. 1978.
  * [4] I. Csiszar and J. Korner, “Broadcast channels with confidential messages,” _IEEE Transactions on Information Theory_ , vol. 24, no. 3, pp. 339–348, Jul. 1978.
  * [5] V. Aggarwal, L. Sankar, A. R. Calderbank, and H. V. Poor, “Secrecy capacity of a class of orthogonal relay eavesdropper channels,” _EURASIP Journal on Wireless Communications and Networking_ , vol. 2009, Mar. 2009.
  * [6] L. Dong, Z. Han, A. P. Petropulu, and H. V. Poor, “Improving wireless physical layer security via cooperating relays,” _IEEE Transactions on Signal Processing_ , vol. 58, no. 3, pp. 1875–1888, Mar. 2010.
  * [7] J. Li, A. P. Petropulu, and S. Weber, “On cooperative relaying schemes for wireless physical layer security,” _IEEE Transactions on Signal Processing_ , vol. 59, no. 10, pp. 4985–4997, Oct. 2011.
  * [8] R. Zhang, L. Song, Z. Han, B. Jiao, and M. Debbah, “Physical layer security for two way relay communications with friendly jammers,” in _Proc. IEEE Global Telecommunications Conference_ , Miami, USA, Dec. 2010.
  * [9] J. Chen, R. Zhang, L. Song, Z. Han, and B. Jiao, “Joint relay and jammer selection for secure two-way relay networks,” in _Proc. IEEE Communications International Conference on Communications_ , Kyoto, Japan, Jun. 2011.
  * [10] J. Huang and A. L. Swindlehurst, “Cooperative jamming for secure communications in MIMO relay networks,” _IEEE Transactions on Signal Processing_ , vol. 59, no. 10, pp. 4871–4884, Oct. 2011.
  * [11] Y. Rebahi, V. E. Mujica-V, and D. Sisalem, “A reputation-based trust mechanism for ad-hoc networks,” in _Proc. IEEE Symposium on Computers and Communications_ , pp. 37–42, Cartagena, Murcia, Spain, Jun. 2005.
  * [12] A. B. MacKenzie and S. B. Wicker, “Game theory in communication: motivation, explanation, and application to power control,” in _Proc. IEEE Global Telecommunications Conference_ , vol. 2, pp. 821–826, San Antonio, USA, Dec. 2001.
  * [13] Y. Fan, H. Zhu, Y. Jiang, J. Chen and Sherman Shen, “Network Coding Based Privacy Preservation against Traffic Analysis in Multi-hop Wireless Networks,” _IEEE Transactions on Wireless Communication_ , Vol. 10, no. 3, pp. 834–843, Mar. 2011.
  * [14] R. Yu, Y. Zhang, Y. Liu, S. Xie, L. Song and M. Guizani, “Secondary Users Cooperation in Cognitive Radio Networks: Balancing Sensing Accuracy and Efficienc”, _IEEE Wireless Communications Magazine_ , vol. 19, no. 2, pp. 30–37, Apr. 2012.
  * [15] X. Zhang and C. Li, “Constructing Secured Cognitive Wireless Networks: Experiences and Challenges”, _Wireless Communication and Mobile Computing_ , vol. 10, no. 1, pp. 50–69, Jan. 2010.
  * [16] Z. Han, D. Niyato, W. Saad, T. Basar, and A. Hjørungnes, _Game Theory in Wireless and Communication Networks: Theory, Models and Applications_ , Cambridge University Press, UK, 2011.
  * [17] R. Zhang, L. Song, Z. Han, B. Jiao, “Physical Layer Security for Two-Way Untrusted Relaying With Friendly Jammers”, _IEEE Transactions on Vehicular Technology_ , vol. 61, no. 8, pp. 3693–3704, Oct. 2012.
  * [18] A. Mas-Collel, M. Whinston, and J. Green, _Microeconomic Theory_ , Oxford University Press, 1995.
  * [19] N. Nisan and A. Ronen, “Algorithmic mechanism design,” _Proc. 31st ACM Symposium on Theory of Computing_ , pp. 129–140, New York, USA, ACM Press, May. 1999.
  * [20] Y. Narahari, D. Garg, R. Narayanam, and H. Prakash, _Game Theoretic Problems in Network Economics and Mechanism Design Solutions_ , Springer, 2009.
  * [21] W. Vickrey, “Counterspeculation, auctions, and competitive sealed tenders,” _Journal of Finance_ , 1961.
  * [22] E. Clark, “Multipart pricing of public goods,” _Public Choice_ , 1971.
  * [23] T. Groves, “Incentives in teams,” _Econometrica_ , 1973.
  * [24] H. Moulin and S. Shenker, “Strategyproof sharing of submodular costs: budget balance versus efficiency,” _Economic Theory_ , vol. 18, no. 3, pp. 511–533, Nov, 2001.
  * [25] P. Maille and B. Tuffin, “Why VCG auctions can hardly be applied to the pricing of inter-domain and ad hoc networks,” in _Next Generation Internet Networks_ , 3rd EuroNGI Conference, Trondheim, Norway, May 2007.
  * [26] K. J. Arrow, “The property rights doctrine and demand revelation under incomplete information,” _Economics and Human Welfare: Essays in Honor of Tibor Scitovsky_ , New York Academic Press, 1979.
  * [27] C. d’Aspremont and L. A. Gerard-Varet, “Incentives and incomplete information,” _Journal of Public Econ_ , vol. 11, no. 1, pp. 25–45, Feb. 1979.
  * [28] D. Fudenburg and J. Tirole, _Game theory_ , MA: MIT Press, 1993.
  * [29] V. Krishna, _Auction theory_ , Academic Press, 2002.
  * [30] E. Dekel, D. Fudenberg, and D. K. Levine, “Learning to play Bayesian games,” _Games and Economic Behavior_ , vol. 46, no. 2 pp. 282–303, Feb. 2004.
  * [31] J. Barros and M. R. D. Rodrigues, “Secrecy capacity of wireless channels,” in _Proc. IEEE International Symposium in Information Theory_ , Washington, USA, Jul. 2006.


††thanks<EMAIL_ADDRESS><EMAIL_ADDRESS>
# Quantum Simulation of Operator Spreading in the Chaotic Ising Model

Michael R. Geller  Center for Simulational Physics, University of Georgia,
Athens, Georgia 30602, USA  Andrew Arrasmith  Theoretical Division, Los Alamos
National Laboratory, Los Alamos, NM, USA.  Zoë Holmes  Information Sciences,
Los Alamos National Laboratory, Los Alamos, NM, USA.  Bin Yan  Center for
Nonlinear Studies, Los Alamos National Laboratory, Los Alamos, NM, USA.
Theoretical Division, Los Alamos National Laboratory, Los Alamos, NM, USA.
Patrick J. Coles  Theoretical Division, Los Alamos National Laboratory, Los
Alamos, NM, USA.  Andrew Sornborger  Information Sciences, Los Alamos National
Laboratory, Los Alamos, NM, USA.

(July 8, 2021)

###### Abstract

There is great interest in using near-term quantum computers to simulate and
study foundational problems in quantum mechanics and quantum information
science, such as the scrambling measured by an out-of-time-ordered correlator
(OTOC). Here we use an IBM Q processor, quantum error mitigation, and weaved
Trotter simulation to study high-resolution operator spreading in a 4-spin
Ising model as a function of space, time, and integrability. Reaching 4 spins
while retaining high circuit fidelity is made possible by the use of a
physically motivated fixed-node variant of the OTOC, allowing scrambling to be
estimated without overhead. We find clear signatures of ballistic operator
spreading in a chaotic regime, as well as operator localization in an
integrable regime. The techniques developed and demonstrated here open up the
possibility of using cloud-based quantum computers to study and visualize
scrambling phenomena, as well as quantum information dynamics more generally.

A key concept in modern quantum physics is the noncommutativity of operators
corresponding to physically separated local observables $W$ and $V$ caused by
scrambling. Scrambling is a spreading of quantum information over many degrees
of freedom, generated by chaotic unitary evolution swingle2018unscrambling.
The resulting growth of an operator $W(t)=e^{iHt}We^{-iHt}$ in time can be
diagnosed by the nonvanishing of the “commutator” hayden2007black;
KitaevKITP15; shenker2014black; maldacena2016bound; sachdev1993gapless;
sachdev2015bekenstein; nandkishore2015many; abanin2019colloquium

$\displaystyle{\rm tr}(\rho\big{|}[W(t),V(0)]\big{|}^{2})={\rm tr}[\rho
W(t)V(0)V(0)W(t)]$ $\displaystyle+\ {\rm tr}[\rho V(0)W(t)W(t)V(0)]-2\,{\rm
Re}\,F(t)$ (1)

in some state $\rho$ (often a thermal state). Here

$\displaystyle F(t)={\rm tr}[\rho W(t)V(0)W(t)V(0)]$ (2)

is the out-of-time-ordered correlator (OTOC). The theoretical study of
scrambling and OTOCs has enhanced our understanding of entanglement in
condensed matter, quantum field theory, and quantum gravity
larkin1969quasiclassical; garcia2017digital; halpern2018quasiprobability;
swingle2018resilience; zhang2019information; yoshida2019disentangling;
babbush2019quantum; alonso2019out; vermersch2019probing; daug2019detection;
Yan2020information; belyansky2020minimal; Yan2020recovery;
touil2021information; lin2018out; xu2019locality; fortes2019gauging;
fortes2020signatures; holmes2021barren.

Fast scrambling appears in a variety of systems, including black holes
hayden2007black; KitaevKITP15; shenker2014black; maldacena2016bound and
strange metals sachdev1993gapless; sachdev2015bekenstein, while slow
scrambling indicates a breakdown of ergodicity and thermalization
nandkishore2015many; abanin2019colloquium. However, the dynamics of
information away from these two extremes, such as operator spreading in
ordinary quantum matter, is less well understood lin2018out; xu2019locality.
Open problems also include predicting the scrambling generated by a given
model Hamiltonian (without simulating it) xu2019locality, the nature of
scrambling in models without particle-like classical limits lin2018out;
xu2019locality; fortes2019gauging; fortes2020signatures, and determining when
a fast scrambler has a dual description as a black hole
swingle2018unscrambling. Additional questions that can be addressed with the
techniques developed here include the dependence of scrambling on $\rho$, the
dependence on $W$ and $V,$ and the difference between thermal scrambling in
gapped and gapless phases, such as integer versus half-integer-spin 1d
antiferromagnets (with or without the Haldane gap haldane1983nonlinear).

Direct experimental measurement of (1) is challenging because it requires
reversing the direction of time (changing the sign of the Hamiltonian) during
the experiment. But it can be simulated on a classical or quantum computer.
While classical simulation is limited to small or weakly correlated models,
fault-tolerant quantum computers promise to make large-scale scrambling
simulations practical. This should provide a valuable tool for quantum
information science by complimenting the study of solvable models
hayden2007black; KitaevKITP15; shenker2014black; maldacena2016bound;
sachdev1993gapless; sachdev2015bekenstein; nandkishore2015many;
abanin2019colloquium. However, near-term quantum simulations are restricted to
a small number of qubits and short circuits. Online users may also face
additional restrictions that limit the number of distinct quantum circuits
that can be measured, and thus the overall complexity of an experiment and the
resulting data quality.

The quantum simulation of scrambling with near-term processors is especially
challenging because, at each time $t$, four Hamiltonian simulations of length
$t$ are implemented to calculate $F$, two each moving forward and backward in
time. In addition, $F$ is complex so it has to be measured interferometrically
swingle2016measuring; zhu2016measurement; yao2016interferometric, requiring
extra qubits and gates, or via weak measurement halpern2017jarzynski, which is
not widely available. It is also possible to measure scrambling via
correlations between randomized measurements vermersch2019probing. But
achieving an accurate simulation over long times with high time resolution is
difficult with standard Trotter simulation cirstoiu2020variational;
commeau2020variational; gibbs2021long; geller2021experimental;
bharti2020iterative; lau2021quantum; haug2020generalized;
barison2021efficient; trout2018simulating; endo2020variational;
yao2020adaptive; benedetti2020hardware. We introduce techniques to address
these limitations and help enable the study and visualization of quantum
information dynamics with cloud-based quantum computers.

The first quantum simulations of an OTOC were made by Li et al.
li2017measuring on a nuclear magnetic resonance simulator and by Gärttner et
al. garttner2017measuring on a long-range Ising spin simulator. Since then,
the experimental study of scrambling has made impressive progress
meier2019exploring; nie2019detecting; landsman2019verified; blok2021quantum;
chen2020detecting; niknam2020sensitivity; mi2021information;
braumuller2021probing; chen2021observation; joshi2020quantum;
zhu2021observation, including recent striking demonstrations of teleportation-
based OTOC measurement landsman2019verified; blok2021quantum, which
distinguishes OTOC decay due to unitary scrambling from decoherence, and
Google’s measurement of OTOC fluctuations on random circuits containing up to
53 qubits mi2021information, which distinguishes operator entanglement from
spreading. Google also measured operator spreading in a 2d array of qubits
mi2021information.

Figure 1: Commutator $C_{1j}(t)$ versus qubit position $j$ and time $t$. (a)
Integrable regime, where no spreading occurs. The OTOC is calculated at times
$t\in\\{0,\tau,2\tau,\cdots,24\tau\\}$, with resolution $\tau\\!=\\!0.06$, and
time is plotted in units of $\tau$. (b) Chaotic regime, calculated with
$\tau\\!=\\!0.03$, showing ballistic operator spreading. Parameters for both
regimes are given in Table 1.

In this work we use quantum simulation techniques to study spreading of the
Pauli operator $X(t)\\!=\\!e^{iHt}Xe^{-iHt}$ in the Ising chain

$\displaystyle H$ $\displaystyle=$ $\displaystyle
H^{0}+B_{x}\sum_{i=1}^{n}X_{i},$ (3) $\displaystyle H^{0}$ $\displaystyle=$
$\displaystyle J\sum_{i=1}^{n-1}Z_{i}Z_{i+1}+B_{z}\sum_{i=1}^{n}Z_{i},$ (4)

with $n$ spins. The model is separated into a classical Ising chain $H^{0}$
plus a noncommuting transverse field. The model (3) permits efficient
Hamiltonian simulation via Trotterization. $H^{0}$ is also exactly solvable, a
property used below. We measure and plot the commutator

$\displaystyle C_{ij}(t)={\rm
tr}(\rho\big{|}[X_{i}(t),X_{j}(0)]\big{|}^{2})=2-2\,{\rm Re}\,F_{ij}(t),$ (5)

in the state $\rho=|0000\rangle\langle 0000|$, with $X(t)$ initially localized
at $i\\!=\\!1$. In particular, we study $C_{1j}$ as a function of qubit
position $j\in\\{1,2,\dots,N\\}$ and time $t$. The quantum simulations are
implemented on the IBM Q processor ibmq_sydney using qubits
$\\{Q_{1},Q_{2},Q_{3},Q_{5}\\}$ SI. The measured OTOC is

$\displaystyle F_{1j}(t)=\langle
0000|U^{\dagger}X_{1}UX_{j}U^{\dagger}X_{1}UX_{j}|0000\rangle,$ (6)

where $U$ is a 4-qubit circuit simulating $e^{-iHt}$. The commutator (5) was
chosen because it exhibits a particularly smooth, easily visualized dynamics,
using an easy-to-prepare state. Operator spreading diagnosed by alternative
commutators are compared in SI.

In the experiments we always use one of the two parameter sets given in Table
1, both of which simulate ferromagnetic spin chains. One set corresponds to an
integrable regime of the dynamics; the other generates quantum chaos, which
causes unitary OTOC decay. The models are chosen to display smooth charge
spreading dynamics on the timescales of interest. The measurements in the
integrable regime are relevant for recent theoretical work investigating the
role of integrability on scrambling lin2018out; fortes2019gauging, as well as
serving as a scrambling-free experimental control. The commutator (5) is a
real number $0\leq C_{1j}(t)\leq 4$, and can be represented by a surface in
spacetime $j\\!\times\\!t$. Figure 1 shows two such surfaces, obtained by
classical simulation, for $n\\!=\\!6$. These simulations assume perfect
Hamiltonian simulation $U=e^{-iHt}$ with no Trotter error. Operator
localization in Fig. 1a and spreading in Fig. 1b are evident. These high-
resolution simulations allow one to investigate operator spreading dynamics in
great detail.

Figure 2: Chaotic $C_{1j}(t)$ commutator of Fig. 1b recalculated with the fixed-node OTOC. Table 1: Ising model parameters. | $J$ | $B_{x}$ | $B_{z}$
---|---|---|---
Integrable regime | -1 | 0 | 1
Chaotic regime | -1 | 0.7 | 1.5

Fixed-node OTOC. A standard approach to measuring an OTOC on $n$ qubits is to
add a qubit that can control the $W$ and $V$ gates swingle2016measuring;
zhu2016measurement. Here we introduce an alternative approach, which is
approximate but allows one to reach larger problem sizes. Writing the OTOC in
polar form as $F_{ij}=e^{i\arg F_{ij}}\,|F_{ij}|$, we note that the phase
becomes irrelevant in the scrambling regime, because $|F_{ij}|\approx 0$
there. $|F_{ij}|$ can be measured directly with no qubit overhead
swingle2016measuring, at least on simple states. Therefore we introduce an
approximation for $\arg F_{ij}$ that is exact in the integrable regime, namely
$\arg F_{ij}^{0}$, where $F_{ij}^{0}$ is the OTOC calculated with the
classical Hamiltonian $H^{0}.$ For the Ising model (3),

$\displaystyle F^{0}_{1j}(t)=\begin{cases}e^{4i(J+B_{z})t}&{\rm if}\ j=1,\\\
e^{4iJt}&{\rm if}\ j=2,\\\ 1&{\rm if}\ j>2.\\\ \end{cases}$ (7)

This results in a fixed-node variant of the OTOC,

$\displaystyle F_{ij}=e^{i\arg F_{ij}^{0}}\,|F_{ij}|.$ (8)

One can think of the fixed-node OTOC as an approximation to (2), or as an
independent quantity that also diagnoses scrambling.

Using the fixed-node OTOC, the commutator takes the form

$\displaystyle C_{ij}=2-2|F_{ij}|\cos(\arg F_{ij}^{0}).$ (9)

The chaotic surface of Fig. 1b, recalculated with the fixed-node OTOC, is
shown in Fig. 2.

By construction, the fixed-node OTOC is close to the exact OTOC in the late
time regime, where $F_{ij}\approx 0\ (C_{ij}\approx 2)$. However, it also
satisfies an important causality constraint that extends its accuracy to the
regime of $F_{ij}\approx 1\ (C_{ij}\approx 0)$ as well, namely, the early
scrambling regime. Causality requires that the exact OTOC satisfies $F_{ij}=1$
outside the lightcone, i.e. when $|{\bf r}_{i}-{\bf r}_{j}|>vt$, with ${\bf
r}_{i,j}$ the local operator positions and $v$ the butterfly velocity.
Therefore ${\rm arg}(F_{ij})\\!=\\!0$ there. Because $F_{ij}^{0}$ also
satisfies this constraint, $C_{ij}$ computed from the fixed-node OTOC is also
accurate outside the lightcone, as is evident in Fig. 2. Thus, while there are
small differences in the peak structure in $C_{1j}(t)$, mainly at $j\\!=\\!1$,
the overall spreading dynamics is accurately captured. The fixed-node
commutator in the integrable regime is identical to the surface of Fig. 1a.

Figure 3: (Color online) Weaved time evolution. (a) Standard Trotter method,
where a step $U(\tau)$ is repeatedly applied. (b) Weaving implements a fine-
grained time evolution, with time resolution $\tau$, without incurring the
gate errors of (a). Here the red column represents the sequence
$U(k\tau)\cdots U(k\tau)$, orange represents $U(k\tau)\cdots U(k\tau)U(\tau)$,
yellow represents $U(k\tau)\cdots U(k\tau)U(2\tau)$ and purple represents
$U(k\tau)\cdots U(k\tau)\,U((k\\!-\\!1)\tau).$

Trotter weave. To measure $C_{ij}(t)$ with the high time resolution used in
Fig. 1, one might construct a Trotter approximation $U(\tau)\approx
e^{-iH\tau}$ for evolution by a short time $\tau$. Then, to simulate later
times $t\\!=\\!\ell\tau$, the operator $U(\tau)$ is applied $\ell$ times:

$\displaystyle e^{-iH\ell\tau}\approx U(\tau)^{\ell}\\!.$ (10)

The value of $\tau$ determines the time resolution. However, the circuit depth
resulting from this standard Trotterization, based on the repeated application
of a single step $U(\tau)$, is $t/\tau$. Thus, the performance of (10) quickly
degrades with $t$ due to gate errors and decoherence, limiting the simulation
to short times. We address this by an extension of Trotter simulation based on
a collection of elementary evolution operators.

Figure 4: (Color online) Measured operator spreading surface in the integral
regime, using the fixed-node OTOC. The main figure uses a 6-weave with
$\tau=0.06$, and includes both CNOT and measurement error mitigation. $C_{1j}$
is defined in (5), with $j\in\\{1,2,3,4\\}$ the coordinate of the probe qubit.
The OTOC is measured at times $t\in\\{0,\tau,2\tau,3\tau,\cdots,24\tau\\}$,
and time is plotted in units of $\tau$. The inset shows the classically
computed noise-free surface. Figure 5: (Color online) Operator spreading in
the chaotic regime using the fixed-node OTOC. We use a 6-weave with
$\tau=0.03$, and also include error mitigation. The OTOC is measured at times
$t\in\\{0,\tau,2\tau,\cdots,72\tau\\}$. The inset shows the noise-free
surface.

A $k$-weave is a set of $k$ unitaries

$\displaystyle\bigg{\\{}U(\tau),U(2\tau),\cdots,U(k\tau)\bigg{\\}},$ (11)

where $\tau$ is a fixed short evolution time and each $U(dt)$ is a Trotterized
evolution operator, propagating a state for a short time $dt$. The integer
$k\in\\{1,2,3,\cdots\\}$ is called the weave modulus. The unitaries in (11)
have different roles: $U(k\tau)$ is the cell operator and the remaining $k-1$
unitaries are called shift operators. Repeated applications of the cell
propagates a state from $t=0$ to a time $t=(\ell-\ell\,{\rm
mod}\,k)\\!\times\\!\tau$, but with coarse time resolution $k\tau$. The coarse
evolution is then followed (or preceeded) by a single shift operator
propagating for a short interval with fine-grained time precision $\tau$.
Instead of (10), weaving implements a time evolution according to

$\displaystyle e^{-iH\ell\tau}\approx U(k\tau)^{\frac{\ell-\ell{\rm
mod}k}{k}}U(\ell\,{\rm mod}\,k\times\tau),$ (12)

where the cell operator is applied $(\ell-\ell\,{\rm mod}\,k)/k$ times after a
single shift operator. This is illustrated in Fig. 3. When $\ell\gg k$, this
leads to a $k$-fold reduction in circuit depth, and to higher circuit
fidelity, at the expense of increased of Trotter error. Weaving can be applied
to Hamiltonian simulation techniques beyond Trotterization as well.

For our first set of measurements we use the weave operators
$\\{U(\ell\tau)\\}_{\ell=1}^{k}$, where

$\displaystyle U(\ell\tau)$ $\displaystyle=$
$\displaystyle\prod_{i=1}^{n}\\!R_{\rm
x}(B_{x}\ell\tau)_{i}\times\prod_{i=1}^{n-1}\\!R_{\rm zz}(2J\ell\tau)_{i,i+1}\
$ (13) $\displaystyle\times$ $\displaystyle\prod_{i=1}^{n}\\!P_{\rm
z}(2B_{z}\ell\tau)_{i}\times\prod_{i=1}^{n}\\!R_{\rm x}(B_{x}\ell\tau)_{i},$

resulting from a Trotterization of the model (3). Here
$R_{x}(\theta)_{i}\\!=\\!e^{-i\theta X_{i}/2}$ is a rotation on qubit $i$,

$\displaystyle R_{zz}(\theta)_{ij}=e^{-i\frac{\theta}{2}Z_{i}\otimes
Z_{j}}={\rm CNOT}_{ij}\ P_{z}(\theta)_{i}\ {\rm CNOT}_{ij}\ \ \ \ \ $ (14)

is a $ZZ$ rotation, $P_{z}(\varphi)\\!=\\!{\rm diag}(1,e^{i\varphi})$ is a
phase gate, and ${\rm CNOT}_{ij}$ is an $X$ on qubit $j$ controlled by $i$.
For general angles $\theta$, $R_{zz}(\theta)_{ij}$ requires two CNOTs per
graph edge, or $2(n-1)$ CNOTs per Trotter step on a chain of length $n$. The
quantum simulation results reported here use (up to) two weave operators per
Hamiltonian simulation, requiring $4(n-1)$ CNOTs per evolution. This leads to
a total of $16(n-1)$ CNOTs per OTOC simulation (48 CNOTs for $n=4$).

Results. All of the quantum simulation results in this study were obtained
with the IBM Q processor ibmq_sydney on the 4-qubit chain
$\\{Q_{1},Q_{2},Q_{3},Q_{5}\\}$ SI. Quantum simulations using Trotter weave
modulus $k=6$ are shown in Figs. 4 and 5. Figure 4 shows the measured
spreading surface $C_{1j}(t)$ in an integral regime of the spin chain. Figure
5 is the same, but calculated in a chaotic regime of the model. The parameter
values used are shown in Table 1. The data in both regimes are corrected for
measurement errors using transition matrix error mitigation
maciejewski2020mitigation; nachman2020unfolding; hamilton2020scalable;
bravyi2021mitigating; geller2021toward, and for incoherent CNOT errors using
zero-noise extrapolation temme2017error; dumitrescu2018cloud. The raw data
from this study is provided in SI.

The values of $\tau$ (time resolution) and $k$ (weave modulus) are chosen to
balance gate errors and Trotter errors over the relevant time scales of the
simulation. In particular, $\tau$ has to be small enough to resolve the
oscillations in the peaks of the spreading surfaces (see Figs. 1 and 2).
However, $\tau$ also has to be large enough to enable simulations that probe
the long-time spreading dynamics. A large value of $k$ is desirable because it
enables longer simulations, as fewer applications of the cell circuit are
required. But a large value of $k$ also leads to larger Trotter errors in the
weave operators.

Figure 6: (Color online) Measured operator spreading surfaces using the fixed-
node OTOC and magic cell operator. (a) 16-weave in the integrable regime with
$\tau=0.098$ and up to 32 steps. (b) 20-weave in the chaotic regime with
$\tau=0.079$ and up to 30 steps. Insets show the noise-free surfaces.

Magic cell. In many weaving applications, the largest Trotter error will come
from the cell $U(k\tau)$, because its evolution time $k\tau$ is largest.
However, some simulations admit simplified Trotter steps $U(dt)$ for certain
“magic” values of $dt$. In the Ising chain, for example, this occurs when
$2J\,dt=\pm\frac{\pi}{2},$ because for these angles we can use the
decomposition

$\displaystyle
R_{zz}({\textstyle\frac{\pi}{2}})_{ij}=e^{-i\frac{\pi}{4}Z_{i}\otimes
Z_{j}}=e^{-i\frac{\pi}{4}}S_{i}S_{j}{\rm CZ}_{ij},\ \ \ $ (15)

or its Hermitian conjugate, instead of (14). Here $S\\!=\\!{\rm
diag}(1,e^{i\frac{\pi}{2}})$ and CZ is a controlled-$Z$ gate that can be
implemented using a single CNOT and two Hadamard gates. This leads to a two-
fold reduction in the number of CNOTs required. We demonstrate this variation,
where the weave is built around a magic cell operator with evolution time
$dt_{\rm magic}\\!=k\tau=\pi/4|J|$. Because $dt_{\rm magic}$ is now fixed to a
special value, the use of a magic cell imposes a constraint $dt_{\rm
magic}\\!=\\!k\tau$ on $k$ and $\tau$; they are no longer independent.
Operator spreading measurements using a 16-weave with magic cell in the
integrable regime, and a 20-weave with magic cell in the chaotic regime, are
shown in Fig. 6. The parameter values used are shown in Table 1. The data in
both regimes are error mitigated. The benefits of using a magic cell here are
modest, because we only apply it once. However, the use of a magic cell has
the potential to significantly extend the range of Trotterized quantum
simulation as gate errors improve and larger circuits become possible.

Conclusions. Recent experiments have established that scrambling can be
simulated with current gate-based quantum computers landsman2019verified;
blok2021quantum; chen2020detecting; niknam2020sensitivity; mi2021information;
braumuller2021probing; chen2021observation; joshi2020quantum;
zhu2021observation, making it possible to investigate interesting unsolved
problems at the intersection of quantum information and physics. In this work
we introduce and demonstrate techniques to enable high-resolution operator
spreading measurements with cloud-based quantum computers. Trotter weaving
provides the high time resolution, and the fixed-node OTOC enables larger
problem sizes. Both approaches are practical for online users and have
applications elsewhere in quantum information science. We observe clear
signatures of operator spreading in a chaotic regime of a 4-qubit Ising model,
as well as operator localization in an integrable regime. These techniques
help make it possible to study information dynamics in strongly correlated and
highly entangled quantum systems.

Acknowledgments. We thank Andreas Albrecht for useful discussions. PJC and AS
acknowledge initial support and MRG acknowledges support from LANL’s
Laboratory Directed Research and Development (LDRD) program under project
number 20190065DR. AA and ZH acknowledge, and PJC and AS acknowledge
(subsequent to the above acknowledged funding) that this work was supported by
the U.S. Department of Energy, Office of Science, Office of High Energy
Physics QuantISED program under Contract No. KA2401032. ZH acknowledges
support from the LANL LDRD-funded Mark Kac Postdoctoral Fellowship. BY
acknowledges support of the U.S. Department of Energy, Office of Science,
Basic Energy Sciences, Materials Sciences and Engineering Division, Condensed
Matter Theory Program, and partial support from the Center for Nonlinear
Studies.

Supplementary Information for
“Quantum Simulation of Operator Spreading in the Chaotic Ising Model”

This document provides additional details about the experimental results.
Section 1 describes the online superconducting qubits used, and gives
calibration results (gate errors, coherence times, and single-qubit
measurement errors) provided by the backend. Section 2 presents raw data. In
Sec. 3 we discuss the error mitigation techniques used and their effect on the
data. In Sec. 4 we calculate the OTOC for the classical Ising model $H^{0}$.
Alternative OTOCs are discussed in Sec. 5.

##  1 Qubits

In this section we discuss the online superconducting qubits used in this
work. Data was taken on the IBM Q processor ibmq_sydney using the BQP software
package developed by the authors. We measure the OTOC on qubits
$\\{Q_{1},Q_{2},Q_{3},Q_{5}\\}$ shown in Fig. S1. Calibration data supplied by
the backend is summarized in Table 1. Here $T_{1,2}$ are the standard
Markovian decoherence times, and

$\epsilon=\frac{T(0|1)+T(1|0)}{2}$ (S1)

is the single-qubit state-preparation and measurement (SPAM) error, averaged
over initial classical states. $T(0|1)$ is the probability of measuring a
$|0\rangle$ state after preparing $|1\rangle$; $T(1|0)$ is the reverse. The
$U_{2}$ error column gives the single-qubit gate error measured by randomized
benchmarking. The reported CNOT errors are also measured by randomized
benchmarking.

Table 1: Calibration data provided by IBM Q for the ibmq_sydney chip during the period of data acquisition. | Qubit | $T_{1}\ (\mu s)$ | $T_{2}\ (\mu s)$ | SPAM error $\epsilon$ |  $U_{2}$ error
---|---|---|---|---
$Q_{1}$ | 99.7 | 37.3 | 0.043 | 2.83e-4
$Q_{2}$ | 107.9 | 65.5 | 0.015 | 1.80e-4
$Q_{3}$ | 78.7 | 51.7 | 0.017 | 3.15e-4
$Q_{5}$ | 147.4 | 61.1 | 0.017 | 1.64e-4
| CNOT gates | CNOT error
---|---
| ${\rm CNOT}_{1,2}$ | ${\rm CNOT}_{2,1}$
---|---
7.67e-3
| ${\rm CNOT}_{2,3}$ | ${\rm CNOT}_{3,2}$
---|---
7.00e-3
| ${\rm CNOT}_{3,5}$ | ${\rm CNOT}_{5,3}$
---|---
7.68e-3
Figure S1: Layout of IBM Q device ibmq_sydney. In this work we use qubits
$Q_{1}$, $Q_{2}$, $Q_{3}$ and $Q_{5}$.

##  2 Raw operator spreading data

The raw operator spreading surfaces are shown in Figs. S2 and S3. The
differences between the raw and error-mitigated data are shown in Sec. 3.

Figure S2: Raw spreading data in the integral regime, with the same settings
as in Fig. 4. Figure S3: Raw spreading data in the chaotic regime, with the
same settings as in Fig. 5.

Figure S4: Difference $C_{\rm TMEM}\\!-\\!C_{\rm raw}$ between measurement-
corrected and raw surfaces in the integrable regime. Figure S5: Difference
$C_{\rm TMEM}\\!-\\!C_{\rm raw}$ between measurement-corrected and raw
surfaces in the chaotic regime.

##  3 Error mitigation

In this work we correct all data for measurement errors using transition
matrix error mitigation (TMEM)maciejewski2020mitigation; nachman2020unfolding;
hamilton2020scalable; bravyi2021mitigating; geller2021toward, and for
incoherent CNOT errors using zero-noise extrapolation temme2017error;
dumitrescu2018cloud. In TMEM, the matrix $T$ of transition probabilities
between all prepared and observed classical states $x\in\\{0,1\\}^{n}$ is
initially measured. Then noisy data is corrected by minimizing $\|T\,p_{\rm
corr}-p_{\rm noisy}\|_{2}^{2}$ subject to constraints $0\leq p_{\rm
corr}(x)\leq 1$ and $\|p_{\rm corr}\|_{1}=1$. Here $\|\cdot\|_{2}$ is the
Euclidean norm and $\|\cdot\|_{1}$ is the $\ell_{1}$-norm. The effect of TMEM
on the operator spreading data is shown in Figs. S4 and S5.

Figure S6: Difference $C_{\rm CNOT}\\!-\\!C_{\rm raw}$ between CNOT-corrected
and raw surfaces in the integrable regime. Figure S7: Difference $C_{\rm
CNOT}\\!-\\!C_{\rm raw}$ between CNOT-corrected and raw surfaces in the
chaotic regime.

The CNOT error mitigation involves measuring each circuit together with a
variant, obtained by replacing each CNOT in the original circuit by a
logically equivalent CNOT3. Let ${\rm Pr}(x|m)$ be the probability of
observing classical state $x$ after implementing a circuit with each original
CNOT replaced by $m$ consecutive CNOTs. Then let $\\{{\rm Pr}(x|1)\\}_{x}$ be
a measured probability distribution for the original circuit, and $\\{{\rm
Pr}(x|3)\\}_{x}$ be that for the CNOT3 variant. Assuming that the total
incoherent CNOT error in the circuit occurs in proportion to the number of
CNOTS implemented, one can use the two data points ${\rm Pr}(x|1)$ and ${\rm
Pr}(x|3)$ to define a line with intercept

$\displaystyle{\rm Pr}(x|0):=\frac{3\,{\rm Pr}(x|1)-{\rm Pr}(x|3)}{2},$ (S2)

which defines a candidate correction. Here $m=0$ means no incoherent CNOT
error. If $0\leq{\rm Pr}(x|0)\leq 1$ for all $x$, then we accept it as the
corrected probability distribution:

$\displaystyle{\rm Pr}(x)_{\rm corr}={\rm Pr}(x|0).$ (S3)

Otherwise we find the physical ${\rm Pr}(x)_{\rm corr}$ closest to ${\rm
Pr}(x|0)$ in Frobenius distance. The effect of CNOT noise extrapolation on the
operator spreading data is shown in Figs. S6 and S7.

Figure S8: Difference $C_{\rm corr}\\!-\\!C_{\rm raw}$ between fully corrected
and raw surfaces in the integrable regime. Figure S9: Difference $C_{\rm
corr}\\!-\\!C_{\rm raw}$ between fully corrected and raw surfaces in the
chaotic regime.

The net effect of TMEM and CNOT noise extrapolation on the operator spreading
data is shown in Figs. S8 and S9. When both error mitigations are applied to
the raw operator spreading data, we obtain the surfaces in Figs. 4 and 5.

##  4 Classical OTOC

In the fixed-node approach, the absolute value of the OTOC is measured on the
quantum processor but its phase is efficiently calculated from $F_{ij}^{0}$,
the OTOC (6) calculated with the classical Hamiltonian $H^{0}$ of (4). To
calculate this phase, we need the energy of the $n$-qubit state $|0\cdots
0\rangle$, which is

$\displaystyle E_{0}=(n-1)J+nB_{z}.$ (S4)

Next we assume that $n\geq 3$. The energy of the single-excitation state
$X_{j}|0\cdots 0\rangle=|0\cdots 1_{j}\cdots 0\rangle$ is

$\displaystyle E_{0\cdots 1_{j}\cdots 0}=\begin{cases}E_{0}-2J-2B_{z}&{\rm
if}\ j\in\\{1,n\\},\\\ E_{0}-4J-2B_{z}&{\rm else}.\\\ \end{cases}$ (S5)

We will also need the energy of the double-excitation state $|10\cdots
1_{j}\cdots 0\rangle$, with $j\geq 2$, which is

$\displaystyle E_{10\cdots 1_{j}\cdots 0}=\begin{cases}E_{0}-2J-4B_{z}&{\rm
if}\ j=2,\\\ E_{0}-4J-4B_{z}&{\rm if}\ j=n,\\\ E_{0}-6J-4B_{z}&{\rm else}.\\\
\end{cases}$ (S6)

To calculate the OTOC we first write it as

$F^{0}_{1j}(t)=\sum_{x}\langle 0\cdots 0|X_{1}(t)X_{j}|x\rangle\langle
x|X_{1}(t)X_{j}|0\cdots 0\rangle,$ (S7)

where $|x\rangle$ is a classical state with $x\in\\{0,1\\}^{n}$. If $j=1$ we
have

$\displaystyle F^{0}_{11}(t)$ $\displaystyle=$ $\displaystyle\langle 0\cdots
0|X_{1}(t)|10\cdots 0\rangle^{2}$ (S8) $\displaystyle=$ $\displaystyle\langle
0\cdots 0|e^{iE_{0}t}X_{1}e^{-i(E_{0}-2J-2B_{z})t}|10\cdots 0\rangle^{2}$
$\displaystyle=$ $\displaystyle e^{4i(J+B_{z})t},$

where we have used (S5).

If $j>1$, we have

$\displaystyle F^{0}_{1j}(t)$ $\displaystyle=$ $\displaystyle\sum_{x}\langle
0\cdots 0|X_{1}(t)X_{j}|x\rangle\langle x|X_{1}(t)X_{j}|0\cdots 0\rangle$ (S9)
$\displaystyle=$ $\displaystyle\langle 0\cdots 0|X_{1}(t)|10\cdots
0\rangle\langle 10\cdots 1_{j}\cdots 0|X_{1}(t)|0\cdots 1_{j}\cdots 0\rangle$
(S10) $\displaystyle=$ $\displaystyle\langle 0\cdots
0|e^{iE_{0}t}X_{1}e^{-iHt}|10\cdots 0\rangle\langle 10\cdots 1_{j}\cdots
0|e^{iHt}X_{1}e^{-iHt}|0\cdots 1_{j}\cdots 0\rangle$ (S11) $\displaystyle=$
$\displaystyle e^{2i(J+B_{z})t}\langle 10\cdots 1_{j}\cdots
0|e^{iHt}X_{1}e^{-iHt}|00\cdots 1_{j}\cdots 0\rangle,$ (S12)

and there are three cases to consider: When $j=2$, (S12) becomes

$\displaystyle F^{0}_{12}(t)$ $\displaystyle=$ $\displaystyle
e^{2i(J+B_{z})t}\langle 110\cdots 0|e^{iHt}X_{1}e^{-iHt}|01\cdots 0\rangle$
(S13) $\displaystyle=$ $\displaystyle e^{2i(J+B_{z})t}\langle 110\cdots
0|e^{i(E_{0}-2J-4B_{z})t}X_{1}e^{-i(E_{0}-4J-2B_{z})t}|01\cdots 0\rangle$
(S14) $\displaystyle=$ $\displaystyle e^{2i(J+B_{z})t}e^{2i(J-B_{z})t}$ (S15)
$\displaystyle=$ $\displaystyle e^{4iJt},$ (S16)

where we have used (S6). When $2<j<n,$ (S12) becomes

$\displaystyle F^{0}_{1j}(t)$ $\displaystyle=$ $\displaystyle
e^{2i(J+B_{z})t}\langle 10\cdots 1_{j}\cdots 0|e^{iHt}X_{1}e^{-iHt}|0\cdots
1_{j}\cdots 0\rangle$ (S17) $\displaystyle=$ $\displaystyle
e^{2i(J+B_{z})t}\langle 10\cdots 1_{j}\cdots
0|e^{i(E_{0}-6J-4B_{z})t}X_{1}e^{-i(E_{0}-4J-2B_{z})t}|0\cdots 1_{j}\cdots
0\rangle$ (S18) $\displaystyle=$ $\displaystyle
e^{2i(J+B_{z})t}e^{-2i(J+B_{z})t}$ (S19) $\displaystyle=$ $\displaystyle 1.$
(S20)

And when $j=n$, (S12) becomes

$\displaystyle F^{0}_{1n}(t)$ $\displaystyle=$ $\displaystyle
e^{2i(J+B_{z})t}\langle 10\cdots 01|e^{iHt}X_{1}e^{-iHt}|0\cdots 01\rangle$
(S21) $\displaystyle=$ $\displaystyle e^{2i(J+B_{z})t}\langle 10\cdots
01|e^{i(E_{0}-4J-4B_{z})t}X_{1}e^{-i(E_{0}-2J-2B_{z})t}|0\cdots 01\rangle$
(S22) $\displaystyle=$ $\displaystyle e^{2i(J+B_{z})t}e^{-2i(J+B_{z})t}$ (S23)
$\displaystyle=$ $\displaystyle 1.$ (S24)

Combining these results leads to the expression (7).

##  5 Other OTOCs

The operator spreading measurements in this work are based on the commutator

$\displaystyle{\rm tr}(\rho\big{|}[X_{i}(t),X_{j}(0)]\big{|}^{2})\ \ {\rm
with}\ \ \rho=|0000\rangle\langle 0000|.\ \ \ $ (S25)

It is interesting to compare (S25) with alternative definitions. A common
alternative is the infinite-temperature version

$\displaystyle{\rm tr}(\rho\big{|}[X_{i}(t),X_{j}(0)]\big{|}^{2})\ \ {\rm
with}\ \ \rho=\frac{I}{d},\ \ $ (S26)

where $I$ is the $d\times d$ identity with $d=2^{n}$. The operator spreading
surfaces of Fig. 1, reevaluated with (S26), are shown in Fig. S10. These
surfaces are ideal results obtained classically. Overall the spreading is
similar to Fig. 1, but there are detailed differences.

It is also interesting to consider a pure state different than
$|0\rangle^{\otimes n}$, such as $|+\rangle^{\otimes n}$. Figure S11 is based
on the commutator

$\displaystyle{\rm tr}(\rho\big{|}[X_{i}(t),X_{j}(0)]\big{|}^{2})\ \ {\rm
with}\ \ \rho=\frac{J}{d},\ \ $ (S27)

where $J$ is the $d\times d$ matrix of ones.

Finally, we consider the commutator

$\displaystyle{\rm tr}(\rho\big{|}[X_{i}(t),Y_{j}(0)]\big{|}^{2})\ \ {\rm
with}\ \ \rho=|0000\rangle\langle 0000|,\ \ \ $ (S28)

which has a peak structure different from (S25) because
$[X_{i}(t),Y_{j}(0)]\neq 0$ at time 0. The operator spreading surfaces of Fig.
1, reevaluated with (S28), are shown in Fig. S12.

Figure S10: Infinite-temperature commutator versus qubit position $j$ and time
$t$. (a) Integrable regime. The OTOC is calculated at times
$t\in\\{0,\tau,2\tau,\cdots,24\tau\\}$, with resolution $\tau\\!=\\!0.06$, and
time is plotted in units of $\tau$. (b) Chaotic regime, calculated with
$\tau\\!=\\!0.03$. Parameters for both regimes are given in Table 1. These
results were obtained by classical simulation. Figure S11: Operator spreading
in the $|+\rangle^{\otimes n}$ state, with other parameters the same as in
Fig. S10.  Figure S12: Spreading of $X_{1}$ probed by $Y_{j}$, with other
parameters the same as in Fig. S10..