• 专利附录
  • 专利说明
  • 权利要求
  • 类似技术
  • 同族专利
  • 引用文献
  • 法律状态
  • 优先权
    • 专利摘要:
    A method of optimizing a quantum circuit composed of an ordered series of quantum gates applied to an initial arrangement of qubits values, comprising inserting a set local SWAP doors, so that all the doors of the circuit are local, including steps consisting of: - for each door of the series, if this is not local, insert a set of local SWAP gate, - determine (S4) the set of permutations, each consisting of a succession of qubit-value inversions along the shortest paths between associated qubit positions. At the door, and, - choose (S5) from the set of permutations, a permutation minimizing a cost representing the number of interversions needed to make the doors of a suite within the home more local. Of substantially smaller size; - restore (S7) the initial arrangement by establishing a tree covering a graph representative of the arrangement of the qubits of the circuit, and performing inversions of qubits values along paths of the tree.
    公开号:FR3072483A1
    申请号:FR1759684
    申请日:2017-10-16
    公开日:2019-04-19
    发明作者:Simon Martiel；Elise Rubat Ciagnus
    申请人:Bull SA；
    IPC主号:
    专利说明:

    OPTIMIZATION OF AN ANTIQUE CIRCUIT BY INSERTING SW AP DOORS
    FIELD OF THE INVENTION
    The present invention relates to the field of quantum computers. More precisely, it concerns the optimization of a quantum circuit so that all of the gates that compose it are local.
    BACKGROUND OF THE INVENTION
    A quantum circuit uses the quantum properties of matter, such as the superposition of states, and entanglement, in order to perform operations on the data. Unlike a conventional computer that manipulates binary data, or "bits", a quantum circuit works on qubits, or quantum bits, which represent a quantum state based on two basic states: 0> and 1>
    First algorithms for quantum calculators appeared in the 1990s. A particularly emblematic algorithm and at the origin of a certain craze for quantum calculators and the Shor algorithm for polynomial computation, described in PW Shor, "Algorithm for quantum computation: discrete logarithms andfactoring ”, in Foundations of Computer Science, pages 124-134, 1994.
    In general, a quantum circuit can be considered as a succession of operators, or quantum gates, applied to a set of qubit. FIG. 1 illustrates a simple quantum circuit, comprising 4 qubits ql, q2, q3, q4 arranged in line. Conventionally, qubits are represented in the form of horizontal lines. The direction from left to right is time. In this figure, 3 quantum gates Gl, G2, G3 make up the circuit and therefore apply over time according to a succession Gl then G2 then G3.
    A quantum gate can involve one or more qubits. They can be of different natures and each represents a cost linked to the time of propagation of the signal or time of passage of the door. Among the doors conventionally used, there may be mentioned the “swap” door Gl which inverts two qubit values.
    The layout of a quantum circuit implementing an algorithm often results from more or less automatic generation processes. The quantum circuit is then described independently of the physical infrastructure on which it is to be deployed.
    In particular, these “theoretical” quantum circuits assume that all of the qubits can interact with each other. Thus, in the example of FIG. 1, the quantum gate G2 makes the qubits ql and q4 interact, while these are not neighboring, but separated by the qubits q2 and q3.
    However, the development of physical infrastructure for quantum computers has revealed physical constraints. Among these constraints, a so-called “locality” constraint means that most infrastructures only allow interactions between close qubits. This locality constraint is imposed by the physical mechanisms used to implement qubits and quantum gates. Thus, a quantum gate such as the gate G2 in FIG. 1 cannot therefore be deployed directly on this type of architecture.
    Some classical algorithms, such as the Shor algorithm, can be optimized allowing them to be implemented on architectures subject to the locality constraint. But in general, as said before, the arrangements of quantum circuits are synthesized, automatically or not, without taking this constraint into account. There therefore appears to be a need for methods and tools to optimize such a circuit, that is to say to transform a circuit independent of the physical infrastructure into a circuit respecting the locality constraint and functionally equivalent.
    Several methods have been proposed which, in general, rely on the insertion of local “SWAP” doors. By inserting Swap gates upstream of a given quantum gate, we can invert qubits so as to make this quantum gate local.
    Figures 2a, 2b, 2c illustrate this problem. FIG. 2a represents a quantum circuit not optimized for a network of 4 qubits ql, q2, q3, q4 arranged in line. There are several nonlocal quantum gates, that is to say causing non-adjacent qubits to interact. Quantum gates are represented by vertical segments with junctions with the lines of qubits on which they act. The graphics of these junctions (points, circles ...) correspond to the type of quantum gate and the type of action on these qubits.
    Figures 2b, 2c show two possible optimizations of this circuit by inserting quantum swap gates, each making local gates. Swap doors are shown with crosses as terminals.
    However, each Swap quantum gate insertion represents a cost, linked in particular to the time it takes to pass through the gate. It is therefore important to determine which of the optimized equivalent circuits minimizes this additional cost.
    Finding an optimal solution to this problem is not possible because there is an exponential number, in number of qubits and gates, of functionally equivalent circuits and respecting the locality constraint.
    Different solutions to this problem have been proposed. We can for example cite the master's thesis "An efficient method to convert arbitrary quantum circuits to ones on a Linear Nearest Neighbor architecture" by Yuichi Hirata, defended at the Institute of Science and Technology of Nara, Japan. We can also cite the article "Depth-optimal Quantum Circuit Placement for Arbitrary Topologies" by Bhattacharjee Debyoti and Chattopadhyay Anupam, from Nanyang Technological University, 2017. We can also cite the article "Optimal SWAP Gâte Insertion for Nearest Neighbor Quantum Circuits" by Robert Wille, Aaron Lye and Rolf Drechsler, in Design Automation Conférence (ASP-DAC), 2014 19th Asia and South Pacifie
    But these solutions are very slow to find a solution since they seek the globally optimal solution. As soon as the number of qubits and gates becomes large, within the framework of a complex algorithm, the determination of the quantum circuit representing a global optimum is no longer possible, and these prior art solutions become unusable in practice .
    Other families of solutions aim to solve the problem in a more framed framework of a given physical infrastructure, in order to limit the combinatorics.
    The invention aims to propose a solution which can both apply to various physical infrastructures and achieve performance allowing its effective exploitation for large numbers of qubits and quantum gates.
    SUMMARY OF THE INVENTION
    The object of the present invention is to provide a solution which at least partially overcomes the aforementioned drawbacks.
    To this end, the present invention proposes a method for optimizing a quantum circuit composed of an ordered series of quantum gates applied to an initial arrangement of qubit values, consisting in inserting a set of local SW AP gates, so that all the doors of said quantum circuit are local, comprising steps consisting in:
    for each quantum gate of said series, if it is not local, insert a set of local SWAP gateways before said quantum gate, determine the set of permutations, each consisting of a succession of reversals of qubit values along the shortest paths between the qubit positions associated with said quantum gate, and choosing from said set of permutations, a permutation minimizing a cost representing the number of conversions necessary to make the quantum gates of a sequence within said series, the size of said series being substantially smaller than that of said series;
    restore said initial arrangement by establishing a tree covering a graph representative of the arrangement of the qubits of said circuit, and by carrying out reversals of qubit values along paths of said tree.
    According to preferred embodiments, the invention comprises one or more of the following characteristics which can be used separately or in partial combination with one another or in total combination with one another: the determination of the set of permutations is carried out by determining a succession of of qubit values along the first shortest paths between any pair of qubit positions associated with said quantum gate, then, if said quantum gate has more than two associated qubit positions, by determining a succession of inversions of qubit values along the second shortest paths between each of the positions outside those already considered, and the first shortest paths already determined;
    said cost takes into account a cost attached to each type of SWAP door to be inserted;
    the restoration of the initial arrangement is carried out according to a token exchange algorithm;
    said token exchange algorithm is that described in paragraph 3.2 of the article “Swapping Labeled Tokens on Graph” by K. Yamanaka, ED Demaine, T. Ito, J. Kawahara, M. Kiyomi, Y. Okamoto, T. Saitô, A. Suzuki, K. Uchizawa and T. Uno;
    the size of said series is between 3 and 5;
    said shortest paths are determined by precomputing the shortest paths between the set of vertices of said graph; said shorter paths are calculated by the Dij sktra algorithm.
    Another object of the invention relates to a computer program comprising instructions which, when executed by a processor of a computer system, entail the implementation of a method as defined above.
    Another object of the invention is a platform for optimizing a quantum circuit composed of an ordered series of quantum gates applied to an initial arrangement of qubit values, consisting in inserting a set of local SW AP gates, so that all the doors of said quantum circuit are local, comprising digital processing means for each quantum gate of said series, if this is not local, insert a set of local SWAP doors before said quantum gate, determine the set of permutations, each consisting of a succession of reversals of qubit values along the shortest paths between the qubit positions associated with said quantum gate, and choosing from said set of permutations, a permutation minimizing a cost representing the number of conversions necessary to make the quantum gates of a sequence within said series local, the size of said sequence is ant substantially lower than that of said series;
    restore said initial arrangement by establishing a tree covering a graph representative of the arrangement of the qubits of said circuit, and by carrying out reversals of qubit values along paths of said tree.
    Other characteristics and advantages of the invention will appear on reading the following description of a preferred embodiment of the invention, given by way of example and with reference to the accompanying drawings.
    BRIEF DESCRIPTION OF THE DRAWINGS
    FIG. 1 schematically represents an example of a simple quantum circuit according to the state of the art.
    FIGS. 2a, 2b, 2c schematically represent an example of a quantum circuit and two possible optimizations by inserting Swap doors, according to the state of the art.
    FIG. 3 represents a schematic flowchart according to an embodiment of the invention.
    FIGS. 4a and 4b schematically represent an example of a graph relating to the arrangement of qubits, according to an embodiment of the invention.
    FIGS. 5a to 5d also represent a graph relating to the arrangement of the qubits, and various steps for passing from one arrangement to another.
    Figure 6 shows schematically a tree structure for the choice of a permutation, according to an embodiment of the invention.
    FIGS. 7a to 7d schematically illustrate steps for reversing qubits on an example of a graph, to go from one arrangement to another.
    DETAILED DESCRIPTION OF THE INVENTION
    The invention therefore aims to optimize a quantum circuit consisting of a set of qubit and a set of quantum gates in order to make the latter local. Obviously, the quantum circuit resulting from this optimization must be functionally equivalent, that is to say provide an identical output for a given input.
    Such an optimized quantum circuit can then be implemented on any physical infrastructure, in particular an infrastructure imposing a locality constraint for the quantum gates.
    Recall that we call "local" the fact of making adjacent qubits interact in the underlying topological arrangement. A door is therefore called "local" if the qubits that it must make interact at the input are adjacent. This notion is well known to those skilled in the art now, and more or less formalized definitions can be found in the literature.
    FIG. 3 represents a flowchart describing a possible implementation of the method according to the invention.
    At the input of this algorithm, there is a data structure describing a qubit arrangement. This structure can be a simple vector in the case of a line arrangement, but it can be more complex for other types of arrangement.
    The first step SI is a preliminary step consisting in determining a graph representative of the arrangement of the qubits of the quantum circuit to be optimized. The vertices of the graph represent the positions of the qubits and the edges represent the neighborhood relationships between the positions of the qubits.
    We distinguish here between the positions of qubits and the values of qubits. The position within the physical infrastructure where a qubit is located is called position. Following a SWAP gate, for example, the values of two qubit positions are exchanged. In FIGS. 1, 2a, 2b, 2c, the qubit positions represent the horizontal lines, while they can move between the lines and be modified due to the quantum gates.
    The graph determined at the end of this step SI is invariant in its topology throughout the optimization process which will be described. However, these nodes, which correspond to qubit positions, carry the value of the qubits which will evolve over the course of the conversions.
    FIG. 4a represents a graph of a simple arrangement, in line, of 4 positions qO, ql, q2, q3 having respectively the values 0, 1, 2, 3, 4. After application of a swap gate between the positions qO and ql, the graph becomes as shown in FIG. 4b.
    FIG. 5a represents a graph of a more complex topological arrangement of 10 positions qO, ql, q2, q3, q4, q5, q6, q7, q8, q9. The edges show the adjacencies and the labels next to each position the respective values.
    Step S2 is another preprocessing step consisting in calculating the shortest path between each pair of vertices of the graph.
    These shorter paths will be used in the rest of the process. Insofar as this method is iterative, it is advantageous to pre-calculate these shorter paths upstream of the iterative loop S3-S6, rather than to calculate them with several iterations during the loop.
    The shortest path between two vertices can be calculated according to several embodiments. One possible algorithm is the Dijsktra algorithm. This algorithm is one of the algorithms well known to those skilled in the art. It is for example described in any general algorithm manual, and on the wikipedia page:
    https://fr.wikipedia.org/wiki/Algorithme_de_Dijkstra
    This pre-calculation has a quadratic complexity in number of qubits, but allows then to be able to estimate in constant time the cost of "localization" of a quantum gate, that is to say the number and the cost of the Swap gates. to insert to make a door local. We can thus obtain the doors to be inserted in a linear time in number of qubits.
    The loop S3-S6 is iterated for each of the quantum gates i of the circuit, which we seek to make local.
    In a step S3, it is verified that the quantum gate i is local or not. If it is already local (which is obviously the case for the doors implying a single qubit), then we consider the following quantum door, by iterating the counter i.
    In a step S4, a set of possible permutations is created making it possible to make the quantum gate i local. We call permutation a bijection of the set of qubits on itself.
    Each permutation can be seen as the result obtained by a series of reversals of the qubit values from two adjacent positions (i.e. a series of Swap gates).
    According to an implementation of the invention, one does not search for all of the possible permutations, but one uses a heuristic making it possible to determine a subset thereof. The heuristic chosen makes it possible to guarantee that this subset is relevant and makes it possible to determine, in fine, a satisfactory solution for optimizing the circuit in its entirety.
    To do this, it is proposed to consider the shortest paths between the qubits concerned by the quantum gate. If the quantum gate is a gate involving two qubits, we consider only these two; if the quantum gate is a gate involving more qubits, we consider any pair of qubits among them.
    For a pair of qubits concerned by said quantum gate, we create the set of possible permutations, each obtained by a succession of qubit reversals located on the shortest path between the qubits of the pair, and making it possible to make local the quantum gate i.
    In the example of FIG. 5a, we consider a quantum gate i implying the positions of qubits ql, q6, q8. We choose, arbitrarily (which can be random) the pair ql, q8.
    We then determine the shortest path on the graph between these two qubit positions. This shortest path is [ql, q2, q3, q8]
    We then create the set of successions of inversions between two adjacent qubits located on this path which make adjacent the qubits initially located at positions ql and q8.
    3 permutations are thus determined, each of which can be obtained by 2 qubit conversions:
    - [1, 3, 9, 2, 6, 0, 8, 5, 7, 4], resulting from the inversions (q8, q3) and (q3, q2);
    - [1, 2, 3, 9, 6, 0, 8, 5, 7, 4], resulting from the inversions (q8, q3) and (ql, q2);
    - [1, 2, 7, 3, 6, 0, 8, 5, 9, 4], resulting from the inversions (ql, q2) and (q2, q3).
    Figures 5b, 5c and 5d show diagrams of topological arrangement corresponding, respectively, to these 3 permutations applied to the example of Figure 5a as an initial state.
    We see that the values 3 and 9, initially located on the positions ql and q8, respectively, are now adjacent, in these 3 permutations.
    If the quantum gate i concerned only these 2 qubits, the work would stop there: the values 3 and 9 being adjacent, they can interact locally.
    As the quantum gate i of the example concerns a third qubit of value 8 in position q6, the process continues by considering the shortest path between this position q6 and the pair of positions where the values 3 and 9 are located, c ' ie ql, q2 in Figure 5b, q2, q3 in Figure 5c and q3, q8 in Figure 5c. The pair of positions where the qubit values 3 and 9 are located are indicated with a thicker line. The shortest paths are represented by a dotted line.
    In the same way as previously, we then create, for each of the permutations obtained previously, the set of series of inversions between two adjacent qubits located on this path which make adjacent the qubits initially located at positions q6 and ql or q2, or either q2 or q3, or q3 or q8, respectively. These additional series can be added to the successions of reversals previously obtained.
    In this example, the shortest path to the third qubit is of length 2: a single reversal is therefore necessary on this shortest path. Consequently, the number of successions of possible inversions making it possible to obtain the 3 permutations remains of 3:
    - [8, 3, 9, 2, 6, 0, 1, 5, 7, 4], resulting from the inversions (q8, q3), (q3, q2) and (q6, qO);
    - [1, 2, 3, 9, 6, 0, 5, 8, 7, 4], resulting from the inversions (q8, q3), (ql, q2) and (q6, q7);
    - [1, 2, 7, 3, 6, 0, 5, 8, 9, 4], resulting from the inversions (ql, q2), (q2, q3) and (q6, q7).
    Each reversal thus applied corresponds to the insertion of a quantum gate of the Swap type.
    It should be noted that this way of doing things is not optimal, in the case of a quantum gate with 3 qubits. In practice, however, most gates are one or two qubits, so the non-optimal contribution of a 3 qubit gate has little impact on the optimization of a whole quantum circuit.
    For each permutation, an associated cost can be calculated. This cost corresponds to the number of Swap quantum gates inserted (therefore to the number of inversions), possibly weighted by a cost per stop of the graph. It can be more or less expensive to swap qubits on certain positions, due to the underlying physical infrastructure.
    This cost C can then be expressed:
    in which Sij represents a number of Swap gates inserted between positions i and j, and pi, j the weight ed stops i, j of the graph, that is to say a cost associated with an inversion of the qubits between the positions i and j.
    In a step S5, a choice is made from the permutations determined in the previous step S3, as a function of a cost. This cost may be the cost C calculated above which we seek to minimize
    Preferably, however, the cost used for the choice is a cost cumulating the costs determined for the different inversions for a certain number w of following quantum gates in the ordered series constituting the quantum circuit.
    In other words, it is a question in this step S5 of choosing the permutation minimizing this cost representing the number of necessary inversions (and possibly their weights pij) to localize the quantum gates of a sequence of length w within the series of doors constituting the quantum circuit.
    Figure 6 shows schematically such a tree structure. The node No represents the initial position of figure 5a. The nodes Ni, N2, N3 represent the 3 permutations corresponding respectively to Figures 5b, 5c, 5d and to the gate i. In order to choose between these 3 permutations, permutations N4, N5, Νό,.,. Νζ are determined for the gates i + 1 and i + 2 (with w = 2), and the costs associated with each permutation are calculated. These costs are cumulated on each path going from one of the permutations Ni, N2 N3 to a sheet. Ultimately, the node associated with the lowest cost can be chosen.
    It should be noted that this is a heuristic based on local optimization, the number of gates w of which is a parameter.
    It defines a depth of a calculation tree, and its determination fixes a compromise between a global search on the entire circuit which would lead to a combinatorial explosion, and a very local search (w = l, w = 2 ..) which would lead to a satisfactory but not optimal final solution.
    The choice of the parameter w can be made experimentally, for example by carrying out a battery of tests on a varied set of quantum circuits. This set of circuits can in particular be obtained randomly.
    Experimentally, it appeared that w = 4 formed a good compromise between the quality of the approximation and the computation time.
    In a step S6, once this choice has been made, it is possible to update data structures, stored in a memory, which will provide the solution at the end of the last iteration of the loop S3-S5.
    In particular, we can update
    The number of Swap doors to insert: nbtotal (i) = nbtotal (il) + nb (i). It is simply a question of adding the number of qubit conversions in the permutation chosen for the current quantum gate i, to a total number calculated for the previous gate i-1.
    The list of Swap doors to insert: listetotale (i) = listetotale (il) + liste (i). It is a question of adding together the intersections which have just been determined for the current door i to the set of all the interverions already determined up to the previous door i-1.
    Finally, the data structure representing the layout of the circuit is updated by taking as a new value that of the permutation chosen.
    If for example the permutation corresponding to the node N2 is chosen, these value structures will have for value, at the end of the iteration corresponding to this gate i:
    Nb (i) = 3
    List (i) = {(q8, q3), (ql, q2) and (q6, q7)}
    And as an arrangement: [1, 2, 3, 9, 6, 0, 5, 8, 7, 4],
    The method can then loop back to step S3, in a following iteration consisting in considering the quantum gate i + 1. The quantum gates of the ordered series forming the quantum circuit are thus treated successively.
    When the last quantum gate of the circuit is reached (i = N), the process continues with a step S7 consisting in restoring the initial arrangement of the qubits.
    This step S7 therefore aims to determine a set of insertions of quantum gates of Swap type allowing, from the permutation obtained for the last iteration of the loop S3-S5 (that is, for i = N) to return to the initial arrangement. . We also seek to minimize the cost associated with these insertions.
    This technical problem can be solved in different ways can be reduced to a general token swapping problem which was described in the article "Swapping Labeled Tokens on Graph" by K. Yamanaka, ED Demaine, T. Ito, J. Kawahara, M. Kiyomi, Y. Okamoto, T. Saitô, A. Suzuki, K. Uchizawa and T. Uno, in Fun with Algorithms (2014): 364-375.
    It has been shown that there is at least one solution, whatever the arrival and departure states, which consists of a succession of token exchanges (or of adjacent qubit reversals, in the equivalent case which interests us) .
    However, since this token exchange problem is NP-complete, it turns out in practice that it is impossible to determine the optimal solution, that is to say which gives a minimum number of exchanges. The article mentioned above therefore proposes a heuristic method for determining an approximate solution.
    Figures 7a, 7b, 7c, 7d are taken from the article mentioned above and illustrate a series of token exchanges (or qubit conversions) between an arrangement fo and an arrangement ft within a graph comprising 6 nodes (or qubit positions), vo, vi, V2, V3, V4, vs, V6, on which are placed 6 tokens (or qubits).
    FIG. 7a represents an initial arrangement fo which can correspond to the last permutation of qubits obtained in step S5 for the last quantum gate i = N. FIG. 7d represents a final arrangement ft which corresponds to the initial arrangement of the qubits, such as for example available in steps S1, S2.
    Figures 7b, 7c represent two intermediate steps in the shortest path among the successions of token exchanges leading from fo to ft: a first exchange between tokens 5 and 1 (initially in positions V4 and vj respectively) gives the arrangement illustrated in Figure 7b; a second exchange between tokens 4 and 1 (respectively in positions vi and V4 gives the arrangement illustrated in FIG. 7c; then the last exchange between tokens 16 and 3 (respectively in positions V3 and vô) gives the final arrangement ft.
    The article "Swapping Labeled Tokens on Graph" mentioned above describes several methods of solving such a technical problem in the case of token exchanges.
    In the context of qubit conversions, we first create a tree covering (or "covering") the graph representative of the arrangement of qubits.
    We call tree covering a tree included in this graph and which connects all the vertices of the graph.
    Among the different trees covering, we choose the one whose sum of the weights on the edges is minimal. If the qubit inversions, i.e. the Swap quantum gates, all have the same weight (or cost), then this problem comes down to a simple journey in depth in the graph.
    Otherwise, existing algorithms for determining spanning trees can be used. Among these algorithms, we can notably cite Kruskal's algorithm. A presentation of this algorithm can be found on the participatory encyclopedia Wikipedia website:
    https://fr.wikipedia.org/wiki/Algorithme_de_Kruskal and https://en.wikipedia.org/wiki/Kruskai%27s_algorithm in English.
    The algorithm was first presented in the article by Kruskal, J. B., On the shortest spanning subtree of a graph and the traveling salesman problem in Proceedings of the American Mathematical Society. 7: 48-50. JSTOR 2033241 (1956).
    From this covering tree, one can use the algorithm described in paragraph 3.2 of the above-mentioned article.
    We call a conflict graph D of an arrangement f, a graph D = (Vd, Ed) corresponding to characteristics (1) and (2):
    (1) (2) There is an arc (vî, Vj) in the graph D, if and only if f (Vi) = ft (Vj) with:
    - Vd of all the nodes, that is to say the positions of the qubits, for the conflict graph D, and V that for the graph G representative of the arrangement of the qubits.
    - Ed and E, the sets of edges for, respectively, the conflict graph D and the graph G.
    - f (vi) is the value of the qubit in position vî in arrangement f.
    Thus, in Figures 7a and 7d, we note in particular that f (vi) = 4 and f t (v4) = 4, that f (vs) = and ft (vi) = l; and that f (v4) = 5 and ft (vs) = 5. We obtain in a subgraph of the conflict graph D linking vi, V4 and vs.
    In other words, each qubit value f (vi) located at position vî in arrangement f, in the conflict graph D must be moved to position vj in this same conflict graph, so that (vî, vj) EEO.
    We then consider the tree covering T previously determined.
    For two nodes u and v of this tree T, we denote P (u, v) a unique path of the tree between these nodes u and v.
    We consider the conflict graph D for an initial arrangement fo qubits of the tree T. We also consider C = (wi, W2, W3 ... Wq) an arbitrary oriented cycle of the conflict graph D with w q = wi .
    If we set ék = fo (wk) for all k such that 1 <k <q -1, then ft (wk + i) = &.
    The proposed iterative algorithm then aims to move the qubits £ i, £ 2, fe ... iq-ι of cycle C to their target positions along the unique paths. More precisely, we construct a sub-sequence of Sc inversions as follows:
    we initialize fi, o = fo in step k, with 1 <Λ <^ - 2, we consider the value of qubit & = fo (wk) whose current position is ffi fi fi, and we move it to the position on the path P (/ A ”o (f fi, ffi o fi k + fi) which is adjacent to the position ffi fi k + l ).
    We denote by fk + i, 0 the arrangement of the tree T which results from this movement.
    In step (q-1), the qubit value £ qi = fo (w q -i) is moved from its current position f q 0 fi q _fi to the position w q (= wi).
    At the end of the flow of the algorithm, this sequence Sc has two characteristics:
    (a) The n (S c ) <X lstii iS p T (w k , W k + fi, where Len (Sc) is the length of the sequence Sc and sp-r (wk, Wk + i) is the number d 'stops on the tree T between positions Wk and Wk + i;
    (b) The arrangement f of the tree T obtained by the sequence Sc satisfies, for each position vî of V (T):
    / (L) = ffiyfi if Vi eC. / o (l) otherwise
    These characteristics allow us to be able to choose the oriented cycles of the conflict graph D in an arbitrary order. And so, by constructing inversion sequences for all the oriented cycles of D, in an iterative fashion, we finally arrive at the arrangement f t of the tree T.
    In other words, we manage to reconstitute, in an iterative manner and in a polynomial time, the initial arrangement of qubits.
    Of course, the present invention is not limited to the examples and to the embodiments described and shown, but it is susceptible of numerous variants accessible to those skilled in the art.
    权利要求:
    Claims (9)
    [1" id="c-fr-0001]
    1. Method for optimizing a quantum circuit composed of an ordered series of quantum gates applied to an initial arrangement of qubit values, consisting in inserting a set of local SWAP gates, so that the set of gates of said quantum circuit are local, comprising steps consisting in:
    for each quantum gate of said series, if it is not local, insert a set of local SWAP gate before said quantum gate, determine (S4) the set of permutations, each consisting of a succession of inversions of values of qubits along the shortest paths between the positions of qubits associated with said quantum gate, and choosing (S5) from said set of permutations, a permutation minimizing a cost representing the number of conversions necessary to make the quantum gates local 'a series within said series, the size of said series being substantially smaller than that of said series; restoring (S7) said initial arrangement by establishing a spanning tree of a graph representative of the arrangement of the qubits of said circuit, and by carrying out reversals of qubit values along paths of said tree.
    [2" id="c-fr-0002]
    2. Method according to the preceding claim, without which the determination (S4) of the set of permutations is carried out by determining a succession of reversals of qubit values along the first shortest paths between any pair of associated qubit positions. to said quantum gate, then, and if said quantum gate has more than two associated qubit positions, by determining a succession of reversals of qubit values along the second shortest paths between each of the positions outside those already considered, and the first shortest paths already determined.
    [3" id="c-fr-0003]
    3. Method according to one of claims 1 or 2, wherein said cost takes into account a cost attached to each type of SWAP doors to be inserted.
    [4" id="c-fr-0004]
    4. Method according to one of the preceding claims, in which the restoration of the initial arrangement is carried out according to a token exchange algorithm.
    56. Method according to one of the preceding claims, in which the size of said series is between 3 and 5.
    67. Method according to one of the preceding claims, in which said shortest paths are determined by precalculating the shortest paths between all the vertices of said graph.
    78. Method according to the preceding claim, in which the said shortest paths are calculated by the Dijsktra algorithm.
    89 · Computer program comprising instructions which, when executed by a processor of a computer system, involve the implementation of a method according to one of the preceding claims.
    910. Optimization platform for a quantum circuit composed of an ordered series of quantum gates applied to an initial arrangement of qubit values, consisting in inserting a set of local SWAP gates, so that the set of gates of said quantum circuit are local, comprising digital processing means for each quantum gate of said series, if the latter is not local, insert a set of local SWAP gates before said quantum gate, by determining the set of permutations, each consisting of a succession of qubit value inversions along the shortest paths between the qubit positions associated with said quantum gate, and by choosing from said set of permutations, a permutation minimizing a cost representing the number of conversions necessary for localize the quantum gates of a sequence within said series, the size of said sequence being substantially inf higher than that of said series; restore said initial arrangement by establishing a tree covering a graph representative of the arrangement of the qubits of said circuit, and by carrying out reversals of qubit values along paths of said tree.
    1. Method for optimizing a quantum circuit composed of an ordered series of quantum gates applied to an initial arrangement of qubit values, consisting in inserting a set of local SWAP gates, so that the set of gates of said quantum circuit are local, comprising steps consisting in:
    for each quantum gate of said series, if it is not local, insert a set of local SWAP gate before said quantum gate, determine (S4) the set of permutations, each consisting of a succession of inversions of values of qubits along the shortest paths between the positions of qubits associated with said quantum gate, and choosing (S5) from said set of permutations, a permutation minimizing a cost representing the number of conversions necessary to make the quantum gates local 'a series within said series, the size of said series being substantially smaller than that of said series; restoring (S7) said initial arrangement by establishing a spanning tree of a graph representative of the arrangement of the qubits of said circuit, and by carrying out reversals of qubit values along paths of said tree.
    2. Method according to the preceding claim, without which the determination (S4) of the set of permutations is carried out by determining a succession of reversals of qubit values along the first shortest paths between any pair of associated qubit positions. to said quantum gate, then, and if said quantum gate has more than two associated qubit positions, by determining a succession of reversals of qubit values along the second shortest paths between each of the positions outside those already considered, and the first shortest paths already determined.
    3. Method according to one of claims 1 or 2, wherein said cost takes into account a cost attached to each type of S WAP doors to be inserted.
    4. Method according to one of the preceding claims, in which the restoration of the initial arrangement is carried out according to a token exchange algorithm.
    [5" id="c-fr-0005]
    5. Method according to one of the preceding claims, in which the size of said series is between 3 and 5.
    [6" id="c-fr-0006]
    6. Method according to one of the preceding claims wherein said shortest paths are determined by precalculating the shortest paths between the set of vertices of said graph.
    [7" id="c-fr-0007]
    7. Method according to the preceding claim, wherein said shortest paths are calculated by the Dijsktra algorithm.
    [8" id="c-fr-0008]
    8. Computer program comprising instructions which, when executed by a processor of a computer system, entail the implementation of a method according to one of the preceding claims.
    [9" id="c-fr-0009]
    9. Optimization platform of a quantum circuit composed of an ordered series of quantum gates applied to an initial arrangement of qubit values, consisting in inserting a set of local SWAP gates, so that the set of gates of said quantum circuit are local, comprising digital processing means for each quantum gate of said series, if the latter is not local, insert a set of local SWAP gates before said quantum gate, by determining the set of permutations, each consisting of a succession of qubit value inversions along the shortest paths between the qubit positions associated with said quantum gate, and by choosing from said set of permutations, a permutation minimizing a cost representing the number of conversions necessary for localize the quantum gates of a sequence within said series, the size of said sequence being substantially inf higher than that of said series;
    restore said initial arrangement by establishing a tree covering a graph representative of the arrangement of the qubits of said circuit, and by carrying out reversals of qubit values along paths of said tree.
    1/4
    类似技术:
    公开号 | 公开日 | 专利标题
    FR3072483A1|2019-04-19|OPTIMIZATION OF A QUANTUM CIRCUIT BY INSERTING SWAP DOORS
    Ducruet et al.2012|Maritime constellations: a complex network approach to shipping and ports
    Underwood et al.2010|Universal quantum computation by discontinuous quantum walk
    EP3314394B1|2019-07-03|Stochastic parallel microprocessor
    Montanaro2005|Quantum walks on directed graphs
    Doveh et al.2021|DEGAS: differentiable efficient generator search
    KR101136200B1|2012-04-17|System, method, and computer-readable recording medium for importance sampling of partitioned domains
    EP3622445B1|2021-06-09|Method, implemented by computer, for searching for rules of association in a database
    EP1431880A1|2004-06-23|Discretisation of a source attribute or of a group of source attributes of a database
    Apt et al.2013|Social network games with obligatory product selection
    Eppstein et al.2010|Linear-time algorithms for geometric graphs with sublinearly many edge crossings
    Imani et al.2010|Properties of a hierarchical network based on the star graph
    Pagourtzis et al.2020|Overlapping community detection via minimum spanning tree computations
    Hossain et al.2019|An Efficient Solution to Travelling Salesman Problem using Genetic Algorithm with Modified Crossover Operator
    Chakraborty et al.2022|Divide-and-conquer based all spanning tree generation algorithm of a simple connected graph
    Ray et al.2019|Web service selection with correlations: A feature-based abstraction refinement approach
    CN110019981B|2021-05-04|Directed super-edge propagation method integrating unsupervised learning and network out-degree
    Gupta2014|Effect of varying the size of initial parent pool in genetic algorithm
    Li et al.2019|Measuring the Clustering Strength of a Network via the Normalized Clustering Coefficient
    FR2765705A1|1999-01-08|METHOD FOR CONSTRUCTING A NEURON NETWORK FOR MODELING A PHENOMENON
    Banitalebi-Dehkordi et al.2021|Model Composition: Can Multiple Neural Networks Be Combined into a Single Network Using Only Unlabeled Data?
    Silva et al.2011|An approach using quantum PBIL to solve the traveling salesman problem
    OMRANI2019|Faculty of Sciences of Tunis
    Laurence2020|La résilience des réseaux complexes
    WO2022018140A1|2022-01-27|Methods for allocating logical qubits of a quantum algorithm in a quantum processor
    同族专利:
    公开号 | 公开日
    WO2019077240A1|2019-04-25|
    FR3072483B1|2021-04-30|
    EP3471028A1|2019-04-17|
    US20200242295A1|2020-07-30|
    US11010527B2|2021-05-18|
    引用文献:
    公开号 | 申请日 | 公开日 | 申请人 | 专利标题
    US20030164490A1|2001-02-13|2003-09-04|Alexandre Blais|Optimization method for quantum computing process|
    US6995404B2|2003-10-22|2006-02-07|The Johns Hopkins University|Techniques for quantum processing with photons and the zeno effect|
    US20060123363A1|2004-12-07|2006-06-08|Williams Colin P|Method and apparatus for automated design of quantum circuits|
    FR3072483B1|2017-10-16|2021-04-30|Bull Sas|OPTIMIZATION OF A QUANTUM CIRCUIT BY INSERTING SWAP DOORS|FR3072483B1|2017-10-16|2021-04-30|Bull Sas|OPTIMIZATION OF A QUANTUM CIRCUIT BY INSERTING SWAP DOORS|
    US20200394544A1|2019-06-11|2020-12-17|Microsoft Technology Licensing, Llc|Swap networks for quantum computation|
    WO2021247125A2|2020-03-26|2021-12-09|Zapata Computing, Inc.|Quantum computing system and method for time evolution of bipartite hamiltonians on a lattice|
    EP3929827A4|2020-06-26|2021-12-29|Bull Sas|Computer computing compiling method and system with partial synthetization of quantum computer compliant quantum circuits|
    法律状态:
    2019-04-19| PLSC| Publication of the preliminary search report|Effective date: 20190419 |
    2019-10-24| PLFP| Fee payment|Year of fee payment: 3 |
    2020-10-27| PLFP| Fee payment|Year of fee payment: 4 |
    2021-10-28| PLFP| Fee payment|Year of fee payment: 5 |
    优先权:
    申请号 | 申请日 | 专利标题
    FR1759684|2017-10-16|
    FR1759684A|FR3072483B1|2017-10-16|2017-10-16|OPTIMIZATION OF A QUANTUM CIRCUIT BY INSERTING SWAP DOORS|FR1759684A| FR3072483B1|2017-10-16|2017-10-16|OPTIMIZATION OF A QUANTUM CIRCUIT BY INSERTING SWAP DOORS|
    US16/756,145| US11010527B2|2017-10-16|2018-10-12|Optimization of a quantum circuit by inserting swap gates|
    EP18200216.2A| EP3471028A1|2017-10-16|2018-10-12|Optimisation of a quantum circuit by insertion of swap doors|
    PCT/FR2018/052543| WO2019077240A1|2017-10-16|2018-10-12|Optimization of a quantum circuit by inserting swap gates|
    [返回顶部]