METHOD FOR SIMULATING A QUANTUM CIRCUIT ON A CLASSIC COMPUTER

专利摘要:
A method of simulating, on a semiconductor integrated circuit computer processing unit, the operation of a quantum circuit model, which comprises the steps of: dividing the quantum circuit into adjacent Lk layers for successive traversing by the n qubits taken together, each layer comprising a single quantum gate Gk; o assign to each quantum gate Gk of the circuit a type among three predefined types of quantum gates: • Gate of diagonal type, whose transfer matrix is diagonal; • Classic type gate, whose transfer matrix is non-diagonal and includes operators worth 0 or 1 due to a single operator per line and column; • Dense type door, which is neither conventional nor diagonal type.
公开号:FR3064380A1
申请号:FR1770299
申请日:2017-03-24
公开日:2018-09-28
发明作者:Cyril Allouche；Minh Thien Nguyen
申请人:Bull SA；
IPC主号:

专利说明:

(54) METHOD FOR SIMULATING, ON A CLASSIC COMPUTER, A QUANTUM CIRCUIT.
FR 3 064 380 - A1 (bg) Method for simulating, on a computer processing unit with an integrated circuit on a semiconductor, of the operation of a quantum circuit model, which comprises the operations consisting in:
o divide the quantum circuit into d adjacent layers L _k intended to be crossed successively by the n qubits taken together, each layer comprising a single quantum gate G _k ;
o assign to each quantum gate G _k of the circuit one type among three predefined types of quantum gates:
Diagonal type door, the transfer matrix of which is diagonal;
Door of conventional type, whose transfer matrix is non-diagonal and includes operators worth 0 or 1 at the rate of a single operator per row and per column;
Dense type door, which is neither classic nor diagonal.

Method for simulating, on a conventional computer, a quantum circuit
The invention relates to the field of data processing, and more precisely to the simulation of a quantum logic circuit by means of a computer structured in a conventional manner - that is to say using processors comprising logic gates each consisting of a circuit of transistors which can be crossed by electron flows.
The design of a computer (which can be likened to a processor, the two terms being synonymous here) is generally based on a preliminary phase of algorithmic simulation of its operation (that is to say of the operation of the logic circuits which make it up) to generally predict its behavior and, more particularly, the results that the computer would provide after the execution of a given program.
The operations (eg addition, subtraction, multiplication) are carried out by combinations of elementary logic gates with transistors, which carry out logic functions applied to input bits (of value 0 or 1) and whose results are bits output (value 0 or 1). Let us cite as an example the logical functions NOT, AND, OR, NOR, NAND.
The miniaturization of transistors, made possible by the increasing smoothness of semiconductor etching processes, has made it possible to multiply the computing power and storage capacity (or memory) of computers. According to Moore's conjecture (known as Law), the density of transistors that can be etched on a semiconductor would have more or less doubled every two years since the 1960s.
As long as the transistors remain on the micrometric scale, classical physics (with the laws of electricity) remains applicable, and the functions performed by the logic gates remain deterministic, which makes it possible to apply a simulation algorithm. simple, linear algebra.
In a conventional computer (in the sense that it comprises transistors operating in accordance with the laws of electricity of classical physics), the output (that is to say the result) of a program requiring n bits in input (each of value 0 or 1) can be modeled by a state vector with 2 ⁿ components, which represents the set of possible values of the output bits.
It is therefore understood that the addition of an input bit leads to a multiplication by 2 of the number of possible values of the output bits. In other words, any linear increase in inputs (adding bits) translates into an exponential increase in the computing (and / or memory) capacity required.
Given the growing application needs (e.g. computer-assisted medicine, driving autonomous vehicles, high-definition image processing), the miniaturization of logic circuits continues, and we are now reaching nanoscales and even atomic.
At these scales, information is no longer conveyed by electrical flows whose behavior can be determined and predicted by the laws of classical physics, but by particles (or quanta) whose behavior, largely probabilistic, responds to the laws of quantum physics.
In a quantum computer, it is the qubit (contraction of quantum bit) which represents the elementary unit of information storage, by analogy to the bit which, itself, represents the elementary unit of information storage in a classic computer.
If the value of a bit is always - and permanently - 0 or 1 depending on the operation applied to it (identity: 0 -> 0 or 1 -> 1; NOT: 0—> 1 or 1 -> 0 ), the value of a qubit is undetermined as probabilistic.
A fairly clear definition of the qubit is proposed by Benenti et al, Principles of Quantum Computation and Information, Volume I: Basic Concepts, World Scientific Publishing Co, 2004. According to this definition, a qubit is a quantum system whose state is described by a wave function ψ, denoted ψ) according to Dirac's bra-ket formalism, in a Hilbert space. The wave function ψ) is written as a linear combination of the possible qubit values:
ψ) = α 0) + β 1)
Where | 0) and | 1) represent the values 0 and 1 (or basic state) of a classical bit, and where the coefficients a and β, called "probability amplitudes", are complex numbers normalized according to the following relation :
| a | ² + | / | ² = l
From a geometric point of view, a qubit can be represented by a point positioned on the surface of a so-called Bloch sphere (of radius 1), whose spherical coordinates are Θ (0 <θ <π) and φ (0 <φ <2π).
Under these conditions, the state φ) of the qubit can be written in the form of the following equation:
θ Θ Ψ) = cos- | 0> + e ^{l <} / sin-11>
... or in the form of the following state vector:
/ Θ / cos 2
These equations testify, counterintuitively, to a continuity of state of the qubit, which can take an infinity of states - as long as it is not measured: therefore its value is determined (0 or 1). This continuity means that in theory a single qubit is capable of storing an infinite amount of information, which gives hope for the quantum computer of particularly interesting performances in terms of computation and storage, even though its compactness makes it attractive. as an object.
However, the laws of quantum mechanics freeze the state of the qubit as soon as it is read; it is impossible to go back to the values of the amplitudes a and β, and therefore impossible to know the instantaneous state of the qubit.
In the current state of knowledge, qubits are intended to be used in a manner analogous to conventional bits, that is to say to be combined into a register of n qubits (n an integer) capable of being processed. within a computer program.
The state of n qubits is described by a wave function φ) generalized in a Hilbert space with 2 ⁿ dimensions:
2 ⁿ —1
IVO = Σ ^α ί ΙΟ i = 0
Where | j) represents the possible values (or basic states) of the classic bit combinations, and where the coefficients a _t are the amplitudes of probability of each value, normalized according to the following relation:
2 ⁿ —1 l “il ² = it = 0
So, for two qubits (n = 2):
ψ) = α _ο | 00) + ^a i | 01) + “ ₂ | 10) + a ₃ | ll)
With:
l " ₀ 1 ² + |" i | ² + | a21 ² + l "31 ² = 1
Unlike a classical computer processing a single state of the register among all of its possible states, the quantum computer is theoretically capable of simultaneously processing all of the possible states of the register, ie 2 ⁿ . In other words, the quantum computer by its nature performs its calculations in parallel. It follows that the addition of a qubit multiplies by 2 the computing power of the computer, this being therefore an exponential function of the size of the register. To fix the ideas, it suffices to indicate that for n = 300 (i.e. 300 qubits), the size of the register - and therefore the number of states (each characterizing information) of it that the computer can process simultaneously - is 2 ³³⁰ = 10 ⁹ °, which corresponds to the estimated number of particles in our observable universe.
In the near future, and realistically, quantum computers are expected to be able to solve problems currently unsolvable by conventional computers due to the unreasonable computational capacity that would be required - and the computational time. required.
A well-known example of a mathematical problem that conventional algorithms running on conventional computers fail to solve in reasonable time is the factorization of a natural integer N (typically 15 = 3x5). It is this relative inability of conventional computers to solve the factorization problem that has made RSA (Rivest-Shamir-Aldeman) encryption crypto exploitable, whose generation of public keys is indeed based on the product of whole numbers.
Shor’s quantum algorithm (see e.g. a presentation of this algorithm in Lomonaco, Shor’s Quantum Factoring Algorithm, Proceedings of Symposia in Applied Mathematics, University of
Maryland, 2000) allows - in theory - to solve the problem of factorization of a natural integer N in a time whose order of magnitude is asymptotically algorithmic, that is to say (in notation called "large O> > from Landau), of the order of 0 (log (N)). The Shore algorithm is based on the use of a quantum Fourier transform, whose efficiency is much higher than that of conventional Fourier transforms.
We can therefore see the interest there is in modeling now, on conventional computers, quantum logic circuits. However, memory space and computing power are limiting factors.
Thus, a known modeling of a quantum logic circuit with n qubits consists in mathematically representing this circuit by a matrix (denoted U, called operation matrix - in English: Operation Matrix) of size 2 ⁿ x2 ⁿ and which, applied to a vector of initial state E of size 2 ⁿ , outputs a vector of final state E ', also of size 2 ⁿ and matrix product of E by U:
E '= U-E
This modeling is tested in particular in Gerdt et al, A Mathematica Program for Constructing Quantum Circuits and Computing Their Unitary Matrices, Workshop on Quantum Physics and Communication, Oct. 2007.
However Patrzyk et al, Towards a Novel Environment for Simulation of Quantum Computing, Computer Science 16 (1) 2015, 103129, evaluated the memory capacity (corresponding to the number of bits that can be stored in memory) necessary, for a conventional computer, to the simulation of a given number of qubits (and more precisely to the storage of the operation matrix), and provided a list of interesting numerical examples presented in the table (Table 1 p.106) reproduced below (the memory is indicated in Bytes (bytes); the prefixes k, M and T corresponding respectively to the operators kilo, mega and Tera):
Number of qubits 5 10 20 21 Memory (state vector) 512 B 16kB 16MB 32MB Memory (Operation Matrix) 16B 16MB 16TB 64TB
It can be shown that, if we denote N the memory capacity of a conventional computer necessary for storing the operation matrix U, the maximum number, noted n _m , of simulable qubits is not greater than:
logQV)
21og (2)
A known technique, to limit the memory capacity necessary for the calculation (or, with equivalent memory capacity, to increase the number n _m of simulable qubits), consists in performing an approximation of the operation matrix U by reducing its size by means of a so-called Schmidt decomposition, the methodology of which is described in particular in the reference work A. Nielsen & I. Chuang, Quantum Computation and Quantum Information, Cambridge University Press, 1 Oth Anniversary Edition, 2010, p.109 et seq. But we note in practice that, if this approximation can provide acceptable results for some simple quantum circuits (eg for an AND type logic gate), it cruelly lacks robustness for more complex circuits (eg for a circuit quantum Fourier transform).
Samad et Al, Memory Efficient Quantum Circuit Simulator Based on Linked List Architecture, 2005, proposes to get rid of a complete memorization of the matrix (noted U above) of the quantum logic circuit by pretending to subdivide it into columns and by successively performing the dot product of each column with the state vector representing the input qubits, the columns being progressively erased from memory as their dot product is produced (cf. Efficient implementation, p. 4-5). However, although he claims to have successfully applied this method to Shor's algorithm, and although he further claims to have been able to simulate 20 qubits in a reasonable amount of time, Samad does not detail this method.
We therefore see that the need persists for a simulation (running on a conventional computer) of a quantum circuit, capable, by comparison with known simulations, of better performance, and more precisely capable of accounting for the state:
either a greater number of qubits with equivalent memory capacity, or the same number of qubits with more reasonable memory capacity.
To this end, a method of simulation is proposed, on a computer processing unit with an integrated circuit on a semiconductor, of the operation of a quantum circuit model configured to process a predefined number n (n an integer such that n> 2) of input qubits and comprising a series of d (of an integer such as d> 2) quantum gates G _k (k an integer, 1 <k <d) elementary selected from a library of predefined models of quantum gates stored in an integrated circuit memory on a semiconductor, each quantum gate model being associated with a transfer matrix U _k comprising operators ordered in rows and columns and defining all the possible state transitions of qubits passing through this gate, this process comprising:
a configuration phase of the quantum circuit, which includes the operations consisting of;
o define the number n of qubits to be processed at the input of the quantum circuit model;
o select the d models of quantum gates; o arrange the d models of quantum gates thus selected to constitute the model of quantum circuit; an analysis phase of the quantum circuit model thus configured, which includes the operations consisting of:
o divide the quantum circuit into d adjacent layers L _k intended to be crossed successively by the n qubits taken together, each layer comprising a single quantum gate;
o assign to each quantum gate of the circuit one type among three predefined types of quantum gates:
• Diagonal type door, whose transfer matrix is diagonal;
• Classic type door, whose transfer matrix is non-diagonal and includes operators worth 0 or 1 at the rate of a single operator per row and per column;
• Dense type door, which is neither classic nor diagonal;
A calculation phase, which includes the repetition, for y = l to j = 2 ⁿ (j an integer) of the following operations:
a) define a vector | φ ₇ ) of state of the n qubits at the input of the quantum circuit, which includes a series of 2 ⁿ amplitude coefficients a [(i an integer, 0 <i <2 ⁿ -1) worth 0 or 1, and such that:
2 ⁿ -l
t = 0
b) repeat, for k = 1 to k = d, the following sequence:
b1) take into account a vector ifj ^] k) state of the n qubits at the input of the layer L _k , this vector ifj ^] k) comprising a series of 2 ⁿ amplitude coefficients a [ ^{, k} ;
b2) identifying the gate G _k included in the layer L _k ;
b3) take into account the type of gate G _k ;
b4) if the gate G _k is of diagonal type, assign to the vector | ι / ^ ₊₁ > state of the n qubits leaving the layer L _k the value of the vector ifj ^] k) state of the n qubits entering in this one :
| ν ^ ₊ ι> = l ^>
b5) if the gate G _k is of conventional type:
o detect in its transfer matrix each operator worth 1 and determine its row number l and column number c (Z and c integers such as 0 <l <2 ⁿ , 0 <c <2 ⁿ and l ψ c) ;
o assign to the amplitude coefficients a / ' ^{fe + 1} of the vector | ip ^ ₊₁ > of the state of the n qubits leaving the layer L _k the following values:
a {' ^{k + 1} = a {' ^k for all i Ψ 1 o memorize the vector | φ ^ ₊₁ ) in a dedicated register of an integrated circuit memory on semiconductor;
b6) if the gate G _k is of dense type:
o determine the set of possible values of the vector | ip ^ ₊₁ > of state of the n qubits leaving the layer L _k such that:
IC) = WJ o memorize each possible value of the vector | ^ _{+ i} > in a dedicated register of an integrated circuit memory on a semiconductor;
c) aggregate, in a single register of a semiconductor integrated circuit memory, the set of possible states of the vector | ^ ₊₁ >.
This method makes it possible to simulate with greater efficiency (that is to say faster, and using less memory space) a quantum circuit, compared to known methods.
The invention will now be detailed in the description of an embodiment, given below with reference to the accompanying drawings in which:
FIG.1 is a schematic representation of an example of a quantum logic gate of the diagonal type, associated with a state transition graph of qubits passing through this gate;
FIG.2 is a schematic representation of an example of a quantum logic gate of the conventional type, associated with a state transition graph of qubits passing through this gate;
FIG. 3 is a schematic representation of an example of a quantum logic gate of dense type, associated with a state transition graph of qubits passing through this gate;
FIG. 4 is a schematic representation of an example of a quantum logic circuit comprising a series of quantum logic gates, associated with a graph of the transitions of qubit states passing successively through these logic gates.
We want to simulate, on a computer processing unit with an integrated circuit on a semiconductor, the operation of a (any) model of quantum circuit configured to process a predefined number n of qubits at the input of this circuit.
The expression “computer processing unit with integrated circuit on semiconductor” designates any processor (also called microprocessor) comprising sets of transistors obtained according to conventional techniques of purification, etching, doping of semiconductor materials (such as silicon ) and each capable of being crossed (or not, depending on the state of the transistor) by a flow of electric current which can be modeled by the laws of classical physics (in particular Ohm's law).
A transistor supplies, at the output, a signal whose value, determined by the state of the transistor, is equal by convention to 0 or 1. This value is allocated to a unit of binary numeration called bit, base of coding of the conventional computers today known (and used) to the general public.
The theoretical advances allowed in particular by Hilbert, Dirac and Schrodinger have opened up a field of investigation aimed at designing a quantum computer, that is to say a computer whose basic component would be miniaturized on a nanometric or even atomic scale, and would no longer see current flows on this scale like the transistor we know, but electrons per unit, which each provide the value of a bit (0 or 1).
As the electron, considered alone, has a behavior which no longer obeys the classical laws of physics but the laws of quantum mechanics, probabilistic by nature, the component in question provides as an output a signal whose value is indeterminate but qu 'it is however possible to describe by means of mathematical tools developed for quantum mechanics, and in particular by means of the equation relating the state (or wave function) called superposition in which the particle is found (here the electron).
We will not explain here the exact nature of the physical phenomena at work (especially with regard to the spin, the position and the momentum of the electron), because this is not only irrelevant, but also remains debated in the scientific community.
However, we will introduce certain physical and mathematical concepts necessary for a reasoned explanation of the proposed simulation method, which also make it possible to understand how this method performs better than known simulation methods.
Here we use the rating conventions adopted by the literature (see the references mentioned in the introduction). Thus, we write ψ) the wave function (in Bra-ket Dirac notation) describing the state of the particle, or of the particles as we will see.
In dimension 2, for a simple particle called qubit capable of providing two values (0 and 1), the wave function (or state) of the qubit is written:
(ψ) = a 0) + β 1) | 0) and | 1) represent, in bra-ket notation, the values 0 and 1 (or basic state) of a classical bit, all expressing the fact that these values are probable (and not certain) values which can be adopted by the qubit, it being understood that, in accordance with the laws of quantum mechanics, any measurement carried out on a qubit (corresponding to a particle) definitively fixes its state.
a and β, called "probability amplitudes" or "amplitude coefficients", are complex numbers which each relate the probability of occurrence of the corresponding value (respectively (0) for a and | 1) for β).
a and β verify the following relation called “normalization”:
| a | ² + | ^ | 2 =!
The wave function ψ) (or state) of the unit qubit can also be written in the form of a vector (column matrix):
In this notation, the states | 0) and | 1) are written as follows:
One could limit oneself to the study of a single qubit, since this one is theoretically likely, according to the literature, to store an infinite quantity of information.
However, as it is by nature impossible, from the observed (i.e. measured) value of a qubit, to determine its initial value (s), we generally consider, in the research carried out on the behavior of the quantum computer, a number n (n an integer such that n> 2) of qubits taken together, which one seeks to determine the global state by a generalized wave function ψ).
In a Hilbertian space of dimension n the wave function (or state) ψ) is written:
2 ⁿ —1
IV9 = Σ ^α ί ΙΟ i = 0 | j) represents, in bra-ket notation (Dirac notation) and in binary, the possible values (or basic states) of the classic bit combinations.
The coefficients a _L are the probability amplitudes (or amplitude coefficients) of occurrence of each of these values; these are complex numbers (in the mathematical sense of the term), which together verify the following relationship:
2 ⁿ —1 l “zl ² = ii = 0
With, for all i:
"Z e {0; 1}
We have already presented the wave function ψ) applied to a single qubit. For this very simple case, let us simply observe, to clarify the notations, that a ₀ is noted a and a _x noted β.
For two qubits (n = 2):
ψ) = α _ο | 00) + ^α ι | 01) + “2110) + α ₃ 111)
With:
l "ol ² + l" il ² + l "21 ² + l" s I ² = 1
In vector notation:
/ "O
For three qubits (n = 3):
ψ) = α _ο | 000) + aJOOl) + α ₂ | 010> + “slOH) + α ₄ | 100) + α ₅ | 101) + α ₆ | 110) + α ₇ | 111> With:
l "ol ² + Ι" ι I ² + Ι "2Ι ² + l" 31 ² + Ι "4Ι ² + Ι" ξΙ ² + l "el ² + Ι" Ι ² = 1 In vector notation:
/ ^a o α _γ a ₂ i ^> = 4 a ₅ aj
As we shall see below, the simulation method of a quantum system that will be described based not on a computational approach, addressing the complex notation of the coefficients a _t amplitude, but on a combinatorial approach that takes into account of the set of possible values that the state vector ψ) can take (i.e. the wave function) while eliminating the improbable values of this state vector ψ) as and as qubits progress through the quantum circuit.
As a preliminary point, let us observe that, for two qubits (n = 2, see above), the possible values that can take ψ) are:
... which correspond respectively to the following values of the two qubits taken together:
| 00>; | 01>; | 10>; | 11>
For three qubits (n = 3, see above), the possible values that can take ψ) are:
... which correspond respectively to the following values of the three qubits taken together:
| 000>; | 001>; | 010>; | 011>; | 100>; | 101>; | 110>; | 111>
A quantum circuit modifies the value of the 2 ⁿ qubits which crosses it.
By convention, and for the rest of the presentation, we note ψ) the state of the qubits entering the circuit and ψ ') the state of the qubits leaving it.
ψ) and ψ ') are linked by a transfer function, operated by the quantum circuit and described by a matrix relation:
W) = υ · ψ)
Where U is a matrix, called transfer, of size 2 ⁿ x2 ⁿ , corresponding to the transfer function applied by the quantum circuit to the incoming qubits. The transfer matrix U includes operators u _xy (x and y integers, 0 <% <2 ⁿ - 1, 0 <y <2 ⁿ - 1) which are in the form of complex numbers (in the mathematical sense of the term) . The transfer matrix U represents the set of operations applied by the quantum circuit to the incoming qubits, as described by their state vector ψ).
Noting:
Ψ) =
IV>'> = ^u 00 fa ₀ < ^a 2 ⁿ -l /'"'o a' ₇ n
2 “-l ^{z U} 0 (2-l) ^u (2-l) 0 ^u (2 ⁿ -l) (2 ⁿ -l) /. The relation between ψ ') and ψ can be written as follows ):
^u oo ^u 0 (2-l) “o a ' ₂ n_ ₂ / ^u (2-l) 0 ^u (2 ⁿ -l) (2 ⁿ -l) / ^a 2 ⁿ -2 /
Enumerating, even in linear algebra, all the possible states of qubits at the output of the circuit, requires for a conventional computer very significant resources as soon as the number of incoming qubits is high. In fact, the memory space required grows exponentially with the number of qubits to be processed.
One thus wishes to avoid having to entirely constitute the transfer matrix U (corresponding to the quantum circuit studied) and to have to carry out the matrix computation ψ ') = U ψ).
To this end, the inventors had, firstly, the idea of subdividing the quantum circuit into several successive adjacent layers, through which pass all the qubits entering the circuit and each containing a predetermined elementary quantum logic gate each effecting an operation also predetermined on one or more of the qubits entering the layer (but not necessarily on all of them).
We note d (of an integer such that d> 2) the number of elementary quantum logic gates of the circuit. We decree that d> 2 because an elementary logic gate corresponds to a simple matrix operation, the result of which is easily resolved by known simulations.
We denote by k the index of each layer (k an integer such that l <k <d), which we assign to the letter L to denote by L _k the k ^th layer and to the letter G to denote by Gk the k ^-th logic gate unit, contained in the layer Lk.
The literature (cf. for example Nielsen & Chuang, op.cit.) Has defined a certain number of models of elementary quantum logic gates, each associated with a determined transfer matrix.
As an example:
Hadamard's door, noted H, which applies its transfer function to a single qubit and is defined as follows:
the Pauli gates, denoted X (or NOT), Y and Z, which apply their transfer functions (respectively a permutation and two rotations of angle π), to a single qubit and are respectively defined as follows:
X (YOT) ^ J)
the “Controlled-NOT” gate, denoted CNOT, which applies its transfer function (an inversion) to two qubits and is defined as follows:
0 0 0
10 0 1 0 0 0 1 1 0 0 10 /
CNOT = qSWAP ± the SWAP gate (or qSWAP), which applies its transfer function (a permutation) to two qubits and is defined as follows:
0 0 0
0 1 0 1 0 1 0 0)
0 0 1 / the controlled phase gate, noted associated with an angle noted φ (in the notation used to describe the qubit on the sphere of
Bloch), which applies its transfer function (a rotation of angle φ) to a single qubit and is defined as follows:
/ ¹ 0 0 ⁰ D A 1 0 1 0 ⁰ 1 ^Κφ - 1 0 0 1 ⁰ / 0 0 0 e * / To facilitate the simulation of a any quantum circuit, the inventors have, secondly, had the idea of classifying the different
basic door models (which can be used to configure the quantum circuit) in three types:
• Diagonal type door, whose matrix is diagonal;
• Classic type door, whose matrix is non-diagonal and includes operators worth 0 or 1 at the rate of a single operator equal to 1 per row and per column;
• Dense type door, which is neither classic nor diagonal.
According to this classification:
• Z, ϋφ, in particular, are diagonal type doors;
• X, Y, CNOT, SWAP, in particular, are conventional type doors;
• H, in particular, is a dense type door.
To further facilitate the simulation, the inventors have, in the third place, had the idea of minimizing the operations carried out on the qubits passing through each layer L _k of the quantum circuit, by simplifying as much as possible the calculations resulting from the application of the transfer function performed by the elementary logic gate G _k residing in this layer, starting from the following triple postulate:
For any vector ifj _k ) of state of the n qubits entering the gate, considered according to its possible values - that is to say that the vector ifj _k ) of state is presented in the form of a column matrix comprising 2 ⁿ -1 coefficients of amplitude coefficients of value 0 and a single amplitude coefficient of value 1 (see the examples provided below):
1) A diagonal type logic gate does not modify the value of the state vector (considered according to its possible values) - this is notably the case of the Pauli Z gate and the phase controlled gates 7 _φ , because a diagonal matrix does not affect the value of the amplitude coefficients of the state vector of the incoming qubits;
2) A logic gate of conventional type performs a single possible transformation of the state vector of the incoming qubits - this is notably the case of the X (NOT), Y, CNOT and SWAP gates - because a non-diagonal matrix comprising operators worth 0 or 1 at the rate of a single operator equal to 1 per line and per column performs a displacement of the coefficient a _c with an amplitude of value 1, from the rank i = c where this coefficient is found in the state vector ψι /} of incoming qubits), towards rank l in the state vector lV> fc + i) of outgoing qubits;
3) A dense type logic gate performs several possible transformations of the state vector ifj _k ) of incoming qubits - this is notably the case of the matrix H, since its matrix includes non-zero values on at least one line and / or a column.
This triple assumption makes it possible to considerably simplify the computations during the simulation of the passage of each door by the n qubits, because it makes it possible to eliminate - that is to say not to take into account - the improbable values of the vector d 'state | ip _{fc + 1} > at the door output, to retain (and memorize in a dedicated memory register) only the probable values.
To illustrate, apply this postulate for each type of logic gate, with reference respectively to FIG.1, FIG.2 and FIG.3 on which various elementary quantum gates have been represented using the known representation rules (described in particular in Nielsen & Chuang, op.cit.), According to which the path of each qubit is represented by a horizontal line, and each elementary quantum gate is superimposed on a line. A vertical line leading to a point on another line than that on which the door is located means that this is controlled by the qubit represented by this other line.
FIG. 1 shows a circuit comprising a single elementary quantum gate of diagonal type crossed by a single qubit: it is a controlled phase R ^, which applies to the qubit which crosses it a rotation of angle
The four possible states of the input qubits have been represented under the door, in superimposed boxes: | 00>, | 01>, | 10> and | 11>, and, at the same height, the four possible states of the qubits output: | 00>, | 01>, | 10> and | 11>.
If the input state is | 00>, then the only possible value of the output state is also | 00>, the other possible values, | 01>, | 10> and | 11>, being improbable and capable of be ignored: the corresponding boxes are grayed out to illustrate the abandonment of these calculation assumptions.
By way of illustration, the state transition | 0> -> | 0> is represented by a horizontal arrow, which means that the quantum gate considered does not modify the value of the qubits processed.
FIG. 2 shows a circuit comprising a single elementary quantum gate of the conventional type, crossed by a single qubit: this is a gate X.
The two possible states of the input qubit are represented under the door, in superimposed boxes: | 0> and | 1>, and, at the same height, the two possible values of the output qubit: | 0> and | 1>.
If the input qubit state is | 0>, then the only possible output qubit state is | 1>, the other possible value, | 0>, being improbable and able to be ignored: the corresponding box appears grayed out .
Conversely, if the state of the input qubit was | 1>, then the only possible state of the output qubit would be | 0>, the other possible state, | 1>, being improbable (and can be ignored).
By way of illustration, the state transition | 0> -> | 1) is represented by an oblique arrow, which means that the quantum gate considered modifies the state of the incoming qubit by assigning it the only other possible state.
FIG. 3 shows a circuit comprising a single elementary quantum gate of dense type, crossed by a single qubit: it is here a gate H (Hadamard).
The two possible states of the input qubit are represented under the door, in superimposed boxes: | 0> and | 1>, and, at the same height, the two possible values of the output qubit: | 0> and | 1).
Regardless of the state of the input qubit, | 0> or | 1>, it is equally likely that its exit state is | 0> (state unchanged) or | 1) (state changed).
Assuming the state of the input qubit at | 0>, the two possible state transitions are represented by illustration by two arrows starting from the box | 0>: one horizontal towards | 0>, signifying the possibility of maintaining the state of the qubit, the other oblique towards | 1>, signifying the possibility of changing the state of the qubit.
These illustration conventions make it possible to illustrate in the form of a graph the simulation method used, which is now described in detail with reference to an example shown in FIG. 4.
We assume that before starting the simulation, we have a library of predefined quantum gate models stored in a semiconductor integrated circuit memory, each quantum gate model being associated with a matrix U _k of transfer comprising operators ordered in rows and columns and defining all the possible state transitions of qubits passing through this gate.
The simulation includes a first configuration phase, which includes the operations of:
o define the number n of qubits to be processed at the input of the quantum circuit model - for example n = 3;
o select the d models of quantum gates, e.g. three Hadamard doors, two R * doors and one door;
4 o arrange the d quantum gate models thus selected to constitute the quantum circuit model - for example, as illustrated in FIG. 4, a circuit modeling a quantum fast Fourrier transform (QFFT: Quantum Fast Fourrier Transform).
Once the quantum circuit to be simulated is thus configured, the simulation includes a second phase of analysis of the quantum circuit model thus configured, which includes the operations consisting in:
o divide the quantum circuit into d adjacent layers L _k intended to be successively crossed by the n qubits taken together, each layer comprising a single elementary quantum gate G _k - thus, in the example of FIG. 4, where d = 6 :
L ₁ = G ₁ = H
L ₂ = G ₂ ⁼ Rtt ï
L ₃ a G ₃ = H
L ₄ AG ₄ = Rn 4
L ₅ AG ₅ = Rn 2
L ₆ = G ₆ = H o assign to each quantum gate of the circuit one type among three predefined types of quantum gates:
• Diagonal type door, whose matrix is diagonal - this is the case, in the example of FIG.4, of G ₂ , G ₄ and G ₅ ;
• Gate of conventional type, whose matrix is non-diagonal and includes operators worth 0 or 1 at the rate of a single operator per row and column (no gate concerned in the example of FIG.4);
• Dense type door, which is neither classic nor diagonal - this is the case, in the example in FIG. 4, of G ₄ , g ₃ and Gg.
Once this analysis is complete, the simulation includes a third phase of calculation, which includes repetition, for j = 1 to j = 2 ⁿ (j an integer; in the example in FIG. 4, n = 3 so that j varies from 1 to 2 ³ = 8) of the following operations:
a) define a vector | ip ₇ ) state of the n qubits at the input of the quantum circuit - in the example of FIG.4 the vector | ip ₇ ) can
... which, in bra-ket notation (used in FIG. 4) can be noted respectively:
| 000); | 001); | 010>; | 011>; | 100>; | 101>; | 110>; | 111>
(stacked in boxes superimposed on FIG. 4)
b) repeat, for k = 1 to k = d (here for k = 1 to k = 6), the following sequence:
b1) take into account a vector ifj ^] k) possible state of the n qubits at the input of the layer L _k , this vector ÿ ^] k) comprising a series of 2 ⁿ amplitude coefficients α / ^Λ thus , in the case of FIG. 4, for j = 1 and k = 1, the state of the n qubits at the input of the layer is | 000>, the other states appear in gray to signify that they are not not taken into account in this iteration on k;
b2) identify the gate G _k included in the layer L _k - in the example of FIG. 4, G ₁ = H; G ₂ = R ; g ₃ = H; G _A = Rn-, C ₅ = Ry
4 2 g ₆ = hb3) take into account the type of gate G _k (in the example
in FIG. 4, and for k = 1: dense gate ; for k = 2: door diagonal; for k = 3: dense gate; for k = 4: door diagonal; for / e = 5: diagonal gate; for k = 6: door
dense;
b4) if the gate G _k is of diagonal type (C ₂ , C ₄ , G ₅ in the example of FIG. 4), assign to the vector | ip / ₊₁ > the state of the n qubits leaving the layer L _k the value of the vector ifj ^] k) of the state of the n qubits entering it:
| ^ ₊ ι> = Ψύ
In the example of FIG. 4, the horizontal arrows joining the gray boxes on either side of the doors G ₂ , G ₄ , and G ₅ illustrate the identity of the entry and exit states;
b5) if the gate G _k is of conventional type:
o detect in its transfer matrix each operator worth 1 and determine its row number l and column number c (Z and c integers such as 0 <l <2 ⁿ , 0 <c <2 ⁿ and l ψ c) ;
o assign to the amplitude coefficients a / ' ^{fe + 1} of the vector | ip ^ ₊₁ > of the state of the n qubits leaving the layer L _k the following values:
a {' ^{k + 1} = ai' ^k for all i Ψ 1 o memorize the vector in a dedicated register of an integrated circuit memory on semiconductor, which allows each calculation step to be carried out in parallel;
b6) if the gate G _k is of dense type:
o determine the set of possible values of the vector | ^ ₊₁ > state of the n qubits leaving the layer L _k such that:
W ₊ 1> = <4 · Φί>
Thus, in the example of FIG. 4, we see that, for the gates G ₁ , G ₃ and G ₆ , the qubit entering the Hadamart gate can take any value at output, while the other two bits are unchanged: this explains why a double arrow leaves the box containing the possible state of the qubits at the entrance of the door and ends at the only two possible states at the exit of the door, according to the value of the qubit affected by the transfer function of the door: in the case, e.g. from gate G ₃ , which affects only the second qubit, and starting from the input state of | 000>, the only two possible states at output are | 000> and | 010>; the other states are improbable and ignored in the following stages of the simulation;
o memorize each possible value of the vector in a dedicated register of a memory with an integrated circuit on a semiconductor, which allows, at this stage, to continue in parallel the sub-calculations resulting from the previous calculations;
c) when the preceding iterations are completed, aggregate, in a single register of an integrated circuit memory on a semiconductor, the set of possible states of the vector | V> d + i) (stored in separate registers, such as we just saw it).
The fact of not taking into account the improbable states of the qubits at each passage of the door makes it possible to considerably reduce the number of iterations (and therefore the power the calculation time), as well as the memory space (of conventional type) required.
To illustrate these advantages, the simulation which has just been described could be carried out on a circuit of the type of FIG. 4 (Quantum transform of fast Fourrier), pourn = 18àn = 24.
In comparison with known algorithms, we were able to speed up the simulation by a factor of between 20 and 40.
More precisely, by noting N the available memory capacity of the computer on which the simulation is carried out, the method makes it possible to process a maximum number n _m of qubits greater than:
logQV) log (2)
This number is a factor of 2 higher than the known numbers, with equivalent memory capacity.

权利要求:
Claims (2)
[1" id="c-fr-0001]
CLAIM
1. Method for simulating, on a computer processing unit with an integrated circuit on a semiconductor, the operation of a quantum circuit model configured to process a predefined number n (n an integer such as n> 2) of input qubits and comprising a series of d (of an integer such that d> 2) quantum gates G _k [k an integer, 1 <k <d) elementary selected from a library of predefined models of quantum gates stored in an integrated circuit memory on semiconductor, each quantum gate model being associated with a transfer matrix U _k comprising operators ordered in rows and columns and defining all the possible state transitions of qubits passing through this gate, this method comprising:
a configuration phase of the quantum circuit, which includes the operations consisting of;
o define the number n of qubits to be processed at the input of the quantum circuit model;
o select the d models of quantum gates; o arrange the d models of quantum gates thus selected to constitute the model of quantum circuit; an analysis phase of the quantum circuit model thus configured, which includes the operations consisting of:
o divide the quantum circuit into d adjacent layers L _k intended to be crossed successively by the n qubits taken together, each layer comprising a single quantum gate;
o assign to each quantum gate of the circuit one type among three predefined types of quantum gates:
• Diagonal type door, whose transfer matrix is diagonal;
• Classic type door, whose transfer matrix is non-diagonal and includes operators worth 0 or 1 at the rate of a single operator per row and per column;
• Dense type door, which is neither classic nor diagonal;
A calculation phase, which includes the repetition, for j = 1 to j = 2 ⁿ (j an integer) of the following operations:
a) define a vector | ip ₇ ) state of the n qubits at the input of the quantum circuit, which includes a series of 2 ⁿ amplitude coefficients a [(j an integer, 0 <i <2 ⁿ -1) worth 0 or 1, and such that:
[2" id="c-fr-0002]
2 ⁿ -lt = 0
b) repeat, for k = 1 to k = d, the following sequence:
b1) take into account a vector ifj ^] k) state of the n qubits at the input of the layer L _k , this vector ifj ^] k) comprising a series of 2 ⁿ amplitude coefficients a [ ^{, k} ;
b2) identifying the gate G _k included in the layer L _k ;
b3) take into account the type of gate G _k ;
b4) if the gate G _k is of diagonal type, assign to the vector | ip / ₊₁ ) state of the n qubits leaving the layer L _k the value of the vector ifj ^] k) state of the n qubits entering this one:
IV'fc + i) = b5) if the gate G _k is of classical type:
o detect in its transfer matrix each operator worth 1 and determine its row number l and column number c (Z and c integers such as 0 <l <2 ⁿ , 0 <c <2 ⁿ and l ψ c) ;
o assign to the amplitude coefficients a / ' ^{fe + 1} of the vector (ip / ₊₁ ) of state of the n qubits leaving the layer L _k the following values:
a {' ^{k + 1} = a {' ^k for all i Ψ 1 o memorize the vector | V> / + i) in a dedicated register of an integrated circuit memory on semiconductor;
b6) if the gate G _k is of dense type:
26 o determine the set of possible values of the 5 o vector | ip ^ ₊₁ > state of the n qubits leaving the layer L _k such that: IC) = WJ memorize each possible value of the vector | ^ _{+ i} > in a dedicated register of an integrated circuit memory on semi -conductor;
c) aggregate, in a single register of a semiconductor integrated circuit memory, all of the possible states of the
10 vector | i / ^ ₊₁ >.
1/1

类似技术:

---

公开号 | 公开日 | 专利标题

---

FR3064380A1|2018-09-28|METHOD FOR SIMULATING A QUANTUM CIRCUIT ON A CLASSIC COMPUTER

---

Tao et al.2015|Local universality of zeroes of random polynomials

---

Harrow et al.2002|Efficient discrete approximations of quantum gates

---

Stanev et al.2018|Unsupervised phase mapping of X-ray diffraction data by nonnegative matrix factorization integrated with custom clustering

---

Li et al.2018|The multi-level and multi-dimensional quantum wavelet packet transforms

---

Araujo et al.2021|A divide-and-conquer algorithm for quantum state preparation

---

Mahmud et al.2019|Scaling reconfigurable emulation of quantum algorithms at high precision and high throughput

---

Penkovsky et al.2018|Efficient design of hardware-enabled reservoir computing in FPGAs

---

Longo et al.2021|Von Neumann entropy in QFT

---

Chen et al.2019|Hybrid classical-quantum linear solver using Noisy Intermediate-Scale Quantum machines

---

Li et al.2019|Quantum circuit design for several morphological image processing methods

---

Longo2019|Entropy of coherent excitations

---

Ahmad et al.2018|Periodic p-adic gibbs measures of q-state potts model on cayley trees i: The chaos implies the vastness of the set of p-adic gibbs measures

---

US10977737B2|2021-04-13|Training gradient boosted decision trees with progressive maximum depth for parsimony and interpretability

---

Wang2022|When quantum computation meets data science: Making data science quantum

---

Molina1930|The theory of probability: Some comments on Laplace's Théorie analytique

---

Aharonov et al.2014|On superoscillations longevity: a windowed Fourier transform approach

---

Gulbahar2020|Theory of quantum path computing with Fourier optics and future applications for quantum supremacy, neural networks and nonlinear Schrödinger equations

---

Navaneeth et al.2021|A study and analysis of applications of classical computing and quantum computing: A survey

---

EP3425497A1|2019-01-09|Classical-quantum hybrid computer architecture

---

Du et al.2020|Arbitrary-Centered Discrete Gaussian Sampling over the Integers

---

EP3622445B1|2021-06-09|Method, implemented by computer, for searching for rules of association in a database

---

Trivedi et al.2022|Three-Qubit Implementation of Quantum Fourier Transform for Shor’s Algorithm

---

Bröker et al.2016|Fourier coefficients of sextic theta series

---

EP0337544B1|1995-07-05|Method and memory management unit for address words

同族专利:

---

公开号 | 公开日

---

JP2020515999A|2020-05-28|

---

EP3602354A1|2020-02-05|

---

CA3057734A1|2018-09-27|

---

FR3064380B1|2019-04-19|

---

CN110709851A|2020-01-17|

---

US20210103692A1|2021-04-08|

---

WO2018172629A1|2018-09-27|

引用文献:

---

公开号 | 申请日 | 公开日 | 申请人 | 专利标题

---

---

FR3090983B1|2018-12-20|2021-09-24|Bull Sas|Analysis method of a simulation of the execution of a quantum circuit|

---

FR3090984B1|2018-12-20|2021-04-30|Bull Sas|Analysis method of a simulation of the execution of a quantum circuit|

---

US11205030B2|2019-01-03|2021-12-21|International Business Machines Corporation|Avoiding data exchange in gate operation for quantum computing gates on a chip|

---

WO2022004274A1|2020-06-30|2022-01-06|国立研究開発法人産業技術総合研究所|Computer system and control device|

法律状态:
2018-02-19| PLFP| Fee payment|Year of fee payment: 2 |

---

2018-09-28| PLSC| Search report ready|Effective date: 20180928 |

---

2019-04-01| PLFP| Fee payment|Year of fee payment: 3 |

---

2020-03-26| PLFP| Fee payment|Year of fee payment: 4 |

---

2021-03-26| PLFP| Fee payment|Year of fee payment: 5 |

优先权:

---

申请号 | 申请日 | 专利标题

---

FR1770299A|FR3064380B1|2017-03-24|2017-03-24|METHOD FOR SIMULATING A QUANTUM CIRCUIT ON A CLASSIC COMPUTER|

---

FR1770299|2017-03-24|FR1770299A| FR3064380B1|2017-03-24|2017-03-24|METHOD FOR SIMULATING A QUANTUM CIRCUIT ON A CLASSIC COMPUTER|

---

CN201880033603.8A| CN110709851A|2017-03-24|2018-03-19|Method for simulating quantum circuit on traditional computer|

---

JP2020501846A| JP2020515999A|2017-03-24|2018-03-19|How to simulate a quantum circuit on a classical computer|

---

PCT/FR2018/000057| WO2018172629A1|2017-03-24|2018-03-19|Method for simulating, on a conventional computer, a quantum circuit|

---

US16/497,004| US20210103692A1|2017-03-24|2018-03-19|Method for simulating a quantum circuit, on a classical computer|

---

CA3057734A| CA3057734A1|2017-03-24|2018-03-19|Method for simulating, on a conventional computer, a quantum circuit|

---

EP18714301.1A| EP3602354A1|2017-03-24|2018-03-19|Method for simulating, on a conventional computer, a quantum circuit|