Methods and apparatuses for operating a gaussian boson sampling quantum device as an annealer
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 the cost function equation into a Boolean formula in Conjunctive Normal; obtaining a Max-Clique problem by processing the Boolean formula; providing the Max-Clique problem to a Gaussian Boson Sampling, GBS, quantum device; and processing light output data of the GBS quantum device so as to find values of the two or more binary variables of the cost function.
1. A method comprising:
obtaining, by a computing apparatus or a computing system, 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, by the computing apparatus or the computing system, 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, by the computing apparatus or the computing system, a Max-Clique problem by processing the Boolean formula;
providing, from the computing apparatus or the computing system, the Max-Clique problem to a Gaussian Boson Sampling, GBS, quantum device by converting the Max-Clique problem into quantum state of light received as input by the GBS quantum device;
outputting, by the GBS quantum device, light resulting from the quantum state of light received as input by the GBS quantum device, the light output having a distribution corresponding to dense subgraphs in a graph of the Max-Clique problem;
transforming the light output into light output data; and
processing, by the computing apparatus or the computing system, the light output data by finding one or more cliques of the subgraphs so as to find values of the two or more binary variables of the cost function; the one or more cliques having the values of the two or more binary variables of the cost function.
2. The method of claim 1 , further comprising providing, by the computing apparatus or the computing system, at least one command to or actuating, by the computing apparatus or the computing system, 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 method of claim 2 , wherein the two or more binary variables relate to one or more devices of the apparatus or system receiving the at least one command or being actuated, 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.
4. The method of claim 1 , wherein the step of obtaining the equation with the cost function further comprises processing, by the computing apparatus or the computing system, the cost function equation so as to derive the integer programming formulation thereof if the cost function equation is not in the integer programming formulation.
5. The method of claim 1 , wherein the integer programming formulation of the cost function equation is: H=Σ <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 .
6. The method of claim 1 , wherein the converting step further comprises: converting, by the computing apparatus or the computing system, the integer programming formulation of the cost function equation into a sums of terms formulation and converting, by the computing apparatus or the computing system, 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.
7. The method of claim 1 , 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.
8. The method of claim 1 , wherein the Max-Clique problem obtained 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.
9. The method of claim 1 , wherein the light output data is processed, by the computing apparatus or the computing system, to find a maximum-size clique of a graph of the Max-Clique problem, and the method comprises processing ( 154 ), by the computing apparatus or the computing system, the maximum-size clique in order to find the values of the two or more binary variables of the cost function.
10. The method of claim 1 , wherein the step of obtaining the equation with the cost function further comprises at least one of:
digitizing, by the computing apparatus or the computing system, 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
processing, by the computing apparatus or the computing system, the cost function to reduce the polynomials of the one or more binary variables to quadratic terms.
11. The method of claim 1 , 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, control of logistics, control of scheduling, routing, portfolio optimization, financial equilibrium, training of a machine learning algorithm, and factoring large numbers.
12. A system comprising:
a Gaussian Boson Sampling, GBS, quantum device, and
an apparatus comprising:
at least one processor;
at least one memory comprising computer program code for one or more programs;
the at least one processor, the at least one memory, and the computer program code configured to cause the apparatus to at least carry out the following:
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 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; and
providing the Max-Clique problem to a Gaussian Boson Sampling, GBS, quantum device;
the GBS quantum device being configured to:
receive, as input, quantum state of light resulting from conversion of the Max-Clique problem into quantum state of light; and
output light resulting from the quantum state of light received as input by the GBS quantum device, the light output having a distribution corresponding to dense subgraphs in a graph of the Max-Clique problem; and
the at least one processor, the at least one memory, and the computer program code configured to cause the apparatus to at least carry out the following:
receiving light output data resulting from transformation of the light output into light output data; and
processing the light output data by finding one or more cliques of the subgraphs so as to find values of the two or more binary variables of the cost function; the one or more cliques having the values of the two or more binary variables of the cost function.
13. The tem of claim 12 , wherein the at least one processor, the at least one memory, and the computer program code are configured to cause the apparatus to further carry out: providing 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.
14. The system of claim 12 , wherein the at least one processor, the at least one memory, and the computer program code are configured to cause the apparatus to further carry out: processing the cost function equation so as to derive the integer programming formulation thereof if the cost function equation is not in the integer programming formulation.
15. The system of claim 12 , wherein the integer programming formulation of the cost function equation is: H=Σ <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 .
16. The system of claim 12 , wherein the at least one processor, the at least one memory, and the computer program code are configured to cause the apparatus to carry out the conversion by further: converting the integer programming formulation of the cost function equation into a sums of terms formulation and converting 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.
17. The system of claim 12 , 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.
18. The system of claim 12 , 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, control of logistics, control of scheduling, routing, portfolio optimization, financial equilibrium, training of a machine learning algorithm, and factoring large numbers.
19. A system comprising:
a Gaussian Boson Sampling, GBS, quantum device, and
a non-transitory computer-readable medium encoded with instructions that, when executed by at least one processor or hardware, make an apparatus to at least perform the following:
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 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; and
providing the Max-Clique problem to a Gaussian Boson Sampling, GBS, quantum device;
the GBS quantum device being configured to:
receive, as input, quantum state of light resulting from conversion of the Max-Clique problem into quantum state of light; and
output light resulting from the quantum state of light received as input by the GBS quantum device, the light output having a distribution corresponding to dense subgraphs in a graph of the Max-Clique problem; and
the non-transitory computer-readable medium being encoded with instructions that, when executed by at least one processor or hardware, make an apparatus to at least perform the following:
receiving light output data, the light output data resulting from transformation of the light output by the GBS quantum device into light output data; and
processing the light output data by finding one or more cliques of the subgraphs so as to find values of the two or more binary variables of the cost function; the one or more cliques having the values of the two or more binary variables of the cost function.