Tensor network contraction is a fundamental operation for dealing with high-dimensional data, which is now widely used in classical simulations of quantum circuits. To improve the performance of simulations, existing methods are implemented by optimizing contraction methods. However, with the increasing size of the tensor network, the contraction efficiency of these methods is difficult to satisfy the performance requirements and also suffers from the challenge of contracting tensor tasks that exceed GPU memory. In this paper, we propose a high-performance chunking method for tensor contraction. By chunking the given tensor, we obtain small tensors or vectors assign the corresponding threads, and contract them in parallel through the GPU. Solving high-order tensor contractions using distributed tensor contraction methods. Compared to the Einsum, our method achieves an average speedup of 22.28×. We also have experiments for large-scale tensor network contractions and our method achieves an average speedup of 13.56× compared to Tensordot.
Tensor network contraction is a fundamental operation for dealing with high-dimensional data, which is now widely used in classical simulations of quantum circuits. To improve the performance of simulations, existing methods are implemented by optimizing contraction methods. However, with the increasing size of the tensor network, the contraction efficiency of these methods is difficult to satisfy the performance requirements and also suffers from the challenge of contracting tensor tasks that exceed GPU memory. In this paper, we propose a high-performance chunking method for tensor contraction. By chunking the given tensor, we obtain small tensors or vectors assign the corresponding threads, and contract them in parallel through the GPU. Solving high-order tensor contractions using distributed tensor contraction methods. Compared to the Einsum, our method achieves an average speedup of 22.28×. We also have experiments for large-scale tensor network contractions and our method achieves an average speedup of 13.56× compared to Tensordot.
Tensor network contraction is a powerful mathematical tool for dealing with complex systems and high-dimensional data, which is widely used in classical simulations of molecules and quantum circuits. To improve the performance of simulations, existing methods are implemented by searching the optimal contraction orderings for tensor networks. In particular, some reinforcement learning (RL) methods show a greater potential for solving. However, with the increasing scale of simulation, the number of tensors in the corresponding tensor network is huge, the existing RL methods suffer from sampling bottlenecks and slow solving speed, which make it difficult to efficiently solve for high-quality contraction orderings. In this paper, we design a massive parallel simulation environment for tensor network contraction ordering solving on a single GPU. We experimented with multiple numbers of parallel environments on the tensor-train network, and achieved the highest speedup when the number of environments was 26. We also have experimented on large-scale tensor-train networks and tree tensor networks, and compared to Kahypar and RL-Baseline, our method achieves average speedup of 8.96× and 7.48× on tensor-train networks, and 10.03× and 7.48× on tree tensor networks.
Exact tensor network contraction underpins quantum circuit simulation, quantum error correction, combinatorial optimization, and many-body dynamics. The dominant parallelization strategy, slicing, scales exponentially and incurs redundant computation. We present a multi-GPU framework that instead distributes intermediate tensors across devices with explicit communication, converting a fixed contraction path into a communication-efficient schedule via GEMM-oriented mode reordering and communication-aware mode distribution planning. Within a single DGX H100 node (8 GPUs, NVLink), distribution delivers 7--173× extra speedup beyond embarrassingly parallel slicing, capturing nearly all of the available compute reduction (87--101%) because NVLink's high bandwidth keeps communication small relative to compute. Scaling the same four workloads to 1024 H100 GPUs over InfiniBand, the extra speedup beyond slicing ranges from 42× to 67,869×, demonstrating that communication-aware distributed contraction far surpasses slicing-based scaling limits for frontier tensor networks.
Efficient simulation of quantum circuits has become indispensable with the rapid development of quantum hardware. The primary simulation methods are based on state vectors and tensor networks. As the number of qubits and quantum gates grows larger in current quantum devices, traditional state-vector-based quantum circuit simulation methods prove inadequate due to the overwhelming size of the Hilbert space and extensive entanglement. Consequently, brutal force tensor network simulation algorithms become the only viable solution in such scenarios. The two main challenges faced in tensor network simulation algorithms are optimal contraction path finding and efficient execution on modern computing devices, with the latter determining the actual efficiency. In this study, we investigate the optimization of such tensor network simulations on modern GPUs and propose general optimization strategies from two aspects: computational efficiency and accuracy. First, we propose to transform critical Einstein summation operations into GEMM operations, leveraging the specific features of tensor network simulations to amplify the efficiency of GPUs. Second, by analyzing the data characteristics of quantum circuits, we employ extended precision to ensure the accuracy of simulation results and mixed precision to fully exploit the potential of GPUs, resulting in faster and more precise simulations. Our numerical experiments demonstrate that our approach can achieve a 3.96× reduction in verification time for random quantum circuit samples in the 18-cycle case of Sycamore, with sustained performance exceeding 21 TFLOPS on one A100. This method can be easily extended to the 20-cycle case, maintaining the same performance, accelerating by 12.5× compared to the state-of-the-art CPU-based results and 4.48–6.78× compared to the state-of-the-art GPU-based results reported in the literature. Furthermore, the strategies presented in this article hold general applicability for accelerating problems that can be tackled by contracting tensor networks such as graphical models and combinatorial optimizations.
Tensors are a natural generalization of matrices, and tensor networks are a natural generalization of matrix products. Despite the simple definition of tensor networks, they are versatile enough to represent many different kinds of "products" that arise in various theoretical and practical problems. In particular, the powerful computational model of quantum computation can be defined almost entirely in terms of matrix products and tensor products, both of which are special cases of tensor networks. As such, (classical) algorithms for evaluating tensor networks have profound importance in the study of quantum computation. In this thesis, we design and implement a parallel algorithm for tensor network contraction. In addition to finding efficient contraction orders for a tensor network, we also dynamically slice it into multiple sub-tasks with lower space and time costs, in order to evaluate the tensor network in parallel. We refer to such an evaluation strategy as a contraction scheme for the tensor network. In addition, we introduce a local optimization procedure that improves the efficiency of the contraction schemes we find. We also investigate the applications of our parallel tensor network contraction algorithm in quantum computation. The most ready application is the simulation of random quantum supremacy circuits, where we benchmark our algorithm to demonstrate its advantage over other similar tensor network based simulators. Other applications we found include evaluating the energy function of a Quantum Approximate Optimization Algorithm (QAOA), and simulating surface codes under a realistic error model with crosstalk.
Abstract Quantum computing holds significant promise for solving complex problems, but simulating quantum circuits on classical computers remains essential due to the current limitations of quantum hardware. Efficient simulation is crucial for the development and validation of quantum algorithms and quantum computers. This paper explores and compares various strategies to leverage different levels of parallelism to accelerate the contraction of tensor networks representing large quantum circuits. We propose a new parallel multistage algorithm based on communities. The original tensor network is partitioned into several communities, which are then contracted in parallel. The pairs of tensors of the resulting network can be contracted in parallel using a GPU. We use the Girvan–Newman algorithm to obtain the communities and the contraction plans. We compare the new algorithm with two other parallelisation strategies: one based on contracting all the pairs of tensors in the GPU and another one that uses slicing to cut some indexes of the tensor network and then MPI processes to contract the resulting slices in parallel. The new parallel algorithm gets the best results with different well-known quantum circuits with a high degree of entanglement, including random quantum circuits. In conclusion, the results show that the main factor that limits the simulation is the space cost. However, the parallel multistage algorithm manages to reduce the cost of sequential simulation for circuits with a high number of qubits and allows simulating larger circuits.
Tensor networks represent the state-of-the-art in computational methods across many disciplines, including the classical simulation of quantum many-body systems and quantum circuits. Several applications of current interest give rise to tensor networks with irregular geometries. Finding the best possible contraction path for such networks is a central problem, with an exponential effect on computation time and memory footprint. In this work, we implement new randomized protocols that find very high quality contraction paths for arbitrary and large tensor networks. We test our methods on a variety of benchmarks, including the random quantum circuit instances recently implemented on Google quantum chips. We find that the paths obtained can be very close to optimal, and often many orders or magnitude better than the most established approaches. As different underlying geometries suit different methods, we also introduce a hyper-optimization approach, where both the method applied and its algorithmic parameters are tuned during the path finding. The increase in quality of contraction schemes found has significant practical implications for the simulation of quantum many-body systems and particularly for the benchmarking of new quantum chips. Concretely, we estimate a speed-up of over 10,000 × compared to the original expectation for the classical simulation of the Sycamore `supremacy' circuits.