Search

EP-4009247-B1 - METHODS AND APPARATUSES FOR OPERATING A GAUSSIAN BOSON SAMPLING QUANTUM DEVICE AS AN ANNEALER

EP4009247B1EP 4009247 B1EP4009247 B1EP 4009247B1EP-4009247-B1

Inventors

  • Orús, Román
  • Mugel, Samuel

Dates

Publication Date
20260506
Application Date
20201201

Claims (15)

  1. A computer-implemented method (100) comprising obtaining (110) an equation with a cost function for minimization related to an optimization problem thereby yielding a cost function equation, the cost function including two or more binary variables, the method further comprising: converting (120) an integer programming formulation of the cost function equation into a Boolean formula in Conjunctive Normal Form comprising a clause for each term of the cost function that includes at least one binary variable; obtaining (130) a Max-Clique problem by processing the Boolean formula; providing (140) the Max-Clique problem to a Gaussian Boson Sampling, GBS, quantum device (20); and processing (150) light output data of the GBS quantum device (20) after the step of providing the Max-Clique problem so as to find values of the two or more binary variables of the cost function.
  2. The computer-implemented method of claim 1, further comprising providing (160) at least one command to or actuating an apparatus or system for configuration thereof, the at least one command or actuation being based on the values of the two or more binary variables found.
  3. The computer-implemented method of any one of the preceding claims, wherein the step of obtaining (110) the equation with the cost function further comprises processing the cost function equation so as to derive an integer programming formulation thereof if the cost function equation is not in an integer programming formulation.
  4. The computer-implemented method of any one of the preceding claims, wherein the integer programming formulation of the cost function equation is: H | I = ∑〈 i,j 〉 R ij x i x j + ∑ i r i x i , where x i and x j are the binary variables, R ij and r i are couplings of the respective binary variables x i and x j .
  5. The computer-implemented method of any one of the preceding claims, wherein the converting (120) step further comprises: converting (122) the integer programming formulation of the cost function equation into a sums of terms formulation and converting (124) the sums of terms formulation into the Boolean formula if the integer programming formulation of the cost function equation is not also in sums of terms formulation, and wherein each sum of the sums of terms formulation has a prefactor of one.
  6. The computer-implemented method of any one of the preceding claims, wherein the Boolean formula is: ∅ = Λ b = 1 m 2 C b 2 Λ a = 1 m 1 C a 1 , where C b 2 and C a 1 are two- and one-binary clauses, respectively, and m 2 and m 1 are total numbers of the two- and one-binary clauses, respectively.
  7. The computer-implemented method of any one of the preceding claims, wherein the Max-Clique problem obtained (130) comprises construction of a graph with cliques of a given size k and in one-to-one correspondence to assignments of the Boolean formula satisfying k clauses of the Boolean formula.
  8. The computer-implemented method of any one of the preceding claims, wherein the light output data is processed (150) to find (152) a maximum-size clique of a graph of the Max-Clique problem, and processing (154) the maximum-size clique in order to find the values of the two or more binary variables of the cost function.
  9. The computer-implemented method of any one of the preceding claims, wherein the step of obtaining (110) the equation with the cost function further comprises: digitizing one or more continuous variables into one or more of the two or more binary variables with the following equation: p s = ∑ α = 0 m − 1 2 α x s , α , where p s is the respective continuous variable, m is the respective number of bits for the digitization, and x s,α is the respective one or more binary variables; and/or processing the cost function to reduce the polynomials of the one or more binary variables to quadratic terms.
  10. The computer-implemented method of claim 2, or any one of claims 3-9 when depending upon claim 2, wherein the two or more binary variables relate to one or more devices of the apparatus or system, and wherein the at least one command is provided to or the actuation is made on one of the following: at least one device of said one or more devices, at least one device different from said one or more devices, and a combination thereof.
  11. The computer-implemented method of any one of the preceding claims, wherein the optimization problem relates to an optimization problem for one of: control of a factory, control of a production line, control of a machine, training of a machine learning algorithm, and factoring large numbers.
  12. The computer-implemented method of any one of the preceding claims, further comprising codifying the Max-Clique problem in the GBS quantum device (20).
  13. A data processing apparatus or system (1-2) comprising means for carrying out the steps of the method (100) of any one of claims 1-11.
  14. The data processing apparatus or system of claim 13, further comprising the GBS quantum device (20) communicatively coupled with the means and adapted for carrying out the step of codifying the Max-Clique problem.
  15. A computer program product comprising instructions which, when the program is executed by a computer, cause the computer to carry out the steps of the method (100) of any one of claims 1-11.

Description

TECHNICAL FIELD The present invention relates to the field of computing apparatuses. More particularly, the present invention relates to methods and apparatuses for operating a photonic quantum device as an annealer thereby optimizing a cost function of an optimization problem for the control or configuration of a process, device or system. STATE OF THE ART The appearance and continued development of quantum devices has opened the door to solving many computing problems that could not be solved up until then due to the complexity thereof, or at least not in acceptable timeframes, e.g. in less than a decade, a year, etc. An example of such computing problems are optimization problems like Quadratic Unconstrained Binary Optimization, whose minimization is NP-Hard. Different types of quantum devices have been developed so far, each type featuring a particular technology with respective advantages and disadvantages. Quantum devices based on circuits having superconducting materials -through which electric currents flow while the materials thereof are at a temperature in the order of tens or hundreds of millikelvin- have been gaining traction lately, and as a result there have been developments for operating devices of this type as annealers. US-10691771-B2 provides a method for generating an embedding pattern used for solving an Integer Linear Programming problem using a Physical Ising Machine. EP-3664099-A1 describes methods and systems for allocating items in an exchange system, which results in the definition of an exchange problem, using quantum computing resources. US-9152746-B2 describes a quantum annealer simulator; with the simulator, a classical computer simulates the unitary dynamics of a quantum annealer for finding the solution to optimization problems. Developments appear to be necessary to exploit the capabilities of other types of quantum devices, such as photonics quantum devices. This type of devices include circuits through which photons propagate; further, many photonics quantum devices can operate at ambient temperature. Gaussian Boson Sampling quantum devices could be used for the solving of optimization problems as well. Gaussian boson sampling (GBS) has been proposed as a photonic quantum computing platform and techniques have been described for applying GBS to graph-based optimisation problems, including problems related to finding dense subgraphs and/or maximum cliques in graphs (see, for example, T. R. Bromley et al., Quantum Sci. Technol. 5 (2020) 034010; and L. Banchi et al., arXiv:1902.00462 (2019)). There is an interest in enabling the operation of photonics quantum devices as annealers because that would make them highly convenient for the control of processes, devices and systems in many applications. DESCRIPTION OF THE INVENTION A first aspect of the invention relates to a computer-implemented method comprising obtaining an equation with a cost function for minimization related to an optimization problem thereby yielding a cost function equation, the cost function including two or more binary variables; converting an integer programming formulation of the cost function equation into a Boolean formula in Conjunctive Normal Form -namely CNF- comprising a clause for each term of the cost function that includes at least one binary variable; obtaining a Max-Clique problem by processing the Boolean formula; providing the Max-Clique problem to a Gaussian Boson Sampling -namely GBS- quantum device; and processing light output data of the GBS quantum device after the step of providing the Max-Clique problem so as to find values of the two or more binary variables of the cost function. The method makes possible to have an optimization problem solved using a GBS quantum device as a quantum optimization device or quantum annealer. To this end, a computing apparatus or system obtains the cost function equation and processes it so as to provide quantum state of light codifiable into the quantum device, and then processes the output of the quantum device to provide a solution to the optimization problem. The optimization problem preferably relates to the operation of devices and/or systems, and/or relates to processes themselves, e.g. how the different entities in a process interact. For example, the optimization problem may relate to an optimization problem for one of: control of a factory, control of a production line, control of a machine, training of a machine learning algorithm, factoring large numbers, quality control of workpieces produced with a machine, etc. The cost function equation is such that it defines an Unconstrained Binary Optimization -namely UBO- that, in some examples, sets out a Quadratic Unconstrained Binary Optimization -namely QUBO- whereas in other examples it sets out a Higher-order Unconstrained Binary Optimization -namely HUBO-. In this sense, the cost function includes a plurality of binary variables, which preferably can take values of 0 and 1 -but could also tak