CN115759270B

CN115759270B - Efficient simulation method based on quantum circuit

Info

Publication number: CN115759270B
Application number: CN202211299951.4A
Authority: CN
Inventors: 沙行勉; 宋玉红; 诸葛晴凤
Original assignee: East China Normal University
Current assignee: East China Normal University
Priority date: 2022-10-24
Filing date: 2022-10-24
Publication date: 2024-07-09
Anticipated expiration: 2042-10-24
Also published as: CN115759270A

Abstract

The invention discloses a quantum circuit-based efficient simulation method, which comprises three steps. First, the invention collects and summarizes the quantum logic gates commonly used in quantum circuits, and establishes a logic gate name-symbol-unitary matrix mapping table, wherein each logic gate uses a single symbol representation. Then, the quantum logic gates at the same time are symbolized according to the target quantum circuit, and all the logic gates at each time are sequentially represented as a symbolized sequence. When in use, all the quantum gate unitary matrices can be obtained by looking up the mapping table. Finally, for the target quantum circuit, initializing quantum state probability amplitude of quantum bits corresponding to the quantum circuit. And then calculating the quantum state probability amplitude after the quantum circuit execution at each moment according to the symbolized quantum gate sequence, so as to realize quantum calculation simulation. The invention can greatly reduce the storage space required by quantum computation simulation and improve the simulation efficiency.

Description

Efficient simulation method based on quantum circuit

Technical Field

The invention belongs to the technical field of quantum computing, and particularly relates to a high-efficiency simulation method based on a quantum circuit.

Background

The electrical automation design (Electronics Automation Design, EDA) plays an important role in designing circuits and systems, while simulation is an important part of the EDA field. With the development of noisy medium-scale quantum machines, quantum computing has shown substantial superiority as an emerging technology in specific applications, quantum computers exhibiting strong computational potential due to the superposition and entanglement properties of the quanta. However, physical quantum computers are quite expensive and the number of qubits that can be supported by them is limited. In order to better understand the quantum behavior and to fully verify the quantum algorithm designed by utilizing the quantum characteristics, quantum circuits are important to simulate in advance on a classical computer. Meanwhile, the quantum circuit simulation can better promote research and popularization in the field of quantum computing.

However, as the number of simulated qubits increases, the storage space required for full state simulation of quanta grows exponentially. Because quantum-wire simulation of full states relies on tensor product operations and matrix-vector product operations, both operations produce an exponential level of operation matrix and state vector. Given a quantum system with n qubits, the operation matrix size obtained by tensor product operation is 2 ⁿ×2ⁿ. Meanwhile, a quantum system of n qubits has a state vector of size 2 ⁿ.

In quantum circuit simulation, each qubit is a two-state quantum system. One qubit may be represented by states |ψ > = α|0> +β|1>, which means that each qubit is in a superimposed state of states |0> and |1 >. In addition, the state of each qubit can also be vectorSuch a column vector is referred to as a state vector V. In generalization, for an n-bit quantum wire, the state vector size at each instant is 2 ⁿ. Each element in the state vector is referred to as a probability amplitude, each probability amplitude being a complex representation. Existing quantum algorithms typically derive the desired state vector by designing the quantum circuit to transform by adding quantum gates to the qubits, all of which are represented in the form of unitary matrices. In a quantum system with n qubits, if a quantum gate G is added to the p-th qubit, in order to calculate the next state vector, an operation matrix of 2 ⁿ×2ⁿ needs to be obtained by tensor product operation. The calculation formula of the operation matrix M is as follows: wherein, Representing tensor product operation, I represents a 2 x 2 invariant matrix, and G represents a 2 x 2 quantum gate matrix. After the operation matrix M is calculated, the updated state vector V _next is obtained by operation matrix-state vector product operation, that is, V _next =m·v. Thus, in conventional full-state quantum wire simulation, each step requires the storage of an operation matrix of size 2 ⁿ×2ⁿ and a state vector of size 2 ⁿ.

Each element in the operation matrix and the state vector uses a double-precision complex representation, so the operation matrix requires 2 ²ⁿ⁺⁴ bytes of memory space and the state vector requires 2 ⁿ⁺⁴ bytes to store. As the number of qubits increases, the memory boundary is soon broken and the memory will undoubtedly become a performance bottleneck. Based on this, much work has relied on large memory supercomputers to alleviate memory bottlenecks. But even the most advanced Fugaku supercomputers with 4.9PB can only simulate a maximum of 24 qubits without any optimization. In addition, conventional matrix-vector product operations require about N ² additions and multiplications, where n=2 ⁿ, N is the number of qubits. In conventional matrix-vector product operations, the regularity in the tensor product operation is not fully explored, which results in the tensor product operation being performed entirely with high computational overhead, and each element of the operation matrix and state vector product operations participating in the operation. When the number of equivalent sub-bits increases, the computational overhead required to complete the quantum circuit simulation will be quite large.

Disclosure of Invention

In order to overcome the problems of the prior art, the invention aims to provide a high-efficiency simulation method based on quantum circuits, which firstly establishes a logic gate name-symbol-unitary matrix mapping table related to common quantum logic gates. The logic gates employed therein are symbolized by traversing the quantum circuits, the quantum gates at each instant being symbolized as a sequence. Then, the probability amplitude of the quantum bit in the quantum circuit is updated by using the sequence, and the efficient simulation of the quantum circuit is completed. The invention can obviously reduce the exponential storage space required by matrix and vector storage and can obviously improve the quantum computing simulation efficiency.

The specific technical scheme for realizing the aim of the invention is as follows:

a quantum-circuit-based efficient simulation method, the method comprising:

step 1, establishing a mapping table: collecting and summarizing quantum logic gates commonly used in a quantum circuit, representing each quantum gate by a symbol, and constructing a logic gate name-symbol-unitary matrix mapping table;

Step 2, symbolizing a quantum circuit: given a target quantum circuit, symbolizing a quantum gate used on each time circuit, and symbolizing the quantum gate added at one moment into a sequence representation in sequence;

Step3, quantum computing simulation: initializing quantum state probability amplitude of corresponding quantum bits in a quantum circuit, and calculating the quantum state probability amplitude in the quantum circuit after quantum gate action by using a symbolized quantum gate sequence.

The constructing a mapping table of the logic gate name-symbol-unitary matrix specifically comprises:

summarizing the names, symbolized representations and corresponding unitary matrices of the quantum logic gates in a mapping table by collecting the quantum logic gates used in a common quantum algorithm and a quantum circuit, wherein the quantum logic gates comprise single-bit logic gates and double-bit logic gates; each logic gate is represented using a separate symbol; for a single bit logic gate, the corresponding unitary matrix size is 2×2; for a two-bit logic gate, the corresponding unitary matrix size is 4×4.

The quantum logic gates used in the common quantum algorithm and the quantum circuit comprise a Hadamard gate, a Pauli-X gate, a Pauli-Y gate, a Pauli-Z gate, an S gate, a T gate, an RX gate, a RY gate, an RZ gate, a Controlled-X gate, a Controlled-Y gate, a Controlled-Z gate and a Swap gate; for quantum wires without any gates, an Identity gate is added to the implied wire.

The given target quantum circuit symbolizes a quantum gate used on each quantum circuit, and specifically comprises the following steps:

for each quantum circuit, the quantum states are converted by using k quantum gates at the same time; according to the name of each logic gate on the quantum circuit, each quantum logic gate is represented by a corresponding symbol in a table by searching a logic gate name-symbol-unitary matrix mapping table; by symbolization, quantum gates at a moment are sequentially converted into a sequence of quantum gates; for a target quantum wire, there are many moments; by symbolizing the representation, one quantum wire is represented as a plurality of symbolized sequences;

When symbolizing representation is carried out, a quantum gate added on a quantum line at one moment is traversed, and when a logic gate encountered is a single-bit gate, the logic gate is directly converted into symbolizing representation by searching a mapping table; when a two-bit logic gate is encountered, the two bits corresponding to the logic gate must be consecutive, symbolized by looking up a mapping table.

The initializing quantum state probability amplitude of the corresponding quantum bit in the quantum circuit specifically comprises the following steps:

When carrying out quantum computation simulation, not each quantum bit carries out state conversion independently, but all the quantum bits carry out operation together; for a given quantum circuit with n quantum bits, all the states of the quantum bits form a state vector through tensor product operation, and the size of the state vector is 2 ⁿ; for the target quantum wire, each qubit is initialized to qubit 0, so the initialized state vector is a column vector of size 2 ⁿ with only the first element being 1.

The method for calculating the quantum state probability amplitude in the quantum circuit after quantum gate action by using the symbolized quantum gate sequence specifically comprises the following steps:

Traversing the symbolized quantum gate sequence, assuming that k quantum gate symbols are total, and finding out a corresponding quantum gate unitary matrix through each symbol searching mapping table; splitting the corresponding state vector into a plurality of sub-vectors according to the size of the unitary matrix of the quantum gate; in the sequence of symbolized gates, for a quantum gate of size 2 x 2 of the first unitary matrix, the state vector is split into two equal sub-vectors; for a quantum gate of unitary matrix size 4 x 4, the state vector is split into four equal sub-vectors;

then, respectively calculating the products of k-1 quantum gates and each sub-vector; after each sub-vector is updated, performing matrix-vector product operation on the first unitary matrix and the sub-vector, wherein the product of each value and the sub-vector is vector scalar operation;

Thus, one symbolized quantum gate sequence completes the update of a state vector, namely the update of a quantum bit probability amplitude; and respectively carrying out the same operation on the quantum gate sequences at other moments to complete quantum circuit simulation.

The method provided by the invention can accommodate more quantum bit numbers. Meanwhile, due to the efficient calculation mode in the quantum calculation simulation, tensor product operation with high calculation cost is saved, a large amount of repeated data calculation is saved in the optimized operation, and the quantum circuit simulation efficiency is remarkably improved.

Drawings

FIG. 1 is a schematic flow chart of the present invention;

FIG. 2 is a schematic diagram of tensor product operation rule and operation matrix-state vector product representation after sub-matrix and sub-vector division;

fig. 3 is a scaling-based operation matrix-state vector product operation method.

Detailed Description

The invention is further illustrated by the following examples in conjunction with the accompanying drawings:

the invention comprises the following steps:

step 1, establishing a mapping table: first, a logic gate name-symbol-unitary matrix mapping table is constructed by collecting and summarizing the quantum logic gates commonly used in quantum circuits. The mapping table contains three parts of contents, namely the name of a quantum logic gate, and the quantum logic gate used in the circuit can be obtained through a quantum circuit. Second, each quantum logic gate uses a specific symbology for symbolizing the quantum circuit. Third, for each quantum logic gate, there is a unitary matrix. For a single-bit quantum gate, the unitary matrix size is 2×2; for a two-bit quantum gate, the unitary matrix size is 4×4.

The reason that the logical gate name-symbol-unitary matrix mapping table works well is that: by creating a mapping table, a unique symbolized representation of the corresponding logic gate can be quickly found when symbolizing the quantum wire. And when the calculation module carries out quantum calculation simulation update state vector, the corresponding unitary matrix can be quickly obtained by searching the mapping table. By the representation mode of the mapping table, the large matrix space required to be stored in the calculation is saved, and the quick access of the mapping table can also improve the simulation efficiency.

Step 2, symbolizing a quantum circuit: for a given target quantum wire, the quantum gates added at each instant are symbolized as a sequence. Traversing each moment in the quantum circuit, and for each quantum gate in each moment, finding a corresponding symbol by searching a logic gate name-symbol-unitary matrix mapping table. The quantum gates that the symbolizing module can handle are single bit quantum gates or double bit quantum gates of consecutive bits. For quantum wires, there are many moments in time when gate operations change the probability amplitude of their qubits. Therefore, after the symbolization of the quantum wire, a plurality of symbolized quantum gate sequences can be obtained.

Quantum circuit symbolization works well for two reasons: first, through the symbolized representation of the quantum gate sequence, the operation matrix with the real size of 2 ⁿ×2ⁿ is not needed to be stored, only the symbolized quantum gate sequence and the corresponding quantum gate matrix mapping table are recorded, and a large amount of storage space is saved. Second, the symbolized gate matrix is used when the quantum computation simulation updates the state vector, and the tensor product operation required in the quantum wire simulation is omitted entirely, thus saving a lot of computation that was originally required to generate an operation matrix of size 2 ⁿ×2ⁿ.

Step 3, quantum computing simulation: the invention provides a scaling-based matrix-vector product operation method for completing calculation of a quantum bit probability amplitude by exploring a tensor product operation rule. For full-state quantum computation simulations, the update of the quantum bit probability magnitudes depends on the product operation of the operation matrix and the state vector. The operation matrix is a matrix of 2 ⁿ×2ⁿ obtained by tensor product operation of k small matrices of 2×2 or 4×4. For the operation matrix obtained by tensor product operation, each submatrix has strong similarity. Dividing the operation matrix of 2 ⁿ×2ⁿ into equal sub-matrices according to the size of the first gate matrix will find that each sub-matrix can be represented as a weight value a multiplied by a matrix a. For each sub-matrix, their weights are the values at the corresponding positions of the first quantum gate, respectively, and all the a matrices are identical. Similarly, after dividing matrix a into equal sub-matrices according to the size of the second quantum gate matrix, it was found that each sub-matrix could also be represented as a weight multiplied by an identical matrix. The weight value is just the value at the corresponding position of the second quantum gate matrix. According to such a rule, the operation matrix can be divided all the time. The product of the operation matrix and the state vector can be converted into a product operation of the sub-matrix and the sub-vector, in which there are a large number of repeated computations. Therefore, the invention only performs one calculation for the same calculation part, and then performs data result scaling adjustment by using the corresponding coefficient weight. Correspondingly, due to the strong regularity of matrix-vector product operation, the operation matrix of 2 ⁿ×2ⁿ can be omitted completely, and the corresponding unitary matrix can be found to realize quantum computation simulation only by using a signed gate sequence. The optimization method provided by the invention can reduce the operation number of multiplication and addition to about Nlog ₂ N times, wherein N= ⁿ, and N is the number of quantum bits.

The reason why the data scaling-based matrix-vector product operation method works well is: and each sub-square matrix is expressed in a form of a.A by fully utilizing the regularity of the tensor product operation result. And meanwhile, the state vector is subjected to sub-vector division, so that the representation of each part has certain regularity. The operation matrix-state vector product operation based on scaling enables only partial operations in the matrix-vector product operation to be executed, and the operation times are remarkably reduced. Compared with the traditional N ² times of operation times, the method can achieveThe performance of the double is improved. Assuming that the number of qubits n=32, then n=2 ³². For the original matrix-vector product operation, the required operand is 2 ⁶⁴, and the operand required by the scaling-based quantum computing simulation method provided by the invention is 2 ³⁷, so that the operand reduction of 2 ²⁷ times is achieved.

Examples

Establishing a mapping table: by collecting and summarizing the quantum logic gates commonly used in quantum circuits, a logic gate name-symbol-unitary matrix mapping table is established. The logic gates commonly used in the quantum circuits summarized in this embodiment include, but are not limited to, hadamard gates, pauli-X gates, pauli-Y gates, pauli-Z gates, S gates, T gates, RX gates, RY gates, RZ gates, controlled-X gates, controlled-Y gates, controlled-Z gates, and Swap gates. For quantum wires without any gates, an Identity gate is implicitly added to the wire. Given one symbolized identifier per quantum logic gate, the symbolized identifier of the logic gate is shown in step 1 of fig. 1. The symbolization mark of the Hadamard gate is H; the symbols of Pauli-X gate, pauli-Y gate and Pauli-Z gate are X, Y, Z respectively; the symbols of the S gate and the T gate are S, T respectively; RX gate, RY gate, RZ gate marks are A, B, C respectively; the Controlled-X gate, controlled-Y gate, and Controlled-Z gate symbolized representations are D, E, F, respectively; the identity of the Swap gate is W; the Identity gate is identified as I.

Symbolizing a quantum circuit: an example of a quantum circuit containing a total of 5 qubits is given in step 2 of fig. 1. For a given target quantum circuit, two moments are included, and two symbolized sequences are finally generated through a symbolizing module. For the first moment, two Hadamard gates, one Pauli-X gate, one Pauli-Y gate and one Pauli-Z gate are added to 5 qubits respectively, and after quantum symbolization, the symbolization sequence formed at the moment is HHXYZ. For the second instant in the quantum circuit, three single bit quantum gates and one double bit quantum gate are added to 5 qubits, respectively. For the first three bits, an S gate, a T gate, an RX gate are added, respectively, and for the last two qubits a two-bit Controlled-X gate is added, so the quantum wire at the second instant is symbolized as STAD. After the symbolizing module, the entire quantum wire is represented using two symbolizing sequences HHXYZ and STAD.

Quantum computing simulation: for conventional matrix-vector product operations, each element in the result vector is obtained by performing a dot product operation on each row in the matrix and the state vector, and the number of operations is about N ². As shown in fig. 2 (a), the operation matrix M may be divided into equal-sized sub-square matrices according to the size of the first matrix in the tensor product operation. Correspondingly, as shown in fig. 2 (b), the state vector V is split into equal-sized sub-vectors according to the number of columns of the first matrix. According to the split mode of the submatrices and the subvectors, the calculation of the original operation matrix-state vector can be represented by the submatrices and the subvectors. Then the resulting state vector R can be expressed asIt is apparent that if matrix multiplications AV ₁ and AV ₂ are calculated in advance, a significant amount of overhead can be saved by scaling with the common factors a ₁、a₂、a₃ and a ₄ to obtain sub-vectors R ₁ and R ₂. Wherein, the matrix A is the result of all matrix tensor product operations after the first matrix. More generally, given k 2×2 matrices, let M ^(k) be the tensor product of k gate matrices and M ^(k-1) be the tensor product of the last k-1 gate matrices. The four elements of the first 2 x 2 gate matrix are labeled a ₁、a₂、a₃ and a ₄, respectively. Let V be the current state vector, V _upper and V _lower be the upper and lower halves of the V vector, respectively. The result vector R can be calculated with the following equation: It is apparent that the above formula can be recursively extended until k=0. When k=0, M ⁽⁰⁾V_s＝V_s, where V _s is a given sub-vector. Similarly, in the process of expansion, if the size of the encountered gate matrix is 4×4, the state vector is split into 4 equal parts, and the corresponding state vector calculation formula is: Wherein T ₁、T₂、T₃、T₄ represents M ^(k-1)V_quarter1、M^(k-1)V_quarter2、M^(k-1)V_quarter3、M^(k-1)V_quarter4, respectively, wherein M ^(k ^-1) represents the tensor product operation result of the k-1 gate vectors at the back, and V _quarter1、V_quarter2、V_quarter3 and V _quarter4 represent the quadportional vectors of the state vector, respectively. By recursively continuing the finding that the tensor product M ^(k) is actually not really calculated, only the value of each position of each quantum gate matrix needs to be known. Therefore, in step 2 of the present embodiment, only the quantum gate sequence is required to be symbolized and stored, and the tensor product operation is not required to be actually performed to obtain the operation matrix with the size of 2 ⁿ×2ⁿ. Thus, for an optimized scaling-based operation matrix-state vector product operation, the matrix size in given quantum gate number k, signed quantum gate sequence G _k, and current state vector V, G _k is 2x 2. The step of completing the updating of a state vector is as follows (as shown in fig. 3):

(1) It is determined whether k is equal to 0. If k=0, then the state vector V is returned directly; if k+.0, then the next operation is continued;

(2) The product of the k-1 quantum gates and the upper half of the state vector after calculation is calculated, namely M ^(k-1)V_upper;

(3) The product of k-1 quantum gates and the lower half of the state vector after calculation is calculated, namely M ^(k-1)V_lower;

(4) Performing coefficient scaling on the results of the steps (2) and (3) by using a ₁、a₂ respectively, namely calculating a ₁M^(k-1)V_upper+a₂M^(k-1)V_lower;

(5) Performing coefficient scaling on the results of the steps (2) and (3) by using a ₃、a₄ respectively, namely calculating a ₃M^(k-1)V_upper+a₄M^(k-1)V_lower;

(6) The results of the steps (4) and (5) are respectively the upper half submatrix and the lower half submatrix in the result vector R, so that the connection of the two submatrices is the final result state vector. When the size of the unitary quantum gate matrix is 2×2 and 4×4 mixed, the method of solving the final state vector is similar to the above steps.

According to the description, the high-efficiency simulation method based on the quantum circuit is realized by three steps of building the mapping table, symbolizing the quantum circuit and simulating the quantum calculation. By constructing and storing the mapping table, the symbolization information corresponding to the quantum logic gate and the corresponding unitary matrix can be obtained quickly when needed. By symbolizing, the cost of a large-scale operation matrix required in the quantum computing simulation can be saved, and the storage and calculation cost in the quantum computing simulation can be remarkably reduced. The method provided by the invention can accommodate more qubits under the same calculation capacity. Meanwhile, due to the efficient calculation mode in the quantum calculation simulation, tensor product operation with high calculation cost is saved, a large amount of repeated data calculation is saved in the optimized operation, and the quantum circuit simulation efficiency is remarkably improved.

Claims

1. A quantum-circuit-based efficient simulation method, the method comprising:

step 3, quantum computing simulation: initializing quantum state probability amplitude of corresponding quantum bits in a quantum circuit, and calculating the quantum state probability amplitude in the quantum circuit after quantum gate action by using a symbolized quantum gate sequence; wherein:

Summarizing the names, symbolized representations and corresponding unitary matrices of the quantum logic gates in a mapping table by collecting the quantum logic gates used in a common quantum algorithm and a quantum circuit, wherein the quantum logic gates comprise single-bit logic gates and double-bit logic gates; each logic gate is represented using a separate symbol; for a single bit logic gate, the corresponding unitary matrix size is 22; for a two-bit logic gate, the corresponding unitary matrix size is 44;

When carrying out quantum computation simulation, not each quantum bit carries out state conversion independently, but all the quantum bits carry out operation together; for a given quantum circuit with n quantum bits, all the states of the quantum bits form a state vector through tensor product operation, and the size of the state vector is 2 ⁿ; for the target quantum wire, each qubit is initialized to qubit 0, so the initialized state vector is a column vector of 2 ⁿ size with 1 as the first element only;

Traversing the symbolized quantum gate sequence, assuming that k quantum gate symbols are total, and finding out a corresponding quantum gate unitary matrix through each symbol searching mapping table; splitting the corresponding state vector into a plurality of sub-vectors according to the size of the unitary matrix of the quantum gate; in the sequence of symbolized gates, for a quantum gate of size 22 of the first unitary matrix, the state vector is split into two equal sub-vectors; for a quantum gate of unitary matrix size 44, the state vector is split into four equal sub-vectors;

2. The efficient quantum-circuit-based simulation method according to claim 1, wherein the quantum logic gates used in the common quantum algorithm and the quantum circuit include Hadamard gates, pauli-X gates, pauli-Y gates, pauli-Z gates, S gates, T gates, RX gates, RY gates, RZ gates, controlled-X gates, controlled-Y gates, controlled-Z gates, and Swap gates; for quantum wires without any gates, an Identity gate is added to the implied wire.

3. The efficient quantum-circuit-based simulation method according to claim 1, wherein the given target quantum circuit symbolizes the quantum gates used on each quantum circuit, in particular comprising: