Efficient parallelization of tensor network contraction for simulating quantum computation
Cupjin HuangFang ZhangMichael NewmanXiaotong NiDawei DingJunjie CaiXun GaoTenghui WangFeng WuGengyan ZhangHsiang‐Sheng KuZhengxiong TianJunyin WuHaihong XuHuanjun YuYuan BoMárió SzegedyYaoyun ShiHui‐Hai ZhaoChunqing DengJianxin Chen
51
Citation
55
Reference
10
Related Paper
Citation Trend
Abstract:
Abstract We develop an algorithmic framework for contracting tensor networks and demonstrate its power by classically simulating quantum computation of sizes previously deemed out of reach. Our main contribution, index slicing, is a method that efficiently parallelizes the contraction by breaking it down into much smaller and identically structured subtasks, which can then be executed in parallel without dependencies. We benchmark our algorithm on a class of random quantum circuits, achieving greater than 10 5 times acceleration over the original estimate of the simulation cost. We then demonstrate applications of the simulation framework for aiding the development of quantum algorithms and quantum error correction. As tensor networks are widely used in computational science, our simulation framework may find further applications.Keywords:
Benchmark (surveying)
Integer factorization
Quantum sort
Quantum circuit
Cite
Citations (0)
Quantum sort
Binary search algorithm
Cite
Citations (0)
The rapid progress of Computer Science and Engineering has been accompanied by a corresponding evaluation of computation, from classical computation to quantum computation. In classical computation, computer memory made up of bits, where each bit represents either a one or a zero. In quantum computation, there are some quantum mechanical phenomena, such as superposition and entanglement, to perform operations on data. Instead of using bits, quantum computation uses qubits (quantum bits). A single qubit can represent a one, a zero, or both at the same time, which is called superposition. Because of this ability, quantum computation can perform many tasks simultaneously, faster than classical computing.
Quantum sort
Cite
Citations (0)
In ensemble (or bulk) quantum computation, all computations are performed on an ensemble of computers rather than on a single computer. Measurements of qubits in an individual computer cannot be performed; instead, only expectation values (over the complete ensemble of computers) can be measured. As a result of this limitation on the model of computation, many algorithms cannot be processed directly on such computers, and must be modified, as the common strategy of delaying the measurements usually does not resolve this ensemble-measurement problem. Here we present several new strategies for resolving this problem. Based on these strategies we provide new versions of some of the most important quantum algorithms, versions that are suitable for implementing on ensemble quantum computers, e.g., on liquid NMR quantum computers. These algorithms are Shor’s factorization algorithm, Grover’s search algorithm (with several marked items), and an algorithm for quantum fault-tolerant computation. The first two algorithms are simply modified using a randomizing and a sorting strategies. For the last algorithm, we develop a classical-quantum hybrid strategy for removing measurements. We use it to present a novel quantum fault-tolerant scheme. More explicitly, we present schemes for fault-tolerant measurement-free implementation of Toffoli and $$\sigma_{z}^{1/4},$$ as these operations cannot be implemented “bitwise”, and their standard fault-tolerant implementations require measurement.
Quantum sort
Cite
Citations (12)
Cite
Citations (54)
The classical computer is restricted by Moore's law and other factors into the development bottleneck, quantum computer by virtue of its natural acceleration advantage into the field of vision. Quantum computing can achieve the acceleration effect compared with classical computing in many fields. In the field of integer decomposition, Shor algorithm can be solved in polynomial time, which breaks the security of RSA public key cryptosystem. However, the quantum bits (logn + 2, where n is the integer to be decomposed) required by Shor algorithm are difficult to be realized on today's quantum computers. Therefore, the hybrid quantum algorithm model of "classical + quantum (Grover algorithm)" is tried to realize the decomposition of large integers. In this paper, based on the previous hybrid quantum algorithm model, considering that the continuous accumulation of errors in the circuit of the quantum algorithm will lead to the failure of the algorithm as the depth increases, part of the circuit of the quantum algorithm oracle is optimized to reduce the consumption of the depth, quantum gate and quantum bit in the circuit of the quantum algorithm, so as to make it easier to run on the actual quantum computer. By running the optimized quantum circuit on the back end of the simulator of IBM Q quantum cloud platform, and trying to add thermal relaxation and depolarization noises to the circuit, the influence of different noises on the circuit under different iterations was explored.
Quantum circuit
Quantum sort
Cite
Citations (2)
Today quantum computer modeling thematic attracts many scientists as it is difficult to examine theoretically synthesized quantum algorithms. The main problem is whether a newly created algorithm would have an efficient implementation on the quantum computer or not. Mathematical core of quantum computations is quite discovered and allows quantum computer workflow simulation using classical computers. However simulating the workflow without optimizations causes performance decrease even for modeling of small quantum systems consisted of less than ten qubits. One of the methods for molding performance improvement is using quantum gates transform optimization algorithm. The algorithm uses heuristic optimizations to achieve better performance result. In this work flowcharts of optimization algorithm presented describing single qubit quantum gate transform and controlled gate transform. The results comparison of the classical mathematical approach for quantum computer simulation and using optimization algorithm shows that there is a significant performance improvement using quantum gates transform optimization algorithm.
Quantum Fourier transform
Flow chart
Quantum circuit
Quantum sort
Cite
Citations (0)
In the past few decades, there has been an acute problem of creating a quantum computer that uses quantum mechanical effects such as quantum parallelism and quantum entanglement for computations. Using these mechanisms, the quantum computer is able to solve some of the NP-class problems in polynomial time. A hardware approach to modeling quantum computing is considered, and a general mathematical model of the operation of a quantum computer is described, and a technique for mathematical modeling of quantum computing is presented. At the stage of consideration of the method of mathematical modeling, the most resource-intensive parts of the model are indicated. Also, issues related to data parallelization on a hardware accelerator, which are planned to be used to simulate quantum computing, were considered, and algorithms for the operation of this type of accelerator were given. A more compact data format is proposed, which is recommended to be used when implementing the accelerator. Using the proposed format, it is possible to reduce the resources spent on elementary arithmetic operations. The possibility of introducing an optimization algorithm to minimize the time spent in computations, as well as to speed up the execution of quantum algorithms in simulators of a quantum computer at the stage of the effect of quantum gates on the quantum register model, is proposed. The results of the optimization algorithm and its comparison with the classical mathematical approach using a software model are presented.
Quantum sort
Cite
Citations (1)
In this paper, we briefly review the basic concepts of quantum computation, entanglement, quantum cryptography and quantum fourier transform.  Quantum algorithms like Deutsch Jozsa, Shor’s  factorization and Grover’s data search are developed using fourier transform and quantum computation concepts to build quantum computers. Researchers are finding a way to build quantum computer that works more efficiently than classical computer. Among the standard well known algorithms in the field of quantum computation and communication we describe mathematically Deutsch Jozsa algorithm in detail for 2 and 3 qubits. Calculation of balanced and unbalanced states is shown in the mathematical description of the algorithm.
Quantum Fourier transform
Quantum sort
Cite
Citations (6)
Quantum computing simulation platform can simulate the computation results of the quantum computer based on traditional computers, which is an effective way to promote the development of quantum computing software, algorithms and hardware at the current immature stage of the real quantum computer. Since quantum computers have exponential calculation acceleration compared with traditional computers, the main problems in implementing quantum computing simulation on traditional computers are low computational efficiency and long time-consuming. A quantum circuit which is a sequence of quantum gates acting on a collection of qubits is the general quantum computing model. So by the means of quantum circuit optimization, the calculation speed can be significantly increased while keeping the calculation result unchanged. The existing empirical rules of quantum circuit optimization methods have limitations and there is no common and automatic quantum circuit optimization method. In this paper, a general and automatic quantum circuit optimization method based on the genetic algorithm is proposed, by which the equivalent optimal quantum circuit is obtained through a finite number of searching in a large searching space. This method is not limited by the hardware of the quantum computing simulation and the composition of the quantum circuit. The experimental results show that for the QFT algorithm of 29 qubits, the running time can be shortened by 41.4% and for the variational circuit of 6 qubits, the running time can be shortened by 18.8% compared with the state-of-the-art quantum circuit optimization method. So this method can improve the quantum computing simulation capability and operating efficiency and provide a rapid development way for quantum algorithms and applications.
Quantum circuit
Quantum sort
Quantum Fourier transform
One-way quantum computer
Cite
Citations (2)