Method for compressing a quantum state vector and process for storing a quantum state vector

Abstract

A method for compressing a quantum state vector includes: aggregating a group of several neighboring states of the vector into a cluster of states of the vector, a parameter representative of the probability of this cluster being associated with it and corresponding to the sum of the probabilities of the aggregated neighboring states in this cluster, the probability of each aggregated neighboring state being below a given aggregation threshold, and/or the sum of the probabilities of the aggregated neighboring states in a cluster being below another given aggregation threshold; and preserving a state of the vector not aggregated in a cluster, the parameter representative of its probability remaining unchanged. The method includes several steps of aggregating several distinct groups of several neighboring states of the vector, respectively into several clusters of states of the vector, and/or an aggregation step and a preservation step.

Claims

1. A method for compressing a quantum state vector during a simulation of a quantum circuit on a quantum computer, the method comprising: at least one step of aggregating a group of several neighboring states of the vector into a cluster of states of the vector, a parameter representative of the probability of this cluster being associated with it and corresponding to the sum of the probabilities of the aggregated neighboring states in this cluster, the probability of each aggregated neighboring state being below a given aggregation threshold, and/or the sum of the probabilities of the aggregated neighboring states in a cluster being below another given aggregation threshold, at least one preservation step, a state of the vector not aggregated in a cluster being preserved, the parameter representative of its probability remaining unchanged, the compression method comprising: at least several steps of aggregating several distinct groups of several neighboring states of the vector, respectively into several clusters of states of the vector, and/or at least one aggregation step and at least one preservation step.

2. The method for compressing a quantum state vector according to claim 1, comprising: several steps of aggregating several distinct groups of several neighboring states of the vector, respectively into several clusters of states of the vector, several preservation steps.

3. The method for compressing a quantum state vector according to claim 1, wherein: the probability of each aggregated neighboring state is below a given threshold, and the sum of the probabilities of the aggregated neighboring states in a cluster is below another given threshold.

4. The method for compressing a quantum state vector according to claim 1, wherein: the probability of each preserved state is above a given preservation threshold, and/or the sum of the probabilities of the preserved states is above another given preservation threshold.

5. The method for compressing a quantum state vector according to claim 1, further comprising: the grouping of several neighboring quantum states for which the probabilities are all identical.

6. The method for compressing a quantum state vector according to claim 1, wherein: said given aggregation threshold and/or said other given aggregation threshold are proportional to the inverse of the logarithm of the number of quantum states.

7. The method for compressing a quantum state vector according to claim 1, wherein: said given preservation threshold and/or said other given preservation threshold is or are chosen so that the number of clusters is proportional to the logarithm of the number of quantum states, and/or said given preservation threshold and/or said other given preservation threshold is or are chosen so that the number of clusters remains less than 1000.

8. The method for compressing a quantum state vector according to claim 7, wherein: said given preservation threshold and/or said other given preservation threshold is or are chosen so that the number of clusters remains greater than 10.

9. The method for compressing a quantum state vector according to claim 1, wherein: the vector comprises at least 2.sup.20 quantum states.

10. The method for compressing a quantum state vector according to claim 1, wherein: at least 90% of the quantum states of the vector are aggregated.

11. The method for compressing a quantum state vector according to claim 1, wherein: the ratio of the number of aggregated states to the number of non-aggregated states is greater than 2.sup.20.

12. The method for compressing a quantum state vector according to claim 1, wherein: one or more steps of aggregating one or more groups of several neighboring states of the vector into one or more clusters of states of the vector, is or are performed by assigning, to said cluster, a parameter representative of the probability of this cluster corresponding to the complement of the sum of the probabilities of the states previously determined, meaning both the aggregated continuous states and the preserved states.

13. The method for compressing a quantum state vector according to claim 1, wherein: the number of states of the quantum state vector is greater than 2.sup.20, the number of quantum state vectors to which the compression method is applied, is greater than 2.sup.20.

14. A process for storing a quantum state vector, comprising: a step of identifying the different states of the vector and the parameters representative of the probabilities respectively associated with them, a step of compressing the vector, using the method for compressing a quantum state vector according to claim 1, a step of determining the probability of the desired quantum state, a step of associating the desired quantum state with the determined probability, either simply by extracting the desired quantum state corresponding to the determined probability, when the desired quantum state is preserved, or by recovering the desired quantum state corresponding to the determined probability, when the desired quantum state is aggregated in a cluster, by recalculating this desired quantum state aggregated in this cluster.

15. The process for storing a quantum state vector according to claim 14, wherein: the desired quantum state vector is returned as output from a quantum computer.

16. The process for storing a quantum state vector according to claim 14, wherein: all or part of the quantum states of the cluster containing said desired quantum state is or are recalculated, no quantum state of the other clusters which do not contain said desired quantum state is recalculated.

17. The process for storing a quantum state vector according to claim 14, wherein: the quantum states of the cluster containing said desired quantum state are successively recalculated until said desired quantum state is obtained, or the quantum states of the cluster containing said desired quantum state are all recalculated in parallel in order to obtain said desired quantum state.

18. The process for storing a quantum state vector according to claim 14, wherein: the recovery recalculates this desired quantum state aggregated in this cluster by applying a partial simulation method to all or part of the quantum states aggregated in this cluster.

19. The process for storing a quantum state vector according to claim 18, wherein the partial simulation method is a Feynman method, in other words via a path integral.

20. A process for storing a quantum state vector, comprising: a step of identifying the different states of the vector and the parameters representative of the probabilities respectively associated with them, a step of compressing the vector using the method for compressing a quantum state vector according to claim 1, a step of determining the probability of the desired quantum state, and one of the following two steps: either a step of associating the desired quantum state with the determined probability, simply by extracting the desired quantum state corresponding to the determined probability, when the desired quantum state is preserved, or a step of recalculating all the quantum states of said stored quantum state vector.

Description

BRIEF DESCRIPTION OF DRAWINGS

(1) FIG. 1 is a flowchart representing the main steps of the method for compressing a quantum state vector according to one exemplary embodiment of the invention.

(2) FIG. 2 is a flowchart representing the main steps of a process for storing a quantum state vector according to the invention.

(3) FIG. 3 is a diagram illustrating a use of the method for the storage and compression of a quantum state vector according to an exemplary embodiment of the invention.

DETAILED DESCRIPTION OF THE INVENTION

(4) FIG. 1 illustrates an example of the compression of a vector V of quantum states, according to an exemplary embodiment of the invention. A quantum state vector is composed of a plurality of qbits, having 0 and 1 as the quantum state.

(5) In step S1, such a quantum state vector V is provided. In one embodiment, this quantum state vector V may comprise 20 qbits, preferably 30 qbits, and even more preferably 36 qbits. The quantum state vector V thus comprises at least 2.sup.20 quantum states, preferably more than 2.sup.25, still more preferably more than 2.sup.30, and advantageously more than 2.sup.35.

(6) A probability is associated with each quantum state of the vector, the sum of all the probabilities being equal to 1. More precisely, the quantum state vector comprises an amplitude for each possible quantum state, the square of the amplitude being the probability associated with this quantum state.

(7) This represents a very large amount of data, in particular about 16 GB of data, up to several TB of data.

(8) The quantum state of each qbit is not known. A parameter representative of its probability of appearance is associated with each quantum state of the vector.

(9) The compression method comprises aggregating several neighboring quantum states (at least two) into a cluster of states, on the basis of a chosen criterion.

(10) The compression method may further comprise the preservation of at least one quantum state, according to a chosen criterion.

(11) In particular, as illustrated in step S2, a first criterion comprises the determination that at least two neighboring quantum states respectively have a probability below a first threshold.

(12) Thus, if the quantum state vector V comprises n quantum states, E, it is verified that a quantum state Ei comprises a probability Pi below the first threshold. If a neighboring quantum state, for example the quantum state Ei−1, also comprises a probability Pi−1 less than the first threshold, the two neighboring quantum states Ei−1 and Ei are aggregated into a cluster of two quantum states. A parameter representative of the probability of this cluster Pr is assigned to them. This parameter, the probability of the cluster Pr, can be the sum of the probabilities Pi, Pi−1 of the two aggregated quantum states Ei, Ei−1.

(13) In the same manner, if the quantum state Ei+1 comprises a probability Pi+1 below the first threshold, Ei+1 is aggregated with the two quantum states Ei−1, Ei to form a cluster of three quantum states, for which the probability Pr is equal to the sum of the probabilities Pi−1, Pi, Pi+1.

(14) The aggregation of several neighboring quantum states E into a cluster of quantum states is illustrated in step S6.

(15) When a quantum state Ej comprises a probability Pj above the first threshold, the aggregation of several neighboring quantum states into a cluster is stopped.

(16) However, even when a quantum state comprises a probability above the first threshold, other neighboring quantum states can be aggregated into a cluster of quantum states according to step S2. Thus, if the quantum states Ej+1 and Ej+2 respectively have a probability below the first threshold, they are aggregated into a cluster of quantum states.

(17) A second aggregation criterion, illustrated in step S3, can also be applied. For example, this second criterion can be applied to quantum states that were not aggregated in step S2.

(18) The second criterion comprises, for example, determining that the sum of the probabilities of at least two neighboring quantum states is less than a second threshold. When the sum of the probabilities of the two neighboring states is less than the second threshold, these two neighboring quantum states are aggregated into a cluster of quantum states. A parameter representative of the cluster probability is associated with it. This parameter is for example the sum of the probabilities of each quantum state of the cluster.

(19) In other words, if the sum of the probabilities Ps of two neighboring quantum states, Ej−1 of probability Pj−1 and Ej of probability Pj, is lower than a second threshold, meaning Pj−1+Pj is lower than the second threshold, the two neighboring states Ej−1, Ej are aggregated into a cluster of quantum states in step S6. The probability of this cluster Ps is equal to Pj−1+Pj.

(20) When neither the first nor the second criterion is met, a third criterion can be applied in step S5.

(21) The third criterion comprises determining that at least two neighboring quantum states comprise the same probability.

(22) In other words, if at least two neighboring quantum states Ek, Ek+1, of respective probability Pk, Pk+1, have equal probability, the two neighboring quantum states Ek, Ek+1 are aggregated into a cluster of quantum states in step S6. The probability of this cluster is the sum of probabilities Pk, Pk+1.

(23) When a quantum state E does not meet one of these three criteria, this state is preserved in step S5. The probability of the preserved quantum state does not change.

(24) In step S7, the compressed quantum state vector V is obtained.

(25) Advantageously, the compression method comprises several steps of aggregating several distinct groups of quantum states into several clusters of quantum states.

(26) Advantageously, the compression method also comprises at least one step of preserving a quantum state.

(27) Preferably, the compression method comprises several aggregation steps and several preservation steps.

(28) The compression method illustrated in FIG. 1 is one exemplary embodiment.

(29) In another example, only the first criterion (step S2) is applied.

(30) In another example, only the second criterion (step S3) is applied.

(31) In another example, only the third criterion (step S4) is applied.

(32) In another example, only the first and second criteria (steps S2 and S3) are applied.

(33) In another example, the first and second criteria are cumulative. In other words, for at least two neighboring quantum states to be aggregated into a cluster of quantum states, their respective probability must be below the first threshold and the sum of their probabilities must be below the second threshold.

(34) In another example, only the first and third criteria (steps S2 and S4) are applied.

(35) In another example, only the second and third criteria (steps S3 and S4) are applied.

(36) It is also understood that the compression method can also be applied using other criteria. For example, a first preservation threshold may be defined. In this variant embodiment, it is possible not to implement steps S1 to S3. In this variant, it is determined whether a quantum state comprises a probability greater than the first preservation threshold. If so, this quantum state is preserved. The neighboring quantum states comprising a probability lower than the preservation threshold are aggregated.

(37) According to another variant, all the quantum states, whether neighboring or not, comprising a probability below the first preservation threshold are aggregated.

(38) According to another variant embodiment, a second preservation threshold may be defined. According to this variant, it is determined whether the sum of the quantum state probabilities is above the second preservation threshold. If such is the case, these quantum states are preserved. The neighboring quantum states comprising a probability below the preservation threshold are aggregated.

(39) According to another variant, all the quantum states, whether neighboring or not, comprising a probability below the second preservation threshold are aggregated.

(40) Another criterion may be defined, according to which the applications of the first and second preservation thresholds are cumulative in order for a quantum state to be preserved. Thus, only the quantum states comprising a probability above the first preservation threshold are preserved. Once the sum of their probability is greater than the second preservation threshold, all remaining quantum states are aggregated.

(41) According to another embodiment, when one or more quantum states are missing, the probability associated with them is deduced from the probabilities associated with the aggregated or preserved quantum states. In fact, the sum of the probabilities associated with a quantum state or a cluster of quantum states is equal to 1. The probability of the missing quantum states is thus equal to the complement of the sum of the known probabilities. In other words, the missing probability is found by the operation: 1−(sum of known probabilities).

(42) Since the number of quantum states of the quantum state vector is very large, the first and second thresholds are chosen to considerably reduce the size of the quantum state vector. However, in applications of the quantum state vector, it may be useful to preserve the quantum states associated with a high probability: it is these quantum states that are most likely to need to be recovered after compression of the quantum state vector. The first threshold and second threshold therefore must not be too low.

(43) For example, the first threshold and the second threshold are proportional to the inverse of the logarithm of the number of quantum states. In other words, if the quantum state vector comprises n quantum states, the first and second threshold will be equal to c/log(n), where c is a real number which may have a different value for the first threshold and for the second threshold.

(44) In particular, c may be chosen such that the number of distinct clusters of quantum states is proportional to the logarithm of the number of quantum states of the quantum state vector. In other words, the number of distinct clusters can be equal to d.Math.log(n), where d is a real number preferably comprised between 0.1 and 10.

(45) Alternatively, c may be chosen so that the number of clusters remains below 10,000, preferably below 1,000, and preferably below 100. These orders of magnitude also depend on the size of the quantum state vector, and therefore on the number of quantum states. The real number c may also be chosen so that the number of clusters is always greater than 10.

(46) Thus, according to these embodiments, between 90% and 99.9% of the quantum states of the quantum state vector are aggregated.

(47) In other words, and in view of the very large number of quantum states of the quantum vector, the compression method according to this exemplary embodiment makes it possible to obtain a ratio of the number of aggregated states to the number of preserved states that is between 2.sup.20 and 2.sup.35.

(48) The compression method is particularly advantageous because it can be applied simultaneously to a number comprised between 2.sup.20 and 2.sup.35 of quantum state vectors, each comprising at least 2.sup.20 quantum states.

(49) FIG. 2 illustrates the main steps of a process for the storage of a quantum state vector. The storage process has applications for example in an execution in a quantum circuit. During such execution, the quantum simulator returns a value of the quantum state vector. For this, the quantum simulator can make a random selection that is dependent upon the probability of each quantum state. To reproduce the execution of the simulation, the random selection can be made from the set of quantum states. This then involves determining which quantum state is associated with the randomly selected probability, as described below with reference to FIG. 2.

(50) In step S10, a quantum state vector V is provided. The quantum state vector is as described with reference to FIG. 1.

(51) In step S11, an identification of the probabilities associated with each quantum state of the quantum state vector is performed. More precisely, the probability of each quantum state is calculated from the amplitude of each quantum state.

(52) The table below illustrates all the quantum states of a quantum state vector of 3 qbits.

(53) TABLE-US-00001 State Value of qbits Amplitude Probability 0 000 0 0 1 001 0.25 + 0 i 0.0625 2 010 0 0 3 011 0.75 + 0 i 0.5625 4 100  0.5 + 0 i 0.25 5 101 0.25 + 0 i 0.0625 6 110 0 0 7 111 0.25 + 0 i 0.0625

(54) Thus, for a quantum state vector comprising 3 qbits, there are 8 quantum states. The sum of the probabilities of each quantum state is indeed equal to 1.

(55) The quantum state vector is compressed in step S12. The compression of the quantum state vector is performed according to the compression method described with reference to FIG. 1.

(56) By following this method, the first threshold and/or the second threshold are defined as being proportional to the logarithm of the number of quantum states, in other words equal to d.Math.log(8). where d is comprised between 0.1 and 10. We thus have a first threshold and/or a second threshold comprised between 0.09 and 1. Indeed, the first threshold and/or the second threshold cannot be greater than 1, as the sum of the probabilities is equal to 1.

(57) In the illustrated numerical example, the first threshold and/or the second threshold are defined as being comprised between 0.25 and 0.35.

(58) Thus, quantum states 0 to 2 can be aggregated into a first group of quantum states. Their respective probabilities are below the first threshold. Moreover, the sum of their probabilities is below the second threshold. The parameter representative of the probability of this cluster is equal to the sum of the probabilities of quantum states 0 to 2.

(59) Quantum state 3 is preserved because its probability is greater than the first threshold and second threshold, and no neighboring quantum state is associated with the same probability.

(60) In the same manner, quantum state 4 is preserved.

(61) Quantum states 5 to 7 are aggregated into a cluster of quantum states in the same manner as described with reference to the cluster of quantum states 0 to 2. The probability associated with this cluster is equal to the sum of the probabilities of quantum states 5 to 7.

(62) The table below illustrates the quantum states of the compressed quantum state vector.

(63) TABLE-US-00002 Quantum states Probability 0-2 0.0625 3 0.5625 4 0.25 5-7 0.125

(64) In step S13, the desired probability is determined. For this, a probability can be randomly selected. Then, the quantum state vector is scanned linearly for example in order to determine the quantum state associated with the desired probability.

(65) More precisely, let x be the randomly selected probability. Probability x is the desired probability. If x is less than 0.0625, the quantum state associated with the desired probability is found in the cluster of quantum states 0 to 2.

(66) If x is between 0.0625 and 0.625, the desired quantum state is quantum state 3. Indeed, 0.0625 is the low range since the probability of the first cluster is 0.025. On the other hand, 0.625 is the high range because the probability of the first cluster added to the probability of state 3 is 0.625.

(67) If x is between 0.625 and 0.875, the desired quantum state is quantum state 4. In fact, 0.625 added to the probability of quantum state 4 gives 0.875.

(68) Finally, if x is between 0.875 and 1, the desired quantum state lies in the cluster of quantum states 5 to 7.

(69) This determination is made in step S14.

(70) If it is determined that the desired probability is associated with a quantum state of a quantum state cluster, the corresponding quantum state is recovered from the cluster. More precisely, the quantum state is recalculated. This can be done using a Feynman or path-integral type of partial simulation method. “Partial simulation” is understood to mean a method that allows calculating at least a portion of the final state vector.

(71) Recovery of the quantum state from a cluster may be done in different ways in step S16.

(72) For example, all quantum states of the cluster may be recalculated, in order to know their probability and to determine which quantum state corresponds to the desired probability. Other quantum states of other clusters may not be recalculated.

(73) The quantum states of the cluster in which the quantum state associated with the desired probability is located may be successively recalculated until the corresponding quantum state is determined. The rest of the quantum states of the cluster are not recalculated for example.

(74) In another variant, the quantum states of the cluster are all recalculated in parallel, and then the quantum state associated with the desired probability is determined.

(75) When the desired probability corresponds to a preserved quantum state, meaning a quantum state not in a cluster, the quantum state is extracted without requiring further calculations, as illustrated in step S15.

(76) The desired quantum state is thus obtained in step S17.

(77) The quantum state vector, which usually comprises a very large number of qbits and therefore an exponentially large number of quantum states, can thus be compressed at a very high ratio. The compressed information, meaning the grouped quantum states, are lost for awhile but can be retrieved if necessary on the basis of their probability. The lost information is recalculated by means of a partial simulation method that is inexpensive in terms of run time.

(78) The desired quantum state may be returned as output from a quantum computer.

(79) FIG. 3 illustrates a use of the method for the storage and compression of a quantum state vector according to one exemplary embodiment of the invention. More precisely, FIG. 3 illustrates the storage of a compressed quantum state vector, in a cache in memory.

(80) The user launches a first execution of the quantum circuit, corresponding to obtaining the quantum state vector in steps S1 and S10 of FIGS. 1 and 2. The execution command is sent to the quantum simulator, which queries the cache or the storage space. The query does not give any result since it is the first execution. The quantum simulator then performs the simulation, corresponding for example to the compression of the quantum state vector described in FIG. 1. The result of this simulation is sent to the user, for example as output from the quantum circuit. At the same time, the result of the simulation, meaning the compressed quantum state vector, is stored in the cache or any other storage space.

(81) The user then launches a second execution of the quantum circuit. The execution command is sent to the quantum simulator, which queries the cache. The execution command is, for example, the search for a quantum state using a randomly selected probability. The quantum simulator queries the cache that comprises the compressed quantum state vector. When the desired quantum state is a preserved quantum state, the quantum simulator simply extracts the quantum state which is then obtained by the user as output from the simulator. When the desired quantum state is located in a cluster, a second simulation is performed, corresponding to a Feynman type partial simulation method or a stabilizer method. The desired quantum state is returned to the user.

(82) Storing the simulation results in a cache makes it possible to reduce the computational resources required, since the compression of the quantum state vector can be carried out only once, the quantum state vector then being stored in the cache.

(83) The methods for storing a quantum state vector and/or compressing a quantum state vector have other applications.

(84) For example, the methods can be used in decoding processes for cryptographic keys, the desired quantum state corresponding to the cryptographic key to be decoded.

(85) The methods can also be used to search for an item stored in a database, on the basis of one or more search criteria.