as) United States
`a2) Patent Application Publication 10) Pub. No.: US 2023/0419155 Al
`(43) Pub. Date: Dec. 28, 2023
`
`You et al.
`
`US 20230419155A1
`
`(54)
`
`QUANTUM COMPUTING-ENHANCED
`SYSTEMS AND METHODS FOR
`LARGE-SCALE CONSTRAINED
`OPTIMIZATION
`
`(71)
`
`Applicant: Cornell University, Ithaca, NY (US)
`
`(72)
`
`Inventors: Fengqi You, Ithaca, NY (US); Akshay
`Ajagekar, Ithaca, NY (US)
`
`(21)
`
`Appl. No.: 18/367,155
`
`(22)
`
`Filed:
`
`Sep. 12, 2023
`
`Related U.S. Application Data
`
`(63)
`
`Continuation of application No. 17/767,247, filed on
`Apr. 7, 2022, now Pat. No. 11,769,070,
`filed as
`application No. PCT/US2020/055019 on Oct. 9,
`2020.
`
`(60)
`
`Provisional application No. 62/913,146,filed on Oct.
`9, 2019, provisional application No. 63/016,076, filed
`
`on Apr. 27, 2020, provisional application No. 63/018,
`737, filed on May 1, 2020.
`Publication Classification
`
`(51)
`
`Int. CL
`GO6N 10/60
`G06Q 10/04
`(52) U.S. Cl
`CPC veeesscceen GO6N 10/60 (2022.01); G06Q 10/04
`(2013.01)
`
`(2006.01)
`(2006.01)
`
`ABSTRACT
`(57)
`Technologies for a quantum/classical hybrid approach to
`solving optimization problemsare disclosed.In the illustra-
`tive embodiment, an optimization problem is decomposed
`into two sub-problems. Thefirst sub-problem is solved on a
`classical computer, and a result from the first sub-problem is
`provided to a quantum computer. The quantum computer
`then solves the second sub-problem based on the result of
`the first sub-problem from the classical computer. The
`quantum computer can then provide a result to the classical
`computer to re-solve the first problem. The iterative calcu-
`lation is continued until an end condition is met.
`
`104
`
`QUANTUM COMPUTER
`
`+o
`304
`3025
`6
`|
`]
`[CLASSICAL]
`SUANTUM
`
`PROCESSOR(S)|LPROCESSOR(S)| | MEMORY
`308
`
`CIRCUITRY PERIPHERAL I 314
`
`/O
`SUBSYSTEM
`
`'_ DEVICES [7
`
`310
`
`342
`
`DATA
`STORAGE
`
`COMM.
`
`1
`
`Exhibit 1032
`Crusoe v. Upstream
`PGR2023-00039
`
`Exhibit 1032
`Crusoe v. Upstream
`PGR2023-00039
`
`1
`
`

`

`Patent Application Publication
`
`Dec. 28,2023 Sheet 1 of 13
`
`US 2023/0419155 Al
`
`102
`
`CLASSICAL
`COMPUTER
`
`\S
`
`100
`
`
`
`QUANTUM
`COMPUTER
`
`104
`
`FIG. 1
`
`2
`
`

`

`Patent Application Publication
`
`Dec. 28,2023 Sheet 2 of 13
`
`US 2023/0419155 Al
`
`CLASSICAL COMPUTER
`
`PROCESSOR(S)
`
`MEMORY
`
`/O
`SUBSYSTEM
`
`DATA
`"PERIPHERAL 1 212
`
`STORAGE DEVICES_[*
`
`CIRCUITRY
`CIRCUITRY
`
`PROCESSORIS
`8
`
`OMM.
`
`FIG. 2
`
`QUANTUM COMPUTER
`
`PROCESSOR(S)
`
`MEMORY
`
`vO
`SUBSYSTEM
`
`|stonAGE._|,PERIPHERAL 1 314
`STORAGE
`DEVICES
`rc
`
`JOMM.
`
`FIG. 3
`
`3
`
`

`

`Patent Application Publication
`
`Dec. 28,2023 Sheet 3 of 13
`
`US 2023/0419155 Al
`
`400
`
`402
`
`CLASSICAL COMPUTER
`
`OPTIMIZATION PROBLEM
`DECOMPOSER
`
`SOLVER
`
`FIG. 4
`
`
`COMMUNICATION ENGINE CLASSICAL SUB-PROBLEM
`
`
`ae
`
`104
`
`QUANTUM COMPUTER
`
` SUB-PROBLEM SOLVER
`
`COMMUNICATION ENGINE
`
`FIG. 5
`
`4
`
`

`

`Patent Application Publication
`
`Dec. 28,2023 Sheet 4 of 13
`
`US 2023/0419155 Al
`
`DETERMINE OPTIMIZATION PROBLEM
`O04 me oe me me me eee ee eee ~
`“DETERMINE MILP OPTIMIZATION
`PROBLEM
`
`UT
`i
`
`DETERMINE MIQP OPTIMIZATION
`PROBLEM
`7
`609Lee2.
`I
`“DETERMINE IQEP OPTIMIZATION
`i
`PROBLEM
`Kee ence isons
`sneer sees sent sete nem wees enh Senet seen cube enn etem wenn eee
`
`602
`
`600
`u
`
`610
`
`PROBLEM
`
`DECOMPOSE OPTIMIZATION PROBLEM INTO
`FIRST SUB-PROBLEM FOR A CLASSICAL
`COMPUTER AND SECOND SUB-PROBLEM
`FOR A QUANTUM COMPUTER
`
`612
`
`DETERMINE FIRST SET OF VARIABLES
`FOR FIRST SUB- PROBLEM
`
`DETERMINE SECOND SET OF
`VARIABLES FOR SECOND SUB-
`
`616
`
`INITIALIZE PARAMETERS FOR THE FIRST
`SUB-PROBLEM AND FOR THE SECOND SUB-
`
`
`
` PROBLEM
`
`TO
`FIG, 7
`
`FIG. 6
`
`5
`
`

`

`Patent Application Publication
`
`Dec. 28,2023 Sheet 5 of 13
`
`US 2023/0419155 Al
`
`FROM
`FIG. 6
`
`
`EXECUTE A FIRST ALGORITHM FOR THE
`FIRST SUB-PROBLEM TO DETERMINE
`CURRENT RESULT OF THE FIRST ALGORITHM
`ON THE CLASSICAL COMPUTER
`
`
`
`SEND THE CURRENT RESULT OF THE FIRST
`ALGORITHM TO THE QUANTUM PROCESSOR
`
`EXEGUTE A SECOND ALGORITHM FOR THE
`SECOND SUB-PROBLEM TO DETERMINE A
`CURRENT RESULT OF THE SECOND
`ALGORITHM ON THE QUANTUM PROCESSOR
`
`SEND THE CURRENT RESULT OF THE
`SECOND ALGORITHM TO THE CLASSICAL
`COMPUTER
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`600
`
`618
`
`620
`
`622
`
`624
`
`626
`
`
`
`DETERMINE WHETHER END CONDITION MET
`
`
`END CONDITION MET?
`
`YES
`
`630
`
`RETURN VARIABLE VALUES
`
`FIG. 7
`
`6
`
`

`

`Patent Application Publication
`
`Dec. 28,2023 Sheet 6 of 13
`
`US 2023/0419155 Al
`
`oi
`
`808
`NG
`SOLUTION
`EXISTS
`
`804
`
`810
`
`B12
`
`816
`
`818
`
`DECOMPOSE MILP OPTIMIZATION PROBLEM
`
`INTO RELAXED MILP PROBLEM AND QUBO
`PROBLEM
`
`SOLVE RELAXED MILP PROBLEM
`
`806
`MILP PROBLEM FEASIBLE?
`
`
`
`
`
`SEND PARTIAL OPTIMAL SOLUTION TO
`QUANTUM PROCESSOR
`
`
`
`FEASIBLE
`YES
`SCHEDULE FOUND?
`
`
`
`
`
`SOLVE QUBO PROBLEM ON QUANTUM
`
`
`PROCESSOR BASED ON PARTIAL OPTIMAL
`
`SOUTION
`
`
`
`
`
`ADD INTEGER CUTS BASED ON MACHINES
`FOR WHILE NO FEASIBLE SCHEDULE FOUND
`
`
`
`RETURN OPTIMAL SOLUTION
`
`FIG. 8
`
`7
`
`

`

`Patent Application Publication
`
`Dec. 28,2023 Sheet 7 of 13
`
`US 2023/0419155 Al
`
`900
`y
`
`902
`
`904
`
`908
`NO
`SOLUTION
`EXISTS
`
`DECOMPOSE MIOP OPTIMIZATION PROBLEM
`INTO DUAL LINEAR PROGRAM AND QUBO
`PROBLEM
`
`
`
`FROM
`FIG. 10
`
`SOLVE DUAL LINEAR PROGRAM
`
`
`
`DUAL LP FEASIBLE?
`
`YES
`
`NO
`
`970
`
`
`
`NEW UPPER BOUND?
`
`
`
`UPDATE UPPER BOUND
`
`914
`
`SEND PARTIAL OPTIMAL SOLUTION TO
`QUANTUM COMPUTER
`
`TO
`FIG. 10
`
`FIG. 9
`
`8
`
`

`

`Patent Application Publication
`
`Dec. 28,2023 Sheet 8 of 13
`
`US 2023/0419155 Al
`
`900
`
`FROM
`FIG. 9
`
`
`
`SOLVE QUBO PROBLEM ON QUANTUM
`
`
`COMPUTER BASED ON PARTIAL OPTIMAL
`
`SOUTION
`
`916
`
`918
`
`UPDATE LOWER BOUND
`
`YES
`
`920
`
`LOWER BOUND 2 UPPER
`BOUND?
`NO
`
`922
`
`COMPUTER
`
`SEND ASSIGNMENT TO CLASSICAL
`
`TQ
`FIG. 9
`
`924
`
`RETURN OPTIMAL SOLUTION
`
`FIG. 10
`
`9
`
`

`

`Patent Application Publication
`
`Dec. 28,2023 Sheet 9 of 13
`
`US 2023/0419155 Al
`
`14100
`
`iv
`
`1102
`
`DECOMPOSE IOFP OPTIMIZATION PROBLEM
`INTO HYBRID QUBO-IQFP PARAMETRIC
`PROBLEM
`
`
`
`1104
`
`SOLVE QUBO PROBLEM ON QUANTUM
`COMPUTER
`
`1108
`NS
`SOLUTION
`EXISTS
`
`
`1106
`
`
`FEASIBLE SOLUTION FOUND?
`
`YES
`
`1110
`
`1112
`
`1114
`
`1116
`
`1120
`
`SEND PARTIAL OPTIMAL SOLUTION TO
`
`CLASSICAL COMPUTER
`FRACTIONAL OBJECTIVE FUNCTION VALUE
`
`UPDATE PARAMETER CORRESPONDING TO
`
`UPDATE PENALTY PARAMETER
`
`DETERMINE WHETHER END CONDITION MET
`
`
`1118
` YES
`
`END CONDITION MET?
`
`NO
`
`RETURN SOLUTION
`
`FIG. 14
`
`10
`
`10
`
`

`

`Patent Application Publication
`
`Dec. 28, 2023 Sheet 10 of 13
`
`US 2023/0419155 Al
`
`WOLNWWSHLVA
`
`TaqOW
`
`UVNOTION
`
`YNVEVIVG
`
`00¢}
`
`ws
`
`
`
`4,¥aNdWOoWoissv10‘\
`
`OL2}
`
`
`
`W3180dSZMVILINI
`
`¥OSSIOONd
`
`NOLLVINWYOITY
`
`C02!
`
`8021
`
`>*
`
`
`
`WAISASENSTWOISS¥TO.
`
`AYOWSN
`
`WALNYAD
`
`Y3AI0S
`
`eee
`
`
`
`YALNdWODWALNYAD
`
`
`
`JUNLONYLSYVINOFION
`
`ccch
`
`
`
`WILNALOdLS¥1
`
`SSNTWAADUSNA
`
`11
`
`
`
`
`
`atoPeeweemeeeeesemesnenesseaesPeonmesersersesesae,
`
`
`
`WALSASENSWALNYNO
`
`
`
`SLINSIYGANIVLEO
`
`11
`
`
`
`
`
`
`

`

`Patent Appl
`
`icat
`
`ion
`
`Publ
`
`icat
`
`ion
`
`Dec. 28, 2023 Sheet 11 of 13
`
`US 2023/0419155 Al
`
`Sgor
`
`
`
`$$d00udVIVG80f
`
`
`
`VLVGJNIHOVA
`
`cSel
`
`
`
` \V1¥0Y3IdHOO0Et
`
` SSNIHOWAXtOLEL
`
`eeWA180UdSZIVILINI
`
`
`
`aneyaganL
`
`inoesweeneseteinsweeesscoinmselhaeseeceestesesseieseetnsveeeweed
`
`(yNOLLWHALI)
`
`
`
`
`
`ACOWIWGAXV73ySATOS[~80E)
`
`
`
`
`
`HOIHMSOdSSNIHOWWASLLNSGH|:
`
`
`
`
`‘GNNO438LONG1N0OSTINGZHOSITIgorssneLopJpaiiosaicisesssa
`
`
`PATOReReMORNEOUOREMORROESHERNOTEAERATTEEHOETENEDTAEUSPENSEEAHAOTROUAHERNOTSATRATEROEEASOD
`
`‘
`
`
`
`JINGSHOSWHLLdO
`
`JONSNDASONY
`
`TACO30ONISNJINGSHOSSNINYALS
`
`qbean
`LONYLSVYINI
`
`anova
`
`WALNYAD
`
`YSA10S
`
`zeBhet
`
`“.MALNdNOD WHINY
`
`b+=)LS
`
`
`
`‘SLNDUSOSLNISALLOSdSAYCCV2
`TWWILdOWiLeVdvies
`
`
`
`
`
`FoOmeaORHeEROGEROTHEEREEEREEHOEEMEERDEERHSERREEHOEENOERDETEEEHOLEREEDRSEDOREDHEEHOEEDETERSREETHERAEDELOSS
`
`
`NOLLMOSuel
`
`YALAdNOO WIISSV1D
`eessoves
`ene e ne eresevesessene®
`
`12
`
`12
`
`
`
`
`
`
`
`
`

`

`PeerSeSVereereUCCESCCUreecreecesreereerecrrerrercrereersteccerseercereerrrreersceteeteree
`
`
`
`
`
`
`NOLLYAMOINIBYINTISOANIHOWASvddh|On
`
`{RPRe)LROR]
`einineisinwaitewinewineeinenincoinwinewine
`
`
`INVIdONIEALOVIANYN
`NOUMOSWLd/2ftSoNOIOSPoo
`SINSNNOISSYNaWOHdT|gp,|b=-------~—4:
`
`b+L=18(LNOLLVHA)ifBB|:
`ooh)CDyon
`SUSLAWVedpip
`
`
`EETINEbeveeuaeesveceeuseaee
`
`GyWOsGNNONNI}YSAT0Sal:_FWOISSYTD1=LEio<i: ioZI;WIIGONd\WedPa
`ReeeaeRemDEOREEEREERETOEEDHEUREERESHEEREETONDHEUEEEREEDEEHS,
`
`
`14Bl
`
`
`
`
`
`
`
`(soxxxxx!{xxxxxx!
`
`00+}
`
`Patent Application Publication
`
`Dec. 28, 2023 Sheet 12 of 13
`
`US 2023/0419155 Al
`
`weeereee
`
`aot eee
`steesee cag
`-” QUANTUM COMPUTER™.
`
`
`
`
`
`
`
`ennwanewanewanesning,gomnnnewanneing,anneanne.
`
`
`
`WAISASENSWNLNYND
`
`vlSis
`
`
`
`ANIHOVINSNINYSL30
`
`SINSANOISSY
`
`dal$90SNISN
`
`
`
`uaddfAivddn
`
`GNNOE
`
`SSNIHOWAGNYSLuVd
`
`
`
`TONLNODSZ/WLLINI
`
`13
`
`13
`
`
`
`
`
`
`
`

`

`Patent Application Publication
`
`Dec. 28, 2023 Sheet 13 of 13
`
`US 2023/0419155 Al
`
`JIOIHSA
`
`S3LNO
`
`WAlLdO
`
`NOLLMIOS
`
`gish:
`
`
`
`TOYLNOSTOXLNOD
`
`SATOIHSA
`
`SuaLSWVuYd
`
`
`
`
`
`
`
`
`
`
`
`oSPPReeeeRRPEROCROCECCOSECRCCCCCOVSSOCEUSLOVESECOSECCCCCEVUSSSVESVCESSSECreSCrVerrr!
`
`
`
`1Od30JTOIHSAoS
`
`90S}v0S!
`
`FIOIHSAFTOIHSArSYOLVALOY,
`
`SYOLWALOY20g}
`
`YAWOLSNO
`
`vv00S!
`
`SZIILIN|
`
`SUSLSAVed
`
`
`
`WALSASNSWALNYND
`
`“aivaanYsATOS
`
`
`
`TEQOW90ONISNSNOLLATIOS
`
`
`
`
`
`TWAILdOWILYVdSNINYSLSCLakSUNLONMESWHSNI
`
`WALNYNO
`
`805)OVS}
`
`YOSSTOOUd
`
`AMOWSIN
`
`
`
`YALAdNOOWOISSVTD
`
`
`
`POROaREOOHERCOEEREOOHOREOAOPEROEHHAETECOHENERDOEEEEPEEREMOTEHEEHOMDOEDHEOREOOHEDGED
`
`
`
`WALSASENSTVOISSV1)
`
`SbOld
`
`
`
`NOLLITIOSTWWLLdOTWLLYVdONISN
`
`
`
`
`
`
`
`TWNOLLOWadTWNIDIHOSLO
`
`
`
`
`
`SANTANOLLONNSSALLOSP8O
`
`14
`
`»* MELNEWOO WALNWNO
`
`14
`
`
`
`
`
`
`
`
`

`

`US 2023/0419155 Al
`
`Dec. 28, 2023
`
`QUANTUM COMPUTING-ENHANCED
`SYSTEMS AND METHODS FOR
`LARGE-SCALE CONSTRAINED
`OPTIMIZATION
`
`CROSS-REFERENCE TO RELATED
`APPLICATIONS
`
`sub-problem to be solved bya first algorithm on the classical
`computer and a second sub-problem to be solved by a
`second algorithm on a quantum processor, wherein thefirst
`sub-problem hasa first set of one or more variables and the
`second sub-problem has a second set of one or more
`variables, wherein each variable of the second set of one or
`more variablesis different from each variable of thefirst set
`
`[0001] The present application is a continuation of U.S.
`patent application Ser. No. 17/767,247 by Fengqi You and
`Ashkay Ajagekar, filed Apr. 7, 2022 and entitled “QUAN-
`TUM COMPUTING BASED HYBRID SOLUTION
`STRATEGIES FOR LARGE-SCALE DISCRETE-CON-
`TINUOUS OPTIMIZATION PROBLEMS,” which is a
`national stage of PCT International Application No. PCT/
`US2020/055019 by Fengqi You and Ashkay Ajagekar, filed
`on Oct. 9, 2020, which claimsthe benefit of U.S. Provisional
`Patent Application No. 62/913,146 by Fengqi You and
`Akshay Ajagekar, filed Oct. 9, 2019, and entitled “QUAN-
`TUM COMPUTING BASED HYBRID SOLUTION
`STRATEGIES FOR LARGE-SCALE DISCRETE-CON-
`TINUOUS OPTIMIZATION PROBLEMS,” US. Provi-
`sional Patent Application No. 63/016,076 by Akshay Ajag-
`ekar and Fengqi You, filed Apr. 27, 2020, and entitled
`“QUANTUM COMPUTING BASED HYBRID SOLU-
`TION STRATEGIES FOR LARGE-SCALE DISCRETE-
`CONTINUOUS OPTIMIZATION PROBLEMS,”and USS.
`Provisional Patent Application No. 63/018,737 by Fengqi
`You and Akshay Ajagekar, filed May 1, 2020, and entitled
`“QUANTUM COMPUTING BASED HYBRID SOLU-
`TION STRATEGIES FOR LARGE-SCALE DISCRETE-
`CONTINUOUS OPTIMIZATION PROBLEMS.” The
`
`entirety of each of these applications is incorporated herein
`by reference.
`
`STATEMENT OF GOVERNMENT SUPPORT
`
`[0002] The Government has rights in this invention pur-
`suant to User Agreement NP-11-0404 between Cornell Uni-
`versity and UT-Battelle, LLC, which manages and operates
`Oak Ridge National Laboratory for the US Department of
`Energy.
`
`BACKGROUND
`
`Solving large-scale optimization problems has
`[0003]
`practical applications, such as protein folding, vehicle rout-
`ing, planning, scheduling, supply chain management, etc.
`However, classical computers cannot always solve large-
`scale optimization problems on a practical timescale. Quan-
`tum computing promises faster and better solutionsto large-
`scale optimization problems, but
`the current
`scale of
`quantum computers limits the feasibility of solving large-
`scale problems directly on quantum computers.
`
`SUMMARY
`
`of one or morevariables; (11) executing thefirst algorithm for
`the first sub-problem with use of the classical computer to
`determine a current result of thefirst algorithm; (iii) execut-
`ing the second algorithm for the second sub-problem with
`use of the quantum processor based on the current result of
`the first algorithm to determine a current result of the second
`algorithm; (iv) executing the first algorithm for the first
`sub-problem with use of the classical computer and with use
`of the current result of the second algorithm and optionally
`with use of the current result of the first algorithm to
`determine the current result of the first algorithm;
`(v)
`repeating steps (iii) and (iv) one or more times; (vi) stop the
`repeating steps until a preset convergencecriteria is reached.
`In other embodiments, the step (i) is the same as above and
`the steps (11)-(vi) are: (11) executingthefirst algorithm for the
`first sub-problem with use of the quantum processor to
`determine a current result of thefirst algorithm; (iii) execut-
`ing the second algorithm for the second sub-problem with
`use of the classical computer based on the current result of
`the first algorithm to determine a current result of the second
`algorithm; (iv) executing the first algorithm for the first
`sub-problem with use of the quantum processor and with use
`of the current result of the second algorithm and optionally
`with use of the current result of the first algorithm to
`determine an updated currentresult ofthe first algorithm;(v)
`executing the second algorithm for the second sub-problem
`with use of the classical computer and with use of the current
`result of the first algorithm and optionally with use of the
`current result of the second algorithm to determine an
`updated currentresult of the second algorithm; (vi) repeating
`steps (iv) and (v) one or more times; (vii) stop the repeating
`steps until a preset convergencecriteria is reached. In some
`embodiments, the preset convergencecriteria is determined
`by at least a portion of the current result (e.g., the current
`result, the updated current result after current updating, or
`the latest current result for the current result in the latest
`iteration) of the first algorithm andat least a portion of the
`current result (e.g., the current result, the updated current
`result after current updating, or the latest current result for
`the current result
`in the latest
`iteration) of the second
`algorithm, for example, an upper bound (or a lower bound)
`of an objective determined by the current result of the first
`algorithm converges to a lower bound(or an upper bound)
`of the objective determined by the current result of the
`second algorithm. In some embodiments, the preset conver-
`gence criteria is determined by a first data value derived
`from the current result of the first algorithm and a second
`data value derived from the current result of the second
`algorithm (in the sameiteration), wherein the first data value
`converges to the second data value. In some embodiments,
`a global optimization result or a global optimal solution of
`the optimization problem and/or the original optimization
`problem can be achieved by using and achieving the above
`convergencecriteria. In other embodiments, the preset con-
`vergencecriteria could be determinedbyat least a portion of
`the current results of the latest two or three iterations of the
`
`[0004] According to one aspect of the disclosure, a
`method for solving optimization problems comprises (i)
`initializing, by a classical computer, a plurality of param-
`eters of an optimization problem comprising an original
`objective and optionally an original set of constraints,
`wherein the optimization problem is decomposed into at
`least
`two sub-problems manually or automatically by a
`pre-processing unit comprising a decomposer, optionally a
`classifier and optionally a library stored in a memory,
`wherein the optimization problem is decomposedintoafirst first algorithm,at least a portion of the current results of the
`
`15
`
`15
`
`

`

`US 2023/0419155 Al
`
`Dec. 28, 2023
`
`latest two or three iterations of the second algorithm,atleast
`a portion of the combinedor processed current results of the
`optimization problem in the latest two or three iterations, or
`any combination thereof. If the convergence criteria is
`determined by the latest two or three iterations, such as no
`improvementof results in the latest two or three iterations,
`at least a local optimization result would be achieved but a
`global optimization result cannot be guaranteed.
`[0005]
`In some embodiments,
`the first sub-problem is
`selected from a mixed-integer linear programming (MILP)
`problem,
`a relaxed mixed-integer
`linear programming
`(MILP) problem, a mixed-integer non-linear programming
`(MINLP) problem,a linear programming (LP), a non-linear
`programming (NLP) problem, a Binary Quadratic program-
`ming (BQP) problem, a Mixed-integer Quadratic Program-
`ming (MIQP)problem, or a Mixed-integer Fractional Pro-
`gramming (MIFP) problem; and the second problem is a
`quadratic unconstrained binary optimization (QUBO) prob-
`lem or an optimization problem solvable by a quantum
`computer or quantum processor directly and/or indepen-
`dently. In some embodiments, thefirst algorithm is selected
`from algorithms or optimization solvers for a mixed-integer
`linear programming (MILP) problem, a relaxed mixed-
`integer linear programming (MILP) problem, a mixed-inte-
`ger non-linear programming (MINLP) problem, a linear
`programming (LP), a non-linear programming (NLP) prob-
`lem, a binary quadratic programming (BQP) problem, a
`mixed-integer quadratic programming (MIQP) problem, or
`a mixed-integer fractional programming (MIFP) problem;
`and the second algorithm is selected from algorithms for a
`quadratic unconstrained binary optimization (QUBO) prob-
`lem or for an optimization problem solvable by a quantum
`computer or quantum processor directly and/or indepen-
`dently.
`[0006] The objective of the optimization problem is to
`minimize or maximize a function comprising a set of
`variables and a set of parameters. In some embodiments,
`objective of the optimization problem is selected but not
`limited from minimizing potential energy, minimizing cost,
`minimizing fees, minimizing resources, maximizing ratio of
`income to cost, minimizing or maximizing a summation, a
`fraction, a multiplication or the combination thereof of
`certain combinations of variables and parameters matching
`an optimization target for a physical system. Solving the
`optimization problem can be used to figure out the best
`arrangementof the physical system, the best structure or the
`most feasible structure of the physical system,
`the best
`design of the physical system, the best operations of the
`physical system, and/or the best results the physical system
`can achieve.
`
`In some embodiments, the optimization problem is
`[0007]
`a cellular manufacturing problem. A cell manufacture sys-
`tem comprises multiple manufacturing cells that perform
`multiple manufacturing processes. In order to achieve an
`optimal design of the cell manufacture system for a goal
`such as minimizing manufacturing costs or maximizing
`manufacturing efficiency, a set of variables and a set of
`parameters for all the manufacturing cells or choices of the
`manufacturing cells are provided and an optimization model
`for the manufacturing cells are also provided. The cellular
`manufacturing optimization problem can be solved by the
`QC-classical computer hybrid system.
`[0008]
`In some embodiments, the optimization problem is
`an integer quadratic fractional program (IQFP) problem,
`
`wherein the first algorithm is an operation for assigning a
`value to a parameter and the second algorithm is solving a
`quadratic unconstrained binary optimization (QUBO) prob-
`lem based on the parameter.
`[0009]
`In some embodiments, the optimization problem is
`a vehicle routing problem. The vehicle routing system
`comprises a map comprising feasible travel routes and one
`or a plurality of vehicles, wherein the vehicles could be
`selected from cars, trucks, buses, airplanes, ships, autono-
`mous vehicles, and/or the combination thereof. A set of
`variables and a set of parameters are provided wherein at
`least a portion of the parameters could be determined by the
`properties of the map, properties of the vehicles, properties
`of current status of the system or material utilized in the
`system (e.g. gasoline price), dynamic updates of the systems
`and/or the combination thereof. The optimization problem
`can be solved by the hybrid quantum computer-classical
`computer hybrid system. The optimal results of the optimi-
`zation problem and/or instructions to achieve the optimal
`results can be transmitted back to a central management or
`coordination unit of the vehicle control or dispatch system.
`Based on the optimal results, the central management or
`coordination unit can send out instructions to controls the
`
`operations of the vehicles.
`[0010]
`In some embodiments, each variable of the second
`set of one or more variables is a binary variable. In some
`embodiments, the variables of the first set of one or more
`variables are selected from continuous variables,
`integer
`variables, binary variables, and/or the combination thereof.
`[0011]
`Insome embodiments, repeating steps (111) and (av)
`one or more times comprises repeating steps (iii) and (av)
`one or more times until an optimal solution of the optimi-
`zation problem is determined.
`the method may further
`[0012]
`In some embodiments,
`comprise decomposing the optimization problem into the
`first sub-problem and the second sub-problem.
`[0013] According to one aspect of the disclosure, a system
`for solving optimization problems comprises a classical
`computer comprising a classical processor and one or more
`non-transitory storage media comprising a plurality of
`instructions that, when executed, cause the classical com-
`puter to initialize a plurality of parameters of an optimiza-
`tion problem, wherein the optimization problem are decom-
`posedto a first sub-problem to be solved byfirst algorithm
`on the classical computer and a second sub-problem to be
`solved by a second algorithm on a quantum processor,
`wherein the first sub-problem hasa first set of one or more
`variables and the second sub-problem has a second set of
`one or more variables, wherein at least one variable of the
`second set of one or more variables is different from the
`variables of the first set of one or more variables and/or
`wherein at least one variable of thefirst set of one or more
`variables is different from the variables of the second set of
`
`one or more variables; execute the first algorithm forthefirst
`sub-problem with use of the classical computer to determine
`a current result of the first algorithm; further comprising a
`quantum processor to execute the second algorithm for the
`second sub-problem with use of the quantum processor
`based on the currentresult ofthe first algorithm to determine
`a current result of the second algorithm, wherein the plu-
`rality of instructions further cause the classical computer to
`execute the first algorithm for the first sub-problem with use
`of the classical computer and with use of the current result
`of the second algorithm to determine an updated current
`
`16
`
`16
`
`

`

`US 2023/0419155 Al
`
`Dec. 28, 2023
`
`result of the first algorithm, wherein the classical computer
`and the quantum processor are configured to repeat the
`execution ofthefirst algorithm based on the current result of
`the second algorithm and repeat execution of the second
`algorithm based on the current result of thefirst algorithm,
`respectively, one or more times.
`
`In some embodiments, the first algorithm is for
`[0014]
`solving a relaxed mixed-integer linear programming (MILP)
`problem andthe second algorithm is for solving a quadratic
`unconstrained binary optimization (QUBO)problem.
`
`In some embodiments, the optimization problem is
`[0015]
`a scheduling problem, a planning problem,or a supply chain
`optimization problem. In some embodiments, the optimiza-
`tion problem is a job-shop scheduling or planning problem
`for enterprise resource planning (ERP) or manufacturing
`execution system (MES) or scheduling over time with a
`limited scope. A physical system comprises a plurality of
`tasks, a plurality of resources wherein each resources com-
`prises at least one relevant costs and related tasks, and at
`least one measure for the performance of the physical
`system, wherein the physical system is but not limited to an
`enterprise system, a manufacturing system, a supply chain
`system, a production system, etc. An optimization problem
`is used to determine the allocation of the resources to the
`
`tasks over a time period in a way that a predefined perfor-
`mance measure is optimized. The optimization problem can
`be solved by the hybrid quantum-classical computing sys-
`tem. Based on the optimalresults of the optimization prob-
`lem, an instruction or a guidanceis generated to allocate the
`provided resources to the provided tasks or a series of
`instructions, guidance, plan, or decisions are generated to
`allocate the provided resources to the provided tasks over
`time.
`
`In some embodiments, the first algorithm is a dual
`[0016]
`linear programming (LP) problem andthe second algorithm
`is a quadratic unconstrained binary optimization (QUBO)
`problem.
`
`In some embodiments, the optimization problem is
`[0017]
`a molecular design or a product design problem. In some
`embodiments, the optimization problem is a molecular con-
`formation design problems, which is used in the areas of
`drug design, protein folding, chemical design, chemistry,
`and biotechnology. A molecule or a design of molecule
`comprises a plurality of atom elements or functional group
`elements and a plurality of bonds between or among two or
`more of the atom elements or functional group elements. An
`optimization problem is used to determine an optimal mea-
`sure of the molecule or the design of molecule such as the
`minimal potential energy, and the corresponding optimal
`structure of the molecule under the optimal measure (e.g.
`minimal potential energy) comprising the optimized atom
`elements or optimized functional group elements and the
`optimized bonds between or among two or more of the
`optimal atom elements or optimal functional group ele-
`ments. The optimization problem can be solved by the
`QC-classical computer hybrid system.
`In some embodi-
`ments,
`the application further comprises synthesizing at
`least one molecule based on the optimal results of the
`optimization problem calculated by the QC-classical com-
`puter hybrid system. In some embodiments, the molecule is
`a protein, a drug, a therapeutic agent, a small molecule, a
`polymer, an enzyme, a receptor of a target cell or target
`molecule, or an inhibitor of another molecule.
`
`In accordance with the present disclosure, a hybrid
`[0018]
`quantum computer-classical computer (QC-CC) based com-
`putation system, comprising: a quantum computerpart (e.g.
`one or more quantum computers, or a quantum computer
`subsystem of a hybrid system) comprises a quantum pro-
`cessor configured to solve at least one type of computation
`problem (e.g. one type of optimization problem, or one type
`of computation problem that is convertible or can be refor-
`mulated to an optimization problem) and a communication
`engine configured to control a communication circuitry to
`send and/or receive data between the quantum computerpart
`and a classical computer part (e.g. one or more classical
`computers) optionally via a local or remote network; and a
`classical computerpart (e.g. one or more classical comput-
`ers, or a classical computer subsystem of a hybrid system)
`comprises at least one classical processor, a communication
`engine, and at least one non-transitory computer readable
`medium to store at least one computation solver, and option-
`ally a computation problem decomposer, wherein the com-
`munication engine is configured to send and/or receive data
`between the classical computer part and the quantum com-
`puter part and optionally between the local classical com-
`puter and other remote classical computers, wherein the
`classical computation solver comprises an optimization
`problem solver configured to solve at least one type of
`optimization problem, wherein a computation problem
`decomposer comprises an optimization problem decom-
`poser configured to decompose an original (large scale)
`optimization problem into at
`least
`two sub-problems,
`wherein at least one of the sub-problems(e.g. a first sub-
`problem) is configured to be solvable by a quantum com-
`puter; wherein the quantum computer solves at least one of
`the sub-problems by the quantum processor using a first
`algorithm and send a current result of the first algorithm to
`the classical computer via the communication engine of the
`quantum computer; wherein the classical computer solves
`the rest of the sub-problems(e.g. a second sub-problem) by
`the classical computation solver using a second algorithm to
`get a current result of the second algorithm;andthe classical
`computer further generates a computation result of the
`original computation problem (e.g. an optimal result of the
`original optimization problem) based on the current result of
`the first algorithm and the current result of the second
`algorithm. In some embodiments, the hybrid QC-CC based
`computation system solves a computation problem in more
`than one iterations (e.g. N+1 iterations), such that in the
`above hybrid QC-CC based computation system, the quan-
`tum computer further receives data based on or derived from
`the current result of the second algorithm, updates one or
`more parametersofthe at least one of the sub-problems(e.g.
`the first sub-problem) and further solves the at least one of
`the sub-problems in the iteration N+1 by the quantum
`processor using a first algorithm to generate an updated
`current result of the first algorithm and send the updated
`current result of the first algorithm to the classical computer
`via the communication engine of the quantum computer; and
`wherein the classical computer further receives the updated
`current result of the first algorithm via the communication
`engine of the classical computer, updates one or more
`parameters of the rest of the sub-problems(e.g. the second
`sub-problem) andfurther solves the rest of the sub-problems
`in the iteration N+1 by the classical computation solver
`using the second algorithm to generate an updated current
`result of the second algorithm; wherein N is selected from an
`17
`
`17
`
`

`

`US 2023/0419155 Al
`
`Dec. 28, 2023
`
`least one (N21) and wherein N
`integer number of at
`increasesas iterations increases; and wherein the at least one
`sub-problem (e.g. a first sub-problem) is an optimization
`problem with objective functions (e.g. a first objective
`function), and/or the result of the sub-problems (e.g. a
`second sub-problem) are (is) also optimization problems
`with objective functions (e.g. a second objective function);
`wherein the first objective function, the second objective
`function andthe original objective function are different. In
`general, an optimization problem comprises an objective
`function in a format of minimizing or maximizing a function
`with variables and optionally subject to a set of constraints
`wherein the constraints could be null (no constraints)or a list
`of equality equations or inequality equations, or the combi-
`nation thereof; wherein the objective function and con-
`straints comprises variables and parameters.
`In some
`embodiments, the original objective function has a format of
`minimizing or maximizing a summation of function A and
`function B (e.g. min (function A+function B) or max (func-
`tion A+function B)); the first objective function has a format
`of minimizing or maximizing a summation of function A and
`function fl
`(e.g. min (function A+function fl) or max
`(function A+function f1)); the second objective function has
`a format of minimizing or maximizing a summation of
`function B and function f2 (e.g. min (function B+function
`f2) or max (function B+function f2)); wherein function f1 in
`the first objective function is related to the rest of sub-
`problems (e.g.
`the second sub-problem) and is updated
`based on the currentsolution of the second algorithm in each
`iteration; and wherein function f2 in the second objective
`function is related to the at least one of sub-problems(e.g.
`the first sub-problem) and is updated based on the current
`solution of the first algorithm. In some embodiments, the
`function fl and function f2 are non-zero, and both function
`fl and function f2 are updated in each iteration. In other
`embodiments, at least of the functions f1 or f2 is zero, and
`at most one function (f1 or f2) is updated in each iteration.
`In other embodiments, function fl and function f2 are zero.
`The function fl or f2 could be one or more parameters, one
`or more variables, or a function comprises combinations of
`parameters and variables. One such example is illustrated by
`using hybrid QC-MIQP decomposition method to solve a
`cell formation manufact