CN116739101B - A quantum optimization method and device - Google Patents

Abstract

The present application discloses a quantum optimization method and device, which includes: converting the problem to be optimized into a QUBO problem, and converting the initial objective function corresponding to the QUBO problem into an energy function in the Ising form; introducing physical bits for the Ising form energy function to convert the two-body interaction term into a monomer local action term, and obtaining the introduced restriction term for ensuring the correctness of the logical bit; constructing an equivalent digital grouping problem for the restriction term, and obtaining the sub-objective function corresponding to the restriction term based on the digital grouping problem; combining the sub-objective function corresponding to the restriction term with the monomer function corresponding to the monomer local action term to obtain the final objective function corresponding to the QUBO problem. This method can realize encoding in a one-dimensional cold atom chain, without the need to use the geometric arrangement of quantum bits to realize the restriction conditions introduced in the encoding process, that is, without the need to arrange atoms in two-dimensional space in the physical system, effectively reducing the complexity of the parity encoding process.

Description

A quantum optimization method and device

Technical Field

The present invention relates to the field of quantum optimization technology, and more particularly to a quantum optimization method. The present invention also relates to a quantum optimization device, an electronic device, and a computer-readable storage medium.

Background technique

Quantum optimization problems are dedicated to solving difficult classical binary optimization problems using the fluctuations of quantum systems. The core is to appropriately encode the solution of the computational problem into the ground state of a programmable quantum many-body system. After the encoding problem is realized, the mature adiabatic algorithm can be used to solve the optimization problem. In the current field of quantum optimization, since most problems can be described in the form of QUBO problems, the important task in the field of quantum optimization research is to encode the objective function of the optimization problem in the Hamiltonian of the physical experimental system, and then use the quantum adiabatic algorithm to solve the optimization problem that is originally NP-complete for classical computers. Since the physical system can only realize local interactions, it is impossible to directly encode binary problems with global connectivity. Therefore, there are currently many encoding schemes dedicated to solving the defect that the physical system only has local interactions. Among them, parity coding is widely used, that is, using a single actual physical quantum bit to encode the multi-qubit interaction term in the original Hamiltonian, and introducing some restrictions on this basis to ensure the correctness of the logical bits.

However, in the process of using existing parity coding to encode the objective function of the optimization problem, there are the following problems: based on parity coding, the existing technology uses the geometric arrangement of quantum bits to implement the restrictions introduced in the encoding process. However, this method requires the arrangement of atoms in two-dimensional space, making the encoding process too complicated.

Summary of the invention

The present invention provides a quantum optimization method, device, electronic device and computer-readable storage medium to solve the problem that when odd-even coding is used to encode the objective function of the optimization problem in the prior art, the encoding process is too complicated.

In order to solve or improve the above technical problems to a certain extent, according to one aspect of the present invention, a quantum optimization method is provided, the method comprising:

Converting the problem to be optimized into a QUBO problem, and converting the initial objective function corresponding to the QUBO problem into an energy function in Ising form;

Introducing physical bits into the Ising form energy function to convert the two-body interaction term into a single-body local interaction term, and obtaining the introduced restriction term for ensuring the correctness of the logical bit;

Constructing an equivalent digital grouping problem for the restriction item, and obtaining a sub-objective function corresponding to the restriction item based on the digital grouping problem;

The sub-objective function corresponding to the restriction term is combined with the monomer function corresponding to the monomer local action term to obtain the final objective function corresponding to the QUBO problem.

In some implementations, constructing an equivalent digital grouping problem for the restriction item includes:

The constraints are converted into SAT statements, and the SAT statements are reduced to a digital grouping problem that can be encoded in a cold atomic system of an optical cavity.

In some embodiments, reducing the SAT statement to a digital grouping problem that can be encoded in a cold atom system of an optical cavity includes:

A number group is defined based on the SAT statement, so that when the SAT statement is evaluated by a satisfiable variable, a subset can be obtained in the number group, and the sum of the numbers included in the subset is equal to a certain target value, wherein the integer power series in the numbers and the target value are replaced by integer square roots without square factors;

Based on the number groups, an objective function of the number grouping problem is constructed.

In some implementations, the SAT statement is composed of M clauses c ₁ , c ₂ , ..., c _M , and the SAT statement contains N variables x ₁ , x ₂ , ... x _N . Defining a number group based on the SAT statement includes:

The numbers defined based on the SAT statement are:

The target value defined based on the SAT statement is:

Where i ranges from 1 to N, j ranges from 1 to M, and α _p represents the pth integer without square factors;

{a _i , b _i , c _j , d _j } constitutes a digital set for a new digital grouping problem, and the digital set is recorded as a sequence {r ₁ , ..., r _k , ...r _2M+2N };

Based on the sequence, we construct an equivalent objective function for the digital grouping problem:

Here, y _k =1 or -1.

In some implementations, obtaining the sub-objective function corresponding to the restriction item based on the digital grouping problem includes:

Substitute the number of variables and the number of sentences of the SAT statement into the objective function of the digital grouping problem to obtain the sub-objective function corresponding to the restriction item.

In some embodiments, the Ising form energy function is expressed as:

The energy function of the Ising form is introduced with a physical bit so as to convert the two-body interaction term into a monomer local action term, and obtain the introduced restriction term for ensuring the correctness of the logical bit, including: introducing a physical bit b _ii′ = s _i s _i′ for the energy function of the Ising form so as to convert the two-body interaction term J _ii′ into a monomer local action term J, converting the energy function into a form of monomer local field action And obtain the (n-1)(n-2)/2 restriction conditions introduced to ensure the correctness of the logic bit, where n is the number of variables of the Ising form energy function, and the restriction terms are introduced to satisfy the following equation:

b _ii′ b _ii′+1 b _i+1i′+1 b _i+1i′ =1.

In some implementations, converting the restriction item into a SAT statement includes:

Write each restriction in the form of a corresponding 3-SAT statement to reduce the (n-1)(n-2)/2 restrictions to a 3-SAT statement with (n-1) ² variables and 4(n-1)(n-2) words:

Among them, x _ii′ =(b _ii′ +1)/2, and β is a newly introduced auxiliary variable.

In some implementations, converting the restriction item into a SAT statement includes:

Write each restriction in the form of a corresponding 4-SAT statement to reduce the (n-1)(n-2)/2 restrictions to a 4-SAT statement with n(n-1)/2 variables and 4(n-1)(n-2) words:

Among them, x _ii′ =(b _ii′ +1)/2.

In some embodiments, the method further comprises:

Based on the final objective function, an adiabatic algorithm is used to solve the problem, and a solution to the problem to be optimized is obtained based on an algorithm calculation for decoding parity codes.

In some embodiments, the problem to be optimized includes a molecular conformation search problem.

According to another aspect of the present invention, a quantum optimization device is provided, the device comprising:

An energy function conversion unit, used for converting the problem to be optimized into a QUBO problem, and converting an initial objective function corresponding to the QUBO problem into an energy function in Ising form;

A monomer local action term conversion unit, used for introducing physical bits into the Ising form energy function, so as to convert the two-body interaction term into the monomer local action term, and obtain the introduced restriction term for ensuring the correctness of the logic bit;

A digital grouping construction unit, used to construct an equivalent digital grouping problem for the restriction item, and obtain a sub-objective function corresponding to the restriction item based on the digital grouping problem;

The final objective function obtaining unit is used to combine the sub-objective function corresponding to the restriction term with the monomer function corresponding to the monomer local action term to obtain the final objective function corresponding to the QUBO problem.

According to another aspect of the present invention, an electronic device is provided, comprising a processor and a memory; wherein the memory is used to store one or more computer instructions, wherein the one or more computer instructions are executed by the processor to implement the above method.

According to another aspect of the present invention, a computer-readable storage medium is provided, on which one or more computer instructions are stored, and the instructions are executed by a processor to implement the above method.

Compared with the prior art, the present invention has the following advantages:

The quantum optimization method provided by the present invention converts the problem to be optimized into a QUBO problem, and converts the initial objective function corresponding to the QUBO problem into an energy function in the Ising form; introduces physical bits for the Ising form energy function to convert the two-body interaction term into a monomer local action term, and obtains the introduced restriction term for ensuring the correctness of the logical bit; constructs an equivalent digital grouping problem for the restriction term, and obtains the sub-objective function corresponding to the restriction term based on the digital grouping problem; combines the sub-objective function corresponding to the restriction term with the monomer function corresponding to the monomer local action term to obtain the final objective function corresponding to the QUBO problem. This method enables encoding to be realized in a one-dimensional cold atom chain, without the need to use the geometric arrangement of quantum bits to realize the restriction conditions introduced in the encoding process, that is, without the need to arrange atoms in two-dimensional space in the physical system, effectively reducing the complexity of the parity encoding process.

BRIEF DESCRIPTION OF THE DRAWINGS

FIG1 is a flow chart of a quantum optimization method provided by an embodiment of the present application;

FIG2 is a schematic diagram of a Mijazawa-Jernigan (MJ) model provided in an embodiment of the present application;

FIG3 is a schematic diagram of an amino acid sequence provided in an embodiment of the present application;

FIG4 is a unit block diagram of a quantum optimization device provided in one embodiment of the present application;

FIG5 is a schematic diagram of the logical structure of an electronic device provided in an embodiment of the present application.

Detailed ways

Many specific details are described in the following description to facilitate a full understanding of the present application. However, the present application can be implemented in many other ways than those described herein, and those skilled in the art can make similar generalizations without violating the connotation of the present application. Therefore, the present application is not limited to the specific implementation disclosed below.

For quantum optimization scenarios, in order to reduce the complexity of the parity encoding process, the present application provides a quantum optimization method, a quantum optimization device, an electronic device and a computer-readable storage medium corresponding to the method. The following embodiments are provided to describe the above method, device, electronic device and computer-readable storage medium in detail.

An embodiment of the present application provides a quantum optimization method. FIG1 is a flow chart of the quantum optimization method provided in the first embodiment of the present application. The method provided in this embodiment is described in detail below in conjunction with FIG1. The embodiments described below are used to explain the principle of the method and are not intended to be limiting for actual use.

The quantum optimization method provided in this embodiment can realize the encoding of QUBO problems in the cold atom system of the optical cavity. The method is based on parity coding, which converts the Hamiltonian originally in the form of two-body interaction with arbitrary connection into the local field form of a monomer, and encodes the restriction terms generated in the process to ensure the correctness of the logical bit into the Hamiltonian that is easy to implement in the cold atom system of the optical cavity, thereby realizing the complete encoding process. As shown in Figure 1, the quantum optimization method includes the following steps:

S101, converting the problem to be optimized into a QUBO problem, and converting the initial objective function corresponding to the QUBO problem into an energy function in Ising form.

This step is used to convert the problem to be optimized into a QUBO (quadratic unconstrained binary optimization) problem, and convert the initial objective function (Boolean function) corresponding to the QUBO problem into an Ising form energy function. In the QUBO problem, the objective function is expressed as a quadratic function of binary variables, where each variable can only take 0 or 1, and the task of this problem is to minimize the objective function.

This example introduces molecular conformation search as a problem to be optimized. Molecular conformation plays an important role in understanding compound structure, reaction mechanism, energy distribution, etc. In calculations such as ECD/NMR calculations, transition state exploration, transition state search, and active conformation generation, molecular conformation search is usually an indispensable step, which is usually calculated and simulated based on common rigid molecular structures and several molecules with flexible changes.

Existing molecular conformation search methods include: systematic search (exhaustive search according to a predetermined strategy. The amount of calculation increases exponentially with the increase in the number of molecules and the number of variable bonds/rotatable bonds, which is limited by software and hardware conditions), random search (with a large number of initial conformations, random search can find the conformation close to the most stable one, but the calculation time is long), and conditional search (based on research work, several initial conditions and search paths are added to the molecular conformation).

The above molecular conformation search method has the following limitations: it is only applicable to static situations; the modeling method is relatively rough, time-consuming and computationally intensive; and it has poor scalability and cannot be applied to larger conformation searches.

Since the search for the global optimal molecular conformation is essentially an NP-hard computational problem, the size of the search space and the corresponding computational complexity grow exponentially with the number of atoms that make up the molecule. Classical computing uses molecular dynamics simulation to reduce computational complexity, but its results cannot guarantee global optimality. Quantum computing has natural computational parallelism due to the principle of quantum superposition, and can perform holistic parallel operations in the entire molecular conformation space. Compared with existing classical algorithms, it can achieve exponential quantum acceleration, especially for large-scale molecular conformation searches, which has significant computational superiority.

The modeling method for molecular conformation search through quantum computing methods is as follows: on the basis of modeling the interaction between atoms using the molecular force field method, the energy function corresponding to the molecular conformation search problem is mapped to the Ising coupled spin glass model that can be effectively solved by quantum computers using quantum coding. The specific coding process can represent the possible bond angles between adjacent chemical bonds in the molecule in the form of binary numbers, and on this basis, the Hamiltonian corresponding to the molecular conformation is quantitatively given according to the three principles of interaction given by the molecular force field, non-overlapping atomic positions, and symmetry.

In this embodiment, the above-mentioned existing technology is used to first convert the molecular conformation search problem into an Ising coupled spin glass model, and a quantum encoding method is proposed, so that the molecular conformation search problem can be conveniently and naturally encoded in an actual optical cavity cold atom experimental system. The molecular conformation search problem is converted into a Hamiltonian ground state problem, which can be solved on a quantum computer through algorithms such as quantum amplitude amplification, quantum adiabatic quenching, variational quantum computing, QAOA, and quantum Lanczos.

For example, for the protein folding problem in the molecular conformation search problem, the folding structure of the protein is determined by the relative positions of adjacent amino acid molecules. The direction of the chemical bond between each two adjacent molecules can be represented by a binary variable, 00 for downward, 01 for right, 10 for left, and 11 for upward. By fixing the direction of the first bond, the folding description of any N amino acids can be simplified to the description of 2N-4 binary variables. Taking into account the molecular structure mergers caused by rotational symmetry restrictions, the third binary variable can be fixed to 0, forcing the third amino acid to go straight or downward, thereby reducing the number of required variables to 2N-5. Therefore, the molecular folding state of a particular structure can be described by the following equation:

q＝010q ₁ q ₂ q ₃ …q _2N-6 q _2N-5

Where q _i = 0 or 1, 01 means the direction of the first chemical bond is to the right, 0q ₁ means the direction of the second chemical bond is to the right or downward, and each subsequent two variables in this binary variable sequence are connected to represent the direction of a chemical bond. In this way, the relative position of each molecule in space can be known, and combined with the known interaction between molecules, it can be expressed as the coupling E _int between quantum bits. In the sub-calculation, it is still necessary to consider constraints such as the inability of groups to overlap in space and the removal of unreasonable rotation angles. These constraints are achieved by adding penalty terms to the energy function. The penalty terms are E _olap and E _constraint , as shown in the following formula:

E(q)＝E _int (q)+E _olap (q)+E _constraint (q)

Generally speaking, the Hamiltonian H(q) of the corresponding quantum optimization problem is a polynomial with respect to the binary variables in the sequence q. At this time, the expression of the Hamiltonian contains coupling terms of more than two bodies. By introducing additional auxiliary variables, the original multi-body interaction terms can be reduced to a series of two-body interaction terms, turning it into the form of a QUBO problem.

Taking the Mijazawa-Jernigan (MJ) model in Figure 2 as an example, the six amino acid sequence of proline-serine-valine-lysine-methionine-alanine (PSVKMA), its molecular folding structure can be described by the sequence q = 010q ₁ q ₂ q ₃ q ₄ q ₅ q ₆ q _7. Based on the known size of the interaction between molecules, the corresponding energy function expression can be obtained as:

E _PSVVKMA (q)＝-q ₂ +8q ₁ q ₂ +15q ₂ q ₃ -18q ₁ q ₂ q ₃ -3q ₁ q ₄ +12q ₁ q ₂ q ₄ +4q ₃ q ₄ +3q ₁ q ₃ q ₄ -6q ₂ q ₃ q ₄ -12q ₁ q ₂ q ₃ q ₄ +4q ₂ q ₅ +3q ₁ q ₂ q ₅ -15q ₂ q ₃ q ₅ +15q ₄ q ₅ +3q ₁ q ₄ q ₅ -6q ₂ q ₄ q ₅ -12q ₁ q ₂ q ₄ q ₅ -15q ₃ q ₄ q ₅ +28q ₂ q ₃ q ₄ q ₅ -2q ₁ q ₂ q ₆ -4q ₃ q ₆ +2q ₂ q ₃ q ₆ +13q ₁ q ₂ q ₃ q ₆ -2q ₁ q ₄ q ₆ +4q ₁ q ₂ q ₄ q ₆ +2q ₃ q ₄ q ₆ +13q ₁ q ₃ q ₄ q ₆ +4q ₂ q ₃ q ₄ q ₆ -37q ₁ q ₂ q ₃ q ₄ q ₆ +7q ₅ q ₆ +2q ₂ q ₅ q ₆ +13q ₁ q ₂ q ₅ q ₆ +4q ₂ q ₄ q ₅ q ₆ +9q ₂ q ₃ q ₅ q ₆ -33q ₁ q ₂ q ₃ q ₅ q ₆ -20q ₄ q ₅ q ₆ +13q ₁ q ₄ q ₅ q ₆ +4q ₂ q ₄ q ₅ q ₆ -37q ₁ q ₂ q ₄ q ₅ q ₆ +9q ₃ q ₄ q ₅ q ₆ -33q ₁ q ₃ q ₄ q ₅ q ₆ -37q ₂ q ₃ q ₄ q ₅ q ₆ +99q ₁ q ₂ q ₃ q ₄ q ₅ q ₆ -4q ₂ q ₇ +4q ₂ q ₃ q ₇ +7q ₄ q ₇ + 2q ₂ q ₄ q ₇ +13q ₁ q ₂ q ₃ q ₇ +4q ₃ q ₄ q ₇ +9q ₂ q ₃ q ₄ q ₇ -33q ₁ q ₂ q ₃ q ₄ q ₇ +4q ₂ q ₅ q ₇ -18q ₄ q ₅ q ₇ +9q ₂ q ₄ q ₅ q ₇ -33q ₁ q ₂ q ₄ q ₅ q ₇ - 33q ₂ q ₃ q ₄ q ₅ q ₇ +62q ₁ q ₂ q ₃ q ₄ q ₅ q ₇ +7q ₆ q ₇ +2q ₂ q ₆ q ₇ +13q ₁ q ₂ q ₆ q ₇ +4q ₃ q ₆ q ₇ +9q ₂ q ₃ q ₆ q ₇ -33q ₁ q ₂ q ₃ q ₆ q ₇ -20q ₄ q ₆ q ₇ +13q ₁ q ₄ q ₆ q ₇ +4q ₂ q ₄ q ₆ q ₇ -37q ₁ q ₂ q ₄ q ₆ q ₇ +9q ₃ q ₄ q ₆ q ₇ -33q ₁ q ₃ q ₄ q ₆ q ₇ -37q ₂ q ₃ q ₄ q ₆ q ₇ +99q ₁ q ₂ q ₃ q ₄ q ₆ q ₇ -18q ₅ q ₆ q ₇ +9q ₂ q ₅ q ₆ q ₇ -33q ₁ q ₂ q ₅ q ₆ q ₇ -33q ₂ q ₃ q ₅ q ₆ q ₇ +62q ₁ q ₂ q ₃ q ₅ q ₆ q ₇ +53q ₄ q ₅ q ₆ q ₇ -33q ₁ q ₄ q ₅ q ₆ q ₇ -37q ₂ q ₄ q ₅ q ₆ q ₇ +99q ₁ q ₂ q ₄ q ₅ q ₆ q ₇ -33q ₃ q ₄ q ₅ q ₆ q ₇ +62q ₁ q ₃ q ₄ q ₅ q ₆ q ₇ +99q ₂ q ₃ q ₄ q ₅ q ₆ q ₇ -190q ₁ q ₂ q ₃ q ₄ q ₅ q ₆ q ₇

Consider the special case shown in Figure 3, where only the fourth and fifth chemical bond angles need to be considered. The corresponding sequence is q = 010010q ₄ 0q ₆ q ₇ . Substituting the energy function and rewriting the notation as q = 010010q ₁ 0q ₂ q ₃ , we obtain the following equation:

E(q)＝-1-4q ₃ +9q ₁ q ₃ +9q ₂ q ₃ -16q ₁ q ₂ q ₃

Here, an additional Boolean variable q ₄ =q ₂ q ₃ is introduced to convert the original three-body problem into a two-body problem. In order to ensure that q ₄ =q ₂ q ₃ can be satisfied, an additional term δ(3q ₄ +q ₂ q ₃ -2q ₂ q ₄ -2q ₃ q ₄ ) is introduced. When this condition is violated, the additional energy is greater than 0, where δ represents the intensity of the penalty term. In this embodiment, δ=9 can be taken. The energy function obtained can be:

E(q′)＝-1-4q ₃ +36q ₄ +9q ₁ q ₃ -16q ₁ q ₄ -18q ₂ q ₄ -18q ₃ q ₄

Introducing a new Ising variable s _i into the energy function, and satisfying q _i =1-s _i )/2, and omitting the constant term in the energy function, the energy function in Ising form is obtained:

(7s ₁ +9s ₂ +8s ₃ -20s ₄ +9s ₁ s ₃ +9s ₂ s ₃ -16s ₁ s ₄ -18s ₂ s ₄ -18s ₃ s ₄ )/4

For the single term, an additional auxiliary logic bit s ₀ can be introduced and s ₀ =1 to write the energy function into the following form which is more convenient for processing in this embodiment: (7s ₀ s ₁ +9s ₀ s ₂ +8s ₀ s ₃ -20s ₀ s ₄ +9s ₁ s ₃ +9s ₂ s ₃ -16s ₁ s ₄ -18s ₂ s ₄ -18s ₃ s ₄ )/4

The energy function converted into the Ising form can be solved using the subsequent steps provided in this embodiment.

S102, introducing physical bits for the Ising form energy function to convert the two-body interaction term into a single-body local interaction term, and obtaining the introduced restriction term for ensuring the correctness of the logical bit.

After the above steps convert the problem to be optimized into a QUBO problem and convert the initial objective function corresponding to the QUBO problem into an Ising form energy function, this step is used to introduce physical bits for the Ising form energy function using parity coding to convert the original global interaction two-body interaction terms into monomer local interaction terms, and obtain the introduced restriction conditions (i.e., restriction terms) for ensuring the correctness of the logical bits.

For example, for the energy function

The physical bit b _ii′ = s _i s _i′ can be introduced to convert the two-body interaction term J _ii′ into the monomer local interaction term J and the energy function into the form of monomer local field action. And obtain the (n-1)(n-2)/2 constraints introduced to ensure the correctness of the logical bits. In this embodiment, n is the number of variables of the Ising form energy function, which can be 5 in the scenario of this embodiment. The restriction items are introduced to satisfy the following equation (other methods can also be used to set the restriction items, which are not limited here): b _ii′ b _ii′+1 b _i+1i′+1 b _i+1i′ =1.

S103, constructing an equivalent digital grouping problem for the restriction item, and obtaining a sub-objective function corresponding to the restriction item based on the digital grouping problem.

After the above steps use parity coding to introduce physical bits for the Ising form energy function to convert the original global interaction terms into monomer local interaction terms, and obtain the introduced constraints (i.e., constraints) to ensure the correctness of the logical bits, this step is used to construct an equivalent digital grouping problem for the above introduced constraints, and obtain the sub-objective function corresponding to the constraints based on the digital grouping problem.

For any Boolean variable equation, a corresponding SAT statement can be obtained, so that when the group of Boolean variables satisfies the original equation, the corresponding SAT statement is also satisfied. Based on this conclusion, this embodiment converts the restriction conditions (i.e., restriction items) that are originally not easy to encode in the physical system into a SAT statement form that is easier to implement in the existing physical system. There are many selectable SAT statement forms. Taking 3-SAT statements as an example, each restriction item can be converted into the corresponding 3-SAT statement form as follows:

Wherein, x _ii , =(b _ii′ +1)/2, β is a newly introduced auxiliary variable. Through this transformation, the above (n-1)(n-2)/2 constraints can be reduced to a 3-SAT problem with (n-1) ² variables and 4(n-1)(n-2) sentences.

In another embodiment, each restriction item may be written in the form of the following 4-SAT statement. Through this transformation, the above (n-1)(n-2)/2 restriction conditions may be reduced to a 4-SAT statement with n(n-1)/2 variables and 4(n-1)(n-2) words:

Wherein, x _ii′ =(b _ii′ +1)/2.

The above-mentioned construction of an equivalent digital grouping problem for the restriction term refers to reducing the SAT statement to a digital grouping problem that can be encoded in the cold atomic system of the optical cavity. Specifically, a digital group can be defined based on the SAT statement, so that when the SAT statement is evaluated by satisfiable variables, a subset can be obtained in the defined digital group, and the sum of the numbers contained in the subset is equal to a certain target value; based on the defined digital group, the objective function of the digital grouping problem is constructed.

In this embodiment, in the process of reducing the SAT statement to a digital grouping problem that can be encoded in a cold atom system of an optical cavity, the integer power series in the defined digital and target values are replaced by integer square roots without square factors. Specifically, based on existing classical calculations, a 3-SAT problem can be reduced to an integer subset sum problem. The difference between this embodiment and the existing classical calculation is that the integer power series in the digital and target values in the existing classical calculations are replaced by integer square roots without square factors. For example, the power series ^bi of the integer b is replaced by the i-th integer square root without square factors. The purpose is to avoid the introduction of exponentially large experimental parameters that may lead to an exponential explosion of experimental parameters, making a realistic experimental platform impossible to implement.

Assuming that a 3-SAT statement consists of M words c ₁ , c ₂ , …, c _M , and the 3-SAT statement contains N variables x ₁ , x ₂ , …, x _N , the above definition of a number group based on the SAT statement specifically includes the following contents:

The numbers defined based on the SAT statement are:

The target value defined based on the SAT statement is:

Where i ranges from 1 to N, j ranges from 1 to M, and α _p represents the pth integer without square factors;

{a _i , b _i , c _j , d _j } constitutes a new digital set for the digital grouping problem. The digital set is marked with serial numbers and re-recorded as a sequence {r ₁ , ..., r _k , ...r _2M+2N };

Based on the sequence, we construct an equivalent objective function for the digital grouping problem:

Wherein, y _k = 1 or -1, and T is the defined target value.

The sub-objective function corresponding to the restriction item obtained based on the digital grouping problem specifically refers to substituting the number of variables and the number of words of the SAT statement into the objective function of the digital grouping problem to obtain the sub-objective function corresponding to the restriction item. For example, substituting M = 4 (n-1) (n-2) and N = (n-1) ² into the objective function of the digital grouping problem, the following sub-objective function corresponding to the restriction item is obtained:

S104, combining the above sub-objective function with the monomer function corresponding to the monomer local action term to obtain the final objective function corresponding to the QUBO problem.

After the two-body interaction term is converted into a monomer local interaction term by parity coding in the above step S102, and the sub-objective function corresponding to the restriction term is obtained in step S103, this step is used to combine the above sub-objective function with the monomer function corresponding to the monomer local interaction term to obtain the final objective function corresponding to the QUBO problem. Specifically, the sub-objective function is added to the monomer function, and the final objective function obtained is:

Here, Δ needs to be set large enough.

It should be noted that after the final objective function corresponding to the QUBO problem is obtained, it is necessary to use an adiabatic algorithm to solve the final objective function, and obtain the solution of the problem to be optimized based on the algorithm for decoding parity codes. Specifically, the final objective function is solved using an adiabatic algorithm to obtain {y _k }, and according to the final objective function obtained in step S104, the first n(n-1)/2 y _k = b _k can be obtained, and the solution to the QUBO problem can be obtained by using the existing algorithm for decoding parity codes to solve the variable {b _k }.

In the prior art, on the basis of parity coding, it is necessary to use the geometric arrangement of quantum bits to realize the constraints brought about in the coding process. However, this embodiment uses the method of problem reduction, and does not directly encode the constraints in the physical platform, but uses the SAT problem as a bridge to link the constraints with the digital grouping problem (converting the constraints introduced by the QUBO problem after parity coding into a digital grouping problem), so that the constraints can be naturally encoded in the cold atom system in the optical cavity without the help of geometric arrangement. That is, through the method of problem reduction, the coding process only needs to be realized in a one-dimensional cold atom chain, and there is no need to arrange atoms in two-dimensional space, which avoids the requirement of regulating atoms in two-dimensional space in the prior art. This scheme fully develops and utilizes the non-local interaction form of the cold atom experimental system in the optical cavity, making it a potential global quantum optimization platform.

Moreover, by reducing the constraints (restrictions) to a digital grouping problem, the quantum optimization problem that originally required n-bit global interactions was encoded into a cold atom system in an optical cavity. The cost of the additional atoms consumed is 2(n-1)(5n-9)-n, which only brings a quadratic scaling speed, making the scaling of the number of atoms used in this scheme better.

The above-mentioned first embodiment provides a method, and correspondingly, the fourth embodiment of the present application also provides a device. Since the device embodiment is basically similar to the method embodiment, the description is relatively simple. For details of the relevant technical features, please refer to the corresponding description of the method embodiment provided above. The following description of the device embodiment is merely illustrative.

Please refer to FIG. 4 to understand this embodiment. FIG. 4 is a unit block diagram of a device provided in this embodiment. As shown in FIG. 4 , the device provided in this embodiment includes:

An energy function conversion unit 201 is used to convert the problem to be optimized into a QUBO problem, and convert the initial objective function corresponding to the QUBO problem into an energy function in Ising form;

A monomer local interaction term conversion unit 202, used for introducing physical bits into the Ising form energy function, so as to convert the two-body interaction term into a monomer local interaction term, and obtain the introduced restriction term for ensuring the correctness of the logic bit;

A digital grouping construction unit 203 is used to construct an equivalent digital grouping problem for the restriction item, and obtain a sub-objective function corresponding to the restriction item based on the digital grouping problem;

The final objective function obtaining unit 204 is used to combine the sub-objective function corresponding to the restriction term with the monomer function corresponding to the monomer local action term to obtain the final objective function corresponding to the QUBO problem.

In some implementations, constructing an equivalent digital grouping problem for the restriction item includes:

The constraints are converted into SAT statements, and the SAT statements are reduced to a digital grouping problem that can be encoded in a cold atomic system of an optical cavity.

In some embodiments, reducing the SAT statement to a digital grouping problem that can be encoded in a cold atom system of an optical cavity includes:

A number group is defined based on the SAT statement, so that when the SAT statement is evaluated by a satisfiable variable, a subset can be obtained in the number group, and the sum of the numbers included in the subset is equal to a certain target value, wherein the integer power series in the numbers and the target value are replaced by integer square roots without square factors;

Based on the number groups, an objective function of the number grouping problem is constructed.

In some implementations, the SAT statement is composed of M clauses c ₁ , c ₂ , ..., c _M , and the SAT statement contains N variables x ₁ , x ₂ , ..., x _N . Defining a number group based on the SAT statement includes:

The numbers defined based on the SAT statement are:

The target value defined based on the SAT statement is:

Where i ranges from 1 to N, j ranges from 1 to M, and α _p represents the pth integer without square factors;

{a _i , b _i , c _j , d _j } constitutes a new digital grouping problem digital set, which is recorded as a sequence {r ₁ , …, r _k , …e _2M+2N };

Based on the sequence, we construct an equivalent objective function for the digital grouping problem:

Here, y _k =1 or -1.

In some implementations, obtaining the sub-objective function corresponding to the restriction item based on the digital grouping problem includes:

Substitute the number of variables and the number of sentences of the SAT statement into the objective function of the digital grouping problem to obtain the sub-objective function corresponding to the restriction item.

In some embodiments, the Ising form energy function is expressed as:

The energy function of the Ising form introduces physical bits to convert the two-body interaction term into a monomer local interaction term, and obtains the introduced restriction term for ensuring the correctness of the logical bit, including:

The physical bit b _ii′ = s _i s _i′ is introduced into the Ising form energy function to convert the two-body interaction term J _ii′ into a monomer local interaction term J and the energy function into a monomer local field action form. And obtain the (n-1)(n-2)/2 constraints introduced to ensure the correctness of the logic bit, where n is the number of variables of the Ising form energy function, and the introduced constraints satisfy the following equation:

b _ii′ b _ii′+1 b _i+1i′+1 b _i+1i′ =1.

In some implementations, converting the restriction item into a SAT statement includes:

Write each restriction in the form of a corresponding 3-SAT statement to reduce the (n-1)(n-2)/2 restrictions to a 3-SAT statement with (n-1) ² variables and 4(n-1)(n-2) words:

Among them, x _ii′ =(b _ii′ +1)/2, and β is a newly introduced auxiliary variable.

In some implementations, converting the restriction item into a SAT statement includes:

Write each restriction in the form of a corresponding 4-SAT statement to reduce the (n-1)(n-2)/2 restrictions to a 4-SAT statement with n(n-1)/2 variables and 4(n-1)(n-2) words:

Wherein, x _ii′ =(b _ii′ +1)/2.

In some embodiments, the device further comprises:

A solving unit is used to solve the problem to be optimized by using an adiabatic algorithm based on the final objective function and calculating the solution based on an algorithm for decoding parity coding.

In the above-mentioned embodiments, a quantum optimization method and a quantum optimization device are provided. In addition, another embodiment of the present application further provides an electronic device, which can be provided with the above-mentioned quantum optimization device in the form of a program to execute the quantum optimization process provided by the embodiment of the present invention. The electronic device embodiment provided in this application is described relatively simply. For the relevant parts, please refer to the corresponding description of the above-mentioned method embodiment. The embodiment described below is merely exemplary. Optionally, an optional hardware structure of the electronic device may be as shown in Figure 3, including: at least one processor 01, at least one communication interface 302, at least one memory 303 and at least one communication bus 304;

Optionally, the communication interface 302 may be an interface of a communication module, such as an interface of a GSM module;

The processor 01 may be a central processing unit CPU, or an application specific integrated circuit ASIC (Application Specific Integrated Circuit), or one or more integrated circuits configured to implement the embodiments of the present invention.

The memory 303 may include a high-speed RAM memory, and may also include a non-volatile memory (non-volatile memory), such as at least one disk memory.

The memory 303 stores a program, and the processor 301 calls the program stored in the memory 303 to execute the quantum optimization method provided in the embodiment of the present invention.

In the above embodiments, a quantum optimization method, a quantum optimization device, and an electronic device are provided. In addition, another embodiment of the present application further provides a computer-readable storage medium for implementing the above quantum optimization method. The computer-readable storage medium embodiment provided in the present application is described relatively simply. For the relevant parts, please refer to the corresponding description of the above method embodiment. The embodiments described below are merely illustrative.

The computer-readable storage medium provided in this embodiment stores computer instructions, and when the instructions are executed by a processor, the quantum optimization method provided in the above embodiment can be implemented.

In a typical configuration, a computing device includes one or more processors (CPU), input/output interfaces, network interfaces, and memory.

The memory may include non-permanent storage in a computer-readable medium, random access memory (RAM) and/or non-volatile memory in the form of read-only memory (ROM) or flash RAM. The memory is an example of a computer-readable medium.

1. Computer-readable media includes permanent and non-permanent, removable and non-removable media that can be used to store information by any method or technology. Information can be computer-readable instructions, data structures, program modules or other data. Examples of computer storage media include, but are not limited to, phase change memory (PRAM), static random access memory (SRAM), dynamic random access memory (DRAM), other types of random access memory (RAM), read-only memory (ROM), electrically erasable programmable read-only memory (EEPROM), flash memory or other memory technology, compact disk read-only memory (CD-ROM), digital versatile disk (DVD) or other optical storage, magnetic cassettes, magnetic tape magnetic disk storage or other magnetic storage devices or any other non-transmission media that can be used to store information that can be accessed by a computing device. As defined herein, computer-readable media does not include non-transitory media such as modulated data signals and carrier waves.

2. Those skilled in the art should understand that the embodiments of the present application can be provided as methods, systems or computer program products. Therefore, the present application can take the form of a complete hardware embodiment, a complete software embodiment or an embodiment combining software and hardware. Moreover, the present application can take the form of a computer program product implemented on one or more computer-usable storage media (including but not limited to disk storage, CD-ROM, optical storage, etc.) containing computer-usable program code.

Although the present application is disclosed as above in the form of a preferred embodiment, it is not intended to limit the present application. Any technical personnel in this field may make possible changes and modifications without departing from the spirit and scope of the present application. Therefore, the scope of protection of the present application shall be based on the scope defined by the claims of the present application.

Claims (10)

1. A quantum optimization method, characterized in that the method comprises: Converting the problem to be optimized into a QUBO problem, and converting the initial objective function corresponding to the QUBO problem into an Ising-form energy function, wherein the problem to be optimized includes a molecular conformation search problem; Introducing physical bits into the Ising form energy function to convert the two-body interaction term into a single-body local interaction term, and obtaining the introduced restriction term for ensuring the correctness of the logical bit; The restriction term is converted into a SAT statement, and the SAT statement is reduced to a digital grouping problem that can be encoded in a cold atom system of an optical cavity, and a sub-objective function corresponding to the restriction term is obtained based on the digital grouping problem; wherein, reducing the SAT statement to a digital grouping problem that can be encoded in a cold atom system of an optical cavity comprises: defining a digital group based on the SAT statement, so that when the SAT statement is taken by a satisfiable variable, a subset can be obtained in the digital group, and the sum of the numbers contained in the subset is equal to a certain target value, wherein the integer power series in the numbers and the target value are replaced by integer square roots without square factors; based on the digital group, constructing an objective function of the digital grouping problem; The sub-objective function corresponding to the restriction term is combined with the monomer function corresponding to the monomer local action term to obtain the final objective function corresponding to the QUBO problem. 2. The method according to claim 1, wherein the SAT statement is composed of M words c ₁ , c ₂ , ..., c _M , and the SAT statement contains N variables x ₁ , x ₂ , ... x _N , and defining a number group based on the SAT statement comprises: The numbers defined based on the SAT statement are: The target value defined based on the SAT statement is: Where i ranges from 1 to N, j ranges from 1 to M, and α _p represents the pth integer without square factors; {a _i , b _i , c _j , d _j } constitute a digital set for a new digital grouping problem, and the digital set is recorded as a sequence {r ₁ , ..., r _k , ...r _2M+2N }; Based on the sequence, we construct an equivalent objective function for the digital grouping problem: Here, y _k =1 or -1. 3. The method according to claim 1 or 2, characterized in that the step of obtaining the sub-objective function corresponding to the restriction item based on the digital grouping problem comprises: Substitute the number of variables and the number of sentences of the SAT statement into the objective function of the digital grouping problem to obtain the sub-objective function corresponding to the restriction item. 4. The method according to claim 1, characterized in that the energy function of the Ising form is expressed as: The energy function of the Ising form is introduced with a physical bit so as to convert the two-body interaction term into a monomer local action term, and obtain the introduced restriction term for ensuring the correctness of the logical bit, including: introducing a physical bit b _ii′ = s _i s _i′ for the energy function of the Ising form so as to convert the two-body interaction term J _ii′ into a monomer local action term J, converting the energy function into a form of monomer local field action And obtain the (n-1)(n-2)/2 constraints introduced to ensure the correctness of the logic bit, where n is the number of variables of the Ising form energy function, and the introduced constraints satisfy the following equation: b _ii , b _ii′+1 b _i+1i′+1 b _i+1i′ =1. 5. The method according to claim 4, characterized in that converting the restriction item into a SAT statement comprises: Write each restriction in the form of a corresponding 3-SAT statement to reduce the (n-1)(n-2)/2 restrictions to a 3-SAT statement with (n-1) ² variables and 4(n-1)(n-2) words: Among them, x _ii′ =(b _ii′ +1)/2, and β is a newly introduced auxiliary variable. 6. The method according to claim 4, characterized in that converting the restriction item into a SAT statement comprises: Write each restriction in the form of a corresponding 4-SAT statement to reduce the (n-1)(n-2)/2 restrictions to a 4-SAT statement with n(n-1)/2 variables and 4(n-1)(n-2) words: Among them, x _ii′ =(b _ii′ +1)/2. 7. The method according to claim 1, characterized in that the method further comprises: Based on the final objective function, an adiabatic algorithm is used to solve the problem, and a solution to the problem to be optimized is obtained based on an algorithm calculation for decoding parity codes. 8. A quantum optimization device, comprising: An energy function conversion unit, used for converting the problem to be optimized into a QUBO problem, and converting an initial objective function corresponding to the QUBO problem into an energy function in Ising form, wherein the problem to be optimized includes a molecular conformation search problem; A monomer local action term conversion unit, used for introducing physical bits into the Ising form energy function, so as to convert the two-body interaction term into the monomer local action term, and obtain the introduced restriction term for ensuring the correctness of the logic bit; A digital grouping construction unit, used for converting the restriction item into a SAT statement, reducing the SAT statement into a digital grouping problem that can be encoded in a cold atom system of an optical cavity, and obtaining a sub-objective function corresponding to the restriction item based on the digital grouping problem; The reducing the SAT statement to a digital grouping problem that can be encoded in a cold atom system of an optical cavity comprises: A number group is defined based on the SAT statement, so that when the SAT statement is evaluated by a satisfiable variable, a subset can be obtained in the number group, and the sum of the numbers included in the subset is equal to a certain target value, wherein the integer power series in the numbers and the target value are replaced by integer square roots without square factors; based on the number group, an objective function of the number grouping problem is constructed; The final objective function obtaining unit is used to combine the sub-objective function corresponding to the restriction term with the monomer function corresponding to the monomer local action term to obtain the final objective function corresponding to the QUBO problem. 9. An electronic device, comprising a processor and a memory; wherein: The memory is used to store one or more computer instructions, wherein the one or more computer instructions are executed by the processor to implement the method according to any one of claims 1 to 7. 10. A computer-readable storage medium having one or more computer instructions stored thereon, wherein the instructions are executed by a processor to implement the method according to any one of claims 1 to 7.