CN110569979B - Logical-physical bit remapping method for noisy medium-sized quantum equipment - Google Patents

Abstract

The invention discloses a logic-physical bit remapping method for noisy medium-sized quantum equipment, aiming at the limitation of quantum hardware, in order to effectively execute a quantum program on the quantum equipment, the necessary remapping is completed by changing the order of quantum instructions and inserting SWAP operation, so that the quantum program is suitable for the limitation of the quantum equipment, and the execution cost of execution time, the number of quantum gates and the like is as low as possible.

Description

A logical-physical bit remapping method for noisy medium-sized quantum devices

technical field

The invention relates to the technical field of quantum computing, in particular to a logic-physical bit remapping method for noisy medium-sized quantum devices.

Background technique

Quantum computing is a device that uses quantum mechanical phenomena such as superposition and entanglement to perform calculations. It has been proven that quantum computing can solve some NP-hard problems in classical computers in quantum polynomial time. For example, Shor's algorithm can solve large prime factors and discrete logarithm problems in quantum polynomial time, making it possible to crack RSA public keys. .

In quantum computing, information is stored in qubits. Similar to classical bits, qubits also have states, which can be two ground states of |0> or |1>, or a linear combination of |0> and |1>, which is called a superposition state. For example, the state of a single qubit (that is, its wave function) |ψ> can be expressed as:

|ψ>=α|0>+β|1> (1)

α and β are complex numbers, satisfying |α| ² +|β| ² =1, so the single-qubit state can also be represented as a vector (α,β) ^T with dimension 2, and the modulo length of this vector is 1.

When multiple qubits are entangled, the number of corresponding ground states increases exponentially. An N-qubit entangled system has 2 ^N ground states, and the system state can be expressed as a linear superposition of the ground states. For example, a two-qubit system has four ground states: |00>, |01>, |10>, |11>, and its state can also be in the linear superposition of these four ground states, such as:

|ψ>=a|00>+b|01>+c|10>+d|11>

a,b,c,d are complex numbers and satisfy |a| ² +|b| ² +|c| ² +|d| ² =1. This state can also be represented as a vector (a,b,c,d) ^T of length 1 and dimension 4. In general, the wave function of N qubits can be represented by a ^2N -dimensional vector.

Taking advantage of the superposition properties of qubits, the ability of a quantum computer to store information increases exponentially with the number of qubits. A measurement operation on a quantum system causes the system to collapse to the ground state randomly, with a probability that depends on the coefficients preceding each ground state. As for the qubit in the aforementioned formula (1), the probability of |α| ² collapses to |0>, and the probability of |β| ² collapses to |1>.

The technology stack derived from the development of quantum computing in the past 10 years is roughly shown in Figure 1. The top layer is quantum algorithms, such as Shor's algorithm for decomposing prime factors; the bottom is various quantum programming languages and corresponding compilers; the bottom is quantum instruction set architecture and quantum computing platforms (simulators or quantum hardware). At present, the more common independent quantum programming languages are the quantum circuit-level OpenQASM launched by IBMQ, Microsoft's Q#, etc.; there are also languages that can be embedded in Python for programmers to use ProjectQ, Quil, etc. High-level programming languages are translated by compilers into quantum assembly language or quantum microinstruction sets.

The main body of a quantum program is a sequence of operations on qubits, called quantum gates, which can change the state of one or more qubits. Quantum programs implement algorithms by operating to change the state of qubits. For example, Figure 2 shows a piece of OpenQASM code. qreg and creg in lines 1-2 declare qubit and classical bit registers, respectively, and each subsequent line is a quantum gate operation that acts on 1 or 2 qubits.

The quantum gate g acting on n qubits can be represented by a 2 ⁿ × 2 ⁿ matrix M, the quantum gate operation g=g(q ₁ ,...,q _n ) is equivalent to the quantum gate represented by The matrix is multiplied by the vector corresponding to the qubit (represented by the wave function |ψ>), and |ψ′>=M|ψ> is the wave function after the quantum gate acts. where g is the quantum gate operation that contains parameter information, and g is a quantum gate name. In fact, in a system of N qubits, the global wave function |ψ> can be written as the direct product of each qubit:

(M_g为直积运算中的第i个运算对象)来表示。矩阵M也即包含了门g作用于哪些比特上的信息。Therefore, for the single quantum gate g acting on the i-th (1≤i≤N) bit, its matrix is M _g , and its effect on the global wave function |ψ> can be calculated by using M _g and (N-1) The direct product of the unit matrix, i.e.

(M _g is the ith operand in the direct product operation) to represent. The matrix M also contains the information on which bits the gate g acts on.

Suppose two quantum gate operations g ₁ =g ₁ (Q ₁ ), g ₂ =g ₂ (Q ₂ ) act on qubit arrays Q ₁ and Q ₂ respectively (Q ₁ and Q ₂ may have intersection), g ₁ The effects of and g ₂ on the global wave function are represented by matrices M ₁ , M ₂ . If g ₁ is executed first, then g ₂ is executed, the effect |ψ′>=M ₂ M ₁ |ψ> and the effect of g ₂ first, then g ₁ is executed |ψ">=M ₁ M ₂ |ψ> total are the same, that is, M ₂ M ₁ |ψ>=M ₁ M ₂ |ψ>, then g ₁ and g ₂ are called commuters. Considering that the calculation satisfies the associative law, the necessary and sufficient conditions for the commutation of g ₁ and g ₂ can be obtained is M ₁ M ₂ =M ₂ M ₁ .

Quantum programs have strong parallelism at runtime. If the qubits to be operated by two quantum gates do not overlap, then the two gates are said to be parallel, and two parallel quantum gates can generally be executed at the same time. For example, row 3 in Figure 2 is a quantum gate that operates on qubit Q[1], and row 4 is a quantum gate that operates on qubit Q[2], so the two quantum gates can be executed simultaneously. In order to reduce the running time of the program, quantum computers can adopt a maximum parallelization strategy, that is, execute as many quantum gates as possible at each moment.

Quantum programs can run on quantum program simulators or quantum computers. ProjectQ, Qiskit, ScaffCC, HiQ and other platforms all provide quantum program simulators; and there are various types of quantum technologies that can potentially realize quantum computers, such as superconductivity, ion traps, neutral atoms, optics, etc. Quantum computers constructed, of which the superconducting-based IBM Q5 Yorktown and Tenerife and Q14 Melbourne, among others, are publicly available online.

Quantum computers entered the NISQ (Noisy Intermediate Scale Quantum) stage in 2018. The characteristics of the quantum computer at this stage are: 1) It consists of 50 to 100 qubits. On the one hand, the number of qubits has exceeded the upper limit that a classical computer can simulate in a reasonable time, and on the other hand, it is far from enough to complete the bit error correction function similar to that of a classical computer. 2) The hardware contains a lot of noise, resulting in information distortion. Qubits in a superposition state entangle with the surrounding environment over time, resulting in distortion of the information stored in the qubits (quantum decoherence); and since quantum gates are limited by hardware, there are certain errors in their execution. rate, which further leads to distortion of the information stored in the qubit.

In addition, multiple qubits under the physical realization of different quantum systems have different characteristics and limitations in layout and supported quantum gate types and manipulations. Multi-quantum gates directly applied to multiple qubits are physically difficult to implement. Currently, only limited two-quantum gates (such as quantum controlled NOT gates CNOT) are supported and they can only act on certain qubit pairs. The two qubits involved in such a qubit pair are said to be adjacent. If two qubits q ₁ and q ₂ are adjacent, it is assumed that both operations g(q ₁ , q ₂ ) and g(q ₂ , q ₁ ) of the double quantum gate g acting on q ₁ and q ₂ are allowed ; and if the platform supports multiple double quantum gates, for any two quantum gates g ₁ , g ₂ , if the operation g ₁ (q ₁ , q ₂ ) is allowed, then g ₂ (q ₁ , q ₂ ) must also be Allowed. Gates acting on more than two qubits can be decomposed into a set of single-quantum gates and double-quantum gates for indirect realization. Different kinds of quantum gates, or even the same quantum gate operating at different qubit positions, may vary in execution time and the rate of distortion introduced.

Quantum algorithm designers and programmers often do not understand or have difficulty understanding the limitations of quantum hardware. Generally, the quantum bits used in quantum programs are called logical bits, which are not affected by the limitations of quantum hardware; the restricted quantum bits in actual quantum hardware are called physical bits; the quantum gates acting on logical bits in quantum programs are called quantum gates. For logic gates, the gates acting on physical bits are physical gates. In order for a quantum program to be executed on quantum hardware, the quantum program compilation system needs to perform logical-physical bit mapping and quantum circuit transformation in its backend.

For the logical-physical bit mapping, generally each logical bit used in the quantum program is first mapped to a physical bit, which is called the initial mapping π. If there are gates in the program that cannot be executed due to the limitations of quantum hardware, the program needs to be transformed and the corresponding logical bits are remapped to other physical bits. A common approach is to use SWAP gates to exchange information between two adjacent physical bits, thereby routing qubit information to where the quantum gate can execute, which is equivalent to changing the mapping position of logical bits. Suppose s=SWAP(q ₁ ', q ₂ ') is executed when mapping π, where q ₁ ' and q ₂ ' are physical bits, and SWAP(q ₁ ', q ₂ ') actually exchanges physical bits q ₁ ' and q ₂ ', the mapping will become π| _s after swapping, where

Here, the logic gate that needs routing operation is called remote gate; the logic gate that can be executed without routing is called immediate gate. In most subsystems, the SWAP gate can generally be decomposed into three CNOT gates or other gate operations to achieve. Quantum programs can be adapted to hardware constraints and executed by mapping and remapping.

The qubit mapping problem has been proved to be NP-complete, so the global solution method consumes too much space and time, and can only handle extremely small-scale programs; in practice, heuristic methods are mostly used to solve such problems. For the qubit remapping problem, the existing research results assume that the execution time of various quantum gates is the same, and on this basis, solve the remapping method that makes the program running time shorter. However, in actual quantum hardware, the execution time of different types of quantum gates has a large deviation. This makes these methods unable to effectively utilize the parallel ability of quantum computers and find a remapping method that reduces the actual running time as much as possible because they do not consider the difference in the execution time of quantum gates.

SUMMARY OF THE INVENTION

The purpose of the present invention is to provide a logic-physical bit remapping method for noisy medium-sized quantum devices, which can make quantum programs adapt to the limitations of quantum devices, and make execution costs such as execution time and the number of quantum gates as small as possible. The invention designs a remapping method that considers the quantum program context and the execution time difference of the quantum gate by modeling the quantum hardware and based on the abstract model. Compared with the traditional mapping scheme, the code execution time after remapping by the method of the present invention is generally shorter than that of the existing similar methods.

The purpose of this invention is to realize through the following technical solutions:

A logic-physical bit remapping method for noisy medium-sized quantum devices, characterized by comprising:

Obtain the logic gate sequence of the quantum program and the initial mapping of logic-physical bits;

Combining the constraint information of the quantum device ready to run the quantum program and the initial mapping of logical-physical bits, the remapping is completed by changing the order of logic gates and inserting SWAP operations to obtain an instruction scheduling sequence that satisfies the constraint information of the quantum device and ensures the execution cost Minimum; each element in the instruction scheduling sequence is a two-tuple composed of the physical gate to be executed and its initial execution time.

It can be seen from the above technical solutions provided by the present invention that, in view of the limitations of quantum hardware, in order to enable quantum programs to be effectively executed on quantum devices, necessary remapping is completed by changing the order of quantum instructions and inserting SWAP operations, so that quantum programs can adapt to Limits of quantum devices, and make execution costs such as execution time and the number of quantum gates as small as possible.

Description of drawings

In order to illustrate the technical solutions of the embodiments of the present invention more clearly, the following briefly introduces the accompanying drawings used in the description of the embodiments. Obviously, the drawings in the following description are only some embodiments of the present invention. For those of ordinary skill in the art, other drawings can also be obtained from these drawings without any creative effort.

1 is a schematic diagram of a quantum computer technology stack provided by the background technology of the present invention;

2 is a schematic diagram of a section of OpenQASM code provided by the background technology of the present invention;

3 is a schematic diagram of a compilation and execution process of a quantum program provided by an embodiment of the present invention;

4 is a schematic diagram of a sign word of a physical bit provided by an embodiment of the present invention;

5 is a schematic diagram of a quantum instruction simulation execution and a maximum parallelization algorithm provided by an embodiment of the present invention;

FIG. 6 is a schematic diagram of a rectangular network of qubits provided by an embodiment of the present invention.

Detailed ways

The technical solutions in the embodiments of the present invention will be clearly and completely described below with reference to the drawings in the embodiments of the present invention. Obviously, the described embodiments are only a part of the embodiments of the present invention, rather than all the embodiments. Based on the embodiments of the present invention, all other embodiments obtained by those of ordinary skill in the art without creative work fall within the protection scope of the present invention.

Embodiments of the present invention provide a logic-physical bit remapping for noisy medium-sized quantum devices; first, obtain a logic gate sequence of a quantum program and an initial mapping of logic-physical bits; then, combine with a quantum device that is ready to run the quantum program The initial mapping between the constraint information and the logical-physical bits is completed by changing the order of the logic gates and inserting the SWAP operation (swap operation) to complete the remapping to obtain an instruction scheduling sequence that satisfies the constraint information of the quantum device, and ensures the minimum execution cost; the instruction scheduling sequence Each element in is a two-tuple consisting of the physical gate to be executed and its starting execution time.

Those skilled in the art can understand that the swap operation acts on two physical bits to swap the states of the two physical bits.

As shown in Figure 3, it is a schematic diagram of the compilation and execution process of the quantum program. Quantum programs are line-level quantum assemblers written by hand or compiled from high-level languages (take OpenQASM as an example). First, the quantum program is preprocessed to fit the instruction set of the target platform, and flattened (implemented by the flattening module shown in Figure 3) into a sequence of logic gates that are executed sequentially; during preprocessing, it is also possible to Implement other optimization techniques for quantum programs. After that, the preprocessed quantum program obtains an instruction sequence acting on physical bits through initial mapping and remapping (implemented by the remapping module shown in FIG. 3 ). The initial mapping is responsible for mapping the logical bits in the program to the physical bits when the program starts executing, and the result of the mapping may have a violation of two quantum gates acting on non-adjacent physical bits. The remapping algorithm obtains an instruction sequence that satisfies the physical bit constraints according to the input initial mapping and logic gate sequence, and some instructions can be executed in parallel. The output of the remapping will mark the planned start time and end time of all instructions under the maximum parallelization as a reference for the hardware issue instruction time, where the time is a relative time. The main contributions of the present invention focus on the design and implementation of the remapping algorithm.

The remapping algorithm proposed in the present invention focuses on considering the context at the remapping location and the parallelization characteristics of the instruction. Because of the possible parallelism between quantum gates in a quantum program and the interchangeability between certain pairs of quantum gates, there are often multiple quantum gates that can start executing at each moment without changing the semantics of the program. The remapping algorithm requires routing logic gates where execution is desired to begin, but cannot be executed due to geometric constraints of the hardware (eg, non-adjacent qubits being acted upon). For logic gates that have met geometric constraints and can be executed, the remapping algorithm will arrange the required quantum gates to be executed in-situ; for logic gates that cannot be executed in-situ due to hardware constraints, the algorithm will arrange routes according to a heuristic strategy, and the logic The bits are remapped to physical bits in another location and the required quantum gates are executed. In order to make the routing path as reasonable as possible, the remapping algorithm will consider as much as possible the impact of routing on the quantum gates that may be executed next, and reasonably arrange the execution order of instructions. Therefore, the algorithm needs to know exactly which quantum gates can be changed in order, the impact of the proposed routing on subsequent quantum gates, and so on.

The remapping algorithm in the present invention will simulate the process of executing a quantum program once, and may partially disrupt the order of each gate and add a SWAP operation without changing the program semantics. During the simulation execution process, for the unexecuted logic gate operation sequence G and one of the gate operations g, if all the unexecuted gate operations before g and g are commutative, then executing g first will not change The execution result of the sequence, such g is called a candidate gate. It should be noted that the elements in the candidate gate set of a program point in a quantum program are not necessarily parallel, for example, the Y gate and the H gate acting on the same bit are commutative but not parallel.

Before introducing the specific implementation of the remapping algorithm, we first abstract the quantum hardware:

并提供m种量子门

初始化和测量等操作，这些操作称为量子指令。Suppose quantum hardware has N physical bits

And provide m kinds of quantum gates

Operations such as initialization and measurement, these operations are called quantum instructions.

则这两个门一定对易；否则，其是否对易取决于门g₁、g₂的性质。若比特q∈Q₁∩Q₂，则称q为g₁(Q₁)和g₂(Q₂)的共同作用比特。对于多比特量子门的情况，对易关系与共同作用比特位于多比特量子门的形参位置有关，记g的第i个形参位置为g.i。如果g是单比特门，可以直接用g表示其形参位置。如CX(q₁,q₂)和X(q₁)不对易，CX(q₂,q₁)却和X(q₁)对易，这里q₁和q₂为不同比特。为此，定义，若对任意量子门g₁(Q₁)和g₂(Q₂)，且Q₁∩Q₂＝{q}，q为g₁的第i个实参并且为g₂的第j个实参，必有g₁(Q₁)和g₂(Q₂)对易，则记g₁.i与g₂.j对易。若对受控门或单量子门g₁(Q₁)和g₂(Q₂)的每一共同作用比特q_k，设q_k为g₁的第i_k个参数且为g₂的第j_k个参数，都有g₁.i_k与g₂.j_k对易，则g₁(Q₁)和g₂(Q₂)对易。若

可以得到类似表1的对易关系表，该二维表是对称的。其中，H、X、Y、Rz、CX等为量子门符号。Consider two logic gates g ₁ (Q ₁ ) and g ₂ (Q ₂ ), if

Then the two gates must commute; otherwise, whether they commute depends on the properties of the gates g ₁ , g ₂ . If the bit q∈Q ₁ ∩ Q ₂ , then q is called the co-operating bit of g ₁ (Q ₁ ) and g ₂ (Q ₂ ). For the case of a multi-bit quantum gate, the commutation relationship is related to the position of the formal parameter of the multi-bit quantum gate where the cooperating bit is located, and the i-th formal parameter position of g is denoted as gi. If g is a single-bit gate, you can directly use g to represent its formal parameter position. For example, CX(q ₁ , q ₂ ) does not commute with X(q ₁ ), but CX(q ₂ , q ₁ ) commutes with X(q ₁ ), where q ₁ and q ₂ are different bits. To this end, define, if for any quantum gates g ₁ (Q ₁ ) and g ₂ (Q ₂ ), and Q ₁ ∩ Q ₂ ={q}, q is the i-th argument of g ₁ and is the value of g ₂ For the jth actual parameter, there must be _a commutation between g ₁ (Q ₁ ) and _{g 2} (Q ₂ ). If for each co-operating bit q _k of the controlled gate or single quantum gate g ₁ (Q ₁ ) and g ₂ (Q ₂ ), let q _k be the ith parameter of g ₁ and be the _j th parameter of g ₂ For _k parameters, g ₁ .ik and g ₂ .j _{k commute} , then g ₁ (Q ₁ ) and g ₂ (Q ₂ ) commute. like

A commutation relation table similar to Table 1 can be obtained, and the two-dimensional table is symmetrical. Among them, H, X, Y, Rz, CX, etc. are quantum gate symbols.

Note: The headings of each row and each column in Table 1 of the commutation relationship table represent the positions of the various formal parameters of the supported physical gates; since the single-bit quantum gate g (g can be one of H, X, Y, Z, Rz) only has is a parameter, so g.1 is abbreviated as g; and the first and second formal parameters of the two-bit quantum gate CX represent the control bit C and the controlled bit T respectively, so CX.1 and CX.2 are also They are denoted as CX.C and CX.T respectively.

Table 1 Commutation relationship between quantum operations

The present invention assumes that different quantum instructions (including operations such as quantum gates and measurements), especially various quantum gates, have differences in execution time, and the execution of the same kind of quantum gates at different times or physical bits has the same execution time. In order to design a qubit mapping algorithm suitable for different quantum hardware, the present invention abstracts the quantum instruction execution time of the quantum hardware by taking the instruction scheduling cycle (hereinafter referred to as the scheduling cycle) as the basic unit. Assuming that the moment when the first instruction in the quantum program starts to execute is marked as 0, each quantum instruction is executed from the beginning of a certain scheduling period, and the execution time is an integer multiple of the scheduling period (that is, the minimum integer to ensure that the quantum instruction is executed completely) times). The present invention uses multiples to represent the execution time of the instruction, and allows the user to set the execution time of each quantum instruction. For example, in the superconducting computer implemented by IBM, the execution time of a single quantum unitary gate (U) and a quantum controlled NOT gate (CNOT, also called CX) can be taken as 1 and 2, and the SWAP operation is implemented with three CNOT gates, so its The execution time is set to 6.

If a quantum instruction is executing, the bit on which it acts is said to be busy, otherwise it is said to be idle. The present invention assumes that two instructions that cannot be parallelized (that is, they both act on the same bit) cannot be executed at the same time. In other cases, as long as all physical bits required by the instruction are free, the instruction can be executed at the beginning of any subsequent scheduling cycle. implement.

The following describes in detail the remapping scheme involved in the present invention and the preferred implementations of the related algorithms involved in the process of executing the remapping scheme.

1. The overall scheme of qubit remapping.

Under the above quantum hardware abstraction, given the logic gate sequence G of the quantum subprogram and the initial mapping π, the qubit remapping will output an instruction scheduling sequence that satisfies the quantum hardware constraints. Each element in the sequence is the physical gate to be executed and its A 2-tuple consisting of the start execution time. The remapping algorithm completes qubit mapping and quantum instruction scheduling by simulating the execution of quantum instructions. In order to track the idle condition of physical bits, a t _end attribute is defined for each physical bit to indicate the busy time when the corresponding bit ends. For physical bit q, its t _end attribute is denoted as qt _end , and the t _end attribute set of all physical bits is denoted is T _end ; initially, the t _end attribute of each bit is 0, and if the current moment t ≥ qt _end , the bit q is idle;

The steps of remapping include:

Step A1, set the current time t=0, initialize the output instruction scheduling sequence I={};

Step A2, initialize the t _end attribute, and set the t _end attribute of each physical bit to 0;

Step A3, utilize the approximate solution algorithm of the candidate gate set in conjunction with the logic gate sequence G and the mapping π of the logic-physical bit (π is the mapping of the current logical bit to the physical bit, and this mapping is called the initial mapping when the remapping starts to execute, Incoming from the outside; in the process of remapping execution, π needs to change constantly to adapt to the limitations of quantum hardware), calculate the current candidate gate set C; where candidate gate refers to, for a logic gate g, if the logic gate g and the logic gate All unexecuted logic gates before gate g are commutative, then executing logic gate g first will not change the execution result of the sequence, then logic gate g is a candidate gate;

Step A4, for the immediate gate set CI in the current candidate gate set C, _traverse each logic gate g in the _CI in turn, and execute: Step A41, if the physical bits mapped to the logical bits of the logic gate g are idle , then use the quantum instruction simulation execution and the maximum parallelization algorithm, combine the instruction scheduling sequence I and the attribute set T _end to transmit the physical instruction corresponding to the logic gate g (composed of the physical gate corresponding to g and the physical bits that function), and from the logic gate Remove g in the sequence G; Step _A42 , take the next logic gate in the immediate gate set CI, continue to execute step A41, until the immediate gate set _CI is empty; otherwise, execute step A5;

Step A5, for the remote gate set _CR in the current candidate gate set C, execute: Step A51, utilize the heuristic algorithm of the optimal route, combine the logical-physical bit map π, the attribute set T _end , and the remote gate set _CR Obtain the SWAP operation sequence S; Step A52, for each SWAP operation in the SWAP operation sequence S, first update the corresponding bit map in the logical-physical bit map π according to the two physical bits exchanged by the corresponding SWAP operation, and then use the quantum The instruction simulation execution and the maximum parallelization algorithm are combined with the instruction scheduling sequence I and the attribute set T _end to transmit the corresponding physical instructions (such as the SWAP operation corresponding to three CX instructions); the remote gate refers to the logic gate that requires routing operations, so The aforementioned immediate gate refers to a logic gate that can be executed without routing;

Step A6, make the current time t=t+1;

Step A7: Return to step A3 until the logic gate sequence G is empty.

It should be noted that, in the above step A5, the heuristic algorithm that adopts the optimal route may sometimes not output the route SWAP, which will be described in detail later. In a very special case, there may be a situation where each bit is free globally or in a local area, but there is neither an immediate gate that can be executed in the candidate gates, nor a feasible routing bit given by the heuristic algorithm. A similar situation is called a "deadlock". A discussion of deadlocks is discussed later.

Second, the approximate solution algorithm of the candidate gate set.

In the foregoing step A3, the current candidate gate set C is solved using the approximate solution algorithm of the candidate gate set.

Given the unexecuted logic gate sequence G at the current time t, the candidate gate set can be solved by the definition of the candidate gate, but it will be time-consuming. Considering that the number of qubits and types of quantum gates supported by actual hardware are very limited, a fixed-length flag word is introduced for each physical bit. In the flag word, a flag bit is set for each formal parameter position g.i of each physical gate g. ; Then read the logic gates in the logic gate sequence G in turn, and the flag bit is true, indicating that the corresponding parameter position of the logic gate and all the logic gates that have been read are commutative. Figure 4 shows a schematic diagram of the physical bit flag word.

The embodiment of the present invention provides two methods for quickly solving the candidate set, the first method is as follows:

Step B1, initially, the current candidate gate set C is an empty set, and each flag bit of each physical bit is true;

Step B2, traverse all the unexecuted logic gates forward in turn, and execute:

Step B21, set the current logic gate to be g=g(Q), and Q represents the logic bit array that the logic gate g acts on; if for each logic bit q∈Q, q is the ith parameter of g, and its corresponding physical If the g.i flag bits of the bit q'=π(q) are all true, put the logic gate g into the candidate gate set C;

Step B22: For all logical bits q∈Q, let q be the i-th parameter of g, and find the column where the g.i flag bit of the physical bit q' corresponding to the logical bit q is located (you can find the name by looking up the commutation relationship table 1). is the column of g.i), if there is a unit with a value of 0 in the column, the row name of the unit is g'.j, indicating that g'.j and g.i are not commutative, then set the physical bit q' g'.j corresponds to The flag bit is false;

Step B23, remove a logic gate, and continue the cycle until the traversal ends or all flag bits are false.

The first method can theoretically find all candidate gates. However, when there are many kinds of gates or a long sequence of quantum gates that are not executed, the time consumption and space consumption of the algorithm are still very large. In addition, since subsequent algorithms need to frequently update the candidate gate set, the above algorithm cannot effectively utilize the results of the last time. Assuming that the candidate gate set obtained last time is C ₀ , and then several gates in C ₀ are executed, so that C ₀ becomes C ₀ ', then the gates in C ₀ ' are still candidate gates at this time. Therefore, The first method can be improved:

1) The initial candidate gate set uses the previous results to avoid a large number of repeated calculations.

2) Increase the loop termination condition, and only select the candidate gates in a certain range of gates to avoid excessive time consumption.

The above improvements can further significantly reduce the execution time of the algorithm. The improved algorithm is an approximate algorithm, and the obtained set is a subset of the actual candidate gate set, but the difference is not very significant.

Then the second method is:

Step C1. In each iteration process of remapping, the candidate gate set needs to be solved. When the candidate gate set is solved for the first time, the candidate gate set C is an empty set;

Step C2. When the candidate gate set is solved in the subsequent remapping iterative process, the last solved candidate gate set is recorded as C _last , and if the C _last subset C _emitted has been emitted and removed in the last remapping, it is recorded as the set C ₀ =C _last -C _emitted ;

Step C3, note that each flag bit of each physical bit is true;

Step C4, traverse the logic gate g=g(Q) in the set C ₀ , Q represents the logic bit array that the logic gate g acts on; for each logic bit q∈Q, let q be the ith parameter of g, and find the logic The column where the gi flag bit of the physical bit q' corresponding to the bit q is located. If there is a unit with a value of 0 in the corresponding column, the row name of the corresponding unit is recorded as g'.j, indicating that g'.j and gi are not commutative. Then set the corresponding flag bit of g'.j of physical bit q'=π(q) to false;

Step C5, traverse all the unexecuted logic gates forward in turn, set the current logic gate to be g=g(Q), and execute:

Step C51, if g is already in the candidate gate set C, then continue to take the next logic gate; otherwise, execute step C52;

Step C52, if for each logical bit q∈Q, q is the ith parameter of g, and the g.i flag bits of the corresponding physical bit q' are all true, then put g into the candidate gate set C; otherwise, execute Step C53;

Step C53: For all logical bits q∈Q, let q be the i-th parameter of g, and find the column where the g.i flag bit of the physical bit q' corresponding to the logical bit q is located. If there is a unit with a value of 0 in the corresponding column, Then the row name of the corresponding unit is denoted as g'.j, indicating that g'.j and g.i are not commutative, then set the corresponding flag bit of g'.j of physical bit q' to false;

Step C54, remove the next logic gate, and continue the cycle until the traversal ends or the total number of logic gates traversed exceeds the set value N.

3. Quantum instruction simulation execution and maximum parallelization algorithm.

The quantum instruction simulation execution and maximum parallelization algorithm are applied in the aforementioned steps A4 and A5, responsible for transmitting the physical instruction corresponding to the physical gate g' or SWAP operation acting on the physical bit, and setting and judging the busy or idle state of the physical bit. .

In the embodiment of the present invention, before performing the quantum instruction simulation execution and the maximum parallelization algorithm, the logical bit array Q acting by the logic gate g has been converted into the physical bit array Q'=π(Q) by mapping π, then The logic gate g becomes the physical gate g'. It should be noted that the actual operation content of the logic gate and the physical gate has not changed. The only difference is that the operation object is changed from a logical bit to a physical bit.

Whenever an instruction g'=g(Q') (where Q' is a physical bit array) or a SWAP operation is to be issued in the remapping algorithm, the quantum instruction simulation execution and the maximum parallelization algorithm receive the corresponding instruction, and then perform the following operations:

1) For each physical bit q'∈Q' acting on the physical gate g', find its latest busy end time t _m =max{q'.t _end }, since the instruction can only be issued when the physical bit is idle, obviously , t _m ≤ t; set the execution duration of the physical gate g' as τ, then for each physical bit q'∈Q', set q'.t _end =t _m +τ.

2) For the SWAP operation, the physical implementation instructions corresponding to the SWAP operation are transmitted, such as three CX operations and their initial execution time.

In the embodiment of the present invention, the physical instruction g' received by the quantum instruction simulation execution and the maximum parallelization algorithm at time t is not directly executed at time t, but after all physical bits whose functions are traced back to the end of the busy state The earliest moment is the moment when g' starts to execute, and this moment is the earliest moment when g' can be executed. Considering the locality of the remapping algorithm, it may happen that an unanticipated command (usually SWAP) is sent later. The simulation execution of quantum instructions and the maximum parallelization algorithm assume that the quantum computer has sufficient parallelism to execute immediately when all instructions can start to be executed, so it is a maximum parallelization algorithm. Given the instruction sequence, the quantum instruction simulation execution and the maximum parallelization algorithm ensure the early execution of instructions, so that the received quantum instructions can be parallelized to the maximum.

As shown in part (a) of Figure 5, CX(q1, q3) needs to be executed at present. Since q1 and q3 are not adjacent, the heuristic algorithm of optimal routing arranges a SWAP (q2, q3) operation, so that the Implement CX operations on adjacent q1 and q2. The quantum instruction simulation execution and the maximum parallelization algorithm do not directly schedule the SWAP instruction to start executing at the current moment (at the dotted line), but go back to the earliest possible moment (as shown in part (b) of Figure 5), so that Advances both SWAP and subsequent CXs (and other potentially affected gates) (as shown in part (c) of Figure 5).

Fourth, the heuristic algorithm of optimal routing.

The embodiment of the present invention provides an optimal routing heuristic algorithm, which is used to provide a set of approximately optimal SWAP operations _S for the non-empty candidate remote gate set CR. Let the set of physical bits for each gate in _CR be Q'. For an idle bit q ₁ ' in the physical bit array Q', if there is a physical bit q ₂ ' adjacent to the physical bit q ₁ ' and q ₂ ' is idle, it is called a SWAP operation between q ₁ ' and q ₂ ' For candidate SWAP, the set composed of all candidate SWAPs is called a SWAP candidate set.

Using the heuristic algorithm of optimal routing, the steps of obtaining the SWAP operation sequence S include:

Step D1, make the SWAP operation sequence S={};

Step D2, obtain the current SWAP candidate set S _c ; Suppose that the logic gate g is a remote gate, the logical bit array Q that the logic gate g acts is converted into a physical bit array Q'(Q'=π(Q)) by mapping π, Then the logic gate g becomes the physical gate g', which is called the remote gate g' here. For the idle bit q ₁ ' in the physical bit array Q', if there is a physical bit q ₂ ' adjacent to the physical bit q ₁ ' And q ₂ ' is idle, then the SWAP operation between the physical bits q ₁ ' and q ₂ ' is called a candidate SWAP;

Step D3: Calculate the priority of each candidate SWAP operation _sk ∈ S _c (the specific method will be introduced later);

Step D4, select the SWAP operation s with the highest priority, if the priority of the SWAP operation s is less than 1; or, if the adjacent relationship between the physical bits can be modeled as a rectangular grid, the priority of the SWAP operation s is less than <1 ,0>, terminate the algorithm, and output the currently obtained SWAP operation sequence S;

Step D5, update the SWAP operation sequence: S=S∪{s};

Step D6, remove the SWAP operation s and the SWAP operation having a common physical bit with the SWAP operation s from the SWAP candidate set S _c ;

Step D7, update the mapping, π=π| _s , that is, after performing the SWAP operation s when mapping π, the mapping π is changed and updated to π| _s ;

Step D8, return to step D3 until the SWAP candidate set is empty.

During the execution of the above algorithm, each time a SWAP is selected, a SWAP that is not parallel to the selected SWAP will be excluded from the candidate SWAPs, so all the generated SWAP operations S are parallel to each other and can be executed immediately. The return value of the algorithm is S, which is the sequence of SWAP operations.

However, in the above execution process, the priority of all candidate SWAP operations _sk ∈ S may be less than 1 or less than <1,0>, and there may be the following two situations:

In the first case, some candidate gates need to be routed, but a certain physical bit of these candidate gates is busy, or the routing will interfere with other executing gates (the quantum gates that are already in the instruction scheduling sequence and are being executed) , the execution here refers to the simulated execution);

In the second case, there are candidate gates that need routing, and these routes do not interfere with the gate being executed;

The reason for the second case is that the algorithm believes that, for any one route, although it reduces the distance of some remote doors, it may increase the distance of the same or more number of remote doors. At this time, the routing and scheduling system is locked - this is very similar to the deadlock in the operating system, so it is called deadlock. For deadlock situations, there are the following release strategies:

1) Select the SWAP operation s with the highest priority from the SWAP candidate set S _c ;

2) Remove the SWAP operation s and the SWAP operation that has a common bit with the SWAP operation s from the SWAP candidate set S _c , execute s and update the mapping π=π| _s ;

3) Re-execute the normal routing algorithm (ie, steps D1 to D8 above) until there is no candidate SWAP with a priority of not less than 1 or <1,0> (for a rectangular grid of physical bits).

Both theoretical analysis and practice show that even if all bits are free and the candidate SWAP set S _c is not empty, it is still possible to find no SWAP with a priority greater than or equal to 1. This is because some of the bits involved in SWAP may involve different remote gates, and neither route will reduce the total distance of the remote gates. In the situation shown in Figure 6, there are 4 candidate gates waiting to be executed on a rectangular grid device, and a candidate CX gate (controlled NOT gate, a kind of two-quantum gate) between bits of the same padding. Each CX has a distance of 1, but swapping any adjacent bits does not reduce the total distance (at most from 1+1+1+1 to 2+1+1+0)

In response to this situation, a candidate SWAP with the highest priority (although still less than 1) can be selected for execution to break this situation. It can be shown that such a highest priority is at least 0, meaning that executing it will not make the situation worse, and must be beneficial to some candidate gate's distance reduction.

The following describes how the priority of candidate SWAP operations _sk is calculated:

The distance (distance) of the remote gate g is defined as the minimum number of SWAP operations required to realize the remote gate g, denoted as g.d; a double quantum gate on two non-adjacent bits is a remote gate; in addition, if a single bit Quantum gates that cannot be executed at the current location and require remapping of bits to another location to execute are also remote gates.

对于每一个候选SWAP操作s_k＝SWAP(q₁’,q₂’)，执行候选SWAP操作s_k，更新逻辑-物理比特映射

定义启发式函数：Define the total candidate distance

For each candidate SWAP operation _sk =SWAP(q ₁ ',q ₂ '), perform the candidate SWAP operation _sk , update the logical-physical bitmap

Define the heuristic function:

The higher the H _basic (π,s), the greater the positive impact of the SWAP operation _sk , then the priority H(π, _sk )=H _basic (π,s); in general, you can directly use H( π, _sk )=H _basic (π, _sk ) measures the positive effect of each candidate SWAP operation _sk , and selects the s that maximizes H(π,s).

If the adjacent relationship between physical bits can be modeled as a rectangular grid; for each candidate dual quantum remote gate g, we can further perform heuristic optimization by examining the characteristics of its candidate SWAP operations on the rectangular grid. In a rectangular grid, each physical bit has location attributes x and y. If the logic gate g is a double quantum remote gate, then g=g(q ₁ , q ₂ ), and the two logic bits q ₁ and q act on it The horizontal and vertical distances between ₂ are defined as:

HD(π,g)=|q ₁ '.xq ₂ '.x|

VD(π,g)＝|q ₁ '.yq ₂ '.y|

Wherein, q ₁ '.x, q ₁ '.y represent the row and column coordinates of the physical bit q ₁ ' corresponding to the logical bit q ₁ in the rectangular grid; q ₂ '.x, q ₂ '.y represent the logical bit The row and column coordinates of the physical bit q ₂ ' corresponding to q ₂ in the rectangular grid;

种。Then the distance d(π,g)=HD(π,g)+VD(π,g)-1; for g, the SWAP operation needs to be introduced to route the bit information to the physical bits that the quantum gate can execute, and its shortest route path can have

kind.

In a rectangular grid, for any bit pair with a distance of d(π,g), when the |VD(π,g)-HD(π,g)| of the bit pair is smaller, the shortest possible distance between the bit pair The larger the number of routing paths; using this property, for each candidate SWAP operation _sk , the following heuristic function is introduced to assist in the selection:

Among them, G ₂ is a set of double quantum remote gates. For the case that can be modeled as a rectangular grid, let the priority be H(π,s _k )=<H _basic (π,s _k ),H _fine (π,s _k ) )>.

It is stipulated that H(π,s ₁ )>H(π,s ₂ ) if and only if H _basic (π,s ₁ )>H _basic (π,s ₂ ) or H _basic (π,s ₁ )=H _basic ( π,s ₂ )∧H _fine (π,s ₁ )>H _fine (π,s ₂ ). If H(π,s ₁ )>H(π,s ₂ ) or denoted as H(π,s ₂ )<H(π,s ₁ ), then the priority of s ₁ is higher than that of s ₂ .

Those skilled in the art can understand that the above priorities are represented by two-tuple groups, and “> and <” represent the partial order relationship of the priorities of the two-tuple groups.

For a sufficiently ideal quantum computer, any supported gate operation can be performed on any qubit. However, remapping is usually required on quantum computers to ensure program execution. A SWAP operation will be introduced during the remapping process, so that the total number of instructions and the total execution time after remapping must be no less than before the remapping transformation. We can measure the pros and cons of a remapping algorithm by two simple metrics: the number of additional SWAP operations introduced, and the increased execution time (compared to execution on ideal hardware) resulting from the introduction of SWAP.

The logical-physical bit remapping method for noisy medium-sized quantum devices provided by the present invention will be referred to as COntext-and Duration-Aware Remapping algorithm (CODAR). The algorithm for benchmark evaluation is the best known SABRE algorithm. Tested on IBM Q16, IBM Q20 Tokyo and Enfield 6*6 models respectively. The test samples include typical quantum algorithms such as quantum Fourier transform (QFT) and Shors algorithm. The test results are shown in Tables 2 to 3. Among them, Qubits is the number of logical bits used by the quantum program, g _t is the total number of gates in the program, T _S and T _C are the shortest execution time after SABRE transformation and after CODAR transformation, where the execution time of a single quantum gate is 1, and CX is 2, SWAP is 6. In the above tests, both CODAR and SABRE go through 12 rounds of forward and reverse bidirectional iterations to find the initial mapping.

Table 2 Test results (the first half)

volume_n5_d2 5 40 20 20 20 100.0% 20 20 100.0% 20 20 100.0% 4mod5-v1_22 5 twenty one twenty two 42 53 79.2% twenty two twenty two 100.0% 42 47 89.4% 9symml_195 11 34881 32084 74352 81711 91.0% 59755 60884 98.2% 71816 78153 91.9% adr4_197 13 3439 3088 6977 7737 90.2% 5345 5444 98.2% 6747 7479 90.2% alu-v0_27 5 36 35 61 71 85.9% 49 39 125.6% 68 71 95.8% cvcle10_2_110 12 6050 5662 12871 14113 91.2% 10077 10626 94.8% 12492 13682 91.3% ising_model_10 10 480 90 89 90 98.9% 89 90 98.9% 89 90 98.9% ising_model_13 13 633 91 91 91 100.0% 91 91 100.0% 91 178 51.1% ising_model_16 16 786 91 91 91 100.0% 91 180 50.6% 91 130 70.0% misex1_241 15 4813 4473 9816 10775 91.1% 7196 6940 103.7% 9296 10663 87.2% mod5mils_65 5 35 37 76 80 95.0% 63 59 106.8% 76 80 95.0% radd_250 13 3213 2990 6727 7404 90.9% 5061 5375 94.2% 6494 7159 90.7% rd73_252 10 5321 4829 10970 12287 89.3% 8834 8933 98.9% 10694 11780 90.8% rd84_142 15 343 191 452 493 91.7% 378 412 91.8% 459 463 99.1% rd84_253 12 13658 12176 28256 31365 90.1% 22054 23183 95.1% 27237 30133 90.4% sqn_258 10 10223 9176 20916 23170 90.3% 16741 16694 100.3% 20581 22263 92.4% square_root_7 15 7630 6367 12399 16269 76.2% 10247 10710 95.7% 12058 15744 76.6% sym6_145 7 3888 3686 8129 9011 90.2% 5885 6221 94.6% 8066 8847 91.2% sym9_193 11 34881 32084 74352 81711 91.0% 59805 60777 98.4% 71920 78153 92.0% z4_268 11 3073 2756 6248 6892 90.7% 5010 5140 97.5% 6082 6827 89.1%

Table 3 Test results (the second half)

In IBM Q16, IBM Q20Tokyo and Enfield 6*6 three models, the running time of CODAR-transformed program is 82.5%, 82.4%, and 80.6%, respectively, compared with that of SABRE-transformed program. CODAR successfully reduces the program running time by 17.5% to 19.4% on different platforms.

From the description of the above embodiments, those skilled in the art can clearly understand that the above embodiments can be implemented by software or by means of software plus a necessary general hardware platform. Based on this understanding, the technical solutions of the above embodiments may be embodied in the form of software products, and the software products may be stored in a non-volatile storage medium (which may be CD-ROM, U disk, mobile hard disk, etc.), including Several instructions are used to cause a computer device (which may be a personal computer, a server, or a network device, etc.) to execute the methods described in various embodiments of the present invention.

The above description is only a preferred embodiment of the present invention, but the protection scope of the present invention is not limited to this. Substitutions should be covered within the protection scope of the present invention. Therefore, the protection scope of the present invention should be based on the protection scope of the claims.

Claims (8)

1. A logical-physical bit remapping method for a noisy medium-sized quantum device is characterized by comprising the following steps:

acquiring a logic gate sequence of a quantum program and initial mapping of logic-physical bits;

combining constraint information of quantum equipment for running the quantum program with initial mapping of logic-physical bits, completing remapping by changing the order of logic gates and inserting SWAP operation, obtaining an instruction scheduling sequence meeting the constraint information of the quantum equipment, and ensuring the minimum execution cost; each element in the instruction scheduling sequence is a binary group consisting of a physical gate to be executed and the initial execution time of the physical gate;

wherein a t is defined for each physical bit _end Attribute to indicate the busy moment of the end of the corresponding bit, for the physical bit q, its t _end The attribute is noted as q.t _end T of the totality of physical bits _end The attribute set is denoted T _end (ii) a Initially, t of each bit _end The attribute is 0, if the current time t is more than or equal to q.t _end If so, bit q is idle;

the step of remapping comprises:

step a1, setting the current time t to be 0, and initializing an output instruction scheduling sequence I to be { };

step A2, initialize t _end Attribute, t of each physical bit _end Setting the attribute as 0;

step A3, calculating a current candidate gate set C by using an approximate solution algorithm of the candidate gate set and combining a logic gate sequence G and a mapping pi of logic-physical bits; the candidate gate is that, for one logic gate g, if the logic gate g and all the logic gates which are not executed before the logic gate g are all easy, the logic gate g is executed first next without changing the execution result of the sequence, and then the logic gate g is the candidate gate;

step A4, set of immediate gates C in set C for current candidate gates _I Sequentially traverse C _I Performs: step A41, if the physical bits mapped by the logic bits acted by the logic gate g are all idle, then using quantum instruction simulation execution and maximum parallelization algorithm, combining the instruction scheduling sequence I and the attribute set T _end Transmitting a physical instruction corresponding to the logic gate G, wherein the physical instruction consists of a physical gate corresponding to the logic gate G and an acting physical bit, and removing the logic gate G from the logic gate sequence G; step A42, get immediate gate set C _I Continues to perform step a41 until the immediate set of gates C _I Is empty; otherwise, executing step A5;

step A5, for remote set of doors C in current set of candidate doors C _R And executing: step A51, utilizing heuristic algorithm of optimal route, combining logic-physical bit mapping pi and attribute set T _end And remote door set C _R Obtaining a SWAP operation sequence S; step A52, for each SWAP operation in the SWAP operation sequence S, firstly updating the corresponding bit mapping in the logic-physical bit mapping pi according to two physical bits exchanged by the corresponding SWAP operation, and then combining the instruction scheduling sequence I and the attribute set T by utilizing the quantum instruction simulation execution and maximum parallelization algorithm _end Transmitting a corresponding physical instruction; the remote gate is a logic gate needing routing operation, and the immediate gate is a logic gate which can be executed without routing;

step a6, setting the current time t to t + 1;

step A7, return to step A3 until logic gate sequence G is empty.

2. The method of claim 1, wherein the remapping by changing the order of logic gates and inserting SWAP operations comprises:

during remapping, the process of quantum program execution is simulated, the context environment of the quantum program and the parallelization characteristics of the logic gates are combined, the order of part of the logic gates is changed and SWAP operation is inserted on the premise of not changing the semantics of the quantum program, so that the instruction scheduling sequence obtained after remapping can be directly executed in corresponding quantum equipment.

3. The method of claim 1, wherein the step of computing the current candidate set of gates C comprises:

introducing a flag word with fixed length for each physical bit, and setting a flag bit for each parameter position g.i of each physical gate g in the flag word; sequentially reading in the logic gates in the logic gate sequence G, wherein the flag bit is true to indicate that the corresponding parameter positions of the logic gates and all the read logic gates are easy;

step B1, initially, the current candidate gate set C is a null set, and each flag bit of each physical bit is true;

step B2, all the logic gates which are not executed are traversed forward in sequence, and the following steps are executed:

step B21, setting the current logic gate as g ═ g (Q), where g is the quantum gate operation including parameter information, g is a quantum gate name, and Q represents the logic bit array acted by the logic gate g; if each logic bit Q belongs to Q, Q is the ith parameter of g, and the g.i flag bit of the corresponding physical bit Q' ═ pi (Q) is true, the logic gate g is put into a candidate gate set C;

step B22, for all logic bits Q belonging to Q, setting Q as the ith parameter of g, searching the column where the g.i flag bit of the physical bit Q ' corresponding to the logic bit Q is located, if the corresponding column has a unit with a value of 0, the row name of the corresponding unit is g '. j, and if the g '. j and the g.i are not easy to match, the flag bit corresponding to g '. j of the physical bit Q ' is false;

and step B23, taking down a logic gate, and continuing to loop until the traversal is finished or all the flag bits are false.

4. The method of claim 1, wherein the step of computing the current candidate set of gates C comprises:

introducing a flag word with fixed length for each physical bit, and setting a flag bit for each parameter position g.i of each physical gate g in the flag word; sequentially reading in the logic gates in the logic gate sequence G, wherein the flag bit is true to indicate that the corresponding parameter positions of the logic gates and all the read logic gates are easy;

step C1, in each remapping iteration process, a candidate gate set needs to be solved, and when the candidate gate set is solved for the first time, the candidate gate set C is an empty set;

step C2, when solving the candidate gate set in the remapping iterative process, recording the candidate gate set solved last as C _last Is provided with C _last Subset C _emitted Having been launched and removed in the last remapping, set C is marked ₀ ＝C _last -C _emitted ；

C3, recording each flag bit of each physical bit is true;

step C4, traversing the set C ₀ The logic gate g ═ g (Q), where g is a quantum gate operation containing parameter information, g is a quantum gate name, and Q represents a bit array acted on by the logic gate g; for each logic bit Q belongs to Q, setting Q to be the ith parameter of g, searching a column where a g.i flag bit of a physical bit Q ' corresponding to the logic bit Q is located, if a unit with a value of 0 exists in the corresponding column, the row name of the corresponding unit is named as g '. j, and if the g '. j and the g.i are not easy, setting the flag bit corresponding to the g '. j of the physical bit Q '. pi (Q) as false;

step C5, sequentially traversing all unexecuted logic gates in the forward direction, and executing:

step C51, if the logic g is already in the candidate gate set C, continuing to take the next logic gate; otherwise, go to step C52;

step C52, if each logic bit Q belongs to Q, Q is the ith parameter of g, and g.i flag bit of the corresponding physical bit Q' is true, putting g into the candidate gate set C; otherwise, go to step C53;

step C53, for all logic bits Q belonging to Q, setting Q as the ith parameter of g, searching the column where the g.i flag bit of the physical bit Q ' corresponding to the logic bit Q is located, if the corresponding column has a unit with a value of 0, the row name of the corresponding unit is g '. j, and if the g '. j and the g.i are not easy to match, the flag bit corresponding to g '. j of the physical bit Q ' is false;

and step C54, taking down a logic gate, and continuing to loop until the traversal is finished or the total number of traversed logic gates exceeds a set value N.

5. The method for remapping the logical-physical bits of the noisy medium-sized quantum device according to claim 1, wherein before the quantum instruction simulation execution and the maximum parallelization algorithm are performed, the logical bit array Q acted by the logical gate g is transformed into a physical bit array Q '═ pi (Q) by using a mapping pi, so that the logical gate g becomes the physical gate g', actual operation contents of the logical gate and the physical gate are not changed, and only the operation object is changed from the logical bit to the physical bit; the quantum instruction simulation execution and maximum parallelization algorithm is responsible for transmitting a physical instruction corresponding to a physical gate g' or SWAP operation acting on a physical bit, and comprises the following steps:

for each physical bit Q ' ∈ Q ' acted on by physical gate g ', its latest ending busy time t is found _m ＝max{q.t _end }，t _m T is less than or equal to t; let the execution time of the physical gate g 'be tau, then for each physical bit Q'. epsilon.Q ', set Q'. t _end ＝t _m +τ；

And for the SWAP operation, transmitting a physical implementation instruction corresponding to the SWAP operation.

6. The logical-physical bit remapping method for the noisy medium-sized quantum device according to claim 1, wherein the step of obtaining the SWAP operation sequence S by using the heuristic algorithm of the optimal route comprises:

step D1, let SWAP operation sequence S { };

step D2, finding the current SWAP candidate set S _c (ii) a Assuming that the logic gate g is a remote gate, the logic bit array Q acted on by the logic gate g is converted into a physical bit array Q 'by mapping pi to pi (Q), and the logic gate g becomes a physical gate g', here called remote gate g ', for the free bits Q' in the bit array Q ₁ ', if any, associated with the physical bit q ₁ ' Adjacent bits q ₂ ' and physical bit q ₂ 'Idle', physical bit q is called ₁ ' and q ₂ SWAP operations between' are candidate SWAP;

step D3, for each candidate SWAP operation s _k ∈S _c Calculating the priority;

d4, selecting the SWAP operation s with the highest priority, if the priority of the SWAP operation s is less than 1; or if the adjacent relation between the physical bits can be modeled as a rectangular grid, the priority of the SWAP operation S is less than <1,0>, the algorithm is terminated, and the SWAP operation sequence S obtained at the current stage is output;

step D5, update SWAP operation sequence: s ═ es { S };

step D6, from SWAP candidate set S _c Removing SWAP operation s and SWAP operation with common physical bit with the SWAP operation s;

step D7, updating mapping, pi ═ pi- _s That is, the SWAP operation s is performed at the initial mapping of π, and the mapping becomes π! memory cells _s ；

And D8, returning to the step D3 until the SWAP candidate set is empty.

7. The method of claim 6, wherein the candidate SWAP operations s are selected from a group consisting of a global operation, a motion, a global operation, a motion, a global operation, a motion, a, and a _k The priority calculation method comprises the following steps:

defining the distance of the logic gate g as the minimum SWAP operand required for realizing the logic gate g, noted as g.d;

defining a total candidate distance

For each candidate SWAP operation s _k ＝SWAP(q ₁ ’,q ₂ ') perform a candidate SWAP operation s _k Updating the initial mapping pi ═ pi _ non conducting phosphor _s Defining a heuristic function:

H _basic the higher (π, s), the SWAP operation s _k The greater the positive impact, the higher the priority H (π, s) _k )＝H _basic (π,s)；

If the neighborhood between physical bits can be modeled as a rectangular grid; each physical bit has location attributes x and y, g ═ g (q) if logic gate g is a dual-quantum remote gate ₁ ,q ₂ ) Two bits q of its effect ₁ And q is ₂ The horizontal and vertical distances therebetween are defined as:

HD(π,g)＝|q ₁ ’.x-q ₂ ’.x|

VD(π,g)＝|q ₁ ’.y-q ₂ ’.y|

wherein q is ₁ ’.x、q ₁ '. y represents a logical bit q ₁ Corresponding physical bit q ₁ ' row, column coordinates in a rectangular grid; q. q.s ₂ ’.x、q ₂ '. y represents a logical bit q ₂ Corresponding physical bit q ₂ ' row, column coordinates in a rectangular grid;

then the distance d (pi, g) ═ HD (pi, g) + VD (pi, g) -1;

in the rectangular grid, for a bit pair with an arbitrary distance d (pi, g), when | VD (pi, g) -HD (pi, g) | of the bit pair is smaller, the number of shortest routing paths possible between the bit pair is larger; using this property, for each candidate SWAP operation s _k The following heuristic function is introduced for auxiliary selection:

wherein G is ₂ For a set of dual-quantum remote gates, for the case that can be modeled as a rectangular grid, let the priority be H (π, s) _k )＝<H _basic (π,s _k ),H _fine (π,s _k )>。

8. The method of claim 7, wherein if all candidate SWAP operations s are performed, the method comprises _k Are all less than 1 or less than<1,0>At this time, there may be two cases: in the first case, some candidate gates need routing, but some physical bit corresponding to these candidate gates is in busy state, or the routing will interfere with other executing gates; in the second case, there are candidate gates that need routes that do not interfere with existing gates;

for the second case, the following processing is adopted:

from SWAP candidate set S _c Selecting the SWAP operation s with the highest priority;

from SWAP candidate set S _c Removing SWAP operation s and SWAP operation having common bit with SWAP operation s, executing s and updating mapping pi ═ pi- _s ；

The normal routing algorithm is re-executed until there are no candidate SWAP with a priority of no less than 1 or <1,0 >.

Images