Patent Description:
A universal quantum circuit simulator stores a mathematical representation of the whole state of a simulated quantum computer in a memory. The size of this state scales as <NUM>n, with n being the number of simulated qubits of the quantum computer. For <NUM> qubits, the size of this state is 16TiB. This requires usage of a multi-node computing system, in order to distribute the large state across multiple memories of the nodes. During simulation of the quantum circuit, access to the parts of the state from the remote nodes is required.

In order to simulate quantum computations on a classical computer, one can use a linear algebraic representation of the quantum computation (quantum circuit). In this representation, the state of an n-qubit quantum circuit is a vector Ψ in a Hilbert space with the orthonormal basis {ψi}. The dimension of the space is equal to <NUM>n. According to quantum computation theory, the following relations hold: <MAT>.

From the above relations, the straightforward way to represent the state of the quantum computer in a memory is to store <NUM>n complex numbers {αi}, which are called amplitudes of corresponding basis states. The value |αi|<NUM> determines the probability to observe the basis state i as an output of the quantum circuit/computer.

The quantum computation may be expressed as a linear unitary operator U acting on the vector Ψ yielding the resulting state Ψ': <MAT>.

Since the basis in the Hilbert space is defined, the operator U is represented by a matrix of dimensions <NUM>n × <NUM>n.

In quantum computation, a quantum gate is defined as the basic unitary operator, which acts on one or a few qubits. Practical quantum gates are of sizes <NUM>-, <NUM>- and <NUM>-qubits. Using these quantum gates, any quantum algorithm can be expressed. According to the above equation (<NUM>), any quantum algorithm can be represented by a unitary matrix and a relation between a sequence of quantum gates and an operator U: <MAT>.

In other words, the quantum algorithm can be expressed as tensor product of quantum gates, each quantum gate acting on a subset of qubits.

A typical set of quantum gates, which are used in most common quantum algorithms, is show in <FIG>. Therein, CNOT and CZ are examples of a special kind of quantum gates, which are called controlled gates. Such quantum gates act on <NUM> or more qubits, wherein one or more qubits act as a control for some operation. The qubit, upon which an operation is performed, is called target, and other qubits are called control.

Using a graphical representation, it is possible to draw a quantum circuit for a quantum algorithm - as exemplarily shown in <FIG>. Numbered horizontal lines represent qubits, and quantum gates acting on qubits are placed on corresponding lines. The quantum gates are applied in order from left to right. From the properties of the tensor product according to the above relation (<NUM>), one can conclude that quantum gates acting on disjoint sets of qubits are commute. A set of quantum gates sharing the same horizontal position is called a layer of a quantum circuit.

As already noted above, the universal quantum circuit simulator stores, in a computer memory, an array of <NUM>n complex numbers (coefficients αi from relation (<NUM>)). Using e.g. IEEE754 double precision floating point representation, this requires <NUM> · <NUM>n bytes of memory. One can easily see that the memory requirements very quickly become intractable for a single computer, when the number of qubits grows (e.g. <NUM> qubits require 16TiB of memory). The simulator program in this case has to split the state vector into parts and store in memory of several computers (nodes, as already described above).

Let the quantum simulator operate on n = L + R qubits. Then, if a single computer can store just <NUM>L elements of a state vector, the number of required computer nodes is <NUM>R.

A natural way to select a basis in the above relation (<NUM>) is to assign to a basis state ψi the state, in which qubits are |<NUM>〉 or |<NUM>〉 according to a binary representation of index i. For example: for three qubits there are <NUM> basis states {ψ<NUM>, ψ<NUM>, ψ<NUM>, ψ<NUM>, ψ<NUM>, ψ<NUM>, ψ<NUM>, ψ<NUM>}. In the basis state ψ<NUM>=<NUM> all qubits are in the state |<NUM>〉, in ψ<NUM>=<NUM> the qubit <NUM> in the state |<NUM>〉 and two others in state <NUM>, and in ψ<NUM>=<NUM> qubits <NUM> and <NUM> are in state |<NUM>〉 and qubit <NUM> in state |<NUM>〉.

According to a state vector distribution scheme, it is obvious that every node stores all amplitudes, which determine the probability of |<NUM>〉 and |<NUM>〉 for first L qubits, when states of other R qubits are fixed equal to the binary representation of a node's rank. In this document, the first L qubits are called local qubits and the last R qubits are called global qubits.

When a quantum gate is applied to one or more local qubits, the matrix-vector multiplication is performed on each node locally, and does not require access to amplitudes stored on remote nodes, because other qubits are not affected by the gate. When a quantum gate is applied to one or more global qubits, the matrix-vector multiplication cannot be performed, because a computing node cannot directly access the memory in a remote computer. In this situation, a mechanism of data exchange is required.

A conventional approach proposed a method of qubit reordering when qubits are renumbered and corresponding amplitudes are transferred between nodes and stored in a corresponding node's memory according to new qubit numbers and the node's ranks. This process is called qubits swapping, because qubits and amplitudes exchange their positions, and is illustrated in <FIG>. This method can be used to simulate a quantum gate, which originally is applied to global qubits. In this case one needs just exchange numbers between global qubits involved in an operation and some unused local qubits, then transfer corresponding amplitudes between nodes. After that, the quantum gate acting on local qubits can be simulated.

It is common for distributed computing to use an MPI library to perform a data exchange between nodes, and so express data exchange patterns in the program in terms of MPI operations. The qubit swapping operation can be done using a single MPI_Alltoall operation. Any number of qubits less than or equal to R can be swapped at once. It is easy to show that the amount of transferred amplitudes is equal to <MAT> where k is the number of swapped global qubits. From the above relation (<NUM>), it is obvious that swapping several qubits at once requires less data to transfer than swapping them sequentially one by one.

However, a typical quantum circuit can contain hundreds of thousands of gates. Without any optimization technique, each gate implies a matrix-vector multiplication and in a distributed case, amplitudes must be transferred between nodes a huge number of times. Thus, in the above-described approach, without a careful definition of a set of qubits to swap, there could be an extra overhead for the data exchange if some qubits in a set are not involved into a sufficient number of gates applications. The approach does not provide any suggestions on how to determine optimal set of qubits to reorder.

Another approach describes an open source implementation of a distributed quantum circuit simulator - QuEST. In QuEST, the above-described method of qubit reordering is used, but the implementation is restricted to single qubit swaps only.

The most sophisticated approach to quantum circuit simulation uses a scheduling component (scheduler), which determines the order of gates to be applied and qubits sets to reorder. Gates are reordered into sequences called stages. A stage contains gates acting on local qubits. Inside the stage gates form subsequences called clusters. Gates from the same cluster are fused into a single multi-qubit gate, and this gate is simulated by a single matrix-vector multiplication. Between stages, a qubit reordering occurs.

<FIG> shows an illustration of such clusters of gates and stages. Assuming that qubits <NUM>-<NUM> are local currently and <NUM>-<NUM> are global, the first stage consists of <NUM> clusters of gates outlined by grey lines, and the second stage consists of cluster outlined by black lines. After applying gates for the first stage qubits, reordering occurs: <NUM>, <NUM> are swapped with <NUM>, <NUM>, and then second stage can be applied.

The main problem in implementing this approach is the methods of construction of clusters and stages. The approach does not describe any algorithm, and does also not provide the source code of the scheduler.

<NPL>, discloses minimizing the number of required qubit reorderings (achieved by inserting explicit SWAP gates) when mapping a quantum circuit into a linear nearest neighbor quantum architecture. Qubits interactions of a given circuit are modelled by introducing an interaction graph, and local qubit reorderings are found in order to minimize the number of required SWAP gates. The approach decomposes a given circuit into several clusters (or subcircuits), where each cluster contains consecutive two-qubit gates, and uses the MINLA problem within each subcircuit to find qubit locations for qubits involved in each subcircuit. Intra-cluster SWAP gates are inserted inside each subcircuit to localize the remaining nonlocalized gates. Additional (intercluster) SWAP gates are inserted between consecutive subcircuits to transform one qubit ordering to another to keep circuit functionally unchanged.

In summary, although a main set of methods for quantum circuit simulation is available, including scheduling of gates, gates clusters construction, and qubits reordering, the problem of finding an optimal order of gates and qubits remains unsolved. All previous approaches do not describe any method to calculate qubits and gates permutation according to a well-defined optimality criteria.

In view of the above-mentioned problems and disadvantages, embodiments of the present invention aim to improve the current approaches. An objective is to provide a sophisticated method for gates and qubits permutation calculation for a quantum circuit simulator. This should result in an optimal data exchange and an optimal quantum gate application schedule in a quantum circuit simulator, and should accordingly reduce the amount of data transferred between nodes. The calculated permutations should provide a minimum number of matrix-vector multiplications and a minimum amount of data transfer. To this end, a device and method should be provided, which can be used in distributed quantum circuit simulator for gate scheduling and qubits reordering scheduling.

The objective is achieved by the embodiments of the invention as described in the enclosed independent claims.

In particular, embodiments of the invention propose a device and method, which calculate an optimal data exchange and quantum gate application schedule, and thus significantly reduce the amount of data transferred between nodes, as well as the amount of arithmetical operations to be performed. All of this leads to an increase of quantum circuit simulator performance, particularly up to several times.

The embodiments of the invention base on the understanding that associativity of a tensor product operation allows splitting the relation (<NUM>) into factors in different ways, thus constructing factors according to performance of computation or memory consumption considerations: <MAT>.

The above relation (<NUM>), and commute properties of quantum gates been applied, lay the core of embodiments of the invention optimizing a quantum circuit simulation by means of gate sequence permutation.

Based on an individual gate's properties, and using a greedy algorithm, the device and method calculate specifically a permutation of gates and a permutation of qubits, which lead to a minimum number of clusters in a stage, and minimum number of stages during a quantum circuit simulation.

A first aspect of the invention provides a device for a quantum circuit simulator, the device being configured to: obtain a first sequence of quantum gates, which when executed on the quantum circuit simulator require performing matrix-vector multiplications on the quantum circuit simulator, generate a second sequence of quantum gates, which is a subsequence of the first sequence of quantum gates, by using a first greedy algorithm, with backtracking, calculate a local qubits set and a global qubits set based on the second sequence of quantum gates, generate a set of clusters of quantum gates based on the second sequence of quantum gates,, wherein each cluster includes a subset of the quantum gates of the second sequence of quantum gates merged together by using a second greedy algorithm without backtracking, generate a third sequence of quantum gates, which contains all quantum gates from the second sequence of quantum gates, according to an order of the clusters, provide the local qubits set and the global qubits set to the quantum circuit simulator, and output the third sequence of quantum gates to the quantum circuit simulator. The device is further configured to, when generating the set of clusters of quantum gates: order a cluster including more quantum gates before a cluster including less quantum gates in the order of the clusters.

The calculated sets of local and global qubits are in particular "best" local qubits and global qubits sets. "Best" thereby means the best the algorithm can do. That is, the algorithm searches for many variants of these qubits sets, and may then select qubits sets which have the maximum number of gates in the second sequence. Local qubits sets can be deliberately predefined before running the algorithm by the device of the first aspect. This implies that the algorithm will include quantum gates, which act on these qubits.

The device of the first aspect can be used in a distributed quantum circuit simulator, and may provide gate scheduling and qubits reordering. In other words, the device can provide a sophisticated gates and qubits permutation calculation for the quantum circuit simulator. The calculated permutations allow an optimal data exchange and quantum gate application schedule in a quantum circuit simulator, thus significantly reducing the amount of data transferred between nodes of the simulator.

In an implementation form of the first aspect, the device is further configured to, when generating the set of clusters of quantum gates: generate the clusters based on a maximum possible number of qubits in a cluster.

The above implementation forms lead to an improved efficiency of the algorithm performed by the device of the first aspect.

In an implementation form of the first aspect, the device is further configured to, when generating the set of clusters of quantum gates: pick one-by-one all possible combinations of qubits associated with the second sequence of quantum gates based on the maximum possible number of qubits in a cluster, construct a cluster for each combination, and select the cluster with the greatest number of quantum gates in it.

In an implementation form of the first aspect, the device is further configured to, when generating the set of clusters of quantum gates: maintain a set of locked qubits, include a quantum gate into a cluster, if matrix representation of the quantum gate is diagonal, skip a quantum gate, if at least one of the qubits that quantum gate acts on does not belong to a picked combination of qubits, and/or skip a quantum gate, if at least one of the qubits that quantum gate acts on is in the set of locked qubits, add all qubits a quantum gate acts on to the set of locked qubits, if that quantum gate is skipped, and include a quantum gate into a cluster otherwise.

In an implementation form of the first aspect, the device is further configured to, when generating the set of clusters of quantum gates: determine a cluster including a maximum number of quantum gates, output the quantum gates of the determined cluster, in particular insert the output quantum gates into the third sequence of quantum gates, and remove the output quantum gates from the second sequence of quantum gates.

In an implementation form of the first aspect, the device is further configured to, when calculating the local qubits set and the global qubits set: determine the local qubits set and/or the global qubits set based on a maximum number of local and/or global qubits, respectively.

In an implementation form of the first aspect, the device is further configured to, when generating the second sequence of quantum gates: fuse a quantum gate acting on a single qubit with an adjacent quantum gate in the first sequence of quantum gates acting on a subset of qubits including the same single qubit.

In an implementation form of the first aspect, the device is further configured to, when generating the second sequence of quantum gates: include, into the second sequence of quantum gates, quantum gates that operate on at most the maximum number of local qubits, and if the first sequence of quantum gates includes at least one quantum gate acting on a single qubit and another quantum gate acting on the same qubit and on at least one other qubit, include, into the second sequence of quantum gates, this single-qubit gate together with the other multi-qubit gate.

In an implementation form of the first aspect, the device is further configured to, when generating the second sequence of quantum gates: create a branch of the first greedy algorithm with a quantum gate included into the second sequence of quantum gates, and/or create a branch of the first greedy algorithm with a quantum gate from the first sequence of quantum gates skipped, add all qubits a quantum gate acts on to the set of local qubits, if that quantum gate is included or, add all qubits a quantum gate acts on to the set of locked qubits, if that quantum gate is skipped.

In an implementation form of the first aspect, the device is further configured to, when generating the second sequence of quantum gates: create at most a maximum number of branches of the first greedy algorithm.

In an implementation form of the first aspect, the device is further configured to, when applying a branch of the first greedy algorithm: construct the second sequence of quantum gates with as much gates as possible, and test each gate from the first sequence of quantum gates and skip or include it into the second sequence of quantum gates based on the result of the test.

In an implementation form of the first aspect, the device is further configured to, when generating the second sequence of quantum gates: maintain a set of locked qubits, skip a quantum gate, if application of this quantum gate will require more qubits than a predetermined threshold to be local, and/or skip a quantum gate, if at least one of the qubits the quantum gate operates on is in a locked qubits set, and add all qubits a quantum gate acts on to the set of locked qubits, if that quantum gate is skipped.

In an implementation form of the first aspect, the device is further configured to, when generating the second sequence of quantum gates: include a quantum gate into the second sequence of quantum gates, if a matrix representation of that quantum gate is diagonal and do not add qubits a quantum gate acts on to the set of local qubits, and/or include a quantum gate into the second sequence of quantum gates, if all qubits that quantum gate operates on are already in the local qubits set.

In an implementation form of the first aspect, the device is further configured to, when calculating the local qubits set and the global qubits set: construct a set of all qubits, on which quantum gates from the first sequence of quantum gates act, include, in the local qubits set, all qubits on which quantum gates from the second sequence of quantum gates act, and include, in the global qubits set, all qubits which are in the set of all qubits and not in the local qubits set.

A second aspect of the invention provides a quantum circuit simulator comprising the device according to the first aspect or any of its implementation forms.

A third aspect of the invention provides a computer-implemented method for quantum gate and qubit scheduling for a quantum circuit simulator, the method comprising: obtaining a first sequence of quantum gates, which when executed on the quantum circuit simulator require performing matrix-vector multiplications on the quantum circuit simulator, generating a second sequence of quantum gates, which is a subsequence of the first sequence of quantum gates, by using a first greedy algorithm, with backtracking, calculating a local qubits set and a global qubits set based on the second sequence of quantum gates, generating a set of clusters of quantum gates based on the second sequence of quantum gates, wherein each cluster includes a subset of the quantum gates of the second sequence of quantum gates merged together by using a second greedy algorithm without backtracking, generating a third sequence of quantum gates, which contains all quantum gates from the second sequence of quantum gates, according to an order of the clusters, providing the local qubits set and the global qubits sets to the quantum circuit simulator, and outputting the third sequence of quantum gates to the quantum circuit simulator. The generating the set of clusters of quantum gates further comprises ordering a cluster including more quantum gates before a cluster including less quantum gates in the order of the clusters.

A fourth aspect of the invention provides a computer program product comprising a program code that, when executed on a computer, carries out, the method according to the third aspect or any of its implementation forms. all qubits a quantum gate acts on to the set of locked qubits, if that quantum gate is skipped, and including a quantum gate into a cluster otherwise.

In an implementation form of the fourth aspect, the method further comprises, when generating the set of clusters of quantum gates: determining a cluster including a maximum number of quantum gates, outputting the quantum gates of the determined cluster, in particular inserting the output quantum gates into the third sequence of quantum gates, and removing the output quantum gates from the second sequence of quantum gates.

In an implementation form of the fourth aspect, the method further comprises, when calculating the local qubits set and the global qubits set: determining the local qubits set and/or the global qubits set based on a maximum number of local and/or global qubits, respectively.

In an implementation form of the fourth aspect, the method further comprises, when generating the second sequence of quantum gates: fusing a quantum gate acting on a single qubit with an adjacent quantum gate in the first sequence of quantum gates acting on a subset of qubits including the same single qubit.

In an implementation form of the fourth aspect, the method further comprises, when generating the second sequence of quantum gates: including, into the second sequence of quantum gates, quantum gates that operate on at most the maximum number of local qubits, and if the first sequence of quantum gates includes at least one quantum gate acting on a single qubit and another quantum gate acting on the same qubit and on at least one other qubit, including, into the second sequence of quantum gates, this single-qubit gate together with the other multi-qubit gate.

In an implementation form of the fourth aspect, the method further comprises, when generating the second sequence of quantum gates: creating a branch of the greedy algorithm with a quantum gate included into the second sequence of quantum gates, and/or creating a branch of the greedy algorithm with a quantum gate from the first sequence of quantum gates skipped, adding all qubits a quantum gate acts on to the set of local qubits, if that quantum gate is included or, adding all qubits a quantum gate acts on to the set of locked qubits, if that quantum gate is skipped.

In an implementation form of the fourth aspect, the method further comprises, when generating the second sequence of quantum gates: creating at most a maximum number of branches of the greedy algorithm.

In an implementation form of the fourth aspect, the method further comprises, when applying a branch of the greedy algorithm: constructing the second sequence of quantum gates with as much gates as possible, and testing each gate from the first sequence of quantum gates and skip or include it into the second sequence of quantum gates based on the result of the test.

In an implementation form of the fourth aspect, the method further comprises, when generating the second sequence of quantum gates: maintaining a set of locked qubits, skipping a quantum gate, if application of this quantum gate will require more qubits than a predetermined threshold to be local, and/or skipping a quantum gate, if at least one of the qubits the quantum gate operates on is in a locked qubits set, and adding all qubits a quantum gate acts on to the set of locked qubits, if that quantum gate is skipped.

In an implementation form of the fourth aspect, the method further comprises, when generating the second sequence of quantum gates: including a quantum gate into the second sequence of quantum gates, if a matrix representation of that quantum gate is diagonal and not adding qubits a quantum gate acts on to the set of local qubits, and/or include a quantum gate into the second sequence of quantum gates, if all qubits that quantum gate operates on are already in the local qubits set.

In an implementation form of the fourth aspect, the method further comprises, when calculating the local qubits set and the global qubits set: constructing a set of all qubits, on which quantum gates from the first sequence of quantum gates act, including, in the local qubits set, all qubits on which quantum gates from the second sequence of quantum gates act, and including, in the global qubits set, all qubits which are in the set of all qubits and not in the local qubits set.

<FIG> shows a device <NUM>. The device <NUM> is suitable for a quantum circuit simulator <NUM>. The device <NUM> may be part of the quantum circuit simulator <NUM>, or may be connected to the quantum circuit simulator <NUM>. The device <NUM> is in particular configured to schedule quantum gates and qubits for the quantum circuit simulator <NUM>, in order to improve the performance of the quantum circuit simulator. The quantum circuit simulator <NUM> may be one or more classical computers or computer nodes, which are together configured to simulate the execution of a quantum circuit on a quantum computer. The quantum circuit simulator <NUM> may include at least one device <NUM>, or may work together with at least one device <NUM>.

The device <NUM> is configured to obtain a first sequence <NUM> of quantum gates, e.g. according to a quantum circuit received as an input to the device <NUM>. The quantum circuit may be a quantum circuit to be simulated on/by the quantum circuit simulator <NUM>. The device <NUM> is further configured to generate a second sequence <NUM> of quantum gates, which is a subsequence of the first sequence <NUM> of quantum gates. The device <NUM> thereby uses a greedy algorithm, in particular with backtracking. That is, the second sequence of quantum gates <NUM> is generated based on the first sequence <NUM> of quantum gates using a greedy algorithm with backtracking.

Further, the device <NUM> is configured to calculate a local qubits set 103a and a global qubits set 103b, respectively, based on the generated second sequence <NUM> of quantum gates. These qubits sets may be referred to as optimal or final qubits sets. In addition, the device <NUM> is also adapted to generate a set of clusters <NUM> of quantum gates, wherein each cluster <NUM> includes a subset of the quantum gates of the second sequence <NUM> of quantum gates, which are merged together by using a greedy algorithm. The greedy algorithm may be similar in nature to the greedy algorithm used for generating the second sequence <NUM>. Then, the device <NUM> is configured to generate a third sequence <NUM> of quantum gates, which contains all quantum gates from the second sequence <NUM> of quantum gates, according to an order of the clusters <NUM> of quantum gates.

Finally, the device <NUM> is configured to provide the local qubits set 103a and the global qubits set 103b to the quantum circuit simulator <NUM>, and to also output the third sequence <NUM> of quantum gates to the quantum circuit simulator. Based on these inputs, the quantum circuit simulator <NUM> can simulate the quantum circuit with less data required to be transferred between multiple nodes of the simulator <NUM>, as well as with less arithmetical operations performed.

Notably, in the device <NUM> of <FIG>, the generating of the clusters <NUM> of quantum gates and the generation of the third sequence <NUM> of quantum gates may be referred to as cluster scheduling algorithm. This algorithm allows the device <NUM> to perform the quantum gate scheduling for the simulator <NUM>. The calculation and outputting of the qubits sets 103a and 103b may be referred to as a stage scheduling algorithm. This algorithm allows the device <NUM> to perform qubit scheduling for the simulator <NUM>.

<FIG> shows a pseudocode of a cluster scheduling algorithm that can be performed by the device <NUM>, in particular by the device <NUM> of <FIG>, in order to generate the sets of clusters <NUM> and output the third sequence <NUM> of quantum gates. <FIG> further shows a block scheme of the cluster scheduling algorithm.

The cluster scheduling algorithm has two parameters: "qubits", i.e. the set of all qubits involved in an input sequence of quantum gates; and k, which is the maximum possible number of qubits in a cluster <NUM>. The algorithm further takes a sequence of quantum gates as an input (i.e. in particular the second sequence <NUM> of quantum gates).

The algorithm further merges quantum gates into clusters <NUM> of quantum gates. It thereby tries to minimize a total number of clusters <NUM> generated. Further, the algorithm uses a greedy approach, which: a) finds a cluster <NUM> with a maximum number of quantum gates included; b) returns the cluster <NUM> as a result; and removes the cluster's <NUM> quantum gates from the input sequence of quantum gates; and c) proceeds again with a).

At step <NUM>, the algorithm may pick all possible combinations of k qubits one by one, may generate a sequence of quantum gates containing only qubits from this combination that could be merged in one cluster <NUM>, and may pick the largest size list as next cluster <NUM>. The device <NUM> can further perform an immediate fusing of single-qubit quantum gates. A single-qubit quantum gate g acting on a qubit q does not change the total number of stages, if there exists at least one multi-qubit gate acting on qubit q. Thus, this quantum gate g can be immediately fused (merged) to/with any of its neighboring quantum gates containing the qubit q. This optimization is beneficial for significantly speeding up a stage scheduling algorithm, which can be performed by the device <NUM> and is described next.

<FIG> shows a pseudocode of a stage scheduling algorithm that can be performed by the device <NUM>, in particular by the device <NUM> of <FIG>, in order to schedule and output qubits. <FIG> shows a block scheme of the stage scheduling algorithm.

The stage scheduling algorithm has two parameters: Lmax, which is the maximum number of local qubits; and Bmax, which is a maximum number of branches to create. The algorithm takes a list of quantum gates as input. The algorithm returns a set 103a of qubits, which have to be local during current stage. The algorithm thereby tries to minimize the total number of stages. The algorithm, in particular, uses a greedy approach, i.e. it constructs the stage, which contains as much quantum gates as possible. The algorithm may also backtrack on a sequence of quantum gates and may maintain: a) locals, i.e. a set of qubits wanted to be local during the stage; b) locked, i.e. a set of locked qubits (qubits with some operation skipped); c) B, i.e. a maximum possible number of new branches in this branch of backtracking; and d) N, i.e. a number of taken quantum gates in this stage.

The process of the algorithm may be specifically according to the following case analysis:.

When the algorithm skips a gate, all its qubits may become locked. When the algorithm decides to apply a non-diagonal gate, all its qubits may be required to be local. If all qubits become locked during the backtracking, the algorithm may return to the previous level of recursion.

Some of the qubits could be kept local deliberately, e.g. by prepopulating locals set of qubits before starting the algorithm. This can allow other optimizations to be performed in the simulator <NUM>, due to regulation of memory placement layout of amplitudes to be swapped.

<FIG> shows, in (a), results of the method performed by the device <NUM>. The device <NUM> has been tested with <NUM> global qubits and a different numbers of total qubits. According to resulting permutation between stages, a swap of all global qubits with the same number of local qubits has been applied.

A quantum circuit simulator <NUM>, i.e. including a device <NUM> as shown in <FIG>, is compared with the QuEST simulator, in particular with a QuEST simulator on an <NUM>-nodes cluster, in (b) of <FIG>. The simulator <NUM> demonstrates an order of magnitude better performance, due to a reduction of the number of matrix-vector multiplications. This is, because of the cluster stage algorithm/method performed by device <NUM>, and the reduction of the amount of data transfer due to stage scheduling algorithm/method.

<FIG> shows a method <NUM>. The method <NUM> is for quantum gate and qubit scheduling for a quantum circuit simulator <NUM>. The method <NUM> may be performed by the device <NUM> of <FIG>, or by a quantum circuit simulator <NUM> including such a device <NUM>.

The method comprises: a step <NUM> of obtaining a first sequence <NUM> of quantum gates; a step <NUM> of generating a second sequence <NUM> of quantum gates, which is a subsequence of the first sequence <NUM> of quantum gates, by using a greedy algorithm, in particular with backtracking; a step <NUM> of calculating a local qubits set 103a and a global qubits set 103b based on the second sequence <NUM> of quantum gates; a step <NUM> of generating a set of clusters <NUM> of quantum gates, wherein each cluster <NUM> includes a subset of the quantum gates of the second sequence <NUM> of quantum gates merged together by using a greedy algorithm; a step <NUM> of generating a third sequence <NUM> of quantum gates, which contains all quantum gates from the second sequence <NUM> of quantum gates, according to an order of the clusters <NUM>; a step <NUM> of providing the local qubits set 103a and the global qubits set 103b to the quantum circuit simulator <NUM>; and a step <NUM> of outputting the third sequence <NUM> of quantum gates to the quantum circuit simulator <NUM>.

Claim 1:
Device (<NUM>) for a quantum circuit simulator (<NUM>), the device (<NUM>) being configured to:
obtain a first sequence (<NUM>) of quantum gates, which when executed on the quantum circuit simulator (<NUM>) require performing matrix-vector multiplications on the quantum circuit simulator (<NUM>),
generate a second sequence (<NUM>) of quantum gates, which is a subsequence of the first sequence (<NUM>) of quantum gates, by implementing a first greedy algorithm with backtracking,
calculate a local qubits set (103a) and a global qubits set (103b) based on the second sequence (<NUM>) of quantum gates,
generate a set of clusters (<NUM>) of quantum gates based on the second sequence (<NUM>) of quantum gates, wherein each cluster (<NUM>) includes a subset of the quantum gates of the second sequence (<NUM>) of quantum gates merged together by implementing a second greedy algorithm without backtracking,
generate a third sequence (<NUM>) of quantum gates, which contains all quantum gates from the second sequence (<NUM>) of quantum gates, according to an order of the clusters (<NUM>),
provide the local qubits set (103a) and the global qubits set (103b) to the quantum circuit simulator (<NUM>), and
output the third sequence (<NUM>) of quantum gates to the quantum circuit simulator,
wherein the device (<NUM>) is further configured to, when generating the set of clusters (<NUM>) of quantum gates:
order a cluster (<NUM>) including more quantum gates before a cluster (<NUM>) including less quantum gates in the order of the clusters (<NUM>).