# Simulating the Sycamore quantum supremacy circuits

Feng Pan  Institute of Theoretical Physics, Chinese Academy of Sciences,
Beijing 100190, China  School of Physical Sciences, University of Chinese
Academy of Sciences, Beijing 100049, China  Pan Zhang<EMAIL_ADDRESS>Institute of Theoretical Physics, Chinese Academy of Sciences, Beijing 100190,
China

###### Abstract

We propose a general tensor network method for simulating quantum circuits.
The method is massively more efficient in computing a large number of
correlated bitstring amplitudes and probabilities than existing methods. As an
application, we study the sampling problem of Google’s Sycamore circuits,
which are believed to be beyond the reach of classical supercomputers and have
been used to demonstrate quantum supremacy. Using our method, employing a
small computational cluster containing $60$ graphical processing units (GPUs),
we have generated one million correlated bitstrings with some entries fixed,
from the Sycamore circuit with $53$ qubits and $20$ cycles, with linear cross-
entropy benchmark (XEB) fidelity equals $0.739$, which is much higher than
those in Google’s quantum supremacy experiments.

An essential question in near-term quantum computation is whether programmable
quantum devices are able to beyond the ability of classical computations in
specific computational tasks. An ideal example is sampling from a random
quantum circuit [1, 2, 3, 4, 5, 6, 7]. In 2019, Google’s quantum computing
group released the Sycamore circuits [1] with $n=53$ qubits, and demonstrated
the quantum supremacy [8, 7] by showing that they can experimentally solve the
noisy sampling task from the output distribution $P_{U}(\mathbf{s})$ of the
Sycamore circuit $U$ in the computational basis $|\mathbf{s}\rangle$, which
would cost $10,000$ years on modern supercomputers.

However, despite the great success of the experiments, we note that the
critical basis for the assertion of the quantum supremacy, the accuracy of
sampling in terms of the linear cross-entropy benchmark (XEB), and the running
time of classic simulations, still leave some space for further discussions.
First, Google was only able to compute the exact XEB values for circuits up to
$m=12$ cycles and estimated the XEB values from $14$ cycles to $20$ cycles
using extrapolations [1]. This means that the fidelity of samples generated
from the quantum supremacy circuits with $m\geq 14$ cycles are not verified.
Second, the estimate of computational time was based on a classic simulation
method, Schrödinger-Feynman algorithm [2, 9, 1]. Potentially there could be
other algorithms which are more efficient then the algorithm used by Google,
demanding much less computational time than the estimate.

There are basically two kinds of methods for simulating quantum circuits. The
first kind stores and evolves the full quantum state vector $\psi$, and is
known as the Schrödinger method. Since bitstring probabilities
$P_{U}(\mathbf{s})=|\langle\psi|s\rangle|^{2}$ are known, sampling from the
bitstring space is easy. The advantage of the method is that the computational
complexity of the algorithm is linear in the number of depth $m$, thus it is
very efficient for quantum circuits with a small number of qubits. Google used
this method for simulating circuits up to $43$ qubits [1]. However, for a
large number of qubits, this method suffers from exponential space complexity.
Using a supercomputer, the largest instance that has been simulated has $49$
qubits [10], beyond which the size of total random access memory (RAM) becomes
the bottleneck even with supercomputers. IBM has justified theoretically that
the $53$-qubit state vector of the Sycamore circuits can be stored and evolved
if one could employ not only all the RAM but also all the hard disks of the
Summit supercomputer. However, the experiment has not been done yet. To
address the issue of exponential space-complexity with a large number of
qubits, Google used the Schrödinger-Feynman method [2, 9] which breaks the
circuits into two parts, connected using Feynman path-integrals, and each part
is simulated using the Schrödinger method. Based on this method, Google
estimated that simulating the Sycamore circuits with $20$ cycles requires
10,000-year running time on the Summit supercomputer.

The second kind of method does not store all the $2^{n}$ bitstring
probabilities in memory, but computes one bitstring probability or a small
batch of them based on tensor networks [11, 12, 13, 14, 9, 4, 7, 15, 16, 17,
18, 19]. Quantum circuits can be treated as particular tensor networks with
unitary constraints. Given an initial state and the bitstring representing the
measurements at the end, contraction of the tensor network gives the amplitude
of the output bitstring. The space complexity of the tensor network method is
controlled by the size of the largest tensor encountered during the
contraction, which equals the exponential of tree width of the line graph
corresponding to the tensor network [11]. For shallow circuits where the tree
width is small, tensor network method is very efficient even for circuits with
a large number of qubits [4, 14, 13, 15]. However, the tensor network method
is not scalable with the circuit depth, because the complexity is usually
exponential to the depth hence very expensive for large circuits with
sufficient depth. For the Sycamore circuits with $20$ cycles, a recent work
[18] (which is considered as the state-of-the-art) estimated that computing
probabilities for a batch of $64$ bitstrings requires about $833$ seconds
using a Summit-compatible supercomputer. To the best of our knowledge, so far
there is no work that has successfully obtained the probability of even one
bitstring for the Sycamore circuit with $20$ cycles, in practice. More
seriously, sampling from the bitstring space is difficult for the tensor
network method, because the computational complexity is proportional to the
number of samples one demands. In order to obtain enough bitstrings, e.g. for
reaching an XEB value that is comparable to Google’s hardware samples, the
tensor network contraction has to be repeated for many times, making the
overall computations intractable.

In this article, we propose a tensor network method that enables us to fill
the gap. Our method is based on the careful design of subspace to enumerate
(or sample) from. The method can be regarded as an intermediate between the
full-state-vector method and the single(or small-batch)-amplitude method. It
is much more efficient than the Schrödinger-Feynman algorithm and the existing
tensor-network methods for computing probabilities of a large number of
correlated samples from the Sycamore circuits. The computational complexity
for obtaining $2$ million bitstring probabilities is much lower than the
method used by Google [1], and is also lower than the computational complexity
for obtaining only $64$ amplitudes in the state-of-the-art tensor network
method [18]. Our method enjoys massive parallelization over multiple GPUs. By
employing a small computational cluster composed of $60$ GPUs, we have
computed exact amplitudes and probabilities for $2$ million correlated
bitstrings in $5$ days from the Sycamore circuits with $53$ qubits and $20$
cycles. We have obtained $1$ million bistrings from a bistring sub-space,
achieving XEB fidelity $0.739$, which is much higher than the samples obtained
in Google’s experiments.

##  I Big-head simulation of quantum circuits

Storing the full state-vector has the advantage of easy sampling for a large
number of bitstrings because the probability distribution,
$P_{U}(\mathbf{s})$, is stored in memory. But it suffers from the large space
complexity. Computing once a time the probability of a single amplitude (or a
small batch of amplitudes) using tensor network contractions largely reduces
the computational complexity. However, the sampling task is difficult because
one has to repeat the tensor network contraction process. Our idea is to
combine the advantages of two methods, using a sub-space simulation.

As depicted in Fig. 1, we separate $n$ qubits in the end-state (at the right-
most layer in the figure) into two groups with group sizes $n_{1}$ (blue) and
$n_{2}$ (red) respectively. An arbitrary bitstring $\mathbf{s}$ is then
represented as a concatenation of partial bitstrings $\mathbf{s}_{1}$ and
$\mathbf{s}_{2}$, and the probability for the bitstring can be expressed as
$P_{U}(\mathbf{s})=P_{U}(\mathbf{s}_{1};\mathbf{s}_{2})$, the joint
probability of $\mathbf{s}_{1}$ and $\mathbf{s}_{2}$. With $n_{2}=0$, the
method is identical to the single amplitude estimation approach using tensor
networks. With $n_{2}$ small, it is essentially the idea which has been
explored in [18, 9, 1], where a number of qubits at the end state is selected
manually and kept open, giving a small batch (typically $64$) of amplitudes by
a single contraction. We refer to this method as batch approach. However,
there are several difficulties for the batch approach to use a large $n_{2}$.
First, using more open qubits significantly increases the contraction
complexity over single-amplitude contraction. In the literatures, only a small
number (typically 6) of open qubits are selected in order to control the
complexity increase. Second, finding an optimal combination of $n_{2}$ qubits
is a hard combinatorial optimization problem, particularly when the cost for
evaluating the quality of the combinations is very high.

Figure 1:  (Top:) Pictorial representation of a quasi $3$ dimensional tensor
network corresponding to a quantum circuit. The leftmost layer represents the
initial state, and the rightmost layer represents the end state, where the
blue circles represent measured (closed) qubits, which fix the entries in the
final bitstring $\mathbf{s}$, and the red circles represent open qubits, where
the corresponding entries in $\mathbf{s}$ can vary. The yellow plane
$\mathcal{C}$ cuts into the tensor network and separates the network into two
parts, $\mathcal{G}_{\mathrm{head}}$ and $\mathcal{G}_{tail}$, which are
depicted in the left panels. The $\mathcal{G}_{head}$ contains all closed
qubits, and $\mathcal{G}_{tail}$ includes all the open qubits. Both
$\mathcal{G}_{\mathrm{head}}$ and $\mathcal{G}_{\mathrm{tail}}$ are further
partitioned into two sub-graphs hierarchically, until size of the sub-graph is
smaller than $60$. The bottom right panel displays the bottleneck in between
$\mathcal{G}_{\mathrm{head}}$ and $\mathcal{G}_{\mathrm{tail}}$, given by
$\mathcal{C}$.

### Big-head simulation—

In this work, we aim to select a large number of open qubits $n_{2}$, without
significantly increase the overall computational complexity. To this end,
rather than selecting open qubits manually, we first find a (special)
contraction order $\mathcal{O}$ (which indicates a sequence of pairwise
contractions to perform) with a good space and time complexity, then choose
the open qubits based on the order.

For difficult circuits, e.g. the Sycamore circuits, the space complexity for
contracting the full tensor network with a large $n_{2}$ open indices are
typically out of reach even with a near-optimal contraction order. So we
proceed by enumerating all possible partial bitstrings $\mathbf{s}_{2}$, that
is, trading off space complexity using time complexity by enumerating all
possible ways for closing the open qubits. However this approach causes a
serious issue on the time complexity—one needs to repeat the contraction for
$2^{n_{2}}$ times, which is intractable. In order to resolve this issue, we
demand the contraction order found in the first place to satisfy a special
constraint—detecting a big-head structure of the tensor network by identifying
a bottleneck, as illustrated in Fig. 1. Given an end-state bitstring
$\mathbf{s}$, the identified bottleneck separates the whole network into two
parts, the head network $\mathcal{G}_{\mathrm{head}}$ containing all the
closed end-qubits, and the tail tensor network $\mathcal{G}_{\mathrm{tail}}$
containing all the open end-qubits, connected by $n_{c}$ edges. In the
contraction order $\mathcal{O}$, $\mathcal{G}_{\mathrm{head}}$ and
$\mathcal{G}_{\mathrm{tail}}$ are contracted independently, resulting to two
vectors $\mathbf{v}_{\mathrm{head}}(\mathbf{s}_{1})$ and
$\mathbf{v}_{\mathrm{tail}}(\mathbf{s}_{2})$. The amplitude of $\mathbf{s}$ is
computed at the final step of contraction in $\mathcal{O}$, as inner product
of the two vectors
$\psi(\mathbf{s})=\mathbf{v}_{\mathrm{head}}(\mathbf{s}_{1})\cdot\mathbf{v}_{\mathrm{tail}}(\mathbf{s}_{2}).$
Since all $n_{2}$ open qubits are located at $\mathcal{G}_{\mathrm{tail}}$, by
fixing the partial bitstring $\mathbf{s}_{1}$, one only needs to compute
$\mathbf{v}_{\mathrm{head}}(\mathbf{s}_{1})$ once, then reuses it to obtain
amplitude $\psi(\mathbf{s})$ for every $\mathbf{s}_{2}$. By carefully
designing the contraction order $\mathcal{O}$, we can make the contraction
cost dominated by contracting $\mathcal{G}_{\mathrm{head}}$, with the
bottleneck $n_{c}$ small enough such that
$\mathbf{v}_{1}(\mathbf{s}_{\mathrm{head}})$ can be stored and reused. In this
way, amplitudes of $2^{n_{2}}$ correlated bitstrings can be computed with
computational complexity almost identical to that of computing one bitstring.

### The algorithm—

The key component of the big head simulation is finding a contraction order
$\mathcal{O}$ satisfying the constraints described in the last section. We
design the order-finding algorithm relying on a partition algorithm which
splits the whole tensor network into two parts, $\mathcal{G}_{\mathrm{head}}$
and $\mathcal{G}_{\mathrm{tail}}$, using the first cut $\mathcal{C}$ cutting
$n_{c}$ edges. In Fig. 1 we give a pictorial illustration of the first cut
made on a 3-dimensional tensor network. The partition algorithm tries to
minimize the cut size $n_{c}$, given constraints on the group sizes
$\\{n_{1},n_{2}\\}$. To find a first cut and the top partition (as illustrated
in Fig. 1), we need to make sure the computational complexity of contracting
two networks is acceptable. We achieve this by hierarchically partitioning
[20, 12, 18] each sub-graph into two smaller sub-graphs using a clustering
algorithm until every sub-graph is small enough (set to $60$ tensors in this
work). The constraint for the hierarchical partitioning is that both the time
and space complexity of the individual contraction must be smaller than target
values. The hierarchical partitioning also gives a contraction order
$O_{\textrm{coarse}}$ to the coarse-grained graph treating the finest sub-
graphs as vertices. After the partitioning, we contract all the finest sub-
graphs using a greedy contraction order, then contract the coarse-grained
graph according to $O_{\textrm{coarse}}$.

For quantum circuits which are hard to simulate, e.g. the Sycamore circuits
with $20$ cycles, the space complexity of the found order are still too large
to store in the memory. In order to solve this problem, we employ the dynamic
slicing method [14, 16, 21, 12, 18, 19] which selects a set of $n_{e}$ edges
from the tensor network and enumerates the indices associated with the edges.
This breaks the overall contraction task into $2^{n_{e}}$ subtasks, each of
which has much smaller space and time complexity hence can be contracted
independently.

##  II  Simulation of the Sycamore circuits

We focus on Google’s Sycamore circuits with $m=20$ cycles which have been used
for demonstrating quantum supremacy. The sycamore circuits have $n=53$ qubits
locating on a two-dimensional layout (see Fig.1). Each cycle of operations
contains a layer of single-qubit gates (randomly sampled from
{$\sqrt{X},\sqrt{Y},\sqrt{W}$}) and two-qubit FSIM gates with different
parameters $\phi$ and $\theta$. The FSIM gates have decompositional rank $4$
hence are believed to be much harder to simulate than the Controlled-Z gates
[22] even in the approximation level. In the supremacy circuits, different
pairing patterns are alternated (termed as ‘ABCDCDAB’) [1]. The circuit files
were downloaded from [23].

### Computing bitstring probabilities—

We first simplify the quantum circuit by absorbing single-qubit gates into
two-qubit gates, resulting in a tensor network with $n=381$ nodes, then find a
contraction order for the network which partitions the tensors into two sub-
graphs ($\mathcal{G}_{\mathrm{head}}$ and $\mathcal{G}_{\mathrm{tail}}$) with
sizes $n_{\mathrm{head}}=345$, and $n_{\mathrm{tail}}=36$ respectively. We
determined $21$ open qubits in $\mathcal{G}_{\mathrm{tail}}$. Without loss of
generality, we assign $32$ entries of $\mathbf{s}_{1}$, i.e. the rest part of
the bitstring corresponding to closed qubits, to $0$. In contracting
$\mathcal{G}_{\mathrm{head}}$ for obtaining the $\mathbf{v}_{\mathrm{head}}$
vector, we use the dynamic slicing method [14, 16, 21, 12, 18, 19] and divide
the $\mathcal{G}_{\mathrm{head}}$-contraction task into $2^{23}$ sub-tasks,
each of which has space complexity $2^{30}$ to fit into $32$G memory of GPU.
The time complexity of contractions are listed in Tab. 1. From the table, we
can see that the time complexity of contracting $\mathcal{G}_{\mathrm{head}}$
dominates $T_{2^{21}}$, the overall computational complexity for obtaining
$2^{21}$ bitstring amplitudes. The computational cost for obtaining a
different number of bitstrings in different algorithms is compared in Tab.2.
We remark that our computational cost for obtaining $2$ million bitstring
probabilities is much lower than the estimated computational cost of the
Shrödinger-Feynman method used by Google [1], and is also lower than the
computational complexity for obtaining $64$ amplitudes in the state-of-the-art
tensor network method [18]. Our algorithm can be trivially parallelized on
multiple GPUs. So in our experiments, we employed a small computational
cluster composed of $48$ NVIDIA V100 and $12$ A100 GPUs. We ran all the sub-
tasks independently on GPUs (sharing with other user jobs), which are
trivially parallelized without any communications among them. The overall
computation cost about $5$ days. More details about the algorithm and the
computations can be found in the Appendices.

#subtasks | $S_{\text{total}}$ | $T_{\text{sub}}$ | $T_{\text{head}}$ | $T_{\text{tail}}$ | $T_{\text{total}}$
---|---|---|---|---|---
$2^{23}$ | $2^{30}$ | $5.37\times 10^{11}$ | $4.51\times 10^{18}$ | $2.87\times 10^{15}$ | $4.51\times 10^{18}$
Table 1: The number of sub-tasks (#subtasks), total space complexity $S_{total}$, time complexity for a single subtask $T_{sub}$, time complexity for contracting the head network, $T_{\mathrm{head}}$, time complexity for contracting the tail network $T_{\mathrm{tail}}$, and time complexity for obtaining totally $2^{21}$ bitstrings $T_{\mathrm{tail}}$ in the simulation of Sycamore circuit with $20$ cycles. | # bitstrings | Time complexity | Space complexity | Computational time | Computational hardware
---|---|---|---|---|---
Google [1] | $10^{6}$ | — | — | 10,000 years | Summit supercomputer
Cotengra [12] | 1 | $3.10\times 10^{22}$ | $2^{27}$ | 3,088 years | One NVIDIA Quadro P2000
Alibaba [18] | 64 | $6.66\times 10^{18}$ | $2^{29}$ | 267 days | One V100 GPU
Ours | $\mathbf{2097152}$ | $4.51\times 10^{18}$ | $2^{30}$ | 149 Days | One A100 GPU
Table 2: Comparison of computational cost among different methods on Sycamore
circuit with $53$ qubits and $20$ cycles.

### Fidelity—

A standard test for accuracy of obtained $L$ bitstrings,
$\\{\mathbf{s}_{i}\\}_{i=1}^{L}$, is the linear cross entropy benchmark (XEB)
fidelity [2, 7, 1],

$F_{\mathrm{XEB}}=\frac{2^{n}}{L}\sum_{i=1}^{L}P_{U}(\mathbf{s}_{i})-1.$ (1)

Notice that $P_{U}(\mathbf{s}_{i})$ is the probability of the bitstring in the
circuit $U$, which requires an exact evaluation of the amplitudes. When the
samples are generated from the Porter-Thomas distribution [24, 25, 7]

$\mathrm{Prob}(p)=2^{n}\exp(-p2^{n}),$ (2)

one has $F_{\mathrm{XEB}}=1$. On the other hand, if the bitstrings are sampled
from the random uniform distribution, one would have $F_{\textrm{XEB}}=0$. In
Google’s quantum supremacy experiments, they achieved
$F_{\textrm{XEB}}=0.002$.

In this work, without loss of generality, we fix $32$ entries as
$\mathbf{s}_{1}=\underbrace{0,0,0,\cdots,0}_{32}$, and enumerate all possible
combinations of other $21$ entries in the bitstring. This produces a set of
$2^{21}$ correlated bitstrings, denoted as
$\Omega=\\{\mathbf{s}_{1};\mathbf{s}_{2}^{(i)}\\}_{i=1}^{L}$, where
$L=2^{21}$. Some samples of bitstrings can be found in Appendices. Since we
assign equal weight for all $2^{21}$ bitstrings, the distribution of the
bitstrings can be regarded as uniform distribution
$P_{\textrm{gen}}(\mathbf{s}_{1};\mathbf{s}_{2})=2^{-21}$ for all $2^{21}$
bitstrings, given an assignment of the rest $32$ entries $\mathbf{s}_{1}$
which the $F_{\mathrm{XEB}}$ should depend on. We plot the histogram of the
obtained $2^{21}$ bitstrings in Fig. 2, where we can see that the obtained
distribution is very close to the Porter-Thomas distribution, with
$F_{\mathrm{XEB}}$ value equals to $-0.000926$, which is close to $0$. The
minimum and the maximum probability of bitstrings are
$P_{\textrm{min}}=8.04\times 10^{-8}\times 2^{-53}\approx 0$ and
$P_{\textrm{max}}=16.1\times 2^{-53}$ respectively. Thus, we are able to post-
select a subset of bitstrings such that the XEB of the selected bitstrings
varies in between $F_{\mathrm{XEB}}^{\textrm{min}}=-1.0$ and
$F_{\mathrm{XEB}}^{\textrm{max}}=15.1$. In Fig. 2 we sort the bitstring
probabilities then plot the $F_{\mathrm{XEB}}$ value as a function of fraction
of bitstrings in the post-selection. In particular, by selecting bitstrings
with top probabilities, we arrive at $10^{6}$ bitstrings with
$F_{\mathrm{XEB}}=0.739$. We remark that for reaching the $F_{\mathrm{XEB}}$,
the probability for all bitstrings are computed exactly. This is in contrast
to the previous methods which require a sampling method, e.g. the frugal
sampling [9, 1], to mix a small number of bitstrings with (known) large
probabilities to a large number of random bitstrings with unknown
probabilities.

Figure 2:  (Left): Histogram of bitstring probabilities
$P_{U}(\mathbf{s})=P_{U}(\mathbf{s}_{1};\mathbf{s}_{2})$ for $L=2^{21}$
bitstrings obtained from the Sycamore circuit with $n=53$ qubits, $m=20$
cycles, sequence ABCDCDAB, seed $0$, and the assignment of partial bitstring
$\mathbf{s}_{1}$ are fixed to $\underbrace{0,0,0,\cdots,0}_{32}$. In the
figure, $N=2^{53}$, $p$ denotes the probability of bitstring
$P_{U}(\mathbf{s})$, and the red line represents the Porter-Thomas
distribution (2). The $F_{\mathrm{XEB}}$ for all the bitstrings is
$-0.000926$. (Right): $F_{\mathrm{XEB}}$ computed for an ensemble of
bitstrings which are post-selected from total $2^{21}$ bitstrings sorted by
probabilities.

##  III Discussions

We have presented the big-head tensor-network method for computing a large
number of bitstring probabilities for quantum circuits. The goal of Google’s
quantum supremacy experiments was to obtain a large number of samples
achieving a high enough $F_{\mathrm{XEB}}$ for the Sycamore circuits with
sufficient depth such that the task is intractable for classical computing. We
have demonstrated that with our algorithm we are able to classically obtain a
large number of samples with an even larger $F_{\mathrm{XEB}}$ than the
Sycamore experiments.

Our algorithm has several advantages over Google’s hardware sampling of the
Sycamore circuits. First, our method is able to output the exact amplitude and
probability of any bitstring, while Google’s samples are not verified, with
XEB estimated using extrapolations; second, our method is less noisy than
Google’s experiments in obtaining samples from the Sycamore circuits, because
the XEB of the post-selected $1$ million bitstrings obtained using our method
is higher than those in Google’s experiments; third, we are able to compute
conditional probabilities $P_{U}(\mathbf{s}_{2}|\mathbf{s}_{1})$ and sample
from this distribution accordingly, which is hard for Google’s quantum circuit
hardwares. At the same time, our experiments also reflect that Google’s
hardware has several advantages over our algorithm. The most significant one
is that Google’s hardware is much faster in sampling the quantum circuits with
sufficient depth, while our algorithm has exponential complexity, hence is not
scalable to both depth and qubit number; Although being noisy, Googles’
samples are not correlated to each other, while in this work we generated
correlated samples, which belong to a subspace of the whole bitstring space
111Notice that the correlation issue of our method can be significantly
relaxed by selecting some large-probability bitstrings, then mixing them with
a large number of random samples. For example, if we select $220$ bitstrings
with top probabilities and mix with $999780$ random bitstrings, the
correlations among the overall $1$ million bitstrings would be negligible,
while the $F_{\mathrm{XEB}}$ would be $0.002$, the same as Google’s
experiments.. As a conclusion, we would like to express our opinion in a
constructive way that based on the newly developed tensor network simulation
methods, it would be very interesting to combine classical computations and
NISQ quantum computations, for solving challenging problems in the real-world.

Although we have focused on the simulation of Google’s Sycamore circuits, our
algorithm is generally designed. The big-head shape and bottleneck structure
are general phenomenons existing in many tensor networks, as well as in many
real-world networks [27], which can be detected using clustering algorithms
[28]. The proposed algorithm can be used straightforwardly for simulating and
verifying existing and near-future NISQ quantum circuits. Our code is
implemented straightforwardly using Python and Pytorch. The contraction code
together with the contraction orders, slicing indices, and the obtained
bitstrings probabilities, are available at [29].

### Acknowledgements–

We thank Xun Gao, Fengyao Hou, Jinguo Liu, Dingshun Lv, Yibo Yang, and Lei
Wang for helpful discussions. We are grateful to Haijun Liao and Lei Wang for
offering A100 GPUs.

## References

  * Arute  _et al._ [2019] F. Arute, K. Arya, R. Babbush, D. Bacon, J. C. Bardin, R. Barends, R. Biswas, S. Boixo, F. G. Brandao, D. A. Buell, _et al._ , Quantum supremacy using a programmable superconducting processor, Nature 574, 505 (2019).
  * Aaronson and Chen [2016] S. Aaronson and L. Chen, Complexity-theoretic foundations of quantum supremacy experiments, arXiv preprint arXiv:1612.05903 (2016).
  * Bouland  _et al._ [2019] A. Bouland, B. Fefferman, C. Nirkhe, and U. Vazirani, On the complexity and verification of quantum random circuit sampling, Nature Physics 15, 159 (2019).
  * Boixo  _et al._ [2017] S. Boixo, S. V. Isakov, V. N. Smelyanskiy, and H. Neven, Simulation of low-depth quantum circuits as complex undirected graphical models, arXiv preprint arXiv:1712.05384 (2017).
  * Aaronson and Gunn [2019] S. Aaronson and S. Gunn, On the classical hardness of spoofing linear cross-entropy benchmarking, arXiv preprint arXiv:1910.12085 (2019).
  * Zlokapa  _et al._ [2020] A. Zlokapa, S. Boixo, and D. Lidar, Boundaries of quantum supremacy via random circuit sampling, arXiv preprint arXiv:2005.02464 (2020).
  * Boixo  _et al._ [2018] S. Boixo, S. V. Isakov, V. N. Smelyanskiy, R. Babbush, N. Ding, Z. Jiang, M. J. Bremner, J. M. Martinis, and H. Neven, Characterizing quantum supremacy in near-term devices, Nature Physics 14, 595 (2018).
  * Preskill [2012] J. Preskill, Quantum computing and the entanglement frontier, arXiv preprint arXiv:1203.5813 (2012).
  * Markov  _et al._ [2018] I. L. Markov, A. Fatima, S. V. Isakov, and S. Boixo, Quantum supremacy is both closer and farther than it appears, arXiv preprint arXiv:1807.10749 (2018).
  * Li  _et al._ [2019] R. Li, B. Wu, M. Ying, X. Sun, and G. Yang, Quantum supremacy circuit simulation on sunway taihulight, IEEE Transactions on Parallel and Distributed Systems 31, 805 (2019).
  * Markov and Shi [2008] I. L. Markov and Y. Shi, Simulating quantum computation by contracting tensor networks, SIAM Journal on Computing 38, 963 (2008).
  * Gray and Kourtis [2020] J. Gray and S. Kourtis, Hyper-optimized tensor network contraction, arXiv preprint arXiv:2002.01935 (2020).
  * Guo  _et al._ [2019] C. Guo, Y. Liu, M. Xiong, S. Xue, X. Fu, A. Huang, X. Qiang, P. Xu, J. Liu, S. Zheng, _et al._ , General-purpose quantum circuit simulator with projected entangled-pair states and the quantum supremacy frontier, arXiv preprint arXiv:1905.08394 (2019).
  * Chen  _et al._ [2018] J. Chen, F. Zhang, M. Chen, C. Huang, M. Newman, and Y. Shi, Classical simulation of intermediate-size quantum circuits, arXiv preprint arXiv:1805.01450 (2018).
  * Pan  _et al._ [2020] F. Pan, P. Zhou, S. Li, and P. Zhang, Contracting arbitrary tensor networks: general approximate algorithm and applications in graphical models and quantum circuit simulations, Physical Review Letters 125, 060503 (2020).
  * Villalonga  _et al._ [2019] B. Villalonga, S. Boixo, B. Nelson, C. Henze, E. Rieffel, R. Biswas, and S. Mandrà, A flexible high-performance simulator for verifying and benchmarking quantum circuits implemented on real hardware, npj Quantum Information 5, 1 (2019).
  * Villalonga  _et al._ [2020] B. Villalonga, D. Lyakh, S. Boixo, H. Neven, T. S. Humble, R. Biswas, E. G. Rieffel, A. Ho, and S. Mandrà, Establishing the quantum supremacy frontier with a 281 pflop/s simulation, Quantum Science and Technology 5, 034003 (2020).
  * Huang  _et al._ [2020] C. Huang, F. Zhang, M. Newman, J. Cai, X. Gao, Z. Tian, J. Wu, H. Xu, H. Yu, B. Yuan, _et al._ , Classical simulation of quantum supremacy circuits, arXiv preprint arXiv:2005.06787 (2020).
  * Schutski  _et al._ [2020] R. Schutski, T. Khakhulin, I. Oseledets, and D. Kolmakov, Simple heuristics for efficient parallel tensor contraction and quantum circuit simulation, Physical Review A 102, 062614 (2020).
  * Kourtis  _et al._ [2019] S. Kourtis, C. Chamon, E. R. Mucciolo, and A. d. E. Ruckenstein, Fast counting with tensor networks, SciPost Physics 7 (2019).
  * Zhang  _et al._ [2019] F. Zhang, C. Huang, M. Newman, J. Cai, H. Yu, Z. Tian, B. Yuan, H. Xu, J. Wu, X. Gao, _et al._ , Alibaba cloud quantum development platform: Large-scale classical simulation of quantum circuits, arXiv preprint arXiv:1907.11217 (2019).
  * Zhou  _et al._ [2020] Y. Zhou, E. M. Stoudenmire, and X. Waintal, What limits the simulation of quantum computers?, Physical Review X 10, 041038 (2020).
  * [23] Martinis, John M. et al. (2021), Quantum supremacy using a programmable superconducting processor, Dryad, Dataset, https://doi.org/10.5061/dryad.k6t1rj8.
  * Porter and Thomas [1956] C. E. Porter and R. G. Thomas, Fluctuations of nuclear reaction widths, Physical Review 104, 483 (1956).
  * Brody  _et al._ [1981] T. A. Brody, J. Flores, J. B. French, P. Mello, A. Pandey, and S. S. Wong, Random-matrix physics: spectrum and strength fluctuations, Reviews of Modern Physics 53, 385 (1981).
  * Note [1] Notice that the correlation issue of our method can be significantly relaxed by selecting some large-probability bitstrings, then mixing them with a large number of random samples. For example, if we select $220$ bitstrings with top probabilities and mix with $999780$ random bitstrings, the correlations among the overall $1$ million bitstrings would be negligible, while the $F_{\mathrm{XEB}}$ would be $0.002$, the same as Google’s experiments.
  * Zhang and Moore [2014] P. Zhang and C. Moore, Scalable detection of statistically significant communities and hierarchies, using message passing for modularity, Proceedings of the National Academy of Sciences 111, 18144 (2014).
  * Krzakala  _et al._ [2013] F. Krzakala, C. Moore, E. Mossel, J. Neeman, A. Sly, L. Zdeborová, and P. Zhang, Spectral redemption in clustering sparse networks, Proc. Natl. Acad. Sci. USA 110, 20935 (2013).
  * [29] https://github.com/Fanerst/simulate_sycamore.

##  Appendix A Details of the contraction algorithm

Based on the big-head simulation scheme, our contraction algorithm is mainly
composed of two parts, the hierarchical partitioning based algorithm for
finding the first cut and a contraction order with tractable computational
cost, and the dynamic slicing which breaks the overall giant contraction
process into many small and tractable contraction processes, each of which can
be contracted independently and parallelly.

### Finding contraction order using hierarchical partitioning

An essential problem in tensor network contraction is to determine an order
for contracting tensors pair by pair, which is referred to as contraction
order. For tensor networks defined on $1$D or $2$D lattices the optimal order
can be easily found. However, the tensor networks associated with quantum
circuits are usually irregular, it is a difficult problem to find an optimal
order for contracting the whole network. Lots of effort has been devoted in
finding a good contraction order. Markov and Shi [11] first showed that one
can use the optimal tree decomposition of the line graph associated with the
tensor network to find the optimal contraction order. However, finding the
optimal tree decomposition for a general graph is NP-hard problem, thus one
usually adopts heuristic algorithms, such as the branch-and-bound algorithm
with a restricted running time, to find a good tree decomposition.

In [20], the authors proposed to use graph partitioning algorithms to find a
good contraction order for contracting tensor networks associated with
constraint satisfaction problems. Later in [12], the method was further
developed and applied to the quantum circuit simulations. In [18], further
improvements were made, and authors were able to justify that contracting the
Sycamore circuits with $20$ circles is reachable using a supercomputer.

In this work, the order-finding algorithm is responsible not only for low
computational cost, but also for detecting the big-head structure of the
network, so that the $\mathrm{head}$ network is only needed to contracted once
and reused for computing all the bitstring probabilities defined by
enumerating the assignment of $\mathbf{s}_{2}$ in
$\mathcal{G}_{\mathrm{tail}}$.

The most important step of our approach is the first cut, given by the initial
partition, which separates the tensor network corresponding to quantum
circuits into the head and tail tensor networks. Notice that we set a
constraint to the first cut such that the pair contraction associated with
subsequent bi-partitions will never create time and space complexity larger
than the target values. If the first cut does not satisfy this constraint, we
will try other partitions until the constraints are satisfied. Based on the
first cut, we use a hierarchical bipartition algorithm, which sequentially and
hierarchically divides the remaining tensor network into two parts. Each
bipartition represents a binary structure in the contraction tree, thus when
the bipartition process ends (if the number of tensors in the sub-graph is
smaller than $60$), it provides a contraction order. If we carefully restrict
the complexity of each bipartition, the time and space complexity of the
resulting order will also be restricted to the corresponding initial partition
can be validated. The complexity of one bipartition is depicted in Fig 3.

Figure 3: Illustration of the bipartition. $n_{AB}$ is the number of indices
shared by sub-graphs A and B, with $n_{A}$ and $n_{B}$ representing the number
of outer indices owned by two sub-graphs respectively. The bond dimension of
each edge studied in network associated with the quantum circuit is $2$, the
time complexity of the contraction is $2^{n_{A}+n_{B}+n_{AB}}$

### Dynamic slicing

For large quantum circuits with a sufficient depth, even with a very good
contraction order, the space complexity is usually out of reach, beyond the
capacity of RAM and GPU memory. For example, the largest tensor we encountered
in contracting the Sycamore circuits with $n=53$ qubits and $m=20$ cycles has
an overall size of $2^{53}$ . If we use single-precision complex numbers, it
will take roughly $13421$ TB memory to store the giant tensor. In order to
make contraction possible using current computational hardwares, we need
techniques to separate the whole contraction task into many sub-tasks, each of
which requires much less memory than the original contraction. Slicing is a
technique of removing some of the indices in the tensor network, enumerating
their dimensions as subtasks, and sum over subtasks to get an equivalent
result. Dynamic slicing [14] or sliced subtree reconfiguration [12] improve
the vanilla slicing method by fine-tuning the contraction tree each time an
index being sliced, this gives a much smaller slicing overhead (proportion of
time complexity after and before slicing). In our experiments for contracting
the $\mathcal{G}_{\mathrm{head}}$ to obtain the $\mathbf{v}_{\mathrm{head}}$
vector, using the dynamic slicing we divided the
$\mathcal{G}_{\mathrm{head}}$-contraction task into $2^{23}$ sub-tasks, each
of which has space complexity $2^{30}$ to fit into $32$G memory of NVIDIA V100
GPU.

bitstring | amplitude | probability
---|---|---
00000000000000000000000100000110100000010000100000000 | $3.62\times 10^{-8}$ | $1.31\times 10^{-15}$
00000000000000000000000000000000000000000100001000000 | $1.55\times 10^{-8}$ | $2.39\times 10^{-16}$
00000000000111000001111100001111100001111100110000000 | $6.3\times 10^{-9}$ | $3.97\times 10^{-17}$
00000000000111000001111100001111100001111000101000000 | $3.14\times 10^{-9}$ | $9.86\times 10^{-18}$
00000000000000000000000000000100000000011100010000000 | $9.17\times 10^{-10}$ | $8.41\times 10^{-19}$
Table 3: Examples of bitstrings with their amplitudes and probabilities
computed using our algorithm for the Sycamore circuit with $53$ qubits and
$20$ cycles.

##  Appendix B  Details of simulations

During the tensor network contractions, we used single-precision complex
numbers (complex64) and the Pytorch library. As a check, we have compared the
contraction results of single sub-task tensor networks to that using complex
single and double precision, and also evaluated the effect of extracting the
largest number or tensor norm from the input and output of each tensors
contractions, and concluded that complex single computation preserves enough
precision that is necessary for evaluating the amplitude of bitstrings.

### GPU efficiency—

One can define the GPU efficiency as

$E=\frac{8\times\text{time complexity}}{\text{GPU FLOPS
capacity}\times\text{running time}}\;.$ (3)

Here 8 is the factor for the FLOPS count with complex tensor operations (2 for
addition and 6 for multiplication).

Directly running the sub-tasks on GPU gives a low GPU efficiency, because a
typical order for contracting $\mathrm{head}$ involves many tensor operations
between a large tensor and a small tensor. To overcome this problem, we merge
two small tensors into a larger tensor before operating with the large tensor.
This approach is called branch merging as introduced in [18]. It balances the
size of tensor operations in the contraction order hence hugely increases the
GPU efficiency, with only a small cost of time complexity increase. In our
numerical experiments for the Sycamore circuits with $n=53$ qubits and $m=20$
cycles, it raises the GPU efficiency in V100 GPUs from $4.4\%$ to $38.4\%$ by
introducing an additional $3.87$ times of time complexity. And the overall
computational time will be around $55\%$ lower than the original one. In our
experiments, the GPU efficiency of NVIDIA A100 (40GB memory, 19.5 TFLOPs) GPU
is $69.40\%$.

### Computation details—

For the Sycamore circuits with $53$ qubits, based on a contraction order we
identify open and closed qubits as shown in Fig. 4. For $m=20$ cycles, there
are $21$ open qubits (qubit ids: 11, 12, 13, 19, 20, 21, 22, 23, 28, 29, 30,
31, 32, 37, 38, 39, 40, 41, 44, 45, 46), time complexity for contracting the
tail network with an assignment of $\mathbf{s}_{2}$ is $1.347\times 10^{9}$
and space complexity is $2^{23}$. for the $\mathrm{head}$ part in order to
make contraction fit into the GPU memory, $23$ edges are sliced so that there
are overall $2^{23}$ sub-tasks. For each sub-task, time complexity is
$2.088\times 10^{12}$, space complexity is $2^{30}$, it takes $1.235$ seconds
for contraction $1.5336$ seconds for overall calculation on an NVIDIA A100
GPU, $2.919$ seconds and $3.044$ seconds respectively on a NVIDIA V100 GPU.
The overall calculation means that all the computation process of a sub-task
of contraction, including tensor preparation, slicing, contraction, and
summation of the final tensors.

Figure 4:  The layout of the sycamore circuits. Colors represent a division of
all $53$ qubits at the end state into open (red) and close (blue) qubits. The
numbering is according to that in the Google’s circuit data [23].

Some samples of obtained bitstring probabilities are listed in Table 3.

For the Sycamore circuits with $53$ qubits and $14$ cycles, ABCDCDAB sequence
and seed $0$, $9$ edges are sliced so there are overall $2^{9}$ sub-tasks. For
each sub-task, time complexity is $2.543\times 10^{11}$, space complexity is
$2^{30}$, it takes $0.541$ seconds on a V100S (32GB memory, 16.35 TFLOPs) to
complete a sub-task and the GPU efficiency is $23.02\%$. On the tail part,
there are $19$ open qubits (qubit ids: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11,
12, 13, 14, 15, 16, 17, 18), time complexity is $1.893\times 10^{7}$ and space
complexity is $2^{21}$. Calculation time on the tail part of both $14$ and
$20$ cycles are negligible compared to the head part. The results for $m=14$
cycles are shown in Fig. 5, where we can see that the histogram of bistring
probabilities deviate a little from the Porter-Thomas distribution, giving
$F_{\mathrm{XEB}}=-0.00687$.

Figure 5:  (Left): Histogram of bitstring probabilities
$P_{U}(\mathbf{s})=P_{U}(\mathbf{s}_{1};\mathbf{s}_{2})$ for $L=2^{19}$
bitstrings obtained from the Sycamore circuit with $n=53$ qubits, $m=14$
cycles, sequence ABCDCDAB, seed $0$, and the assignment of partial bitstring
$\mathbf{s}_{1}$ are fixed to $\underbrace{0,0,0,\cdots,0}_{34}$. In the
figure, $N=2^{53}$, $p$ denotes the probability of bitstring
$P_{U}(\mathbf{s})$, and the red line represents the Porter-Thomas
distribution (2). The $F_{\mathrm{XEB}}$ for all bit-strings is $-0.00687$.
(Right): $F_{\mathrm{XEB}}$ computed for an ensemble of bitstrings which are
post-selected from total $2^{19}$ bitstrings sorted by probabilities.

##  Appendix C Distribution of conditional probabilities and marginal
probability

The probability of a bitstring is the joint probability over $\mathbf{s}_{1}$
and $\mathbf{s}_{2}$, i.e.
$P_{U}(\mathbf{s})=P_{U}(\mathbf{s}_{1};\mathbf{s}_{2})$. In our settings,
entries of $\mathbf{s}_{1}$ is fixed to an arbitrary assignment, and we are
able to compute probabilities for all possible bitstrings obtained by
enumerating $\mathbf{s}_{2}$. This means that in addition to computing
$P_{U}(\mathbf{s})$, we are also able to compute the marginal probability

$P_{U}(\mathbf{s}_{1})=\sum_{\mathbf{s}_{2}}P_{U}(\mathbf{s}_{1};\mathbf{s}_{2}),$

and conditional probability distribution

$P_{U}(\mathbf{s}_{2}|\mathbf{s}_{1})=\frac{P_{U}(\mathbf{s}_{1};\mathbf{s}_{2})}{P_{U}(\mathbf{s}_{1})}.$

Apparently, $P_{U}(\mathbf{s}_{1})$ is nothing but $F_{\mathrm{XEB}}+1$, hence
in our experiments (in the main text) for the Sycamore circuits with $n=53$
qubits and $m=20$ cycles, $P_{U}(\mathbf{s}_{1})=0.999*2^{-n_{1}}$, which is
really close to $2^{-n_{1}}$. For the random quantum circuits, we anticipate
that the expectation of $P_{U}(\mathbf{s}_{1})$ averaged over $\mathbf{s}_{1}$
should be around $\langle
P_{U}(\mathbf{s}_{1})\rangle_{\mathbf{s}_{1}}=2^{-n_{1}}$. We see that
according to the computed $P_{U}(\mathbf{s}_{1})$ value, an instance of
$P_{U}(\mathbf{s}_{1})$ is indeed tightly around this expectation.

In Fig. 6 we plotted the histogram of the conditional probabilities
$P_{U}(\mathbf{s}_{2}|\mathbf{s}_{1})*2^{21}$, which is normalized and sum to
$1$. This also means that the XEB of the this distribution is exactly $0$.
From the figure we can see that the histogram of the $2^{21}$ conditional
probabilities coincides perfectly to the Porter-Thomas distribution.

Figure 6:  Histogram of conditional probability
$P(\mathbf{s}_{1}|\mathbf{s}_{2})$ for $L=2^{21}$ bitstrings obtained from the
Sycamore circuit with $n=53$ qubits, $m=20$ cycles (Left) and $m=14$ cycles
(Right), seed $0$, sequence ABCDCDAB. In the figure, $N=2^{21}$ for the left
panel and $N=2^{19}$ for the right panel, $p$ denotes the conditional
probability $P_{U}(\mathbf{s}_{2}|\mathbf{s}_{1})$, and the red line
represents the Porter-Thomas distribution (2). The XEB (1) for the conditional
probability distribution is exactly $0$ in both panels.


h\right)=t_{0}^{m}t_{1}^{m}\otimes\dot{\mu}\left(h\right)-\rho_{\mu}\left(h\right)m\text{k}_{m,n},\\\
\widehat{R}_{\mu}\left(\text{k}_{m,n}\right)=\text{k}_{m,n},\quad\widehat{R}_{\mu}\left(\text{d}_{m,n}\right)=\text{d}_{m,n}+\left(m+1\right)t_{0}^{m}t_{1}^{n}\otimes\boldsymbol{h}+\frac{\left\langle\boldsymbol{h},\boldsymbol{h}\right\rangle}{2}\left(m+1\right)m\text{k}_{m,n},\end{split}$
(6.14)

for $x\in\mathfrak{g}_{\alpha}$ with
$\alpha\in\Delta^{\times}\cup\left\\{0\right\\},$ $h\in\dot{\mathfrak{h}},$
$m\in\mathbb{Z}$ and $n\in\mathbb{Z}^{\ast}.$ Moreover, from Proposition 4.3
we have a Lie automorphism $\hat{\mu}$ of
$\mathcal{T}\left(\dot{\mathfrak{g}}\right)$, which preserves
$\widehat{\mathfrak{g}}$. And one can check that $\hat{\mu}=\widehat{R}_{\mu}$
on $\widehat{\mathfrak{g}}$. Thus $\widehat{R}_{\mu}$ is an automorphism of
the Lie algebra $\widehat{\mathcal{C}}_{\mathfrak{g}}$ with order $T$. The
assertion of the lemma then follows from Lemma 2.7. ∎

Set $G_{\mu}=\langle R_{\mu}\rangle$, an automorphism group of
$\mathcal{C}_{\mathfrak{g}}$, and let $\chi_{\omega}$ be the linear character
of $G_{\mu}$ defined by $\chi_{\omega}\left(R_{\mu}\right)=\omega^{-1}$.
Associated to the $G_{\mu}$-conformal algebra $\mathcal{C}_{\mathfrak{g}}$ and
the character $\chi_{\omega}$, there is a Lie algebras
$\widetilde{\mathcal{C}}_{\mathfrak{g}}\left[G_{\mu}\right]$ by (2.19).
Recalling the surjective map
$\eta_{\mu}:\widetilde{\mathfrak{g}}\rightarrow\widetilde{\mathfrak{g}}\left[\mu\right]$
defined in (4.25), we have:

######  Proposition 6.4.

The following assignment

$\displaystyle\overline{u\left[m\right]}\mapsto\eta_{\mu}\left(t_{0}^{m}u\right),\
\overline{K_{n}\left[m\right]}\mapsto\eta_{\mu}\left(\text{k}_{m,n}\right),\
\overline{D_{n}\left[m\right]}\mapsto\eta_{\mu}\left(\widetilde{\text{d}}_{m,n}\right),\
\overline{\text{k}_{0}\left[m\right]}\mapsto\delta_{m,0}T\text{k}_{0},\
\mathbf{d}\mapsto-\text{d}_{0}$ (6.15)

for $u\in\mathfrak{g},$ $m\in\mathbb{Z}$ and $n\in\mathbb{Z}^{\ast}$,
determines an isomorphism from the Lie algebra
$\widetilde{\mathcal{C}}_{\mathfrak{g}}\left[G_{\mu}\right]$ to the Lie
algebra $\widetilde{\mathfrak{g}}$$\left[\mu\right]$.

###### Proof.

Corresponding to the automorphism $R_{\mu}$ of ${\mathcal{C}}_{\mathfrak{g}}$,
there is an automorphism $\widetilde{R}_{\mu}$ of
$\widetilde{\mathcal{C}}_{\mathfrak{g}}$ (see (2.17)). Via the isomorphism
$\tilde{i}_{\mathfrak{g}}:\widetilde{\mathcal{C}}_{\mathfrak{g}}\rightarrow\widetilde{\mathfrak{g}}$
given in Proposition 6.2, $\widetilde{R}_{\mu}$ induces an automorphism of
$\widetilde{\mathfrak{g}}$. It is straightforward to check that this
automorphism of $\widetilde{\mathfrak{g}}$ coincides with $\tilde{\mu}$ (see
(4.23)). Since $G_{\mu}$ is a cyclic group of order $T$, it follows from
Remark 2.10 that $\widetilde{\mathcal{C}}_{\mathfrak{g}}\left[G_{\mu}\right]$
is isomorphic to the subalgebra of $\widetilde{\mathcal{C}}_{\mathfrak{g}}$
fixed by $\widetilde{R}_{\mu}$. This implies that
$\widetilde{\mathcal{C}}_{\mathfrak{g}}\left[G_{\mu}\right]$ is isomorphic to
$\widetilde{\mathfrak{g}}[\mu]$ with the isomorphism given in the proposition.
∎

###  6.3 The correspondence theorem for
$\widetilde{\mathfrak{g}}\left[\mu\right]$

In this subsection we generalize the correspondence theorem (Theorem 3.11) for
affine Kac-Moody algebras to the nullity $2$ twisted toroidal extended affine
Lie algebras $\widetilde{\mathfrak{g}}\left[\mu\right]$.

Form the following generating functions $a^{\mu}\left[z\right]$,
$a\in\mathcal{A}_{\mathfrak{g}}$ in
$\widetilde{\mathfrak{g}}\left[\mu\right]\left[\left[z,z^{-1}\right]\right]$:

$\displaystyle
u^{\mu}\left[z\right]=\sum_{n\in\mathbb{Z}}\eta_{\mu}\left(t_{0}^{n}u\right)z^{-n},\quad
D_{m}^{\mu}\left[z\right]=\sum_{n\in\mathbb{Z}}\eta_{\mu}\left(\widetilde{\text{d}}_{n,m}\right)z^{-n},\quad
K_{m}^{\mu}\left[z\right]=\sum_{n\in\mathbb{Z}}\eta_{\mu}\left(\text{k}_{n,m}\right)z^{-n},$

for $u\in\mathfrak{g}$ and $m\in\text{$\mathbb{Z}^{\ast}.$}$ Note that all the
components of these generating functions together with $\text{k}_{0}$,
$\text{d}_{0}$ span the algebra $\widetilde{\mathfrak{g}}\left[\mu\right]$. As
in the affine Kac-Moody algebra case, we formulate the following definition.

######  Definition 6.5.

We say that a $\widetilde{\mathfrak{g}}\left[\mu\right]$-module $W$ is
_restricted_ if for any $a\in\mathcal{A}_{\mathfrak{g}}$,
$a^{\mu}\left[z\right]\in\mathrm{Hom}\left(W,W\left(\left(z\right)\right)\right)$.
And $W$ is said _of level $\ell\in\mathbb{C}$_ if the central element
$\text{k}_{0}$ acts as the scalar $\ell/T$. Furthermore, if $\mu$ is
nontransitive, we say that $W$ is _integrable_ if for any
$\alpha\in\tilde{\Delta}_{\mu}^{\times}$,
$\widetilde{\mathfrak{g}}\left[\mu\right]{}_{\alpha}$ acts locally nilpotent
on $W$.

For each $i\in I=\\{0,1,\cdots,l\\}$, one recalls the positive integer
$T_{i},s_{i}$ defined in (4.27), and set

$p_{i}\left(z\right)=\frac{1-z^{s_{i}T_{i}}}{1-z^{T_{i}}}.$

Then we have the following analogue of Proposition 3.12.

######  Proposition 6.6.

Assume that $\mu$ is nontransitive. Then for any $i\in I$,

$\displaystyle
p_{i}\left(z_{1}/z_{2}\right)\left[x_{\pm\alpha_{i}}^{\mu}\left[z_{1}\right],x_{\pm\alpha_{i}}^{\mu}\left[z_{2}\right]\right]=0.$
(6.16)

Furthermore, if $W$ is a restricted
$\widetilde{\mathfrak{g}}\left[\mu\right]$-module of level $\ell$, then $W$ is
integrable if and only if $\ell$ is a nonnegative integer and for any $i\in
I$,

$\displaystyle\left(\prod_{1\leq
i<j\leq\epsilon_{i}\ell+1}p_{i}\left(z_{i}/z_{j}\right)\right)x_{\pm\alpha_{i}}^{\mu}\left[z_{1}\right]x_{\pm\alpha_{i}}^{\mu}\left[z_{2}\right]\cdots
x_{\pm\alpha_{i}}^{\mu}\left[z_{\epsilon_{i}\ell+1}\right]|_{z_{1}=z_{2}\cdots=z_{\epsilon_{i}\ell+1}}=0\quad\text{on}\
W.$ (6.17)

###### Proof.

For each $i\in I$, denoted by $\widetilde{\mathfrak{g}}\left[\mu\right]{}_{i}$
the subalgebra of $\widetilde{\mathfrak{g}}\left[\mu\right]$ generated by the
elements $t_{0}^{m}x_{\pm\alpha_{i}}$, $\text{d}_{0}$ for $m\in\mathbb{Z}$. We
first show that $\widetilde{\mathfrak{g}}\left[\mu\right]{}_{i}$ is isomorphic
to the affine Kac-Moody algebra of type $A_{s_{i}}^{(s_{i})}$. For $k=1,2$, we
denote by $\theta_{k}$ the order $k$ diagram automorphism of the simple Lie
algebra $\mathfrak{sl}_{k+1}$. Then for each $i\in I$, we have an affine Kac-
Moody algebra
$\widetilde{\mathcal{L}}\left(\mathfrak{sl}_{s_{i}+1},\theta_{s_{i}}\right)$
of type $A_{s_{i}}^{(s_{i})}$ (see Section 3.2). Recall that
$\eta_{\mu}\left(t_{0}^{m}x_{\pm\alpha_{i}}\right)=\sum_{p=0}^{T-1}t_{0}^{m}x_{\pm\alpha_{\mu(i)}}$
for $i\in I$ and $m\in\mathbb{Z}$. In particular, we have
$\eta_{\mu}\left(t_{0}^{m}x_{\pm\alpha_{i}}\right)\neq 0$ if and only if $m\in
T_{i}\mathbb{Z}$. By Lemma 4.7, it is straightforward to see that the
assignment ($m\in\mathbb{Z}$ and $\beta$ a fixed simple root of
$\mathfrak{sl}_{s_{i}+1}$)

$\displaystyle\eta_{\mu}\left(t_{0}^{T_{i}m}x_{\pm\alpha_{i}}\right)\mapsto
t^{m}\otimes\left(x_{\pm\beta}\right){}_{(m)},\quad\frac{T}{s_{i}}\text{k}_{0}\mapsto\text{k},\quad\text{d}_{0}\mapsto
T_{i}\text{d}$

determines an isomorphism from the Lie algebra
$\widetilde{\mathfrak{g}}\left[\mu\right]{}_{i}$ to the Lie algebra
$\widetilde{\mathcal{L}}\left(\mathfrak{sl}_{s_{i}+1},\theta_{s_{i}}\right)$.
This together with (3.9) implies the first assertion of the proposition.

For the second assertion, let $W$ be a restricted
$\widetilde{\mathfrak{g}}\left[\mu\right]$-module of level $\ell$. For each
$i\in I$, via the isomorphism
$\widetilde{\mathfrak{g}}\left[\mu\right]{}_{i}\cong\widetilde{\mathcal{L}}\left(\mathfrak{sl}_{s_{i}+1},\theta_{s_{i}}\right)$,
$W$ becomes a restricted
$\widetilde{\mathcal{L}}\left(\mathfrak{sl}_{s_{i}+1},\theta_{i}\right)$-module
of level $\ell$. Note that the
$\widetilde{\mathfrak{g}}\left[\mu\right]$-module $W$ is integrable if and
only if the elements $t_{0}^{m}x_{\pm\alpha_{i}}$, $i\in I,m\in\mathbb{Z}$ act
locally nilpotent (as they generate the core
$\mathfrak{t}\left(\dot{\mathfrak{g}},\mu\right)$). Thus, $W$ is integrable if
and only if $W$ is integrable as an
$\widetilde{\mathcal{L}}\left(\mathfrak{sl}_{s_{i}+1},\theta_{i}\right)$-module
for all $i\in I$. Thus the assertion follows from Proposition 3.12. ∎

Note that $\text{k}_{0}$ is a central element in $\mathcal{C}_{\mathfrak{g}}$.
Thus, for any $\ell\in\mathbb{C}$, the
$\widehat{\mathcal{C}}_{\mathfrak{g}}$-submodule
$\langle\text{k}_{0}-\ell\rangle$ of $V_{\mathcal{C}_{\mathfrak{g}}}$
generated by $\text{k}_{0}-\ell$ is an ideal of
$V_{\mathcal{C}_{\mathfrak{g}}}$ (as a vertex algebra). Recall the isomorphism
$\hat{i}_{\mathfrak{g}}:\widehat{\mathcal{C}}_{\mathfrak{g}}\to\widehat{\mathfrak{g}}$
given in Proposition 6.2. One can readily check that
$\hat{i}_{\mathfrak{g}}\left(\widehat{\mathcal{C}}_{\mathfrak{g}}^{+}\right)=\widehat{\mathfrak{g}}_{+}$
and
$\hat{i}_{\mathfrak{g}}\left(\widehat{\mathcal{C}}_{\mathfrak{g}}^{-}\right)=\widehat{\mathfrak{g}}{}_{-}\oplus\mathbb{C}\text{k}_{0}$
(see (2.9) and (6.6)). This implies that
$V_{\widehat{\mathfrak{g}}}\left(\ell,0\right)$ is isomorphic to the quotient
vertex algebra
$V_{\mathcal{C}_{\mathfrak{g}}}/\langle\text{k}_{0}-\ell\rangle$. Recall also
that the automorphism group $G_{\mu}=\langle R_{\mu}\rangle$ of
$\mathcal{C}_{\mathfrak{g}}$ can be uniquely lifted to an automorphism group
of its universal enveloping vertex algebra $V_{\mathcal{C}_{\mathfrak{g}}}$.
As $R_{\mu}\left(\text{k}_{0}\right)=\text{k}_{0}$, $G_{\mu}$ is naturally an
automorphism group of $V_{\widehat{\mathfrak{g}}}\left(\ell,0\right)$.
Furthermore, we have

######  Lemma 6.7.

For each nonnegative integer $\ell$,
$J_{\widehat{\mathfrak{g}}}\left(\ell,0\right)$ is a $R_{\mu}$-stable ideal of
$V_{\widehat{\mathfrak{g}}}\left(\ell,0\right)$.

###### Proof.

The assertion follows from the fact that

$R_{\mu}\left(\left(t_{0}^{-1}x_{\pm\alpha_{i}}\right){}^{\epsilon_{i}\ell+1}\mathbf{1}\right)=\left(t_{0}^{-1}\mu\left(x_{\pm\alpha_{i}}\right)\right){}^{\epsilon_{i}\ell+1}\mathbf{1}=\left(t_{0}^{-1}x_{\pm\alpha_{\mu(i)}}\right){}^{\epsilon_{\mu(i)}\ell+1}\mathbf{1}\in
J(\ell),$

where $\epsilon_{\mu(i)}=\epsilon_{i}$ for $i\in I$. ∎

In view of the above lemma, $G_{\mu}$ is also an automorphism group of the
vertex algebra $L_{\widehat{\mathfrak{g}}}\left(\ell,0\right)$. Now we state
one of the main results of the paper.

######  Theorem 6.8.

Let $\ell$ be a complex number. For any restricted
$\widetilde{\mathfrak{g}}\left[\mu\right]$-module $W$ of level $\ell$, there
is a $\left(G_{\mu},\chi_{\omega}\right)$-equivariant $\phi$-coordinated quasi
$V_{\widehat{\mathfrak{g}}}\left(\ell,0\right)$-module structure
$(Y_{W}^{\phi},d)$ on $W$, which is uniquely determined by

$\displaystyle d=-\text{d}_{0},\ \quad
Y_{W}^{\phi}\left(a,z\right)=a^{\mu}\left[z\right],$

for $a\in\mathcal{A}_{\mathfrak{g}}.$ On the other hand, for any
$\left(G_{\mu},\chi_{\omega}\right)$-equivariant $\phi$-coordinated quasi
$V_{\widehat{\mathfrak{g}}}\left(\ell,0\right)$-module
$\left(W,Y_{W}^{\phi},d\right)$, $W$ is a restricted
$\widetilde{\mathfrak{g}}\left[\mu\right]$-module of level $\ell$ with action
given by

$\displaystyle\text{d}_{0}=-d,\ \quad
a^{\mu}\left[z\right]=Y_{W}^{\phi}\left(a,z\right),$

for $a\in\mathcal{A}_{\mathfrak{g}}$. Furthermore, if $\ell$ is a nonnegative
integer and $\mu$ is nontransitive, then the integrable restricted
$\widetilde{\mathfrak{g}}\left[\mu\right]$-modules of level $\ell$ are exactly
the $\left(G_{\mu},\chi_{\omega}\right)$-equivariant $\phi$-coordinated quasi
$L_{\widehat{\mathfrak{g}}}\left(\ell,0\right)$-modules $(W,Y_{W}^{\phi},d)$.

###### Proof.

By Proposition 2.5 and Proposition 6.4, the restricted
$\widetilde{\mathfrak{g}}\left[\mu\right]$-modules are exactly the
$\left(G_{\mu},\chi_{\omega}\right)$-equivariant $\phi$-coordinated quasi
$V_{\mathcal{C}_{\mathfrak{g}}}$-modules. Thus the fact that
$V_{\widehat{\mathfrak{g}}}\left(\ell,0\right)\cong
V_{\mathcal{C}_{\mathfrak{g}}}/\left\langle\text{k}_{0}-\ell\right\rangle$
implies the first assertion of the theorem.

For the second part of the theorem, we assume that $\ell$ is a nonnegative
integer, $\mu$ is nontransitive and $W$ is an integrable restricted
$\widetilde{\mathfrak{g}}\left[\mu\right]$-module of level $\ell$. Note that
for each $i$, we have
$\left[x_{\pm\alpha_{i}}\left(z_{1}\right),x_{\pm\alpha_{i}}\left(z_{2}\right)\right]=0$
on $\widehat{\mathfrak{g}}$. This implies that for any $n\in\mathbb{N}$ and
$i\in I$,

$\displaystyle\left(x_{\pm\alpha_{i}}{}\right)_{n}\left(x_{\pm\alpha_{i}}\right)=0\quad\text{on}\quad
V_{\widehat{\mathfrak{g}}}\left(\ell,0\right).$ (6.18)

Viewing $W$ as a faithful $\left(G_{\mu},\chi_{\omega}\right)$-equivariant
$\phi$-coordinated quasi $V_{\widehat{\mathfrak{g}}}\left(\ell,0\right)/\ker
Y_{W}^{\phi}$-module, by Proposition 6.6, we have

$\displaystyle\left(\prod_{1\leq
i<j\leq\epsilon_{i}\ell+1}p_{i}(z_{i}/z_{j})\right)Y_{W}^{\phi}\left(x_{\pm\alpha_{i}},z_{1}\right)Y_{W}^{\phi}\left(x_{\pm\alpha_{i}},z_{2}\right)\cdots
Y_{W}^{\phi}\left(x_{\pm\alpha_{i}},z_{\epsilon_{i}\ell+1}\right)|_{z_{1}=z_{2}\cdots=z_{\epsilon_{i}\ell+1}}=0\quad\text{on}\
W$ (6.19)

for all $i\in I$. This together with (6.18) and Proposition 2.5 proves that
$\left(\left(x_{\pm\alpha_{i}}\right){}_{-1}\right){}^{\epsilon_{i}\ell+1}\mathbf{1}\in\ker
Y_{W}^{\phi}$ for $i\in I$. Thus, we have
$J_{\widehat{\mathfrak{g}}}\left(\ell,0\right)\subset\ker Y_{W}^{\phi}$ and
$W$ becomes a $\left(G_{\mu},\chi_{\omega}\right)$-equivariant
$\phi$-coordinated quasi
$L_{\widehat{\mathfrak{g}}}\left(\ell,0\right)$-module.

Conversely, let $\left(W,Y_{W}^{\phi},d\right)$ be a
$\left(G_{\mu},\chi_{\omega}\right)$-equivariant $\phi$-coordinated quasi
$L_{\widehat{\mathfrak{g}}}\left(\ell,0\right)$-module. Then it is also a
$\left(G_{\mu},\chi_{\omega}\right)$-equivariant $\phi$-coordinated quasi
$V_{\widehat{\mathfrak{g}}}\left(\ell,0\right)$-module, and such that for any
$i\in I$,
$\left(\left(x_{\pm\alpha_{i}}\right){}_{-1}\right){}^{\epsilon_{i}\ell+1}\mathbf{1}$
acts trivially on $W$. Recall from the first part of the theorem that $W$ is
then a $\widetilde{\mathfrak{g}}[\mu]$-module with
$a^{\mu}\left[z\right]=Y_{W}^{\phi}\left(a,z\right)$ for
$a\in\mathcal{A}_{\mathfrak{g}}$. Combining this with (6.16), we obtain

$\displaystyle\left(\prod_{1\leq
i<j\leq\epsilon_{i}\ell+1}p_{i}\left(z_{i}/z_{j}\right)\right)Y_{W}^{\phi}\left(x_{\pm\alpha_{i}},z_{1}\right)Y_{W}^{\phi}\left(x_{\pm\alpha_{i}},z_{2}\right)\cdots
Y_{W}^{\phi}\left(x_{\pm\alpha_{i}},z_{\epsilon_{i}\ell+1}\right)\in\mathrm{Hom}\left(W,W\left(\left(z_{1},\dots,z_{\epsilon_{i}\ell+1}\right)\right)\right).$

Then again by (6.18) and Proposition 2.5, we see that (6.19) holds. This
implies, viewing $W$ as a restricted $\widetilde{\mathfrak{g}}[\mu]$-module of
level $\ell$, that (6.17) holds. Thus, by Proposition 6.6, $W$ is an
integrable $\widetilde{\mathfrak{g}}[\mu]$-module. This completes the proof of
the theorem. ∎

######  Remark 6.9.

For any complex number $a$, two vertex algebras
$V_{\widehat{\mathfrak{t}}(\mathfrak{g},a)^{o}}\left(\ell\right)$ and
$L_{\widehat{\mathfrak{t}}(\mathfrak{g},a)^{o}}(\ell)$ were constructed in
[CLiT], and such that
$V_{\widehat{\mathfrak{t}}\left(\mathfrak{g},0\right){}^{o}}\left(\ell\right)=V_{\widehat{\mathfrak{g}}}\left(\ell,0\right)$
and
$L_{\widehat{\mathfrak{t}}(\mathfrak{g},0)^{o}}\left(\ell\right)=L_{\widehat{\mathfrak{g}}}\left(\ell,0\right)$.
By a similarly argument as above, one can prove that the Lie algebra
$\widetilde{\mathfrak{g}}\left[\mu\right]{}_{\tau_{a}}$ can be associated with
the vertex algebras
$V_{\widehat{\mathfrak{t}}(\mathfrak{g},a)^{o}}\left(\ell\right)$ and
$L_{\widehat{\mathfrak{t}}(\mathfrak{g},a)^{o}}\left(\ell\right)$ via their
equivariant $\phi$-coordinated quasi modules, where
$\widetilde{\mathfrak{g}}\left[\mu\right]{}_{\tau_{a}}$ and the affine cocycle
$\tau_{a}$ are defined in Remark 5.8.

##  7 Associating $\widetilde{\mathfrak{sl}}_{N}\left(\mathbb{C}_{q}\right)$
with vertex algebras

Let $N\geq 2$ be a positive integer and $q\in{\mathbb{C}}^{\ast}$ a generic
complex number. In this section we prove an analog of Theorem 6.8 for the
extended affine Lie algebra
$\widetilde{\mathfrak{sl}}_{N}\left(\mathbb{C}_{q}\right)$.

First, we define the following generating functions in
$\widetilde{\mathfrak{sl}}_{N}\left(\mathbb{C}_{q}\right)[[z,z^{-1}]]$:

$\displaystyle\left(E_{i,j}t_{1}^{m}\right)\left[z\right]$
$\displaystyle=\sum_{n\in{\mathbb{Z}}}\left(E_{i,j}t_{0}^{n}t_{1}^{m}\right)z^{-n},\quad
H_{k}\left[z\right]=\sum_{n\in\mathbb{Z}}\left(E_{k,k}-E_{k+1,k+1}\right)t_{0}^{n}z^{-n},$
$\displaystyle H_{N}\left[z\right]$
$\displaystyle=\sum_{n\in\mathbb{Z}}\left(E_{N,N}t_{0}^{n}-q^{-n}E_{1,1}t_{0}^{n}-\delta_{n,0}{\text{k}}_{1}\right)z^{-n},$

where $1\leq i,j\leq N,\ m\in\mathbb{Z}$ with
$\left(i-j,m\right)\neq\left(0,0\right)$ and $1\leq k\leq N-1$. Note that all
the coefficients of these generating functions, together with $\text{k}_{0}$,
$\text{d}_{0}$ and $\text{d}_{1}$, form a basis of
$\widetilde{\mathfrak{sl}}_{N}\left(\mathbb{C}_{q}\right)$.

######  Definition 7.1.

We say that an
$\widetilde{\mathfrak{sl}}_{N}\left(\mathbb{C}_{q}\right)$-module $W$ is
_restricted_ if $\left(E_{i,j}t_{1}^{m}\right)\left[z\right]$,
$H_{k}\left[z\right]\in\mathrm{Hom}\left(W,W\left(\left(z\right)\right)\right)$
for $1\leq i,j,k\leq N,\ m\in\mathbb{Z}$ with $\left(i-j,m\right)\neq(0,0)$.
$W$ is said to be _of level_ $\ell\in\mathbb{C}$ if the central element
$\text{k}_{0}$ acts as the scalar $\ell$. Furthermore, we say that $W$ is
_integrable_ if $E_{i,j}t_{0}^{n}t_{1}^{m}$ acts locally nilpotent on $W$ for
$1\leq i\neq j\leq N,\ m,n\in\mathbb{Z}$.

The following result is from [CLiTW, Proposition 3.13].

######  Proposition 7.2.

Let $W$ be a restricted
$\widetilde{\mathfrak{sl}}_{N}\left(\mathbb{C}_{q}\right)$-module of level
$\ell$. Then $W$ is integrable if and only if $\ell$ is a nonnegative integer
and

$\left(E_{i,j}t_{1}^{m}\right)\left[z\right]^{\ell+1}=0\ \ \text{on}\ W$

for $1\leq i\neq j\leq N$ and $m\in{\mathbb{Z}}$.

Let $\mathfrak{gl}_{\infty}$ be the algebra of all doubly infinite complex
matrices with only finitely many nonzero entries. For $m,n\in\mathbb{Z}$, let
$E_{m,n}$ denote the unit matrix whose only nonzero entry is the $(m,n)$-entry
which is equal to $1$. Equip $\mathfrak{gl}_{\infty}$ with a nondegenerate,
invariant and symmetric bilinear form $\langle\cdot,\cdot\rangle$ defined by

$\displaystyle\left\langle
E_{i,j},E_{k,l}\right\rangle=\delta_{j,k}\,\delta_{i,l},$

for $i,j,k,l\in\mathbb{Z}.$ Let
$\mathfrak{sl}_{\infty}=\left[\mathfrak{gl}_{\infty},\mathfrak{gl}_{\infty}\right]$
be the derived subalgebra of $\mathfrak{gl}_{\infty}$. Then
$\left\langle\cdot,\cdot\right\rangle$ is also nondegenerate on
$\mathfrak{sl}_{\infty}$. And associated to the pair
$\left(\mathfrak{sl}_{\infty},\langle\cdot,\cdot\rangle\right)$, we have the
corresponding affine Lie algebra
$\widehat{\mathcal{L}}\left(\mathfrak{sl}_{\infty}\right)$, the universal
affine vertex algebra
$V_{\widehat{\mathcal{L}}\left(\mathfrak{sl}_{\infty}\right)}\left(\ell,0\right)$,
and the simple affine vertex algebra
$L_{\widehat{\mathcal{L}}\left(\mathfrak{sl}_{\infty}\right)}\left(\ell,0\right)=V_{\widehat{\mathcal{L}}\left(\mathfrak{sl}_{\infty}\right)}\left(\ell,0\right)/J_{\widehat{\mathcal{L}}\left(\mathfrak{sl}_{\infty}\right)}\left(\ell,0\right)$
(see the subsection 3.2). The following result is given in [CLiTW, Lemma
3.11].

######  Lemma 7.3.

If $\ell$ is a nonnegative integer, then
$J_{\widehat{\mathcal{L}}\left(\mathfrak{sl}_{\infty}\right)}\left(\ell,0\right)$,
as $\widehat{\mathcal{L}}\left(\mathfrak{sl}_{\infty}\right)$-module, is
generated by the set of vectors

$\displaystyle\\{\left(t^{-1}\otimes
E_{mN+i,nN+j}\right){}^{\ell+1}{\mathbf{1}}\mid\ \text{for}\ 1\leq i\neq j\leq
N,\ m,n\in{\mathbb{Z}}\\}.$ (7.1)

Let $\sigma_{N}$ be the automorphism of the algebra $\mathfrak{gl}_{\infty}$
defined by

$\displaystyle\sigma_{N}\left(E_{m,n}\right)=E_{m+N,n+N},$ (7.2)

for $m,n\in\mathbb{Z}$. Restrict $\sigma_{N}$ to the subalgebra
$\mathfrak{sl}_{\infty}$, we see that $\sigma_{N}$ is also an automorphism of
$\mathfrak{sl}_{\infty}$ that preserves the bilinear form
$\left\langle\cdot,\cdot\right\rangle$. Denoted by
$G_{N}=\langle\sigma_{N}\rangle$ the automorphism group of
$\mathfrak{sl}_{\infty}$ generated by $\sigma_{N}$. As pointed out in Section
3.2, $G_{N}$ can be extended uniquely to an automorphism group of the vertex
algebras
$V_{\widehat{\mathcal{L}}\left(\mathfrak{sl}_{\infty}\right)}\left(\ell,0\right)$
and
$L_{\widehat{\mathcal{L}}\left(\mathfrak{sl}_{\infty}\right)}\left(\ell,0\right)$.
Let $\chi_{q}:G_{N}\rightarrow\mathbb{C}^{\times}$ be the linear character
defined by $\chi_{q}\left(\sigma_{N}^{n}\right)=q^{n}$ for $n\in\mathbb{Z}$.

Define a ${\mathbb{Z}}$-grading
$\mathfrak{gl}_{\infty}=\oplus_{n\in\mathbb{Z}}\mathfrak{gl}_{\infty(n)}$ on
$\mathfrak{gl}_{\infty}$ by assigning

$\displaystyle\deg E_{mN+i,nN+j}=n-m,$ (7.3)

for $m,n\in\mathbb{Z},\ 1\leq i,j\leq N$. Note that $\mathfrak{sl}_{\infty}$
is a graded subalgebra of $\mathfrak{gl}_{\infty}$. Denoted by $\mathcal{P}$
the derivation of $\mathfrak{sl}_{\infty}$ defined by $\mathcal{P}(a)=na$ if
$a\in\mathfrak{sl}_{\infty}$ with $\deg a=n$. Note that for
$a,b\in\mathfrak{sl}_{\infty}$, one has $\langle\mathcal{P}a,b\rangle+\langle
a,\mathcal{P}b\rangle=0$. This allows us to lift the derivation $\mathcal{P}$
of $\mathfrak{sl}_{\infty}$ to be a derivation of the affine Lie algebra
$\widehat{\mathcal{L}}\left(\mathfrak{sl}_{\infty}\right)$ with

$\displaystyle\mathcal{P}\left(\text{k}\right)=0,\
\quad\mathcal{P}\left(t^{n}\otimes a\right)=t^{n}\otimes\mathcal{P}(a),$ (7.4)

for $n\in\mathbb{Z},a\in\mathfrak{sl}_{\infty}$. As
$\mathcal{P}\left(t^{-1}\mathbb{C}\left[t^{-1}\right]\otimes\mathfrak{sl}_{\infty}\right)\subset
t^{-1}\mathbb{C}\left[t^{-1}\right]\otimes\mathfrak{sl}_{\infty}$,
$\mathcal{P}$ is also a derivation of the associative algebra
$\mathcal{U}\left(t^{-1}\mathbb{C}\left[t^{-1}\right]\otimes\mathfrak{sl}_{\infty}\right)$.
Via the isomorphism
$\mathcal{U}\left(t^{-1}\mathbb{C}\left[t^{-1}\right]\otimes\mathfrak{sl}_{\infty}\right)\cong
V_{\widehat{\mathcal{L}}\left(\mathfrak{sl}_{\infty}\right)}\left(\ell,0\right)$,
$\mathcal{P}$ becomes a derivation of
$V_{\widehat{\mathcal{L}}\left(\mathfrak{sl}_{\infty}\right)}\left(\ell,0\right)$
(as a vertex algebra). Furthermore, if $\ell$ is a nonnegative integer, then
by Lemma 7.3, we see that $\mathcal{P}$ also preserves the submodule
$J_{\widehat{\mathcal{L}}\left(\mathfrak{sl}_{\infty}\right)}\left(\ell,0\right)$.
Therefore, it descends to a derivation of
$L_{\widehat{\mathcal{L}}\left(\mathfrak{sl}_{\infty}\right)}\left(\ell,0\right)$.

######  Definition 7.4.

A $\left(G_{N},\chi_{q}\right)$-equivariant $\phi$-coordinated quasi
$V_{\widehat{\mathcal{L}}\left(\mathfrak{sl}_{\infty}\right)}\left(\ell,0\right)$-module
$\left(W,Y_{W}^{\phi},d,p\right)$ is a
$\left(G_{N},\chi_{q}\right)$-equivariant $\phi$-coordinated quasi module
$\left(W,Y_{W}^{\phi},d\right)$ equipped with a linear transformation $p$ on
$W$ such that

$\left[p,Y_{W}^{\phi}(v,z)\right]=Y_{W}^{\phi}\left(\mathcal{P}v,z\right),$

for $v\in
V_{\widehat{\mathcal{L}}\left(\mathfrak{sl}_{\infty}\right)}\left(\ell,0\right)$.
Similarly, when $\ell$ is a nonnegative integer, we can define the notion of
$\left(G_{N},\chi_{q}\right)$-equivariant $\phi$-coordinated quasi
$L_{\widehat{\mathcal{L}}\left(\mathfrak{sl}_{\infty}\right)}\left(\ell,0\right)$-module
$\left(W,Y_{W}^{\phi},d,p\right)$.

######  Theorem 7.5.

Let $\ell$ be a complex number. If $W$ is a restricted
$\widetilde{\mathfrak{sl}}_{N}\left(\mathbb{C}_{q}\right)$-module of level
$\ell$, then there is a $\left(G_{N},\chi_{q}\right)$-equivariant
$\phi$-coordinated quasi
$V_{\widehat{\mathcal{L}}\left(\mathfrak{sl}_{\infty}\right)}\left(\ell,0\right)$-module
structure $\left(Y_{W}^{\phi},d,p\right)$ on $W$ uniquely determined by

$\displaystyle p=-\text{d}_{1},\ d=-\text{d}_{0},\
Y_{W}^{\phi}\left(E_{mN+i,j},z\right)=\left(E_{i,j}t_{1}^{m}\right)\left[z\right],\
\ Y_{W}^{\phi}\left(E_{k,k}-E_{k+1,k+1},z\right)=H_{k}\left[z\right]$

for $1\leq i,j,k\leq N$, $m\in{\mathbb{Z}}$ with
$\left(i-j,m\right)\neq(0,0)$. On the other hand, if
$\left(W,Y_{W}^{\phi},d,p\right)$ is a
$\left(G_{N},\chi_{q}\right)$-equivariant $\phi$-coordinated quasi
$V_{\widehat{\mathcal{L}}\left(\mathfrak{sl}_{\infty}\right)}\left(\ell,0\right)$-module,
then $W$ is a restricted
$\widetilde{\mathfrak{sl}}_{N}\left(\mathbb{C}_{q}\right)$-module of level
$\ell$ with action given by

$\displaystyle\text{d}_{1}=-p,\ \text{d}_{0}=-d,\
\left(E_{i,j}t_{1}^{m}\right)\left[z\right]=Y_{W}^{\phi}\left(E_{mN+i,j},z\right),\
\ H_{k}\left[z\right]=Y_{W}^{\phi}\left(E_{k,k}-E_{k+1,k+1},z\right)$

for $1\leq i,j,k\leq N$, $m\in{\mathbb{Z}}$ with
$\left(i-j,m\right)\neq(0,0)$.

Furthermore, if $\ell$ is a nonnegative integer, then the integrable
restricted $\widetilde{\mathfrak{sl}}_{N}\left(\mathbb{C}_{q}\right)$-modules
of level $\ell$ are exactly the $\left(G_{N},\chi_{q}\right)$-equivariant
$\phi$-coordinated quasi
$L_{\widehat{\mathcal{L}}\left(\mathfrak{sl}_{\infty}\right)}\left(\ell,0\right)$-modules
$\left(W,Y_{W}^{\phi},d,p\right)$.

###### Proof.

Recall that
$\widetilde{\mathfrak{sl}}_{N}\left(\mathbb{C}_{q}\right)=\widehat{\mathfrak{sl}}_{N}\left(\mathbb{C}_{q}\right)\oplus\mathbb{C}\text{d}_{0}\oplus\mathbb{C}\text{d}_{1}$.
It was proved in [CLiTW, Proposition 3.8] that the restricted
$\widehat{\mathfrak{sl}}_{N}\left(\mathbb{C}_{q}\right)$-modules $W$ of level
$\ell$ are exactly the $\left(G_{N},\chi_{q}\right)$-equivariant quasi
$V_{\widehat{\mathcal{L}}\left(\mathfrak{sl}_{\infty}\right)}\left(\ell,0\right)$-modules
$\left(W,Y_{W}\right)$ with

$\displaystyle
z^{-1}\left(E_{i,j}t_{1}^{m}\right)\left[z\right]=Y_{W}\left(E_{mN+i,j},z\right),\
\ z^{-1}H_{k}\left[z\right]=Y_{W}\left(E_{k,k}-E_{k+1,k+1},z\right)$

for $1\leq i,j,k\leq N$, $m\in{\mathbb{Z}}$ with
$\left(i-j,m\right)\neq\left(0,0\right)$. It then follows from Proposition 3.5
that the restricted
$\widehat{\mathfrak{sl}}_{N}\left(\mathbb{C}_{q}\right)$-modules $W$ of level
$\ell$ are exactly the $\left(G_{N},\chi_{q}\right)$-equivariant
$\phi$-coordinated quasi
$V_{\widehat{\mathcal{L}}\left(\mathfrak{sl}_{\infty}\right)}\left(\ell,0\right)$-modules
$\left(W,Y_{W}^{\phi}\right)$ with

$\displaystyle\left(E_{i,j}t_{1}^{m}\right)\left[z\right]=Y_{W}^{\phi}\left(E_{mN+i,j},z\right),\
\ H_{k}\left[z\right]=Y_{W}^{\phi}\left(E_{k,k}-E_{k+1,k+1},z\right).$

Furthermore, by (7.3) and Lemma 2.2 we have

$\displaystyle\left[-\text{d}_{1},\left(E_{i,j}t_{1}^{m}\right)\left[z\right]\right]$
$\displaystyle=-m\left(E_{i,j}t_{1}^{m}\right)\left[z\right]=-mY_{W}^{\phi}\left(E_{mN+i,j},z\right)=Y_{W}^{\phi}\left(\mathcal{P}\left(E_{mN+i,j}\right),z\right),$
$\displaystyle\left[-\text{d}_{1},H_{k}\left[z\right]\right]$
$\displaystyle=0=Y_{W}^{\phi}\left(\mathcal{P}\left(E_{k,k}-E_{k+1,k+1}\right),z\right),$
$\displaystyle\left[-\text{d}_{0},\left(E_{i,j}t_{1}^{m}\right)\left[z\right]\right]$
$\displaystyle=z\frac{d}{dz}\left(E_{i,j}t_{1}^{m}\right)\left[z\right]=z\frac{d}{dz}Y_{W}^{\phi}\left(E_{mN+i,j},z\right)=Y_{W}^{\phi}\left(\mathcal{D}\left(E_{mN+i,j}\right),z\right),$
$\displaystyle\left[-\text{d}_{0},H_{k}\left[z\right]\right]$
$\displaystyle=z\frac{d}{dz}H_{k}\left[z\right]=z\frac{d}{dz}Y_{W}^{\phi}\left(E_{k,k}-E_{k+1,k+1},z\right)=Y_{W}^{\phi}\left(\mathcal{D}\left(E_{k,k}-E_{k+1,k+1}\right),z\right).$

Therefore, we have finished the proof for the first part of the theorem.

To prove the second part of the theorem, we suppose that $\ell$ is a
nonnegative integer and $W$ an integrable restricted
$\widetilde{\mathfrak{sl}}_{N}\left(\mathbb{C}_{q}\right)$-module of level
$\ell$. Then for $1\leq i\neq j\leq N$ and $m,n\in\mathbb{Z}$, we have
$\left(E_{mN+i,nN+j}\right){}_{r}\left(E_{mN+i,nN+j}\right)=0$ for $r\geq 0$
in
$V_{\widehat{\mathcal{L}}\left(\mathfrak{sl}_{\infty}\right)}\left(\ell,0\right)$.
And as a $\left(G_{N},\chi_{q}\right)$-equivariant $\phi$-coordinated quasi
$V_{\widehat{\mathcal{L}}\left(\mathfrak{sl}_{\infty}\right)}\left(\ell,0\right)$-module
we have

$\displaystyle
Y_{W}^{\phi}\left(E_{mN+i,nN+j},z\right)=Y_{W}^{\phi}\left(\sigma_{N}^{n}\left(E_{(m-n)N+i,j}\right),z\right)=Y_{W}^{\phi}\left(E_{(m-n)N+i,j},\chi_{q}(\sigma_{N})^{n}z\right)=\left(E_{i,j}t_{1}^{m-n}\right)\left(q^{n}z\right).$

This implies that

$\left[Y_{W}^{\phi}\left(E_{mN+i,nN+j},z_{1}\right),Y_{W}^{\phi}\left(E_{mN+i,nN+j},z_{2}\right)\right]=\left[\left(E_{i,j}t_{1}^{m-n}\right)\left(q^{n}z_{1}\right),\left(E_{i,j}t_{1}^{m-n}\right)\left(q^{n}z_{2}\right)\right]=0.$

Thus, by Propositions 2.5 and 7.2, we have
$\left(\left(E_{mN+i,nN+j}\right){}_{-1}\right){}^{\ell+1}{\mathbf{1}}=0$ in
$V_{\widehat{\mathcal{L}}\left(\mathfrak{sl}_{\infty}\right)}\left(\ell,0\right)/\ker
Y_{W}^{\phi}$. This together with Lemma 7.3 implies that
$J_{\widehat{\mathcal{L}}\left(\mathfrak{sl}_{\infty}\right)}\left(\ell,0\right)\subset\ker
Y_{W}^{\phi}$, and hence $\left(W,Y_{W}^{\phi},d,p\right)$ is a
$\left(G_{N},\chi_{q}\right)$-equivariant $\phi$-coordinated quasi
$L_{\widehat{\mathcal{L}}\left(\mathfrak{sl}_{\infty}\right)}\left(\ell,0\right)$-module.
Conversely, let $\left(W,Y_{W}^{\phi},d,p\right)$ be a
$\left(G_{N},\chi_{q}\right)$-equivariant $\phi$-coordinated quasi
$L_{\widehat{\mathcal{L}}\left(\mathfrak{sl}_{\infty}\right)}\left(\ell,0\right)$-module.
Then it is a restricted
$\widetilde{\mathfrak{sl}}_{N}\left(\mathbb{C}_{q}\right)$-module of level
$\ell$. Again by Lemma 7.3, Proposition 2.5 and Proposition 7.2, one deduces
that $W$ is integrable as required. ∎

## Acknowledgement

This work was supported by the National Natural Science Foundation of China
11971396, 11971397, and the Fundamental Research Funds for the Central
Universities 20720190069, 20720200067. The authors would like to thank
Institute for Advanced Study in Mathematics, Zhejiang. Part of this work was
carried out while the first and the third author were visiting the institute.

## References

  * [AABGP] B. Allison, S. Azam, S. Berman, Y. Gao, A. Pianzola, Extended affine Lie algebras and their root systems, _Memoir Amer. Math. Soc._ 126 (1997), x+122 pp.
  * [ABFP] B. Allison, S. Berman, J. Faulkner, A. Pianzola, Multiloop realization of extended affine Lie algebras and Lie tori, _Trans. Amer. Math. Soc._ 361 (2009), 4807–4842.
  * [ABGP] B. Allison, S. Berman, Y. Gao, A. Pianzola, A characterization of affine Kac-Moody Lie algebras, _Commun. Math. Phys._ 185 (1997), 671–688.
  * [ABP] B. Allison, S. Berman, A. Pianzola,__ Multiloop algebras, iterated loop algebras and extended affine Lie algebras of nullity 2, _J. Eur. Math. Soc._ 16 (2014), 327–385.
  * [B1] Y. Billig, A category of modules for the full toroidal Lie algebra,_Int. Math. Res. Not._ (2006), Art. ID 68395, 46 pp.
  * [B2] Y. Billig, Representations of toroidal extended affine Lie algebra, _J. Algebra_ 308 (2007), 252–269.
  * [BGK] S. Berman, Y. Gao, Y. Krylyuk, Quantum tori and the structure of elliptic quasi-simple Lie algebras, _J. Funct. Anal._ 135 (1996), 339–389.
  * [CJKT] F. Chen, N. Jing, F. Kong, S. Tan, Twisted toroidal Lie algebras and Moody-Rao-Yokonuma presentation,_Sci. China Math._ 64 (2021) , 1181–1200.
  * [CLiT] F. Chen, H.-S. Li, S. Tan, Toroidal extended affine Lie algebras and vertex algebras, arXiv:2102.10968.
  * [CLT1] F. Chen, Z. Li, S. Tan, Integrable representations for toroidal extended affine Lie algebras, _J. Algebra_ 519 (2019), 228–252.
  * [CLT2] F. Chen, Z. Li, S. Tan, Classification of integrable representations for toroidal extended affine Lie algebras, _J. Algebra_ 574 (2021), 1–37.
  * [CLiTW] F. Chen, H.-S. Li, S. Tan, Q. Wang, Extended affine Lie algebras, vertex algebras, and reductive groups, arXiv: 2004.02821.
  * [CLTW] F. Chen, X. Liao, S. Tan, Q. Wang, $\left(G,\chi_{\phi}\right)$-equivariant $\phi$-coordinated quasi modules for vertex algebras, arXiv:2103.10038v1.
  * [CNPY] V. Chernousov, E. Neher, A. Pianzola, U. Yahorau, On conjugacy of cartan subalgebras in extended affine lie algebras, _Adv. Math._ 290 (2016), 260–292.
  * [DLM] C. Dong, H.-S. Li, G. Mason, Vertex Lie algebras, vertex Poisson algebras and vertex algebras, in: Recent Developments in Infinite-Dimensional Lie Algebras and Conformal Field Theory, Charlottesville, VA, 2000, in: _Contemp. Math._ , vol. 297, Amer. Math. Soc., Providence, RI, 2002, pp. 69–96.
  * [ESB] S. Eswara Rao, S. Sharma, P. Batra, Integrable modules for twisted toroidal extended affine Lie algebras, _J. Algebra_ , 556 (2020), 1057–1072.
  * [FHL] I. B. Frenkel, Y. Huang, J. Lepowsky, On axiomatic approaches to vertex operator algebras and modules, Memoirs Amer. Math. Soc. 104, 1993.
  * [FLM] I. B. Frenkel, J. Lepowsky, A. Meurman, Vertex operator algebras and the monster, Pure and Applied Math. Vol. 134, Academic Press, Boston, 1988.
  * [FSS] J. Fuchs, B. Schellekens, C. Schweigert, From Dynkin diagram symmetries to fixed point structures, _Commun. Math. Phys._ 180 (1996), 39–97.
  * [FZ] I. B. Frenkel, Y.-C. Zhu, Vertex operator algebras associated to representations of affine and Virasoro algebras, _Duke Math. J._ 66 (1992), 123–168.
  * [G1] Y. Gao, Representations of extended affine Lie algebras coordinatized by certain quantum tori, _Compositio Math._ 123 (2000), 1–25.
  * [G2] Y. Gao, Vertex operators arising from the homogeneous realization for $\widehat{gl_{N}}$, _Commun. Math. Phys._ 211 (2000), 745–777.
  * [G3] Y. Gao, Fermionic and bosonic representations of the extended affine Lie algebra $\widetilde{gl_{N}(\mathbb{C}_{q})}$, _Canada Math. Bull._ 45 (2002), 623–633.
  * [GZ] Y. Gao, Z. Zeng, Hermitian representations of the extended affine Lie algebra $\widetilde{gl_{2}(\mathbb{C}_{q})}$, _Adv. Math._ 207 (2006), 244–265.
  * [G-KK] M. Golenishcheva-Kutuzova, V. Kac, $\Gamma$-conformal algebras, _J. Math. Phys._ 39 (1998), 2290–2305.
  * [GP] P. Gille, A. Pianzola, Torsors, reductive group schemes and extended affine Lie algebras, _Memoirs Amer. Math. Soc._ 226, vi+112, 2013.
  * [H-KT] R. Hoegh-Krohn, B. Torresani, Classification and construction of quasisimple Lie algebras, _J. Funct. Anal._ 89 (1990), 106–136.
  * [JKLiT] N. Jing, F. Kong, H.-S. Li, S. Tan, $\left(G,\chi_{\phi}\right)$-equivariant $\phi$-coordinated quasi modules for nonlocal vertex algebras,_J. Algebra_ 570  (2021), 24–74.
  * [K1] V. Kac, Infinite Dimensional Lie Algebras, Third edition, Cambridge University Press, 1990.
  * [K2] V. Kac, Vertex Algebras for Beginners, 2nd edition, University Lecture Series, 10, Amer. Math. Soc., 1998.
  * [KW] V. Kac, S. P. Wang, On automorphisms of Kac-Moody algebras and groups, _Adv. Math._ 92 (1992), 129–195.
  * [Li1] H.-S. Li, Local systems of vertex operators, vertex superalgebras and modules, _J. Pure Appl. Algebra_ 109 (1996), 143–195.
  * [Li2] H.-S. Li, Local systems of twisted vertex operators, vertex superalgebras and twisted modules,_Contemporary Math._ 193, Amer. Math. Soc., Providence, 1996, 203–236.
  * [Li3] H.-S. Li, A new construction of vertex algebras and quasi modules for vertex algebras, _Adv. Math._ 202 (2006), 232–286.
  * [Li4] H.-S. Li, On centain generalizations of twisted affine Lie algebras and quasimodules for $\Gamma$-vertex algebras, _J. Pure Appl. Algebra_ 209 (2007), 853–871.
  * [Li5] H.-S. Li, Twisted modules and quasi-modules for vertex operator algebras, _Contemporary Math._ 422, Amer. Math. Soc., Providence, 2007, 389–400.
  * [Li6] H.-S. Li, $\phi$-coordinated quasi-modules for quantum vertex algebras, _Commun. Math. Phys._ 308 (2011), 703–741.
  * [Li7] H.-S. Li, Vertex $F$-algebras and their $\phi$-coordinated modules, _J. Pure Appl. Algebra_ 215 (2011), 1645–1662.
  * [Li8] H.-S. Li, $G$-equivariant $\phi$-coordinated quasi modules for quantum vertex algebras, _J. Math. Phys._ 54 (2013), 1–26.
  * [LLi] J. Lepowsky, H. Li, Introduction to vertex operator algebras and their representations, Progr. Math., vol. 227, Birkh$\ddot{a}$user, Boston, 2004.
  * [LP] Y. Lin and L. Peng, Elliptic Lie algebras and tubular algebras, _Adv. Math._ 196 (2005), 487–530.
  * [MRY] R. Moody, S. E. Rao, T. Yokonuma, Toroidal Lie algebras and vertex representations, _Geom. Dedicata_ 35 (1990), 283–307.
  * [N] E. Neher, Extended affine Lie algebras,_C. R. Math. Acad. Sci. Soc. R. Can._ 26 (2004), 90–96.
  * [P] M. Primc, Vertex algebras generated by Lie algebras, _J. Pure Appl. Algebra_ 135 (1999), 253–293.
  * [Sa] K. Saito, Extended affine root systems. I. Coxeter transformations, _Publ. Res. Inst. Math. Sci._ 21 (1985), no. 1, 75–179.
  * [Sl] P. Slodowy, Singularitäten, Kac-Moody-Liealgebren, assoziierte Gruppen und Vebrallgemeinerungen, Habilitationsschrift publication of the Max-Planck-Institut für Mathematik, Bonn (1984).
  * [Z] Y.-C. Zhu, Modular invariance of characters of vertex operator algebras, _J. Amer. Math. Soc._ 9 (1996), 237–302.

F. Chen: School of Mathematical Sciences, Xiamen University, Xiamen, 361005,
China<EMAIL_ADDRESS>
S. Tan: School of Mathematical Sciences, Xiamen University, Xiamen, 361005,
China<EMAIL_ADDRESS>
N. Yu: School of Mathematical Sciences, Xiamen University, Xiamen, 361005,
China<EMAIL_ADDRESS>