Classical Simulation of Quantum Circuits: Parallel Environments and Benchmark
Authors: Xiao-Yang Liu
Zeliang Zhang
Venue: NeurIPS 2023 Datasets and Benchmarks Poster (2023)
Keywords: Quantum circuits; tensor network contraction; reinforcement learning; classical simulation

Abstract: Google's quantum supremacy announcement has received broad questions from academia and industry due to the debatable estimate of 10,000 years' running time for the classical simulation task on the Summit supercomputer. Has quantum supremacy already come? Or will it come in one or two decades later? To avoid hasty advertisements of quantum supremacy by tech giants or quantum startups and eliminate the cost of dedicating a team to the classical simulation task, we advocate an open-source approach to maintain a trustable benchmark performance.  In this paper, we take a reinforcement learning approach for the classical simulation of quantum circuits and demonstrate its great potential by reporting an estimated simulation time of less than 4 days, a speedup of 5.40x over the state-of-the-art method.  Specifically, we formulate the classical simulation task as a tensor network contraction ordering problem using the K-spin Ising model and employ a novel Hamiltonina-based reinforcement learning algorithm. Then, we establish standard criteria to evaluate the performance of classical simulation of quantum circuits.  We develop a dozen of massively parallel environments to simulate quantum circuits.  We open-source our parallel gym environments and benchmarks. We hope the AI/ML community and quantum physics community will collaborate to maintain reference curves for validating an unequivocal first demonstration of empirical quantum supremacy.

Classical Simulation of Quantum Circuits Using Reinforcement Learning: Parallel Environments and Benchmark
Xiao-Yang Liu and Zeliang Zhang
Rensselaer Polytechnic Institute, "Columbia University, 1iux33drpi.edd edu, XL24278columbia. edu, hust04268gmail.com com
Abstract
Google's "quantum supremacy" announcement [3] has received broad questions from academia and industry due the debatable estimate of 10, 000 years' run- ning time for the classical simulation task on the Summit supercomputer. Нas "quantum supremacy" already come? Or will it come in one or two decades later? To avoid hasty advertisements of "quantum supremacy" by tech giants quantum startups and eliminate the cost of dedicating team the classical sim- ulation task, we advocate an open-source approach to maintain trustable bench- mark performance. this paper, we take a reinforcement learning approach for the classical simulation of quantum circuits and demonstrate its great potential by reporting an estimated simulation time of less than 4 days, speedup of 5.40x over the state-of-the-ar method. Specifically, we formulate the classical simula- tion task as a tensor network contraction ordering problem using the K-spin Ising model and employ a novel Hamiltonian-basee reinforcement learning algorithm. Then, we evaluate the performance classical simulation of quantum circuits. We develop dozen of massively parallel environments to simulate quantum circuits. We open sourcs our parallel gym environments and benchmarks.
Introduction
Google proudly announced "achieving quantum supremacy" [3] with its 53-qubit Sycamore circuits back in 2019, which was later challenged by researchers claiming to have pulled ahead of Google classical computers. Quantum supremacy [46] aims to demonstrate that a programmable quantum device can solve a problem that no classical com- puter can solve in any feasible amount of time, irrespective of the usefulness of the problem. As illustrated in Fig. 1, for the problem of random number generation, Google's "quan- tum supremacy" announcement [3] relied on an estimated simulation time of 10, 000 years on the Summit supercom- puter, while existing works reduce to less than 21 days and scale the number of quantum qubits up to around 100. This raises the debate: Has "quantum supremacy" already come? Or will it come in one or two decades later? Our goal is to use machine learning methods to derive the best performance curves for the classical simulation task, to settle down the present debate and suggest
Google
existing
Running time
goel
years
21
days
Suproraay
Quantup
irouit
53
100
Figure 1: Running time of different quantum circuit simulation methods.
"Zeliang Zhang completed this work as a research assistant at Columbia University.
37th Conference on Neural Information Processing Systems (NeurIPS 2023) Track on Datasets and Bench-
marks.

---

that achieving "empirical quantum supremacy" requires continuing quantum hardware develop- ments without an unequivocal first demonstration.
There are several existing works on the classical simulation of quantum circuits [8]. One promising method is using tensor networks [42] since quantum circuits can be naturally represented as tensor networks, i.e., executing a quantum gate is mathematically a tensor contraction operation. There- fore, establishing benchmark curve for the classical simulation task is mathematically searching for the optimal tensor network contraction ordering (TNCO), which is a combinatorial optimization problem [25]. a variant of the well-known traveling salesman problem (TSP) where reinforcement learning (RL) algorithms [33] have shown powerful capability. We are motivated to take reinforce- ment learning approach establish state-of fette-of-the-aaee fif-the-rt art performance.
There is a debate on the estimate of running time for classical simulation tasks, as illustrated in Fig. 2. Huang al. [21] used heuristic tensor network approach on computing cluster and estimated the simulation time to be 21 days. Meirom et al. [34] used a reinforcement learning algorithm where the policy network used a graph neural network and reported an order-wise reduction compared to the best heuristic method. However, there is no available dataset for training and benchmarking machine learning algorithms, and it is reasonable maintain a publically trustable performance curve for the coming quantum supremacy.
To avoid hasty advertisements of "quantum supremacy" by tech giants or quantum startups and eliminate their cost of dedicating team to the classical simulation of quantum cir- cuits, establishing a standard benchmark important. In this paper, take a reinforcement learning (RL) approach for the classical simulation of quantum circuits and demon- strate its great potential by reporting an estimated simulation time of less than days, a speedup of 5.40x over the state- of-the-art method. The result demonstrates that the "quan- tum supremacy" claim still lacks an unequivocal first demon- stration. Specifically, we adopt the K-spin Ising model for the classical simulation of quantum circuits, i.c., the tensor network contraction order (TNCO) problem, and employ the Hamiltonian-be based reinforcement learning algorithm to mini- mize the number of multiplications. Then, we establish stan- dard criteria evaluate the simulation performance for Google's Sycamore circuits. We de- velop a dozen massively parallel environments for training and evaluating RL agents. We release multiple datasets, including tensor-train, synthetic, and sycamore quantum circuits, and benchmark curves, including OPT-Einsum, Cotengra, and our RL method, on Github at https: // //github com/Xi aaiiaoaannnuuuiia Fttinnn//AAAaaaaannniiaaattt
Google (2019)
10,000
years
21
days
10
Neuristi
days
days
(2020)
RL
Ours
[2022]
(2023)
Figure 2: Debatable time estimates of classical simulation of Google's Sycamore circuits.
We hope the AI/ML community and quantum physics community will collaborate maintain ref- erence curves for validating an unequivocal first demonstration of "empirical quantum supremacy".
Related Works
Random circuit sampling: Random Circuit Sampling (RCS) [35] is an approach that has garnered considerable attention within the quantum computing community. It involves the generation of random quantum circuits, which are subsequently subjected to measurement procedures. By sam- pling the measurement outcomes, RCS enables the evaluation of the distribution of classical output probabilities, providing valuable insights into the computational power of noisy intermediate-sed seale quantum devices. While many works [27, 38, 35] demonstrate the hardness of RCS, highlighting its computational complexity, the reinforcement learning-baid based method [34] presents a promising way to accelerate the classical simulation of RCS.
Quantum circuits for random number generation task: One notable example of the application of quantum circiuits [53] is the random number generation. It is NP-hard since simulating proba- bility distribution on classical computers involves an exponential time complexity. For the problem of random number generation, Google's Sycamore circuit [3] was milestone in quantum comput- ing, which used the random cireuit sampling technique to achieve the random selection process and claimed to demonstrate "quantum supremacy". However, it is hard for most researchers to access

---

the computing resources of quantum circuits for study. It is critical to simulate the quantum circuits and establish the dataset and benchmark performance verify such scientific claims.
the field of classical simulation, several approaches have been proposed to simulate quantum circuits, including the matrix representation methods [8], variational algorithms [51], and tensor network methods [42]. Among these, the tensor network method leverages the mathematical framework of tensor networks approximate quantum states and perform efficient simulations. Tensor network methods, such as the matrix product state (MPS) [16] and projected entangled pair state (PEPS) [59], have shown promising results in simulat- ing both one me-dimensioonll and two- ro--imensional quantum systems. In this paper, we take the tensor network method for simulating quantum eircuits.
Classical simulation of quantum circuits:
Tensor network contraction [48] and the search for the optimal contraction path [4] have gar- nered significant attention in computational physies and quantum information theory. Various tech- niques [9] are employed to identify the most efficient way to contract tensors, minimizing computa- tion cost. These advancements enable efficient simulation of quantum circuits. There are two pop- ular open-source libraries, OPT-Einsum [13] and Cotengra [18] (CTG-Greedy and CTG-Kahypar), while Cotengra achieves state-of-the-art performance for most tensor networks.
The Ising model [11] can serve as a unified formulation combinatorial optimization problems. including graph coloring, maximum cut problems, and traveling salesman problems. The Ising model describes a system of interacting spins that can be either up or down, representing binary variables in studied problems. By mapping the studied problem onto an Ising model, the problem can be reformulated as finding the configuration of spins that minimizes the corresponding energy function [57]. The tensor network contraction problem can be analyzed into one kind of combination problem, especially the TSP. Thus, it motivates us to model the tensor network contraction problem as the Ising model and learn the optimal tensor contraction path by minimizing the energy function to reduce the computation complexity.
Ising model:
In recent years, the integration of artificial intelligence (AI) and machine learning (ML) techniques in scientific research has revolutionized various domains [12, 26, 6, 23]. The application of AI/ML in scientific fields, often referred to as AI+X machine learning for science, has brought about significant advancements and novel approaches to solving complex problems [54]. For exam- ple, tensor network factorization can be used for probabilistic modeling [15]. The quantum entan- glement can be built as a fundamental connection with deep neural network design [28]. Quantum K-spin Hamiltonian Regularization is proposed stabilize the reinforcement learning process [29]. A recent study uses the tensor network-base quantum circuits for image classification [19].
AI/L X:
3 Classical Simulation of Quantum Circuits Using Tensor Networks
We use uppercase calligraphic letters to denote tensors, e.g., A' E RXXX uppercase and lowercase boldface letters to denote matrices and vectors, e.g., X E RIXJ and a E R'.
3.1 Quantum Circuits
Qubits: A qubit in superposition state can be represented as (ő) = au (0) 0q [1), where ag, an C, and Joul 2 + |a1|2 2 1. For n qubits, we use a linear combination of 2" coefficients and states J0...0). 0 00..1).... 1). respectively,
(+) = o 10...0) + + on... (1...)),
(1)
where Cg.... ..., Q1... C, and |oo...o! +... 13 1
Quantum gates: Single- and double-qubit quantum gates are building blocks of quantum circuits,
Single-qubit gate:
-i
1
-1
V=
VX
vY
VW
(2)
2
V2
i 1
V2
3

---

Double-qubil gate:
1
0
0
0
cos 0
- i sin 0
0
f)im(0,
(3)
0
sin 0
cos 0
0
0
0
exp
where = x/2 and Φ = 7/6 6 are used in the Sycamore quantum circuits.
Quantum circuits consists of sequence of quantum gates. For a given initial state (vo) and a quantum circuit = Um...US the final state is w) - Um ... x U1 (v)- Fig. 3 illustrates example of 4 qubits and circuit U of = cycles. the ini- tial state (10) [0000). The quantum circuit U takes an initial state (()) of n qubits input, performs cycles of gate operations, and outputs bit-string i1ndd of length n.
In the i-th cycle, two operations are performed:
classiall quantum
00
1. A single-qubit gate R. E C2x2 randomly selected from set {v .Y, v }} is applied to 11 re- sulting in state (bx)) - R. 114-1)z5-
00:
R
(0)
R
(0)
Then, execute two-qubit quantum gate U. E Cixt to 11 and [1)=1) and obtain Specifically, during an odd cycle, such
single-qubit gate
double-qubit
state 10%)
Figure 3: A quantum circuit where the classical simulation lies in the middle.
qubit pairs with indices originating (0, 1), (2, 3), are chosen. For even cycles, qubit pairs with indices starting at 1 selected, including pairs such as (1, 2). (3, 4). This systematic ap- proach ensures the appropriate application of the U.P operation on the designated qubit pairs.
Before measurement, each qubit l1mm), undergoes random single-qubit quantum gate R Rm+--- The random binary bit-string b1...a is sampled from the probability distribution P (61é2...n (1)+)) 12, which obtained from the measurement outcome. More details about the random circuit sampling can be found in Appendix A.
3.2 Random Circuit Sampling
Quantum supremacy refers major milestone in quantum computing, representing the point at which a quantum computer can solve a specific problem that is practically infeasible for classical computers to solve within reasonable timeframe. It demonstration of the superior computational power of quantum systems compared to classical counterparts. Achieving quantum supremacy sigmifies the ability of a quantum computer to perform computations exponen- tially faster than even the most powerful classical supercomputers.
Quantum supermacy:
A quantum circuit defines distribution: Quantum circuit is sequence of quantum operations or gates applied to a set of qubits. These gates manipulate the quantum state of the qubits, transforming them according the specific operations performed. At the end of quantum circuit, measurements are typically performed on the qubits, extracting classical information from the quantum system. The results of these measurements are probabilistic, meaning that they occur with certain probabil- ities. Therefore, a quantum circuit defines a distribution by specifying how these probabilities are distributed among the different possible measurement outcomes.
For example, given a quantum circuit U, the initial state (0). and the output sampling bit-string 01 ajag...a, E {0, 1)" the modeled probability is p(x) Kz|U J0) 12. The Google team used [1] the following noise model for the noisy samples produced by the Sycamore circuits,
N.(x) Φ + (1 -)2-"
(4)
where @ a fidelity parameter describing the quality of the sample, Po the probability distribution defined by the quantum circuit. The parameter á is estimated by follows,
II (1 c..) 9Еgn
II (1 gEGa
6g2)
II (1 eg), Q
(5)

---

where G1 is the set of single-qubit gate, 92 is the set of double-qubits gate, and Q1 is the set of qubits. Google set [1] cn 0.16%, Gg 0.62% and e = 3.8%.
XEB [2]: XEB stands for "Linear Cross-Entropy Benchmarking" and a metric used to assess the performance of quantum processors. It quantifies the fidelity of quantum computer's output compared to a classical reference model. Mathematically. XEB is defined as:
1
(x)
2"
Σ ZED
p(x) - 1,
6
M
where we have collection of M random bit-strings D [ TM}. If random quantum circuit runs without errors, we have FXEB = 1. If bit-strings are sampled from classical uniform distribution, we have FXEB 0.
By evaluating the XEB metric, researchers can assess the performance of quantum circuits. It pro- vides a quantitative measure of how well quantum computer reproduces the expected outcomes and is a valuable tool for evaluating and improving quantum computing technologies.
3.3 Classical Simulation Using Tensor Networks
The classical simulation task aims to efficiently calculate U U ... in (7) classical computers, as marked red in Fig. 3. It is mathematically a combinatorial optimization problem tensor network contraction ordering (TNCO).
Iwb) = Um x ... x U, (o)
classical simulation task
Tensor contraction operation: Given two tensors X' [XXXX and y E RKXMXN their con- traction results 4D tensor E B where
K
Zij.m
Xr..kk
(8)
which takes IJKMN multiplications. Using the tensor diagram representation, as in Fig. 4, a node denotes tensor and an edge denotes tensor contraction operation.
Tensor network representation: Leaving the input quantum bits and the final measurement out, the quantum circuit U Um. U₁ can be represented as a tensor network. Specifically, single-qubit gate R represented as a matrix (a 2D tensor), while a double-qubit quantum gate U is represented 4D tensor. Using tensor diagrams, quantum circuit in Fig. 3 is mapped into tensor network in Fig. 4. Note that the final result the classical simulation task is an 8D tensor shown Fig. 4. We provide more details about the tensor representations in Appendix B.
Simulation efficiency: We would like to illustrate that the contraction ordering for calculating U = Un ... U₁ is critical to the simulation efficiency. Different orderings may result in sig- nificant difference in the number multiplications. The difference may be hundreds orders quantum circuits with a large number of qubits and many cycles [34]. For simple example in Fig. 4, two contraction orderings (blue and red) for the same quantum eircuit involve 976 and 5056 multiplications, respectively.
4 Tensor Network Contraction Ordering Using Reinforcement Learning
First, we formulate the classical simulation task as a combinatorial optimization problem, i.c., tensor network contraction order (TNCO). Then, we adopt K-spin Ising model whose Hamiltonian is used as the loss function to train a policy network via curriculum learning. We also provide a pool of implementation tricks to improve training efficiency and boost performance.
4.1 Problem Formulation
Tensor network contraction order (TNCO). Given tensor network G (V, F), a contraction path P (pt.)..,pp-))) E Fg, and corresponding sequence of graphs ... Gn-1), the
5

---

3,3
7,9
1,11
R
R
R
U
4,4
8,1
13,2
11,13
U
5,7
9,5
R
14,6
12,14
R
U
6,8
10,10
2,12
Figure 4: For the quantum cirtuis in Fig. 3, two contraction orderings (blue and red) involove 976 and 5056 multiplications, respectively.
goal is to find path P with minimum cost,
P" ('( argmin
Σ Rg (et)
s.t. P .n- Es,
where E, is the of remaining edges between tensors, G. is the tensor network af- ter 1-th tensor contraction and the reward Rg is defined as the number of multiplica- tions for the tensor contraction along edge ex. This formulation is consistent with [34].
Consider an example in Fig. graph (1,2,3, 4), Ej
G1 has Vi (k,j, m, i, ss, w = M, As- suming that the first contraction operation on index m GG. tensors and 4 are contracted into tensor 34 a com- putation cost of IJMS multiplications. Then, the graph is updated to G2 with (k, ij. s), w =
1
34
3
12
G.
G2
Ga
V22 = (1, 34), IJ.)). Assuming the second traction operation is on index l in G2, tensor 1 and 2 are contracted into tensor 12 at a computation cost of SKTJ multiplications. The updated graph G3 has V (12,34), E3 (sij), {sij)- Finally, tensors 12 and 34 are contracted into real number using SIJ multiplications. The total number of multiplications is IJMS + SKIJ 1JJ+++ SIJ.
Figure 5: An example of tensor network contraction.
4.2 The Proposed Reinforcement Learning Method
First, we reformulate (9) into an Ising model. Then, we extend K-spin Ising model, which allows training a policy network using the curriculum learning method [5].
TNCO using Ising model: The Ising model of TNCO problem uses 222 spins Fu.j. where u denotes the tensor and denotes its order in the TNCO path. We use J to denote the cost introduced by the tensor contraction between и and v for the i-th order, i.e., the number of multiplications. The energy of the original TNCO problem has three terms. The first term requires each tensor appear at least once in the TNCO path. The second term requires there are exactly two tensors selected at order j along a path. The third term measures the contraction cost at order j. These are encoded in the following Hamiltonian:
N-1
N Σ
N a=l Σ
(1x) = Σ
Sy Fu,
(10)
As shown for example, in Fig. 6. it be computed by H(x) (2 21,1 E2,1 D3,1
x2,1)² (2 21,2 22,2 23,22 2 (2 L1 22 wi (1, ())4),112220 + w/ (1, 22,21,1122222
+
in (223))m2,133.11 w/ 4)222,1444111111 + wi (3, 4) 1) + wa (2,11,1
+ (2(11, (1,21,,111150 2) +
(2, (22 w3 1

---

Iteration: k
k+1
order
order
order
3
2
tensor
tensoo
censo
Figure 6: Illustration of TNCO problem: conventional Ising model vs. our K-spin Ising model.
TNCO using K-spin Ising model: Our solution takes K steps to solve the TNCO problem, i.e.. which can be encoded in the following Hamiltonian,
x²
H Σ
H
ΣΣ
Σ
J ,
(11)
LEVE
where Ji,-..s =k== KK wwl 12) (2) is) w(i ix).
Policy network: We build the policy network with a transformer neural network. We represent the tensor network with an undirected graph, demonstrated as symmetric matrix M. If i-th and j-th tensors are connected with shared index then M, = d. The policy network takes M input and generates the contraction ordering P = (e1, "C,,,.. 1n- where 6, E E, is the connected edge between u-th and i-th tensors Cu
Several challenges for using RL algorithms include the wide dynamic range, huge search space, slow convergence due to Heavy-tailed cost distribution, incorporating existing solvers, and credit assignment problem [34]. The sampling bottleneck is major challenge in training RL agents [32]. Next, in Section 4.3, we develop pool of implementation tricks overcome these challenges, including massively parallel gym-ennironnent, learning to optimize, dual replay buffers, swarm intelligence, and curriculum learning.
Challenges:
4.3 Implementation Tricks
Massively parallel gym-environment. The sampling bottleneck is a major challenge in training RL agents. We implement massively parallel gym-environment to accelerate the sampling efficiency. We initialize N independent environments and generate and forward different tensor network con- traction paths to these environments at each step. Each environment performs the contraction oper- ations according to the given path, yielding the next state and calculating the number of multiplica- tions as rewards. We store these transitions, including the tensor networks and their corresponding multiplications, in the replay buffer.
Learn to optimize. We adopt the learn-to- learntt-ooptimize (L20) strategy [10] for training an RL agent. Instead of using conventional optimizers like Adam or Nestrov, we employ long-short-term mem- ory (LSTM) network. It takes the current gradient and loss value inputs and produces gradients. This L20 strategy effectively accelerates the convergence process, particularly in the presence of a Heavy-tailed cost distribution. This approach enables faster and more efficient training by dynami- cally adapting the parameter updates based on the current gradient and loss value.
Dual replay buffers. We maintain two replay buffers, one saves the tensor contraction ordering from the agent in an iterative rollout manner, and the other saves high-quality tensor contraction orders so far. The reason for two replay buffers is that want to avoid high-quality tensor contraction ordering being deleted by the rule of first in, first out (FIFO) due to the GPU memory limit. We the Hamiltonian value measure the quality. We sample from two replay buffers alternatively during the training process, which stabilizes the RL training.
Swarm intelligence. We train multiple optimizers since different optimizer is easily stuck into local optima [7, 39]. To mitigate the impact, different optimizer shares knowledge with others reg- ularly, thus escaping local optima and approaching the global optima. Specifically, during training,
7

---

optimizers keep the top-N solutions while optimizers share them. Rather than directly using the orderings for training, the optimizer will manually add some noise the shared orders search for the solution in the neighhorhood of that local optimum.
Curriculum learning. We apply curriculum learning method [5, 17, 62]. With acceptable performance on small-scale tensor network contraction problems, the optimizer has successfully escaped multiple local optima. The optimizer may approach the global optima when varying the studied tensor networks from small to large scale. We have two tricks for measuring the problem scale: the number of iterations and parameter freezing strategies.
The first trick varying the number of iterations, K. A large K may result in insufficient optimization, while in contrast, small-scale optimization problems corresponding to a small may experience over-fitting. Therefore, starting with an initial large K, we gradually decrease K during the training process.
The second trick is masking network parameters, i.e., freezing different ratios of param- eters. Specifically, at first, we randomly freeze 90% of the parameters and optimize the rest 10% parameters, which is easy to optimize. Then, we gradually decrease the ratio of masked parameters. It can help the optimizer escape the local minima.
Note that the two curriculum learning tricks can be integrated with the swarm intelligence trick to boost performance.
5 Performance Evaluation and Benchmark
We present experimental results on both synthetic tensor networks and Google's Sycamore circuits. Further, we investigate the scalability performance of our method for large-scale quantum circuits that have similar structure to Google's 's Sycamore circuits.
5.1 Baseline Methods
We provide the following five baselines for verification purposes:
OE-GREEDY [13]: an open-source solver from OPT-Einsum library, which uses the greedy search algorithm to find the optimal tensor contraction path.
CTG-Greedy [18]: open-source solver from the Cotengra library, which uses the greedy search algorithm to find the optimal tensor contraction path.
CTG-Kahypar [18]: A robust graph partitioning- based solver from the Cotengra library, which achieves state-of-the-an results in many tensor networks.
ACQDP [21, 22]: Using the stem optimization, including the hypergraph partitioning, local
optimization, and dynamic slicing, to search the optima tensor contraction order?.
RL-TNCO [34]: an RL approach combined with graph neural networks to search the opti- mal tensor contraction order, which is one of the Mate-of-the-arr methods for the classical simulation of quantum circuits?.
Experiment setup. We conducted all experiments on a DGX-2 server with NVIDIA A100 GPUs, each of which consists of 48 GB device memory. There are two Intel(R) Xeon(R) Gold 5118 CPUs. Each of CPUs has 12 cores @2.30GHz supporting 24 hardware threads. There are 128 GB DDR4 memories on the server. We set the learning rate 7) as 3 x 10-3 with a decay factor 0.9 (reduce the learning rate every 1, 000 epochs), and the total number of epochs is 1, 000, 000. We set K = 3 for our K-spin Ising model. The number of parallel environments 2048, while the large-seale cases use 1024. When the number of tensors increases, the GPU memory consumption increases; therefore, we use 1024 environments for large-scale tensor networks.
It is not generalizable to all tensor networks. We only add ACQDP's performance in Sycamore circuits. "hh codes are public, so took results from Table of the paper [34].
8

---

5.2 Verification on Synthetic Tensor Networks
Synthetic tensor-train networks. We tested tensor-train networks with tensors from 400 up to 2000. From Table our RL-Ising method achieves speedup of 2 over the CTG-Kahypar method for tensor size from 400 to 1000. Both DE-Greedy and CTG-Greedy cannot work for the problem instances with over 1, 500 tensors, while the RL-Ising method exhibits good scalability, outperform- ing CTG-Kahypar by speedup of 1.73x for tensor sizes 1500 and 2000.
Table Results on synthetic tensor-train networks.
Tensors
400
600
800
1000
1500
2000
Scale
x 10
X x10080
X x10241
x x10301
x10451
X x10602
OE-Greedy [13]
17.22
27.67
4.44
3.83
CTG-Greedy [18]
10.33
16.60
2.67
4.28
CTG-Kahypar [18]
10.23
16.60
4.67
4.26
14.12
4.57
RL--Ising
5.16
8.28
2.14
2.14
7.01
2.29
Synthetic random tensor networks. generate random tensor networks with the same settings in [34]. Random networks were generated with varying tensors, namely 25, 50, 75, and 100. The connections in these networks were assigned an average degree 3, with the degrees of individual nodes independently drawn from the set {2, 3, 4, 5, 6}. We report the mean and median results of random instances for each size. As given in Table 2, our RL-Ising method outperforms all baselines with speedup of 3.98x.
Table 2: Number of multiplications for synthetic random tensor networks.
Qbits
25
50
75
100
Scale
x10
X 10
x10
x10
OE-Greedy [13]
53.7/27.7
75.4/11.3
104/4.5
5296/26.4
CTG-Greedy [18]
40.3/20.3
12.8/ 4.2
8.3/0.9
27.9/
2.2
CTG-Kahypar [18]
46.4/24.8
13.4/ 4.3
4.1/0.4
54.2/ 1.2
RL-TNCO [34]
13.1/12.5
3.2/ 1.8
1.2/0.2
5.5/ 1.8
RL-Ising
12.5/11.4
2.5/ 1.5
0.7/0.1
4.9/ 1.1
5.3 Benchmark Performance Google's Sycamore Circuits
Google's Sycamore circuits [3] has 53 qubits and m cycles, m = 12, 14, 16, 18, 20. As shown in Fig. 3, each cycle has layer of random single-qubit gates and one layer of two-qubit gates. In different cycles, the two-qubit gates are applied to different pairs of quantum qubits.
The results are summarized in Table 3. Specifically, the RL-Ising method outperforms the RL-TNCO method with a speedup 2.84x. With cycles, our RL-Ising method has speedup of 4.64x over the CTG-Kahypar method, 5.40x over the ACQDP method, and
Table 3: Number of multiplications for Google's Sycamore circuits.
Cycles
m = 12
m = 14
m 16
m = 18
m = 20
Scale
10
X 10
X 10
X x6016
x x1018
OF-Greedy [13]
6.23 x 10"
4.77 x 10'
7.74 x 10T2
6.21 x 10TH
9.59 x 10"
CTG- CTG-Greedy [18]
1.16 107
1.91
107
1.42 10a0
3.71 x 107
4.19 107
CTG-Kahype [18]
2.55 1
1.41
102
1.03 104
48.0
6.69
ACQDP [21]
1.09 103
71
1.15 104
25.8
6.65
RL-TNCO [34]
5.44
7.39
3.49
RL-Ising
1.31
1.07
9.27
12.98
1.23

---

2.42x over the RL-TNCO method. The estimated running time of ACQDP is 21 days [21,
22]; therefore, the estimated running time of our RL-Ising method 21/5.40 3.9 days.
We provide a comparison of different methods in Fig. 7. With an increasing number of cycles, the number of multiplications in the log scale increases linearly, which corresponds to expo- nential trends (as illustrated Fig. 1). Both RL methods, the RL-TNCO method and our RL-Ising method, are much lower than existing heuristic methods. Furthermore, the RL-Ising method is lower than that of the RI.-TNCO method, with an improvement of 0.384 orders.
27.5
OE-Greedy
CTG Gready
Number of multiplic ations (logte)
25.0
Kahypor
RLTNNCO RListing
22.5
20.0
17.3
15.0
12.5
Take-home message I: The "quantum supremacy" claim still lacks an unequivocal first demonstration, since Google's 's announce- ment [3] was under serious questions due to the debatable estimate of 10, 000 years' running time for the classical simulation task on the Summit supercomputer.
10.0
12
16
20
Number of cycles Sycamore circuit
Figure 7: Number of multiplications (in log-scale) by different methods.
Table 4: Number of multiplications large-scale quantum circuits.
Qbits Scale
100
200
300
400
500
x10
X x1023
x 10
X x1028
x1033
OE- Or-Gryy [13]
8.31 109
2.26 x 109
6.90 10
7.55 x 10
4.34 X 109
CTG-Greedy [18]
3.34 x 108
4.24 x 108
5.37 x 109
4.49 x 109
1.38 X 10
CTG-Kahypar [18]
3.96 x 10a
2.31 X 10
3.51 x 103
6,25 x 102
4.18 x 102
RL-Issng
3.85
5.12
2.27
3.98
1.84
5.4
Scale Up to Large-Scale Quantum Circuits
Scalability is very important for evaluating future hardware developments. We scale up to large- scale quantum circuits with 100, 200, 300, 400 and 500 qubits, respectively. There are 20 cycles for each generated quantum circuit, taking a similar structure as in Fig. 3. As given in Table 4, our RL-Ising method surpasses all the baseline methods with 227 speedups. With increasing the scale of quantum circuits, the performance gap between our method and the runner-up method CTG-Kahypar becomes large. It further shows the strong scalability of our RL.-Ising method.
Therefore, we believe that reinforcement learning methods have great potential for finding the best performance curve.
Take-home message II: To validate "empirical quantum supremaey" for future quantum hardware developments, the machine learning community is expected to play critical role in maintaining publicly trustable benchmark performances with open-souree source training datasets..
Conclusion and Future work
In this paper, we have demonstrated the potential of reinforcement learning approach for the clas- sical simulation of quantum circuits. We reported an estimated simulation time of less than 5 days, which is remarkable speedup of 4.62x over the of-te-of-the-ar heuristic methods. We conduct ex- tensive experiments to evaluate the classical simulation performance. Moreover, we have developed parallel gym environments and benchmarks, which are openly accessible open-source resources.
However, the provided environments may not cover all types of classical simulation tasks. The best performance is an open question, which asks for continuing efforts. This project may initiate long- term collaborations from the AI/ML and quantum physics communities to maintain reference curves for validating the "empirical quantum supremacy" and drive continuing hardware advancements.
10

---

References
[1] Jack Y Araz and Michael Spannowsky. Classical versus quantum: comparing tensor network- based quantum circuits Ihc data. arXiv preprint WXXi::2202.10471, 2022.
[2] F Arute, K Arya, R Babbush, et al. Supplementary information for "quantum supremacy using a programmable superconducting processor," Nat. Int. Wkly. J. Sci, 574:505-505, 2020.
[3] Frank Arute, Kunal Arya, Ryan Babbush, Dave Bacon, Joseph C Bardin, Rami Barends, Rupak Biswas, Sergio Boixo, Fernando GSL Brandao, David A Buell, et al. Quantum supremacy using a programmable superconducting processor. Nature, 574(7779:505-510, 2019.
[4] Reinhard Bauer, Tobias Columbus, Ignaz Rutter, and Dorothea Wagner. Search-space size in contraction hierarchies. Theoretical Computer Science, 645: 12-127, 2016.
[5] Yoshua Bengio. Jérôme Louradour, Ronan Collobert, and Jason Weston. Curriculum learning. In International Conference on Machine Learning (ICML), pages 41 2009.
[6] Jacob Biamonte, Peter Wittek, Nicola Pancotti, Patrick Rebentrost, Nathan Wiebe, and Seth Lloyd. Quantum machine learning. Nature, (49(7671): 2017.
[7] Christian Blum and Xiaodong Li. Swarm intelligence in optimization. Swarm intelligence: introduction and applications, pages 43-85. Springer, 2008.
[8] Sima E Borujeni, Saideep Nannapaneni, Nam H Nguyen, Elizabeth C Behrman, and James E Steck. Quantum circuit representation of bayesian networks. Expert Systems with Applications, 176:114766 2021.
[9] Lukas Burgholzer, Alexander Ploier, and Robert Wille. Simulation paths for quantum circuit simulation with decision diagrams. IEEE Transactions on Computer-Aided Design of Inte- grated Circuits and Systems, 2022.
[10] Tianlong Chen, Xiaohan Chen, Wuyang Chen, Zhangyang Wang, Howard Heaton, Jialin Liu, and Wotao Yin. Learning to optimize: A primer and benchmark. The Journal of Machine Learning Research, 23(1):8522-862) 2022.
[11] Barry A Cipra. An introduction the Ising model. The American Mathematical Monthly, 94(10):937-959, 1987.
[12] Nadav Cohen, Or Sharir, and Amnon Shashua. On the expressive power of deep learning: A tensor analysis. In Conference on Learning Theory, pages 698-728. PMLR, 2016.
[13] Daniel, Johnnie Gray, et al. einsuun-- python package for optimizing contraction order for einsum-like expressions. Journal of Open Source Software, 3(26):753, 2018.
[14] Glen Evenbly and Guifre Vidal. Quantum criticality with the multi-scale entanglement renor- malization ansatz. Strongly correlated systems: numerical methods, pages 99-130, 2013.
[15] Ivan Glasser, Ryan Sweke, Nicola Pancotti, Jens Eisert, and J Ignacio Cirac. Expressive power of tensor-network factorizations for probabilistic modeling. In Thirty-third Conference Neural Information Processing Systems (NeurIPS), 2019.
[16] Li-Hua Gong, Ling-Zhi Xiang, Si-Hang Liu, and Nan-Run Zhou. Born machine model based on matrix product state quantum circuit. Physica A: Statistical Mechanics and its Applications, 593: 26907, 2022.
[17] Kelam Goutam, S Balasubramanian, Darshan Gera, and R Raghunatha Sarma. Layerout: Freezing layers in deep neural networks. SN Computer Science, 1(5):295, 2020.
[18] Johnnie Gray and Stefanos Kourtis. Hyper-optimized tensor network contraction. Quantum, 5:410, 2021.
[19] Diego Guala, Shaoming Zhang, Esther Cruz, Carlos A Riofrío, Johannes Klepsch, and Juan Miguel Arrazola. Practical overview of image classification with tensor-network quantum circuits. Scientific Reports, 13(1):4427, 2023.

---

[20] Reza Haghshenas, Johnnie Gray, Andrew C Potter, and Garnet Kin-Lic Chan. Variational power of quantum circuit tensor networks. Physical Review X. 12(1):011047, 2022.
[21] Cupjin Huang, Fang Zhang, Michael Newman, Junjie Cai, Xun Gao, Zhengxiong Tian, Junyin Wu, Haihong Xu, Huanjun Yu, Bo Yuan, et al. Classical simulation of quantum supremacy circuits. arXiv preprint arXiv:2005.0677
2020.
[22] Cupjin Huang, Fang Zhang, Michael Newman, Xiaotong Ni, Dawei Ding, Junjie Cai, Xun Gao, Tenghui Wang, Feng Wu, Gengyan Zhang, et al. Efficient parallelization of tensor network contraction for simulating quantum computation. Nature Computational Science, 199):778-
587, 2021.
[23] William Huggins, Piyush Patil, Bradley Mitchell, K Birgitta Whaley, and Miles Stoudenmire. Towards quantum machine learning with tensor networks. Quantum Science and technology, 4(2):024001, 2019.
[24] Cameron Ibrahim, Danylo Lykov, Zichang He, Yuri Alexeev, and Ilya Safro. Constructing optimal contraction trees for tensor network quantum circuit simulation. In IEEE High Perfor- mance Extreme Computing Conference (HPEC), pages 1-8. IEEE, 2022.
[25] Elias Khalil, Hanjun Dai, Yuyu Zhang, Bistra Dilkina, and Le Song. Learning combinatorial optimization algorithms over graphs. Advances in Neural Information Processing Systems, 30, 2017.
[26] Hiroaki Kitano. Artificial intelligence win the nobel prize and beyond: Creating the engine for scientific discovery. AI Magazine, 37(1):39 2016.
[27] Yasuhiro Kondo, Ryuhei Mori, and Ramis Movassagh. Quantum supremacy and hardness of estimating output probabilities of quantum circuits. In 2021 IEEE 62nd Annual Symposium Foundations of Computer Science (FOCS), pages 1296-1307. IEEE, 2022.
[28] Yoav Levine, David Yakira, Nadav Cohen, and Amnon Shashua. Deep learning and quantum entanglement: Fundamental connections with implications to network design. In International Conference on Learning Representations, 2018
[29] Xiao- Yang Liu, Zechu Li, Shixun Wu, and Xiaodong Wang. Stationary deep reinforcement learning with quantum k-spin hamiltonian regularization. In ICLR 2023 Workshop on Physics for Machine Learning, 2023.
[30] IA Luchnikov, AV Berezutskii, and AK Fedorov. Simulating quantum circuits using the multi- scale entanglement renormalization ansatz. arXiv preprini arXiv:2/ 14046, 2021.
[31] Ian MacCormack, Alexey Galda, and Adam L Lyon. Simulating large peps tensor networks on small quantum devices. arXiv preprint arXiv:2110.00
2021.
[32] Viktor Makoviychuk, Lukasz. Wawrzyniak, Yunrong Guo, Michelle Lu, Kier Storey, Miles Macklin, David Hoeller, Nikita Rudin, Arthur Allshire, Ankur Handa, et al. Isaac Gym: High performance GPU based physics simulation for robot learning. In Thirty-fifth Conference on Neural Information Processing Systems Datasets and Benchmarks Track (Round 2).
[33] Nina Mazyavkina, Sergey Sviridov, Sergei Ivanov, and Evgeny Burnaev, Reinforcement leamn ing for combinatorial optimization: A survey. Computers & Operations Research, 105400, 2021.
[34] Eli Meirom, Haggai Maron, Shie Mannor, and Gal Chechik. Optimizing tensor network con- traction using reinforcement learning. In International Conference on Machine Learning, pages 15278-15292. PMLR, 2022.
[35] A Morvan, B Villalonga, X Mi, S Mandra, A Bengtsson, PV Klimov, Z Chen, S Hong. Erickson, IK Drozdov, et al. Phase transition in random circuit sampling. arXiv preprint
arXiv:2304.1110 11119, 2023.
[36] Valentin Murg. Frank Verstraete, Örs Legeza, and Reinhard M Noack. Simulating strongly correlated quantum systems with tree tensor networks. Physical Review B, 82(20))205105, 2010.
12

---

[37] Naoki Nakatani and Garnet Kin-Lic Chan. Efficient tree tensor network states (ttns) for quan- tum chemistry: Generalizations of the density matrix renormalization group algorithm. The Journal of chemical physics, 138(13):1341) 13, 2013.
[38] John C Napp, Rolando L La Placa, Alexander M Dalzell, Fernando GSL Brandao, and Aram W Harrow. Efficient classical simulation random shallow 2d quantum circuits. Physical Review X, 12(2):021021, 2022.
[39] Anand Nayyar, Dac-Nhuong Le, and Nhu Gia Nguyen. Advances in swarm intelligence for optimizing problems in computer science. CRC press, 2018.
[40] Román Orús and Guifré Vidal. Simulation of two-dimensional quantum systems on an in- finite lattice revisited: Comerr transfer matrix for tensor contraction. Physical Review B, 80(9):094403, 2009.
[41] Román Orús. A practical introduction to tensor networks: Matrix product states and projected entangled pair states. Annals of Physics, 349:117-158, 2014.
[42] Feng Pan and Pan Zhang. Simulation of quantum circuits using the big-batch tensor network method. Physical Review Letters, 123(3)00, 2022.
[43] Yuchen Pang, Tianyi Hao, Annika Dugad, Yiqing Zhou, and Edgar Solomonik. Efficient 2d tensor network simulation quantum systems. International Conference for High Perfor- mance Computing, Networking, Storage and Analysis, pages 1-14. IEEE, 2020.
[44] Dheeraj Peddireddy, Vipul Bansal, Zubin Jacob, and Vancet Aggarwal. Tensor ring parametrized variational quantum circuits for large scale quantum machine learning. arXiv preprint 1eXiv:2201.08877 2022.
[45] Alejandro Perdomo-Ortiz, Manuel Rudolph, Jing Chen, Jacob Miller, and Atithi Acharya. Decomposition of matrix product states into shallow quantum eircuits. 2022.
[46] John Preskill. Quantum computing and the entanglement frontier. Bulletin of the American Physical Society, 58, 2013.
[47] Shi-Ju Ran. Encoding of matrix product states into quantum circuits of one-and two-qubit gates. Physical Review A, 101(3):032300, 2020.
[48] Shi-Ju Ran, Emanuele Tirrito, Cheng Peng. Xi Chen, Gang Su, and Macicj Lewenstein. Review of tensor network contraction approaches. arXiv preprint arXiv:1706 7720019111,, 2017.
[49] Norbert Schuch, Ignacio Cirac, and David Pérez-García. Peps ground states: Degeneracy and topology. Annals of Physics. 325 (25(11))21332119 2010.
[50] Philipp Seitz, Ismael Medina, Esther Cruz, Qunsheng Huang, and Christian B Mendl. Simu- lating quantum circuits using tree tensor networks. arXiv preprint arXiv:2206.0/ 01000, 2022.
[51] Raja Selvarajan, Manas Sajjan, and Sabre Kais. Variational quantum circuits to prepare low energy symmetry states. Symmetry, 14(3):457, 2022.
[52] Y.-Y. Shi, L.-M. Duan, and G. Vidal. Classical simulation of quantum many-body systems with tree tensor network. Phys. Rev, A. 74:022320, Aug 2006.
[53] Andrea Skolik, Michele Cattelan, Sheir Yarkoni, Thomas Bäck, and Vedran Dunjko. Equivari- ant quantum circuits for learning on weighted graphs. Quantum Information, 9(1):47, 2023.
[54] Edwin Stoudenmire and David Schwab. Supervised learning with tensor networks. Advances in Neural Information Processing Systems, 29, 2016.
[55] Luca Tagliacozzo, Glen Evenbly, and Guifré Vidal. Simulation of two-dimensional quantum systems using tree tensor network that exploits the entropic area law. Physical Review B, 80(23):235127, 2009.
[56) Kristan Temme and Frank Verstraete. Stochastic matrix product states. Phys. Rev. Lett. 105:210502, May 2010.
13

---

[57] Bram Vanhecke, Jeanne Colbois, Laurens Vanderstraeten, Frank Verstraete, and Frédéric Mila. Solving frustrated Ising models using tensor networks. Physical Review Research, 3(1):013 2021.
[58] F. Verstraete and J. I. Cirac. Valence-bond states for quantum computation. Phys. Rev. A. 70:060302, Dec 2004.
[59] Zhi- Yuan Wei, Daniel Malz, and J Ignacio Cirac. Sequential generation of projected entangled- pair states. Physical Review Letters, 128(1):010007, 2022.
[60] Yiqing Zhou, E Miles Stoudenmire. and Xavier Waintal. What limits the simulation of quantum computers? Physical Review X, 10(4):041038 2020.
[61] Qingling Zhu, Sirui Cao, Fusheng Chen, Ming- Ming-Cheng Chen, Xiawei Chen, Tung- Hsun Chung, Hui Deng. Yajie Du, Daojin Fan, Ming Gong, al. Quantum computational advantage 60-qubit 24-cycle random circuit sampling. Science bulletin, 67(3):240-244 2022.
[62] Qingqing Zhu, Xiuying Chen, Pengfei Wu, JunFei Liu, and Dongyan Zhao. Combining cur- riculum learning and knowledge distillation for dialogue generation. In Findings of the Asso- ciation for Computational Linguistics: EMNLP 2021, pages 1284-1295, 2021.
14

---

Appendix A Classical simulation task
It should be needed sample one million samples, achieving the required XEB.
Fig. 3 shows a corresponding circuit example. It has n = qubits for the initial state (tb)) and 2 cycles. The sampling process using the quantum circuit is computed as follows,
1. In the first cycle, random selected single-qubit quantum gates are first applied to all the four qubits of Iooo): Then, the double-qubit quantum gates are applied R. vooo,, and
R.
(002,33 respectively, and obtain |x>1);
2. In the second cycle, random selected single-qubit quantum gates are first applied to all the four qubits of 14/);; Then, the double-qubit quantum gates are applied R |1)),,2 and obtain (22);;
3. Next, random selected single-qubit quantum gates are first applied to all the four qubits of 122), and obtain R2 1 = 0, 2,3;
4. Last, we have a measurement O'ipigia (i1d2igi4 (va). The sampled output is a bit-string 011g
Algorithm Random circuit sampling
I: Input: initial state (e0o), number of cycles m, single-quhit quantum gate (vX, VY, WW) double-qubit quantum gate U,,
2: for 1..... m do
3: for j = 0, .... -
4:
R + randomly select from (vX, YY, WW),
5:
1 R. 1
6:
end for
7:
for j (i 1)%2. .... n/2 -
8:
p compute the manipulate quantum bit index 2j 1)%2
9:
(()) p.t1
U (1 p
10: end for
11: end for
12: for j O,..., n
13: Ri randomly select from (VX,VY, vW).
14:
[Mm+1), R (m)l
15: end for
16: Obtain measurement by 0r162-...n = (i1 ba..da (pm+1),
17: Output: a bit-string Oliyg......
Quantum circuits: There have been many quantum circuits proposed as follows,
Sycamore quantum [3]: consists of 53 qubits and 20 cycles. For the Boson sampling problem, it only needs 200 seconds to finish this task, while it needs 10, 000 years for classical simulation.
Jiu Zhang [60]: It consists of 74 qubits. For the Gaussian Boson Sampling problem, it can use 200s to finish up million times compared with classical simulations.
Zuchongzhi [61]: It has 60 qubits with the number of 24. The achieved sampling task is about 6 orders of magnitude more difficult than that of Sycamore in the classic simulation.
Appendix B Data Generators and Reinforcement Learning Environments.
B.1 Tensor Network Representations
We use the unidirectional graph to represent the tensor network. Specifically, for given tensor net- work with n tensors, we use symmetric X matrix M to represent the dimensional relationships between tensors, which named the dimension matrix. Specifically, if the tensors with index and j are connected with shared dimension dg, then set Mij M, dij. otherwise, it is
15

---

A
S
D
A
CD
D
D
k
m
k
B
K
B
K
C
B
C
D
m
m
G1
G2
M1
M2
Figure 8: Example of the tensor network contraction environment.
set as O. We also denote connection matrix C, where Cij = Cji indicates the connection between the i-th tensor and j-th tensor.
B.2 Tensor Network Contraction
We employ tensor network contraction the underlying computational framework in quantum circuit simulation. Given a specific tensor network structure and specified contraction order, the environment is designed provide the number of multiplications required during the tensor traction process.
Specifically, illustrated in Figure 8, consider tensor network comprising 4 tensors connected grid structure. When performing a tensor contraction between tensors C' and D, it is necessary to compute the number of multiplications involved. From the unidirectional graph representation, tensor has dimensions M x tensor has dimensions S x I x M, and a shared edge with dimension M exists.
To contract tensors and D along the edge with dimension M, the number of multiplications can be computed as (MJ)x(SIMM) This expression takes into account the multiplication of the dimensions M MJ from tensor C and SIM from tensor D, divided by the shared dimension M.
essential to update the unidirectional graph representation. The contracted tensor formed by the contraction of C and D retains independent edge with di- mension M (M33 M31 M M11 M). The connected edges between the contracted tensor (C or D) and other tensors determined by multiplying the original edge dimensions be- tween them (M23 = M24 = M32 = M42 = IJ). This update to the unidirectional graph ensures
Upon completing the contraction,
accuracy and reflects the changes resulting from the contraction step.
By incorporating the update of the unidirectional graph and computing the number of multiplica- tions, we complete the current simulation step.
B.3 Verification
Unified representation: We use a tuple consisting the contracted tensor indices to represent tensor contraction order. The resulting tensor is labeled as new index. As shown for example in Fig. 5, we first write down (3, 4) for the first contraction operation. We label the generated tensor 34 as 5. Next. we use (1,2) to label the second tensor contraction operation and to label the resulting tensor 12. Last, we contract the tensor 12 and 34, where we use (5, 6) to represent the contraction record. Thus, we have the contraction order {33 4), (1, (12,
Calculating the number of multiplications: Given the tensor contraction order, we will compute the number of involved multiplications. In Fig. 5, using different optimizers, we can get a specific contraction order, like ((3, 4), (1, 2), (12, We first contract the 3-th and 4-th tensor, of which the number of multiplication is TJMS. Then, for the contraction order (1,2), 2), we have the num- ber of multiplication as SKTJ. Last, for the contraction order (12, 34), we have the number of multiplication SIJ.
16

---

(a) Tensor-train network.
(b) Tensor-ring network.
Figure Illustration of the tensor train and tensor ring network.
B.4 Datasets for Different Tensor Networks
In this section, will first introduce the data structure used describe the relationships between different tensor nodes. Then, we will demonstrate the generation process of the dataset for different tensor networks.
Data Structure:
The tensor network can be represented as an undirected graph G = {V, E, w) and is amenable to be stored using the adjacent table, which can be defined as follows (C-format),
class Tensor {
int V; // number of tensor nodes int E; number edges Queue [] adj; // adjacent nodes for each node
TensorNetwork int V) { // init the graph this
this this adj = new [V]: for (i 0; i < V; i++) {
this adj = new Queue [];
12
13
void AddEdge (int v. int w) { // add the edges if (w > v) v. w w. v; this adj[vl enqueee (w); this E++;
14
16
17
18
void Build (...): differs in different tensor networks
Specifically, we use V and E to save the number of tensor nodes and edges, respectively. The variable adj is queue with flexible length, where adjij] is also queue to save the adjacent tensor nodes. Given the total number of tensor nodes V, T Tensor N Nelwork(V) is used to initialize the undirected graph, where each tensor node assigned an empty queue. The addedge( invoked to add the connected relationship between the connected tensor nodes v and We make simplified assumption that only the larger index w can be added to the adjacent queue v. Different tensor network differs in the implementation of the Build(...) function, which invokes the addelge(:," depending on the specified tensor network structure.
Fansor-Train Network or Matrix Product States: The matrix product state (MPS) [41, 56] or tensor-train (TT) represents tensor as a chain-like contraction of third-order tensors with the head and tail as matrices. The tensor diagram of MPS/TT is shown in Fig. 9()).
MPS has been widely used in modeling quantum circuits such [47, 16, 45). In the (uild(...) function, for each tensor node i, we need to use the AddEdge i + 1) to add the i + 1-th node to the adjacent lists of i-th node, i < [V| 1. We can set up different number of tensor nodes N to generate the dataset for MPS tensor network.
void TensorNetwork Build (f // Build for MPS for (i 0: i this V-1; i++) this AddEdge(i. i+1);

---

The generation code for the tensor-train network is saved in https://github... com/ Tensor ring network:
py. The tensor ring (TR) represents a high-order (or high-dimensional) tensor by sequence of 3rd-order tensors that are multiplied circularly, whose tensor diagram notation be represented in Fig. 9()).
The tensor-ring network has been utilized to simulate the quantum circuit in [44].
The main difference between the tensor ring and the MPS tensor network is that the first and last tensor nodes in tensor ring network are also connected. Thus, only minor modification of MPS generation can be applied generate the tensor ring network.
void TensorNetwork: :: Build Of Build for tree tensor for (int i = 0; i < this V; i++) this AddEdge(i. (i+1)%this.V),
The generation code for the tensor-ring network is saved in https://github com/ http://hw.......ataatatto/ata/aa
Tree Tensor Network: Tree tensor network (TTN) [37, 52, 55] or Hierarchical Tucker (HT) is a generalization of MPS that encodes tree entanglement structure. The diagram notation of TTN can be represented in Fig. 10.
Figure 10: Tree tensor network.
Tree tensor network has been used model the quantum [24, 50), and quantum chemistry [36, 37]. Tree tensor network is fully binary tree structure, which the number of tensor nodes depends on the height. we reload the initialization function and write the build function as follows,
:: TensorNetwork Networ pow (2 H) 1; this this adj = new Queue[V];
iint H) { // init the graph
this H
this
for (i= = 0; i < V; i++) {
this. adjaad[i]] = new Queue [];
void TensorNeiwork: :: Build () Build for tensor ring this (O 1); this AddEdge(O,, 2); for (h 1; h this .H; h++){
for (v (2, h-2); pow (2, h-1) v++){
12
this AddEdge (v. 2v): this AddEdge 2v+1):
13
16
The generation code for the tree tensor network is saved in https://github.ce com/ py.
PEPS Network: The PEPS (projected entangled pair state) tensor network [49, 58] generalizes MPS from one-dimensional network network arbitrary graph, whose tensor diagram notation can be represented in Fig. 11.
Some work applics the PEPS network to quantum circuits [43] and quantum systems [40, 31].
18

---

Figure 11: PEPS tensor network.
The generation code for the PEPS network is saved in https://github... com/ py.
MERA Network: The MERA (Multiscale Entanglement Renormalization Ansatz) [14] tensor net- work colleagues refinement of the MPS and PEPS. It has hierarchical structure, with layers of tensors representing increasingly coarse- coarse-grained degrees freedom, which can be represented in Fig. 12.
Figure 12: MERA tensor network.
Some work applies the MERA network to quantum circuits [1, 20, 103.
The generation code for the MERA tensor network is saved in https://github. com/ py-
Google's Sycamore Circuits: Some work has put efforts into transforming the Sycamore circuits into tensor representations. The provided data is usually organized into the adjacent graph structure, while the indices the i-th row are the indices connected tensors to i-the tensor. The tensor network representation of the Sycamore circuits corresponds to complicated net structure. To map Sycamore circuits into the tensor network environment, we need to iteratively read each line of the given Sycamore file and fill it up with corresponding dimension information.
The generation code for the Sycamore circuit is saved in https://github. com/ wttp////aaaunniitttteteeeeeeeeee hateee/ainaatttt/////aaaeea
B.5 Environment
We provide the gym-environment for the tensor network contraction problem in our clas- sical simulation of quantum circuits. The code provided in https://github.cm com/ sor network and https: / //te::///tttttt com/Xiaol hetm/XiaaYaangiien Vin. haagg//rraPPaaaaAAgggaaaantntner main/r1/sycamore env py for Sycamore circuits.
py for tensor-train ten-
19

---

Specifically, the gym- rem--eirronment for the tensor network contraction problem in our classical sim- ulation of quantum circuits is designed follows,
Init/Restart: initialize the states of environments, including the number of nodes, the num- ber of edges, etc.
Given the tensor network contraction order, compute the number of involved multi- plications as the reward. The rewards are represented in log scale.
Step:
The implementations can be found in init(), and get_log 10 multiple functions of our enapy.
B.6 Hiigh-Performance Reinforcement Learning for TNCO
Mapping onto the K-spin Ising Model: We use the K-spin Ising model to formulate the TNCO problem follows,
N-1 H(x)=
N Wi
2
Σ
2
Tusi
Jus
1
uml
ual cml
(12)
H(w ..... x*)
H
Σ
E
Jos..
k=
liVe
where we denote the N(N 1) spin as Zu.j. the tensor and j denotes its order in the TNCO path.
We use the variational annealing methods to solve the K-spin Ising model problem of TNCO. Specif- ically, we minimize the KI. divergence between the transition distribution of x to x' with the target Boltzmann distribution as follows,
go + x') plx - x')
DEL (p)
Σ ( +z')In In
Σ g0 + x In go + x¹)
(13)
Lo (x - (
- (x))) + In Zn,
T
where T is the temperature, qo is the distribution of TNCO path x' parameterized by 0,
p(a'(x) (x) the transition distribution of Boltzmann distribution p(x'(x) exp( H(=²)
Z
Σ (H((')<((a)) e mie During the learning process, we gradually anneal the temperature to op-
timize (13).
Parallel data sampling: We use RNN parameterized by 0 as the policy network to model the transition probability qe(x x'). We imput the K-spin representation of tensor contraction order, (I1, ...K). sequentially from left to right, and compute the transition probability as follows,
1. Randomly initialize the hidden variable h1;
2. Input æı and h1 to the RNN, and output the next hidden variable h2 and a transition prob- ability (o()));
3. Input 22 and ha the RNN, and output the next hidden variable ha and transition prob- ability ( + x2);
4.
5. Input Fı and hg to the RNN, and output the next hidden variable hx+1 and transition probability (0( + xx).
Then, by sampling the tensor contraction ordering trajectories, (I1 x2, ..., FK), we can optimize (13) to train the RNN. The sampling process can be batched onto multiprocess to achieve high- performance data sampling, thus alleviating the performance bottleneck of reinforcement learning training.
20

---

Parallel training: We initialize multiple optimizers in parallel to learn to optimal tensor contraction order. Specifically, the t-th iteration
1. We parallelly sample N tensor contraction ordering from the TNCO environment and store them the reply buffer.
2. For the optimizer i -th, we first freeze Pt.s parameters, < Ps < then sample data from replay buffer, and compute the loss function (13) with the temperature Ti, independently.
3. For i-th optimizer, we compute the gradient and use LSTM to learn to optimize the param- eter.
We vary the parameter masked ratio and temperature 7 by increasing the number of iterations and initialized all the parameters differently achieve swarm intelligence integrated with the curriculum learning.
Appendix C Accessibility, Usage, License, and Maintenance
Accessibility: All the code, dataset, and tensor network contraction orderings, including the Sycamore circuits, can be found in our open source project https: https:///ithub.... com/ hitYaagL.L--iiii///////aaanttnn
without personal request.
Dataset generation: We generate the classical simulation of quantum circuits synthetically using /wt.eeeeeee/aaaaaaatttteae
For example, we run /etpasttttt/ms/pppeggeeeetttttee -y to generate quantum circuits based on the tensor train, where V in code controls the number of nodes in generated data.
Code organization: We implement the baseline methods using Opt-einsum and Cotengra to search for the tensor network contraction orderings. The codes for calling these solvers are wttp///LLADunntmiirutttet
provided in https://g/ https://githbb httbbttttbb../// com/ wwm//iio baseline. We provide two methods to solve each type of quantum circuit, like tensor train-based quantum circuits.
Usage: To rum the baseline methods, execute "python cotengra.py" or "python opt_einsum.py" where the variable n is the number of nodes. To generate the dataset, please execute "python gener- ate.py", where the variable V in the central part the number of tensor nodes.
License: MIT License.
Maintenance: On GitHub, we keep updating our codes, merging pull requests, and fixing bugs and issues. We welcome contributions from community members and researchers.
21


Reviews:
[{"review_id": "PtYUFHGutQ", "reviewer": "Reviewer_K8x3", "summary": "", "questions": "", "limitations": "In its current state, I would rate this paper between a 4 to 6. However, given the issues with writing quality and the significant gaps concerning Variational Quantum Eigensolver (VQE) and Variational Quantum Classifier (VQC) baselines, the draft requires substantial revisions. For instance, Section 1's walkthrough should highlight different quantum simulation-based RL solutions and more precisely define RL in the title to reflect the actual benchmarking efforts.", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "Overall the code quality is reasonable. Although some connection to exiting compatible connection to `cuQuantum`, `Qiskit`, `Pennylane` are missing", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": ""}, {"review_id": "1GCwJ2UoXu", "reviewer": "Reviewer_m3Yv", "summary": "", "questions": "", "limitations": "The paper has not presented a significant discussion of the limitations of the proposed approach. For example, under what conditions should this benchmark be relied upon to declare quantum supremacy (or not)? ", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "(+) The idea of using a Hamiltonian derived from the K-spin Ising model for solving the TNCO problem is interesting, and shows experimental promise based on the results of this paper.\n(+) Experimentally, the code associated with the paper can simulate Google's Sycamore circuits in 5 days, while the earlier state-of-the-art takes 10 days. This is an impressive experimental performance.\n(+) Five different baseline implementations are provided together with the proposed approach. \n(+) The implementation details, such as L2O strategy, masking network parameters, and separate saving of high-quality tensor contractions orders in the replay buffers, are clearly discussed in the paper.", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": ""}, {"review_id": "OiQ0cwnjlK", "reviewer": "Reviewer_YFU3", "summary": "", "questions": "", "limitations": "Very limited information were provided on the dataset, while the paper was submitted to a Datasets Track.", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "The paper explains the basic concepts of quantum circuits in a clear manner for non-quantum experts.\nThe training algorithm and reinforcement learning approach was clearly articulated, and has lead to strong results compared to other methods on both the proposed synthetic dataset and on Google's Sycamore circuits.", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": ""}, {"review_id": "g3bc5FeqmC", "reviewer": "Reviewer_m3Yr", "summary": "", "questions": "", "limitations": "N/A", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "The concept of quantum supremacy is indeed a significant and contemporary topic in the field of quantum computing. If true quantum advantage is achieved, it could herald a new era of computation, potentially revolutionizing fields such as cryptography, optimization, and material science. The proposed benchmark could provide a more transparent and trustable way to validate empirical quantum supremacy. \n\nThis work proposes a reinforcement learning method that achieves a remarkable speedup over SOTA heuristic methods, which demonstrates potential of RL for the classical simulation of quantum circuits. In addition, five baselines are provided in benchmark, which offers a solid, meaningful reference for subsequent research in this field. Furthermore, a pool of implementation tricks is also provided to overcome challenges for developing RL algorithms.\n\nOverall, I believe the contribution of this work is significant for its research topic, solid experiments, and well-organized GitHub repo.\n", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": ""}]

Author rebuttal:

Meta-review: The work sets out to challenge the "quantum supremacy" claim put forward by Google in 2019 (NB: the claim has been found to be bogus before by others), demonstrating that the by Google projected 10K years claim to reproduce the results classically, can essentially be done in 4 days, essentially rejecting the supremacy claim. To avoid future vendor-driven advertisement campaigns of wrongful nature, the authors publish code and data (i.e., scripts to produce data) that would help to check future circuits against supremacy claims to avoid misleading statements of the nature reported by Google in Nature!

A fruitful discussion among authors and reviewers led to improvements being applied to the paper throughout the process.

It is our impression that there still remains some confusion as to the data provided by the authors, i.e., binary vs. text; whether the data is provided at all or only scripts to generate the data. We'd like to encourage the authors to make these aspects crystal clear and if in doubt provide samples (or the entire data) of the data generated by the scripts such that others would be able to reproduce the results without much guess work involved. Thank you.
Decision: Accept (Poster)