Compiling method and system with partial synthetization of quantum computer compliant quantum circuits

Abstract

The present disclosure relates to a compiling method (50) for converting an input quantum circuit into an output quantum circuit compliant with predetermined constraints of a quantum computer, said input quantum circuit being composed of quantum gates to be applied to a set of qubits, said quantum gates arranged successively in an execution order, wherein said method comprises, for each quantum gate of the input quantum circuit processed according to the execution order: if the processed quantum gate corresponds to an operator of a set of synthesizable operators: (S53) update the synthesizable accumulated operator to include the operator corresponding to the quantum gate, otherwise: a) (S54) synthesize a partial quantum sub-circuit partially implementing the current synthesizable accumulated operator and modify accordingly the synthesizable accumulated operator, and b) (S55) append the partial quantum sub-circuit to the output quantum circuit.

Claims

1. A compiling method for converting an input quantum circuit into an output quantum circuit compliant with predetermined constraints of a quantum computer, said input quantum circuit being composed of quantum gates to be applied to a set of qubits, said quantum gates arranged successively in an execution order, wherein a predetermined set of synthesizable operators is defined, wherein said compiling method comprises: initializing a synthesizable accumulated operator and the output quantum circuit; and processing the quantum gates of the input quantum circuit according to the execution order, and for each processed quantum gate: responsive to the processed quantum gate corresponding to an operator of the predetermined set of synthesizable operators, updating the synthesizable accumulated operator to include the operator corresponding to the processed quantum gate; and responsive to the processed quantum gate not corresponding to an operator of the predetermined set of synthesizable operators: decomposing the synthesizable accumulated operator into a first synthesizable operator and a second synthesizable operator, said second synthesizable operator referred to as modified synthesizable accumulated operator, wherein said modified synthesizable accumulated operator is not impacted by the processed quantum gate in that it commutes with the operator corresponding to the processed quantum gate; synthesizing a partial quantum sub-circuit by synthesizing the first synthesizable operator to produce a quantum sub-circuit and by appending the processed quantum gate to the quantum sub-circuit, wherein the modified synthesizable accumulated operator becomes the synthesizable accumulated operator for a subsequent processed quantum gate; and appending the partial quantum sub-circuit to the output quantum circuit.

2. The compiling method according to claim 1, comprising synthesizing a last quantum sub-circuit implementing a last synthesizable accumulated operator obtained after having processed a last quantum gate of the input quantum circuit according to the execution order, and appending the last quantum sub-circuit to the output quantum circuit.

3. The compiling method according to claim 1, comprising implementing by a non-quantum computer a last synthesizable accumulated operator obtained after having processed a last quantum gate of the input quantum circuit according to the execution order.

4. The compiling method according to claim 1, wherein the quantum gates that correspond to synthesizable operators include Clifford gates.

5. The compiling method according to claim 4, wherein the quantum gates that correspond to synthesizable operators consist of CNOT gates.

6. The compiling method according to claim 5, wherein, if the input quantum circuit comprises SWAP gates, the compiling method further comprises a preliminary step of decomposing each SWAP gate of the input quantum circuit into CNOT gates.

7. The compiling method according to claim 4, wherein the input quantum circuit consists of one-qubit quantum gates and two-qubits quantum gates, wherein each two-qubits quantum gate of the input quantum circuit can be decomposed into one or more CNOT gates.

8. The compiling method according to claim 1, wherein the predetermined set of synthesizable operators correspond to reversible linear Boolean operators, described as N.sub.q×N.sub.a invertible Boolean matrices, wherein N.sub.q is the number of qubits of the input quantum circuit.

9. The compiling method according to claim 8, wherein, if the processed quantum gate of the input quantum circuit is a one-qubit quantum gate applied to the qubit of index q, the step of synthesizing the partial quantum sub-circuit comprises synthesizing a quantum sub-circuit c such that the corresponding operator {tilde over (c)} satisfies the following expression:
B.sup.−1={tilde over (c)}.Math.A.sup.−1 wherein: A is the current synthesizable accumulated operator; and B is the modified synthesizable accumulated operator and B.sup.−1 is composed of coefficients b.sub.ij such that, for some index q′: $\{\begin{array}{c}{b}_{\mathrm{iq}}=0\forall i\ne q^{\prime }\\ b_{q\prime j}=0\forall j\ne q\\ b_{q^{\prime }q}=1\end{array}\hspace{1em}$ wherein the partial quantum sub-circuit corresponds to the quantum sub-circuit c followed by the processed quantum gate applied to the qubit of index q′.

10. The compiling method according to claim 1, wherein, if the processed quantum gate of the input circuit is a one-qubit quantum gate applied to the qubit of index q, and A being the operator corresponding to a current synthesizable accumulated operator, the step of synthesizing the partial quantum sub-circuit comprises synthesizing a set of fan-in CNOT gates having a qubit of index q′ as a target qubit, the set of fan-in CNOT gates corresponding to an operator which modifies A.sup.−1 to produce an operator B.sup.−1 having a row of index q′ with a single non-null value at a column of index q, wherein B is the modified synthesizable accumulated operator and the partial quantum sub-circuit comprises the set of fan-in CNOT gates followed by the processed quantum gate applied to the qubit of index q′.

11. The compiling method according to claim 10, wherein the step of synthesizing the partial quantum sub-circuit further comprises synthesizing a set of fan-out CNOT gates having the qubit of index q′ as a source qubit, the set of fan-out CNOT gates further causing the operator B.sup.−1 to have the column of index q with a single non-null value, wherein the partial quantum sub-circuit comprises the set of fan-in CNOT gates followed by the set of fan-out CNOT gates followed by the processed quantum gate applied to the qubit of index q′.

12. The compiling method according to claim 11, wherein the step of synthesizing the partial quantum sub-circuit comprising synthesizing a set of fan-in CNOT gates comprises: synthesizing a plurality of candidate partial quantum sub-circuits for one first processed quantum gate of the input quantum circuit, associated to respective candidate target qubits for a set of fan-in CNOT gates, a set of fan-in CNOT gates corresponding to a set of CNOT gates having a same target qubit; synthesizing a plurality of candidate partial quantum sub-circuits for at least one second processed quantum gate of the input quantum circuit, associated to respective candidate target qubits for a set of fan-in CNOT gates and/or to respective candidate partial quantum sub-circuits of the first processed quantum gate; and selecting one candidate partial quantum sub-circuit for each of said one first processed quantum gate and said at least one second processed quantum gate, the selected candidate partial quantum sub-circuits minimizing a number of CNOT gates over a predetermined number of successive processed quantum gates of the input quantum circuit.

13. A computer program product comprising instructions which, when executed by at least one non-quantum processor, configure said at least one non-quantum processor to carry out a compiling method according to claim 1.

14. A computer-readable storage medium comprising instructions which, when executed by at least one non-quantum processor, configure said at least one non-quantum processor to carry out a compiling method according to claim 1.

15. A computer system comprising at least one non-quantum processor configured to carry out a compiling method according to claim 1.

Description

BRIEF DESCRIPTION OF DRAWINGS

(1) The invention will be better understood upon reading the following description, given as an example that is in no way limiting, and made in reference to the figures which show:

(2) FIG. 1: a diagram representing the main steps of an exemplary embodiment of a quantum computing compiling method;

(3) FIG. 2: a schematic representation of a graph representing the connectivity constraints of a target quantum computer;

(4) FIG. 3: a schematic representation of an example of input quantum circuit;

(5) FIG. 4: a schematic representation of a tree computed for the synthesis of a set of fan-in CNOT gates, for the input quantum circuit of FIG. 3;

(6) FIG. 5: a schematic representation of the synthesis of a set of fan-in CNOT gates, for the input quantum circuit of FIG. 3;

(7) FIG. 6: a schematic representation of a tree computed for the synthesis of a set of fan-out CNOT gates, for the input quantum circuit of FIG. 3;

(8) FIG. 7: a schematic representation of the synthesis of a set of fan-out CNOT gates, after having synthesized a set of fan-in CNOT gates, for the input quantum circuit of FIG. 3;

(9) FIG. 8: a schematic representation of an example of output quantum circuit obtained for the input quantum circuit of FIG. 3;

(10) FIG. 9: a schematic representation of an example of optimized output quantum circuit obtained for the input quantum circuit of FIG. 3;

(11) FIG. 10: a schematic representation of another example of input quantum circuit;

(12) FIG. 11: a schematic representation of a tree illustrating the benefits of a recursive optimization scheme;

(13) FIG. 12: schematic representations of output quantum circuits obtained for the input quantum circuit of FIG. 10, with and without the recursive optimization scheme;

(14) FIG. 13: a schematic representation of another example of input quantum circuit;

(15) FIG. 14: a schematic representation of a tree computed for the synthesis of a set of fan-in CNOT gates, for the input quantum circuit of FIG. 13;

(16) FIG. 15: a schematic representation of an output quantum circuit obtained for the input quantum circuit of FIG. 13.

(17) In these figures, references identical from one figure to another designate identical or analogous elements. For reasons of clarity, the elements shown are not to scale, unless explicitly stated otherwise.

DETAILED DESCRIPTION

(18) As discussed above, the present disclosure relates to a compiling method 50 and system in the context of quantum computing.

(19) More specifically, the compiling method 50 aims at converting a high level input quantum circuit into a low level output quantum circuit that is compliant with predetermined constraints of a target quantum computer, such as connectivity constraints between qubits of the target quantum computer.

(20) The input quantum circuit is composed of quantum gates to be applied to a set of qubits. The quantum gates appear in the input quantum circuit in an execution order, which corresponds to the order according which said quantum gates are successively applied to the set of qubits over time.

(21) FIG. 1 represents the main steps of a compiling method 50 for converting the input quantum circuit into an output quantum circuit compliant with the constraints of the target quantum computer.

(22) The compiling method 50 is carried out by a computer system (not represented in the figures). In preferred embodiments, the computer system comprises one or more processors (which may belong to a same computer or to different computers) and storage means (magnetic hard disk, optical disk, electronic memory, or any computer readable storage medium) in which a computer program product is stored, in the form of a set of program-code instructions to be executed in order to implement all or part of the steps of the compiling method 50. Alternatively, or in combination thereof, the computer system can comprise one or more programmable logic circuits (FPGA, PLD, etc.), and/or one or more specialized integrated circuits (ASIC), etc., adapted for implementing all or part of said steps of the compiling method 50. In other words, the computer system comprises a set of means configured by software (specific computer program product) and/or by hardware (processor, FPGA, PLD, ASIC, etc.) to implement the steps of the compiling method 50. It is emphasized that the compiling method is carried out by a classical (non-quantum) computer, it is the output quantum circuit that is then executed by a quantum computer.

(23) For instance, we can assume that the input quantum circuit c.sub.in is composed of a set .sub.in of unitary quantum gates, and that the output quantum circuit c.sub.out has quantum gates in a quantum gate set .sub.out. It should be noted that the set .sub.out may contain the exact same quantum gates as .sub.in but with additional constraints, such as connectivity constraints between the qubits of the target quantum computer.

(24) We also define a subset S.Math..sub.in of quantum gates that correspond to synthesizable operators. As discussed above, the synthesizable operators correspond to operators that can be described by a high level synthesizable description language, and that can be accumulated, i.e. such that combining two synthesizable operators yields a synthesizable operator. Hence, the subset S corresponds to a predetermined set of synthesizable operators. We also define the subset S=.sub.in\S (i.e. the complement of S in .sub.in), which includes the quantum gates that do not correspond to synthesizable operators.

(25) Formally, we also define a set of high-level synthesizable descriptions of synthesizable operators. Hence, any quantum gate in the subset S corresponds to a synthesizable operator that has a high-level synthesizable description in the set and, for h∈, h corresponds to the synthesizable operator described by h. It should be noted that the distinction between high-level description of an operator and the operator itself is mainly formal and is not necessarily maintained throughout the present disclosure.

(26) As can be seen in FIG. 1, the compiling method 50 comprises a step S51 of initializing both a synthesizable accumulated operator h.sub.acc and the output quantum circuit c.sub.out.

(27) Preferably, the synthesizable accumulated operator h.sub.acc is initialized to the identity operator Id, i.e. it does not modify the qubits. Also, the output quantum circuit c.sub.out is preferably initialized to an empty quantum circuit ε. In other embodiments, other initializations can be possible, for instance if the input quantum circuit c.sub.in corresponds to a portion of a larger quantum circuit, in which case the synthesizable accumulated operator h.sub.acc and the output quantum circuit c.sub.out might be initialized to the synthesizable accumulated operator and to the output quantum circuit obtained for the previous portion of the larger quantum circuit.

(28) In the following description, we assume in a non-limitative manner that the synthesizable accumulated operator h.sub.acc is initialized to the identity operator Id and that the output quantum circuit c.sub.out is initialized to an empty quantum circuit ε.

(29) As can be seen in FIG. 1, the compiling method 50 then iteratively processes the quantum gates of the input quantum circuit according to the execution order of these quantum gates. It should be noted that two parallel quantum gates of the input quantum circuit c.sub.in, if any, are processed one after the other, the order of their processing being indifferent.

(30) For a processed quantum gate g of the input quantum circuit, the compiling method 50 comprises a step S52 of evaluating whether the processed quantum gate g corresponds to a synthesizable operator, e.g. by evaluating whether the processed quantum gate g is in the subset S or in the subset S.

(31) If the processed quantum gate g is in the subset S (g∈S, reference S52a in FIG. 1), then the compiling method 50 comprises a step S53 of updating the synthesizable accumulated operator h.sub.acc to include the operator {tilde over (g)} corresponding to the processed quantum gate g. Formally, this can be described by an update function u: ×S.fwdarw. that verifies:
u(h.sub.acc,g)={tilde over (g)}.Math.h.sub.acc

(32) In the sequel, we denote by :: the concatenation of quantum circuits or gates, wherein c−g.sub.1:: g.sub.2 corresponds to the quantum circuit c obtained by appending the quantum gate g.sub.2 to the quantum gate g.sub.1. The operator {tilde over (c)} corresponding to the quantum circuit c is given by the following expression {tilde over (c)}={tilde over (g)}.sub.2.Math.{tilde over (g)}.sub.1, wherein {tilde over (g)}.sub.1 and {tilde over (g)}.sub.2 correspond to the operators associated to the quantum gates g.sub.1 and g.sub.2, respectively.

(33) If the processed quantum gate g is not in the subset S (g∈S, reference S52b in FIG. 1), then the compiling method 50 comprises a step S54 of synthesizing a partial quantum sub-circuit c.sub.p which partially implements the synthesizable accumulated operator h.sub.acc. The synthesizing step S54 uses a synthetization algorithm that is aware of the quantum computer's constraints, and the partial quantum sub-circuit c.sub.p is therefore quantum computer compliant. For instance, the synthetization algorithm used during the synthesizing step S54 may be one those described in [KvdG19] or [vdGD20]. Some detailed non-limitative examples are also provided hereinbelow.

(34) Basically, the partial quantum sub-circuit c.sub.p implements only the operations of the current synthesizable accumulated operator h.sub.acc that, in the output quantum circuit c.sub.out, need to be implemented before the processed quantum gate g and not after. The operations of the current synthesizable accumulated operator h.sub.acc that can be implemented after the processed quantum gate are preferably not synthesized and remain in a modified synthesizable accumulated operator h′.sub.acc. The modified synthesizable accumulated operator h′.sub.acc becomes the current synthesizable accumulated operator h.sub.acc for the subsequent processed quantum gate of the input quantum circuit c.sub.in (h.sub.acc←h′.sub.acc).

(35) The partial quantum sub-circuit c.sub.p is such that applying the synthesizable accumulated operator h.sub.acc followed by the operator {tilde over (g)} corresponding to the processed quantum gate g is equivalent to applying the operator {tilde over (c)}.sub.p corresponding to the partial quantum sub-circuit c.sub.p followed by the modified synthesizable accumulated operator h′.sub.acc. Formally, this can be described by an extraction function e: ×S∵×*.sub.out, wherein * stands for Kleene's star, that verifies:
h′.sub.acc,c.sub.p=e(h.sub.acc,g).Math.{tilde over (g)}.Math.h′.sub.acc.Math.{tilde over (c)}.sub.p

(36) In other words, the extraction function e tells how to commute the processed quantum gate g with the synthesizable accumulated operator h.sub.acc as the cost of updating h.sub.acc into h′.sub.acc and turning the quantum gate g into a partial quantum sub-circuit c.sub.p.

(37) After the synthesizing step S54, the compiling method 50 comprises a step S55 of appending the partial quantum sub-circuit to the output quantum circuit c.sub.out(c.sub.out←c.sub.out::c.sub.p).

(38) After the updating step S53 or the appending step S55, the compiling method 50 comprises a step S56 of evaluating whether the last quantum gate of the input quantum circuit c.sub.in has been processed.

(39) If the last quantum gate of the input quantum circuit c.sub.in has not been processed (reference S56a in FIG. 1), the compiling method 50 continues by processing the next quantum gate of the input quantum circuit c.sub.in, according to the execution order of the quantum gates.

(40) If the last quantum gate of the input quantum circuit c.sub.in has been processed (reference S56b in FIG. 1), then the result of the compiling method 50 corresponds to the output quantum circuit c.sub.out (which is compliant with the target quantum computer's constraints) and to the last synthesizable accumulated operator h.sub.acc, such that {tilde over (c)}.sub.in=h.sub.acc.Math.{tilde over (c)}.sub.out.

(41) In most cases, the last synthesizable accumulated operator h.sub.acc will be different from the identity operator. If the last synthesizable accumulated operator h.sub.acc is indeed different from the identity operator, then it is possible, according to a first example, to synthesize a last quantum sub-circuit c.sub.1 implementing the last synthesizable accumulated operator h.sub.acc and to append the last quantum sub-circuit c.sub.l to the output quantum circuit c.sub.out (c.sub.out←c.sub.out::c.sub.l). According to another example, all or part of the last synthesizable accumulated operator h.sub.acc may be implemented by a non-quantum computer (i.e. a classical computer manipulating bits rather than qubits), if the corresponding operations can be efficiently applied by a non-quantum computer on the measured qubit values.

(42) An exemplary pseudo-code implementation for the compiling method 50 depicted in FIG. 1 is given below.

(43) TABLE-US-00001 h.sub.acc ← Id c.sub.out ← ε for g in c.sub.in do // according to the execution order if g ∈ S then h.sub.acc ← u(h.sub.acc, g) else h′.sub.acc, c.sub.p ← e(h.sub.acc, g) h.sub.acc ← h′.sub.acc c.sub.out ← c.sub.out :: c.sub.p end if end for return h.sub.acc, c.sub.out

(44) In practice, the set of synthesizable operators may vary, together with how the update function u and the extraction function e may be implemented. In the sequel, we provide examples for the case where the set of synthesizable operators corresponds the set of reversible linear Boolean operators, and for the case where the set of synthesizable operators corresponds to the Clifford operators (the set of reversible linear Boolean operators being actually a subset of the Clifford operators).

Example with Reversible Linear Boolean Operators

(45) In this example, we consider in a non-limitative manner the set of reversible quantum circuits over N.sub.q qubits comprising only CNOT gates. This set generates the entire set of reversible linear Boolean operators over N.sub.q variables and contains the set of all N.sub.q elements permutations. Each synthesizable operator may be represented as a N.sub.q×N.sub.q invertible Boolean matrix, each row representing an output parity of the quantum circuit. It is also simple to update such an operator via some row (resp. column) operations to accommodate for left (resp. right) composition of the operator by a CNOT gate.

(46) In this example, we assume in a non-limitative manner that:

(47) .sub.in contains any one-qubit quantum gate and CNOT gates on arbitrary pairs of qubits; if necessary, it is possible to convert beforehand two-qubits quantum gates of the input quantum circuit c.sub.in into CNOT gates (for instance any SWAP gate can be converted into three CNOT gates, or any two-qubits quantum gate can be decomposed into CNOT gate(s) and local rotations);

(48) .sub.out contains any one-qubit quantum gate and CNOT gates compliant with some connectivity graph G (representing the connectivity constraints of the target quantum computer);

(49) S={CNOT.sub.i,j|i, j∈V(G)} is the set of CNOT gates on arbitrary pairs of qubits (the qubits being the vertices V(G) of the graph G);

(50) S corresponds to the one-qubit quantum gates of the input quantum circuit c.sub.in;

(51) is the set of invertible N.sub.q×N.sub.q Boolean matrices.

(52) In this case, the update function u may be expressed as follows:
u(A,CNOT.sub.i,j)=E.sub.i,j.Math.A
expression in which:

(53) A corresponds to the N.sub.q×N.sub.q Boolean matrix describing the synthesized accumulated operator;

(54) E.sub.i, j corresponds to the N.sub.q×N.sub.q identity matrix with one additional 1 at row j column i.

(55) Given some one-qubit quantum gate g acting on the qubit of index q and the N.sub.q×N.sub.q Boolean matrix A describing the synthesized accumulated operator, the extraction function e produces a G-compatible quantum sub-circuit c consisting in CNOT gates in the subset S such that B.sup.−1={tilde over (c)}.Math.A.sup.−1, up to some row permutations, can be expressed as:

(56) $B^{-1}=\left(\begin{array}{ccccccc}0& .Math.& 0& \stackrel{\stackrel{q}{︷}}{1}& 0& .Math.& 0\\ & & & 0& & & \\ & B^{\prime }& & .Math.& & B^{″}& \\ & & & 0& & & \end{array}\right)$
expression in which B′ and B″ are (N.sub.q−1)×(N.sub.q−1) Boolean matrices. In other words, B.sup.−1 is composed of coefficients b.sub.ii such that, for some index q′:

(57) $\{\begin{array}{c}{b}_{\mathrm{iq}}=0\forall i\ne q^{\prime }\\ b_{q\prime j}=0\forall j\ne q\\ b_{q^{\prime }q}=1\end{array}$

(58) In other words, the quantum sub-circuit c synthesizes a row and a column of A in order to make it act as the identity on the wanted qubit. Purely in terms of linear operator synthesis, it means that we synthesize the parity {q} on some qubit of index q′ and remove the qubit of index q from any other parity carried by the other qubits. The extraction function e can be expressed as:
e(A,g)=(B,c::g′)
expression in which g′ is the one-qubit quantum gate g applied to the qubit of index q′ and B and c are defined as above. The partial quantum sub-circuit c.sub.p corresponds to c.sub.p=c::g′.

(59) We now describe an exemplary implementation of the extraction function e. We denote by e.sub.q the parity row vector comprising a single 1 at the column of index q:

(60) $e_q=\left[0.Math.0\stackrel{\stackrel{q}{︷}}{1}0.Math.0\right]$

(61) Then, the extraction function e works in two stages:

(62) computing the vector y=e.sub.q.Math.A produces a bit vector describing which wire of the quantum sub-circuit should be fold using a set of fan-in CNOT gates (i.e. CNOT gates that share the same target) onto one of them; this sets one line (of index q′) of our linear operator to the singleton parity {q}; this is the line whose qubit will receive the processed one-qubit quantum gate g′;

(63) after updating A.sup.−1 accordingly, the qth column of the operator may be synthesized by distributing the line chosen at the previous step onto every line containing a nonzero qth component; this can be achieved using a set of fan-out CNOT gates (i.e. CNOT gates sharing the same control).

(64) It should be noted that, in some cases, it is not necessary to implement a set of fan-out CNOT gates. This will be the case if the processed quantum gate g is a phase gate (i.e. a diagonal operator). Indeed, for a phase gate, it is sufficient to produce an operator B.sup.−1 having the parity {q}. Since the operator corresponding to a phase gate is diagonal, it will trivially commute, and it is not necessary to clean up the column of index q of B.sup.−1, thus avoiding the need for a set of fan-out CNOT gates and saving up approximately half of the CNOT gates required to insert the processed quantum gate g into the output quantum circuit c.sub.out. Hence, we simply need to be able to produce the implementation of a set of fan-in CNOT gates and, possibly, a set of fan-out CNOT gates that are compliant with the quantum computer's constraints.

(65) To perform this synthesis of the quantum sub-circuit c such that B.sup.−1={tilde over (c)}.Math.A.sup.−1, it is possible to:

(66) compute the vector y=e.sub.q.Math.A, and define {y.sub.1, . . . , y.sub.k} the set of indexes of the non-null values of the vector y;

(67) compute a tree T (preferably a Steiner tree) comprising nodes, including terminal nodes which correspond to the qubits having their indexes in {y.sub.1, . . . , y.sub.k}, using the connectivity graph G;

(68) select a terminal node y.sub.l as the root (i.e. target of the set of fan-in CNOT gates).

(69) Once the root is selected, the algorithm as described by the following pseudo-code implementation may be applied to compute the set of fan-in CNOT gates of the quantum sub-circuit c.

(70) TABLE-US-00002 c ← ε while |T| > 1 do v ← a leaf of T that is not the root u ← the only neighbor node of v in T if u .Math. {y.sub.1, ..., y.sub.k} c ← c :: CNOT.sub.u,v end if c ← c :: CNOT.sub.v,u T.remove(v) // remove the node v from T end while return c

(71) The quantum sub-circuit c produced corresponds to a set of fan-in CNOT gates with the input terminal nodes {y.sub.1, . . . , y.sub.k} as control except for the selected root which corresponds to the target. All CNOT gates used in the quantum sub-circuit c are compliant with the connectivity graph G, making the quantum sub-circuit c compliant with the qubits' connectivity. The resulting quantum sub-circuit c comprises (2(l−1)−k) CNOT gates where l=|T| is the size of the tree and k is the number of terminal vertices (i.e. the Hamming weight of y), including the selected root.

(72) When necessary, the set of fan-out CNOT gates may be synthesized in a similar way, except that the terminal nodes {y′.sub.1, . . . , y′.sub.k} used to compute a tree T′, are found by looking at lines of the intermediate operator obtained after having obtained the parity {q} at the row which corresponds to the selected root (i.e. target of the set of fan-in CNOT gates), that have a non-zero qth component.

(73) The algorithm as described by the following pseudo-code implementation may be applied to compute the set of fan-out CNOT gates of the quantum sub-circuit c.

(74) TABLE-US-00003 ones ← {y′.sub.1, ..., y′.sub.k} Tmp ← T′ // copy of T′ while |Tmp| > 1 do // setting all the vertices of Tmp (T′) to one v ← a leaf of Tmp u ← the only neighbor node of v in Tmp if u .Math. ones c ← c :: CNOT.sub.v,u ones.insert(u) // add a one at index u end if Tmp.remove(v) // remove the node v from Tmp end while while |T′| > 1 do // getting rid of all ones (except for root) v ← a leaf of T′ that is not the root u ← the only neighbor node of v in T′ c ← c :: CNOT.sub.u,v T′.remove(v) // remove the node v from T′ end while return c

(75) The quantum sub-circuit c obtained comprises both a set of fan-in CNOT gates and a set of fan-out CNOT gates.

(76) We now provide a practical example in order to illustrate the conversion of an input quantum circuit c.sub.in into a quantum computer compliant output quantum circuit c.sub.out, in the case where the quantum gates which correspond to synthesizable operators consist in CNOT gates on arbitrary pairs of qubits. The one-qubit quantum gates do not correspond to synthesizable operators and belong to the subset S.

(77) FIG. 2 represents schematically a connectivity graph G representing the connectivity constraints of a target computer comprising N.sub.q=6 qubits q.sub.0 to q.sub.5. Qubits that can interact directly are connected by a single line. For instance, while a CNOT gate CNOT.sub.0,1 is compatible with the connectivity constraints of the target quantum computer, the CNOT gates CNOT.sub.0,3 and CNOT.sub.3,4 are not compatible with said connectivity constraints.

(78) FIG. 3 represents schematically an example of input quantum circuit c.sub.in. This input quantum circuit c.sub.in comprises, in the execution order: first a CNOT gate CNOT.sub.0,3; then a CNOT gate CNOT.sub.3,4; and finally, a Hadamard gate H.

(79) For instance, the output quantum circuit c.sub.in is initialized to an empty quantum circuit and the synthesizable accumulated operator, represented by a N.sub.q×N.sub.q matrix A is initialized to the identity operator:

(80) $A=\left(\begin{array}{cccccc}1& 0& 0& 0& 0& 0\\ 0& 1& 0& 0& 0& 0\\ 0& 0& 1& 0& 0& 0\\ 0& 0& 0& 1& 0& 0\\ 0& 0& 0& 0& 1& 0\\ 0& 0& 0& 0& 0& 1\end{array}\right)$

(81) The CNOT gate CNOT.sub.0,3 is processed first and corresponds to a synthesizable operator. The update function u multiplies the matrix E.sub.0,3 by the matrix A and updates the matrix A (representing the synthesizable accumulated operator) by adding its row of index 0 into its row of index 3. After the update, the matrix A is as follows:

(82) $A=\left(\begin{array}{cccccc}1& 0& 0& 0& 0& 0\\ 0& 1& 0& 0& 0& 0\\ 0& 0& 1& 0& 0& 0\\ 1& 0& 0& 1& 0& 0\\ 0& 0& 0& 0& 1& 0\\ 0& 0& 0& 0& 0& 1\end{array}\right)$

(83) Then, the CNOT gate CNOT.sub.3,4 is processed and corresponds to a synthesizable operator. The update function u multiplies the matrix E.sub.3,4 by the matrix A and updates the matrix A (representing the synthesizable accumulated operator) by adding its row of index 3 into its row of index 4. After the update, the matrix A is as follows:

(84) $A=\left(\begin{array}{cccccc}1& 0& 0& 0& 0& 0\\ 0& 1& 0& 0& 0& 0\\ 0& 0& 1& 0& 0& 0\\ 1& 0& 0& 1& 0& 0\\ 1& 0& 0& 1& 1& 0\\ 0& 0& 0& 0& 0& 1\end{array}\right)$

(85) Then, the Hadamard gate H is processed and does not correspond to a synthesizable operator. For this Hadamard gate H, the extraction function e will produce a set of fan-in CNOT gates and a set of fan-out CNOT gates.

(86) The Hadamard gate H is to be applied on the qubit q.sub.4 (i.e. q=4) such that the goal is to produce a matrix N.sub.q×N.sub.q matrix B.sup.−1 having a row having a single non-null value at the column of index q=4, and having a single non-null value in the column of index q=4.

(87) Then the compiling method 50 computes the vector y by multiplying the vector e.sub.4=(0 0 0 0 1 0) by the matrix A (representing the synthesizable accumulated operator), which gives:
y=(1 0 0 1 1 0)

(88) Based on the vector y, the possible choices for the index q′ (i.e. for the root/row of the matrix B.sup.−1 that will be made identical to e.sub.4) are 0, 3 or 4. (i.e. {y.sub.1, . . . ,y.sub.k}={0,3,4}) We assume that we select the index q′=3. It should be noted that the selected index q′ might impact the number of CNOT gates that will be inserted, such that it might be beneficial to try different values for the index q′ in order to minimize the number of CNOT gates inserted.

(89) As discussed above, the matrix B.sup.−1 is given by B.sup.−1={tilde over (c)}.Math.A.sup.−1, such that it is possible to determine B.sup.−1 by making operations on the rows of the matrix A.sup.−1, which operations will correspond to CNOT gates in the quantum sub-circuit c corresponding to the operator {tilde over (c)}. The matrix A.sup.−1 is the following:

(90) $A^{-1}=\left(\begin{array}{cccccc}1& 0& 0& 0& 0& 0\\ 0& 1& 0& 0& 0& 0\\ 0& 0& 1& 0& 0& 0\\ 1& 0& 0& 1& 0& 0\\ 0& 0& 0& 1& 1& 0\\ 0& 0& 0& 0& 0& 1\end{array}\right)$

(91) FIG. 4 represents schematically a tree which comprises the terminal nodes {0, 3,4}, i.e. qubits q.sub.0, q.sub.3 and q.sub.4. In FIG. 4, the nodes (qubits) which are not terminal nodes are represented by dark dots.

(92) The target (root) for the set of fan-in CNOT gates corresponds to the qubit of index q′=3, i.e. q.sub.3, and the rows of indexes 0 and 4 are going to be added to the row of index 4 (target/root) according to the tree.

(93) When applying the algorithm described above for the synthetization of the set of fan-in CNOT gates, we can see that, when considering the root q.sub.3, there is a single leaf q.sub.4. The algorithm will follow the path from the root q.sub.3 to the leaf q.sub.4. Along this path, the algorithm will add CNOT gates between a node and its parent node if this node is not a terminal node. In the considered example, the algorithm inserts the CNOT gates CNOT.sub.1,3 and CNOT.sub.2,0 in the synthesized quantum sub-circuit c. Part a) of FIG. 5 represents schematically the corresponding quantum sub-circuit c at this stage.

(94) By adding the corresponding rows of the matrix A.sup.−1 (adding the row of index 1 into the row of index 3, and then adding the row of index 2 into the row of index 0), we get the following matrix:

(95) $\left(\begin{array}{cccccc}1& 0& 1& 0& 0& 0\\ 0& 1& 0& 0& 0& 0\\ 0& 0& 1& 0& 0& 0\\ 1& 1& 0& 1& 0& 0\\ 0& 0& 0& 1& 1& 0\\ 0& 0& 0& 0& 0& 1\end{array}\right)$

(96) Then the algorithm will follow the reverse path in T and add a CNOT gate between each node and its parent node along the reverse path. In the considered example, the algorithm inserts the CNOT gates CNOT.sub.4,2, CNOT.sub.2,0, CNOT.sub.0,1 and CNOT.sub.1,3 in the quantum sub-circuit c. Part b) of FIG. 5 represents schematically the corresponding quantum sub-circuit c at this stage.

(97) By adding the corresponding rows of the previous matrix (adding the row of index 4 into the row of index 2, then adding the row of index 2 into the row of index 0, then adding the row of index 0 into the row of index 1, and then adding the row of index 1 into the row of index 3), we get the following matrix, which comprises the parity e.sub.4 at the row of index q′=3:

(98) 0$\left(\begin{array}{cccccc}1& 0& 0& 1& 1& 0\\ 1& 1& 0& 1& 1& 0\\ 0& 0& 1& 1& 1& 0\\ 0& 0& 0& 0& 1& 0\\ 0& 0& 0& 1& 1& 0\\ 0& 0& 0& 0& 0& 1\end{array}\right)$

(99) The compiling method 50 proceeds with the algorithm for synthesizing the set of fan-out gates, aiming at cancelling the non-zero values of the column of index q=4, except the non-zero value at the row of index q′=3. The non-zero values are located at the rows of indexes 0, 1, 2, 3 and 4, such that {y′.sub.1, . . . ,y′.sub.k}={0,1,2,3,4}. FIG. 6 represents schematically a tree which comprises the terminal nodes {0, 1,2, 3,4}, i.e. qubits q.sub.0, q.sub.1, q.sub.2, q.sub.3 and q.sub.4.

(100) When applying the algorithm described above for the synthetization of the set of fan-out CNOT gates, the algorithm will follow the path from the root (control) q.sub.3 to any leaf. Along this path, the algorithm will add CNOT gates between the root q.sub.3 and any node for which the row in the previous matrix has a zero value at the column of index q=4. In the previous matrix, the row of index 5 is the only one having a zero value at the column of index 4. Hence, the algorithm inserts the CNOT gate CNOT.sub.3,5 to the quantum sub-circuit c in part b) of FIG. 5. Part a) of FIG. 7 represents schematically the corresponding quantum sub-circuit c at this stage.

(101) By adding the corresponding rows of the previous matrix (adding the row of index 3 into the row of index 5), we get the following matrix:

(102) $\left(\begin{array}{cccccc}1& 0& 1& 0& 0& 0\\ 0& 1& 0& 0& 0& 0\\ 0& 0& 1& 0& 0& 0\\ 1& 1& 0& 1& 0& 0\\ 0& 0& 0& 1& 1& 0\\ 0& 0& 0& 0& 1& 1\end{array}\right)$

(103) Then the algorithm will follow the reverse path in T′ and cancel the non-zero values, until the root q.sub.3 is reached, by adding a CNOT gate between each node and its parent node along the reverse path. In the considered example, the algorithm inserts the CNOT gates CNOT.sub.to, CNOT.sub.4,2, CNOT.sub.3,1, CNOT.sub.5,4 and CNOT.sub.3,5 in the quantum sub-circuit c. Part b) of FIG. 7 represents schematically the corresponding quantum sub-circuit c at this stage.

(104) By adding the corresponding rows of the previous matrix (adding the row of index 1 into the row of index 0, then adding the row of index 4 into the row of index 2, then adding the row of index 3 into the row of index 1, then adding the row of index 5 into the row of index 4 and then adding the row of index 3 into the row of index 5), we get the matrix B.sup.−1, which comprises the parity e.sub.4 at the row of index q′=3, and a single non-zero value in the column of index q=4:

(105) $B^{-1}=\left(\begin{array}{cccccc}0& 1& 0& 0& 0& 0\\ 1& 1& 0& 1& 0& 0\\ 0& 0& 1& 0& 0& 0\\ 0& 0& 0& 0& 1& 0\\ 0& 0& 0& 1& 0& 1\\ 0& 0& 0& 0& 0& 1\end{array}\right)$

(106) The description of the modified synthesized accumulated operator is given by the matrix B. FIG. 8 represents the partial quantum sub-circuit c.sub.p which corresponds to the quantum sub-circuit c represented in part b) of FIG. 7 followed by the Hadamard gate H applied on the qubit of index q′=3, i.e. on qubit q.sub.3. In this example, the Hadamard gate H is the last quantum gate of the input quantum circuit c.sub.in, such that the output quantum circuit c.sub.out corresponds to the partial quantum sub-circuit c.sub.p represented in FIG. 8.

(107) As discussed above, the last synthesized accumulated operator, which corresponds in the present example to the matrix B, may then be fully synthesized and the last synthesized quantum sub-circuit may be appended to the output quantum circuit c.sub.out. Alternatively, it is possible to implement all or part of the operations of the matrix B by a non-quantum computer.

(108) FIG. 9 represents schematically the output quantum circuit c.sub.out obtained from the input quantum circuit c.sub.in of FIG. 3, and by selecting q′=4 (instead of q′=3) together with more optimal trees. Compared to the output quantum circuit c.sub.out represented in FIG. 8, it can be seen that the number of CNOT gates has been drastically reduced. Hence, it is possible to optimize the partial quantum sub-circuit c.sub.p (and, in fine, the output quantum circuit c.sub.out) by e.g. accurately selecting the root, i.e. the index q′.

(109) Such an optimization may be performed for a single partial quantum sub-circuit c.sub.p or, preferably, by considering recursively a plurality of successive partial quantum sub-circuits c.sub.p computed for successive quantum gates which belong to the subset S. Hence, in preferred embodiments, the compiling method 50 may comprise

(110) synthesizing a plurality of candidate partial quantum sub-circuits c.sub.1,p for one first processed quantum gate of the input quantum circuit c.sub.in, associated to respective candidate target qubits (i.e. terminal nodes) for a set of fan-in CNOT gates,

(111) synthesizing a plurality of candidate partial quantum sub-circuits C.sub.2,p for at least one second processed quantum gate of the input quantum circuit c.sub.in, associated to respective candidate target qubits (i.e. terminal nodes) for a set of fan-in CNOT gates and/or to respective candidate partial quantum sub-circuits c.sub.1,p of the first processed quantum gate,

(112) selecting one candidate partial quantum sub-circuit c.sub.1,p, c.sub.2,p for each processed quantum gate among the first processed quantum gate and each second processed quantum gate, the selected candidate partial quantum sub-circuits c.sub.1,p, c.sub.2,p minimizing the number of CNOT gates over a predetermined number of successive processed quantum gates of the input quantum circuit c.sub.in which belong to the subset S.

(113) FIG. 10 represents schematically another example of input quantum circuit c.sub.in which comprises two quantum gates which belong to the subset S, a phase quantum gate R.sub.Z(π) applied on the qubit q.sub.4 and an Hadamard gate H applied on the qubit q.sub.3. When applying the algorithm for synthesizing the set of fan-in CNOT gates for the phase quantum gate R.sub.S(π), there will be three different terminal nodes for selecting the root (index q′): {y.sub.1, . . . , y.sub.k}={0, 3, 4}. As discussed above, the choice of the root may impact the number of CNOT gates of the partial quantum sub-circuit c.sub.1,p. It may also impact the number of CNOT gates of the partial quantum sub-circuit c.sub.2,p synthesized to insert the Hadamard gate H.

(114) FIG. 11 represents a tree illustrating how the choice of specific roots might impact the total number of CNOT gates of the output quantum circuit c.sub.out, in the case of the input quantum circuit c.sub.in of FIG. 10.

(115) The top of the tree in FIG. 11 represents the situation right before computing the partial quantum sub-circuit c.sub.1,p. For computing the partial quantum sub-circuit c.sub.1,p, three different terminal nodes (i.e. candidate target qubits) are possible for selecting the root ({y.sub.1, . . . , y.sub.k}={0, 3, 4}), yielding three different candidate partial quantum sub-circuits c.sub.1,p. The following nodes of the tree in FIG. 11 provide the costs in terms of CNOT gates of each of the candidate partial quantum sub-circuits c.sub.1,p:

(116) the first candidate partial quantum sub-circuit c.sub.1,p (for q′=0) comprises six CNOT gates;

(117) the second candidate partial quantum sub-circuit c.sub.1,p (for q′=3) comprises six CNOT gates; and

(118) the third candidate partial quantum sub-circuit c.sub.1,p (for q′=4) comprises six CNOT gates.

(119) At this stage, all three different terminal nodes (i.e. candidate target qubits) are equivalent in terms of CNOT gates required.

(120) When applying the algorithm for synthesizing the set of fan-in CNOT gates for the Hadamard gate H, there will be also, in general, different terminal nodes (candidate target qubits) for selecting the root (index q′). The candidate target qubits are not necessarily the same after each candidate partial quantum sub-circuit c.sub.1,p:

(121) after the first candidate partial quantum sub-circuit c.sub.1,p, the candidate target qubits for the root node are {0, 3};

(122) after the second candidate partial quantum sub-circuit c.sub.1,p, the only candidate target qubit for the root node is {0}; and

(123) after the third candidate partial quantum sub-circuit c.sub.1,p, the candidate target qubits for the root node are {3, 4}.

(124) For each of these candidate target qubits of each candidate partial quantum sub-circuit c.sub.1,p, a candidate partial quantum sub-circuit c.sub.2,p is computed. This yields five different candidate partial quantum sub-circuits c.sub.2,p comprising respectively six, six, three, six and eight CNOT gates. This yields also five different candidate output quantum circuits c.sub.out comprising respectively twelve, twelve, nine, twelve and fourteen CNOT gates. Hence, the best choice corresponds to the output quantum circuit c.sub.out obtained by selecting q′=3 for the partial quantum sub-circuit c.sub.1,p and q′=0 for the partial quantum sub-circuit c.sub.2,p, which comprises nine CNOT gates.

(125) It should be noted that such a recursive optimization may be performed other all or part of the quantum gates of the input quantum circuit c.sub.in which belong to the subset S, or over a predetermined number N.sub.g of these quantum gates (in which case (N.sub.g−1) is referred to as the depth of the recursive optimization).

(126) FIG. 12 represents schematically the output quantum circuits c.sub.out obtained for different depths for the input quantum circuit c.sub.in of FIG. 10. More specifically, part a) of FIG. 12 represents the output quantum circuit c.sub.out obtained for a depth of zero (i.e. no recursive optimization), while selecting successively q′=0 for the partial quantum sub-circuit c.sub.1,p and q′=0 for the partial quantum sub-circuit c.sub.2,p. Part b) of FIG. 12 represents the output quantum circuit c.sub.out obtained for a depth of one (i.e. recursive optimization over two successive quantum gates which belong to S), while selecting successively q′=3 for the partial quantum sub-circuit c.sub.1,p and q′=0 for the partial quantum sub-circuit C.sub.2,p.

Example with Clifford Operators

(127) The natural extension of the class of reversible linear Boolean operators is the Clifford group . Clifford operators are operators that stabilize the Pauli group P. They can be represented efficiently using data structures called “Tableau” that specify how they act by conjugation over generators of the Pauli group [AG04]. In practice, this means that we can implement a data structure T.sub.a (a Tableau), representing a Clifford operator in that:

(128) can be easily updated: T.sub.a←{tilde over (g)}.Math.T.sub.a or T.sub.a←T.sub.a.Math.{tilde over (g)} for some Clifford gate g;

(129) can be used to efficiently compute the conjugate of some n-qubits Pauli operator P with respect to a Clifford operator T.sub.a, by computing T.sub.aPT.sub.a.sup..Math., yielding another Pauli operator (and potentially a phase s).

(130) In the sequel, we define the support of a Pauli operator P as the set of qubits such that P acts non-trivially on them. For instance, if P=[I.Math.Z.Math.X.Math.I], then the support of P is the set of indexes {1, 2} since P acts as the identity operator on the qubits of indexes 0 and 3. For ease of notations, we drop the operators .Math. in the sequel.

(131) In the present example, we consider that .sub.in contains only Clifford gates and arbitrary Pauli rotations, R.sub.p for P∈. We assume in a non-limitative manner that .sub.out contains the quantum gates CNOT, H, R.sub.X(π/2), R.sub.X(−π/2) and arbitrary R.sub.Z(θ) rotations, the CNOT gates being restricted to some connectivity graph G.

(132) Formally, we assume in the sequel that the set of high-level synthesizable descriptions of synthesizable operators corresponds to the set of Tableaus representing Clifford operators. . is the standard Tableau interpretation but reversed for ease of notation: t.sub.a=U(T.sub.a).sup.† where U: T.sub.a.fwdarw.U(T.sub.a) associates to each Tableau T.sub.a its Clifford operator. In other words, t.sub.a is the inverse of the Clifford operator described by T.sub.a.

(133) The subset S corresponds to the set of Clifford gates. Accordingly, the subset S includes the arbitrary Pauli rotations (i.e. the Pauli rotations with an angle θ≠k.Math.π/2 with k being an integer).

(134) The update function u is the update of a stabilizer Tableau using a Clifford gate by right composition with the inverse:
u(T.sub.a,g)=T.sub.a.Math.{tilde over (g)}.sup.†

(135) Upon encountering a non-Clifford Pauli rotation R.sub.p(θ), and assuming the synthesizable accumulated operator is described by a Tableau T.sub.a, the extraction function e performs as follows:

(136) i) compute a Pauli operator P′ and a phase s=±1 such that:
s.Math.P′=T.sub.aPT.sub.a.sup.†

(137) ii) for each qubit i in the support of P′, perform a local basis change using either a quantum gate H or R.sub.S(π/2) in order to change its basis to the axis Z (the choice of the axis Z is arbitrary and is the reason why we assume in the present example that the arbitrary Pauli rotations are R.sub.Z(θ) rotations in .sub.out; however, another axis may be chosen in other examples), i.e. if P′[i]=Y then apply a quantum gate R.sub.X(π/2) on the qubit of index i, and if P′[i]=X then apply a quantum gate H on the qubit of index i; for instance, if P′=[I X Y Z I], then we produce a Clifford quantum sub-circuit c=H.sub.1::R.sub.X,2(π/2) (i.e. H on the qubit of index 1 and R.sub.X(π/2) on the qubit of index 2);

(138) iii) select a target qubit of index q′ in the support of P′ and perform the algorithm for synthesizing a set of fan-in CNOT gates presented above, in order to generate a set of fan-in CNOT gates from all qubits in support of P′ to the qubit of index q′ (which index q′ might be optimized according to the recursive optimization scheme described above), thus updating the Clifford quantum sub-circuit c by appending to it the set of fan-in CNOT gates;

(139) iv) compute the modified synthesizable accumulated operator, described by a Tableau T′.sub.a, by left composition with c:
T′.sub.a←{tilde over (c)}.Math.T.sub.a

(140) v) return the Tableau T′.sub.a as the description of the modified synthesizable accumulated operator and the partial quantum sub-circuit c.sub.p=c::R.sub.Z,q′(s.Math.θ), with the phase quantum gate R.sub.Z(s.Math.θ) applied on the selected qubit of index q′ (root).

(141) It is easy to verify that:
u(T.sub.a,g)=T.sub.a.Math.g.sup.†=U(g).Math.U(T.sub.a).sup.†={tilde over (g)}.Math.T.sub.a

(142) Moreover, the following proposition about the extraction function e holds. Let T.sub.a be a Tableau and R.sub.p(0) be an arbitrary Pauli rotation. If (T′.sub.a, c.sub.p)=e(T.sub.a, R.sub.p(θ)) then R.sub.p(θ).Math.t.sub.a=T′.sub.a.Math.{tilde over (c)}.sub.p.

(143) Indeed, by construction we have:

(144) $c_p=c\colon\colon R_{Z,q\prime }\left(s.Math.\theta \right)$
expression in which c and q′ are such that:

(145) $c\colon\colon R_{Z,q^{\prime }}\left(s.Math.\theta \right)\colon\colon c^{†}=R_{P\prime }\left(s.\theta \right)$
where s.Math.P′=T.sub.aPT.sub.a.sup.† and c is a Clifford quantum sub-circuit. This implies that {tilde over (c)}.sub.p={tilde over (c)}.Math.R.sub.p′(s.Math.θ). More specifically, c holds the local basis changes and the set of fan-in CNOT gates necessary to the implementation of R.sub.p′(s.Math.θ).

(146) Hence, we have:

(147) $\begin{array}{c}{R}_P\left(\theta \right).〚T_a〛=〚T_a〛.{〚T_a〛}^{†}.R_P\left(\theta \right).〚T_a〛.{〚T_a〛}^{†}.〚T_a〛\\ =〚T_a〛.U\left(T_a\right).R_P\left(\theta \right).{U\left(T_a\right)}^{†}\\ =〚T_a〛.R_{T_a{\mathrm{PT}}_a^{†}}\left(s.Math.\theta \right)\\ =〚T_a〛.R_{P\prime }\left(s.Math.\theta \right)\\ =〚T_a〛.{\tilde{c}}^{†}.\tilde{c}.R_{P\prime }\left(s.Math.\theta \right)\\ =〚\tilde{c}.T_a〛.{\tilde{c}}_p\\ =〚T_a^{\prime }〛.{\tilde{c}}_p\end{array}$

(148) FIG. 13 represents schematically an example of input quantum circuits c.sub.in which comprises a single non-Clifford Pauli rotation (the last quantum gate R.sub.Y(θ)). The target quantum computer is assumed to have the connectivity graph G represented in FIG. 2.

(149) The compiling method 50 aggregates a synthesizable accumulated operator represented by a Tableau T.sub.a corresponding to all the quantum gates except the last one, using right composition with the inverse of the quantum gates (update function u).

(150) Upon reaching the last quantum gate R.sub.Y(θ), the compiling method 50 constructs the rotation axis of the quantum gate, yielding the Pauli operator P corresponding to [I Y I I I I]. Once conjugated with respect to the current Tableau T.sub.a, this gives the Pauli operator P′ which corresponds to [I Z X Z I Z] and an additional phase s=+1. Hence, the qubits in support of P′ are {1, 2, 3, 5}, and we need to synthetize a rotation of support {1, 2, 3, 5}. For that purpose, we insert a Hadamard quantum gate H in order to change the basis of the qubit of index 2 into the Z axis.

(151) Then we compute a tree T (preferably a Steiner tree) containing all the support of the rotation, i.e. having the terminal nodes {1, 2, 3, 5}. FIG. 14 represents the computed tree T. Then the algorithm for synthetizing the set of fan-in CNOT gates, presented above, is applied. The selected root corresponds for instance to the qubit of index q′=1.

(152) FIG. 15 represents schematically the output quantum circuit c.sub.out obtained for the input quantum circuits c.sub.in represented in FIG. 13. As can be seen in FIG. 15; the output quantum circuit c.sub.out comprises first the Hadamard quantum gate H applied to the qubit of index 2 (local basis change), and the set of fan-in CNOT gates which comprise CNOT gates CNOT.sub.5,3, CNOT.sub.2,3 and CNOT.sub.3,1. Finally, the output quantum circuit c.sub.out comprises the phase quantum gate R.sub.Z(s.Math.θ) (with s=+1) applied on the selected qubit (root), i.e. applied on the qubit of index q′=1. The modified synthesizable accumulated operator T′.sub.a is obtained by left composition of the of the current synthesizable accumulated operator T.sub.a with the operator e corresponding to the quantum sub-circuit c.

(153) As discussed above, the last synthesizable accumulated operator, represented by a Tableau T.sub.a, can be either completely synthesized, or processed in all or part by a non-quantum computer.

(154) It is emphasized that the present invention is not limited to the above exemplary embodiments. Variants of the above exemplary embodiments are also within the scope of the present invention.

(155) The above description clearly illustrates that by its various features and their respective advantages, the present disclosure reaches the goals set for it. In particular, by accumulating in the synthesizable accumulated operator the operators of a set of synthesizable operators, the need for synthetization is reduced together with the associated computational complexity. Also, when encountering an operator that does not belong to the set of synthesizable operators, the synthesizable accumulated operator may be only partially synthesized, thereby reducing also the need for synthetization.

REFERENCES

(156) [AG04] Scott Aaronson and Daniel Gottesman: “Improved simulation of stabilizer circuits”, Physical Review A, 70(5), November 2004, arxiv.org/pdf/quant-ph/0406196.pdf.

(157) [KvdG19] Aleks Kissinger and Arianne Meijer van de Griend: “CNOT circuit extraction for topologically-constrained quantum memories”, 2019, arxiv.org/pdf/1904.00633.pdf.

(158) [vdGD20] Arianne Meijer van de Griend and Ross Duncan: “Architecture-aware synthesis of phase polynomials for NISQ devices”, 2020, arxiv.org/pdf/2004.06052.pdf.