DETAILED ACTION
The present application, filed on or after March 16, 2013, is being examined under the first inventor to file provisions of the AIA .
Claims 1-9 are presented for examination based on the amended claims in the application filed on January 3, 2023.
Claims 3, 6, and 9 are rejected under 35 U.S.C. § 112(b) or 35 U.S.C. § 112 (pre-AIA ), second paragraph, as being indefinite for failing to particularly point out and distinctly claim the subject matter which the inventor or a joint inventor (or for applications subject to pre-AIA 35 U.S.C. § 112, the applicant), regards as the invention.
Claims 1-9 are rejected under 35 U.S.C. § 101 because the claimed invention is directed to judicial exception, an abstract idea, and it has not been integrated into practical application. The claims further do not recite significantly more than the judicial exception.
Claims 1-9 are rejected under 35 U.S.C. § 102(a)(2) as being anticipated by US 2020/0401650 A1 Chen, Wei-Peng et al.
This action is made non-Final.
Notice of Pre-AIA or AIA Status
The present application, filed on or after March 16, 2013, is being examined under the first inventor to file provisions of the AIA .
Information Disclosure Statement
The information disclosure statement (IDS) submitted on December 22, 2023 is in compliance with the provisions of 37 CFR 1.97. Accordingly, the information disclosure statement is being considered by the examiner.
The information disclosure statement (IDS) filed on January 3, 2023 fails to comply with 37 CFR 1.98(a)(2), which requires a legible copy of each cited foreign patent document; each non-patent literature publication or that portion which caused it to be listed; and all other information or that portion which caused it to be listed. It has been placed in the application file, but the information referred to therein has not been considered.
Priority
Receipt is acknowledged of certified copies of papers required by 37 CFR 1.55. Should applicant desire to obtain the benefit of foreign priority under 35 U.S.C. 119(a)-(d) prior to declaration of an interference, a certified English translation of the foreign application must be submitted in reply to this action. 37 CFR 41.154(b) and 41.202(e). Failure to provide a certified translation may result in no benefit being accorded for the non-English application.
Claim Rejections - 35 U.S.C. § 112
The following is a quotation of 35 U.S.C. § 112(b):
(b) CONCLUSION.—The specification shall conclude with one or more claims particularly pointing out and distinctly claiming the subject matter which the inventor or a joint inventor regards as the invention.
The following is a quotation of 35 U.S.C. § 112 (pre-AIA ), second paragraph:
The specification shall conclude with one or more claims particularly pointing out and distinctly claiming the subject matter which the applicant regards as his invention.
Claims 3, 6, and 9 are rejected under 35 U.S.C. § 112(b) or 35 U.S.C. § 112 (pre-AIA ), second paragraph, as being indefinite for failing to particularly point out and distinctly claim the subject matter which the inventor or a joint inventor (or for applications subject to pre-AIA 35 U.S.C. § 112, the applicant), regards as the invention.
Claim 3, 6, and 9 recites the term “larger” and “smaller”, which are relative terms that renders the claim indefinite. The terms “larger” and “smaller” is not defined by the claim, the specification does not provide a standard for ascertaining the requisite degree, and one of ordinary skill in the art would not be reasonably apprised of the scope of the invention (See MPEP § 2173.05(b)). Claims 6 and 9, having similar limitations of claim 3, is also rejected under the similar rationale.
Claim 3 recites the phrase “the processor sets α to a larger value the larger absolute value of a difference between the degree of wish to change and Vave” and “sets α to a smaller value the smaller absolute value of the difference between the degree of wish to change and Vave” in lines 21-24. This phrase renders the claim indefinite, because it is unclear what a “larger absolute value” and a “smaller absolute value” are. As mentioned above the terms “larger” and “smaller” are relative terms. Additionally, as provided in the claim, since the “the degree of wish to change” is a, singular, continuous value from the first predetermined point to the second determined point and “Vave” is an average of the first predetermined point to the second determined point, again a singular value, it is unclear how an absolute value of the difference between the “the degree of wish to change” and “Vave” can be larger or smaller given “the degree of wish to change” and “Vave” are fixed values. Therefore, it is unclear which is being referred to and the scope of the claim is unclear (See MPEP § 2173). Claims 6 and 9, having similar limitations of claim 3, are also rejected under the similar rationale.
Claim Rejections - 35 U.S.C. § 101
35 U.S.C. § 101 reads as follows:
Whoever invents or discovers any new and useful process, machine, manufacture, or composition of matter, or any new and useful improvement thereof, may obtain a patent therefor, subject to the conditions and requirements of this title.
Claims 1-9 are rejected under 35 U.S.C. § 101 because the claimed invention is directed to judicial exception, an abstract idea, and it has not been integrated into practical application. The claims further do not recite significantly more than the judicial exception. Examiner has evaluated the claims under the framework provided in the 2019 Patent Eligibility Guidance published in the Federal Register 01/07/2019 and has provided such analysis below.
Step 1:
Claims 1-3 are directed to a device and fall within the statutory category of a machine; claims 4-6 are directed to a method and fall within the statutory category of a process; and claims 7-9 are directed to a non-transitory computer-readable medium and fall within the statutory category of articles of manufacture. Therefore, “Are the claims to a process, machine, manufacture or composition of matter?” Yes.
In order to evaluate the Step 2A inquiry “Is the claim directed to a law of nature, a natural phenomenon or an abstract idea?” we must determine, at Step 2A Prong 1, whether the claim recites a law of nature, a natural phenomenon or an abstract idea and further whether the claim recites additional elements that integrate the judicial exception into a practical application.
Step 2A Prong 1:
Claims 1, 4, and 7: The limitations of “generate a term, when a solution to a combinatorial optimization problem, an energy function, which is used to obtain the solution, of a model representing states of individual spins by a first value or a second value, and a pair of identification information of spin and degree of wish to change which indicates degree to which an user wishes to change state of spin corresponding to the identification information in the solution are given, wherein the term is generated for each pair of the identification information and the degree of wish to change, based on the state of spin corresponding to the identification information in the solution and the degree of wish to change” and “derive a new energy function by adding terms generated by the processor for each pair to the energy function”, as drafted, is an operation that, but for the recitation of generic computing components, under its broadest reasonable interpretation, covers performance of the limitation of mathematical evaluations. For example, calculating a term for an energy function that captures a current spin state and a user wish to change the spin state (target spin) can be accomplished using the relationship between the current spin state and the target spin, and calculating a new energy function can be accomplished by simply adding the newly generated terms to the previous energy function (see Para. 0010-0016 and mathematical Expression (1) and (2) which show examples of the energy function, Para. 0047 “The term generation unit 3 generates a term of the form α × (ki - xi)2 for each pair” and Para. 0059 show that the terms are also mathematical expressions, Para. 0063, “the energy function derivation unit 4 derives a new energy function by adding the above multiple terms to the right-hand side of Expression (2). This new energy function is expressed as in Expression (3) below” and mathematical Expression (3) show the new equation for the energy function, and the examiner would also like to note that the invention is directed to changing an energy function of a previous solution to arrive at a new energy function for a new solution, see Para. 0024, “it is desirable to be able to derive an energy function that can obtain a solution to a combinatorial optimization problem with the desired modifications to already-obtained-solution, when the user wishes to change the already-obtained-solution” see MPEP § 2106.04(I), “The Supreme Court’s decisions make it clear that judicial exceptions need not be old or long-prevalent, and that even newly discovered or novel judicial exceptions are still exceptions. For example, the mathematical formula in Flook, the laws of nature in Mayo, and the isolated DNA in Myriad were all novel or newly discovered, but nonetheless were considered by the Supreme Court to be judicial exceptions because they were "‘basic tools of scientific and technological work’ that lie beyond the domain of patent protection." Myriad, 569 U.S. 576, 589, 106 USPQ2d at 1976, 1978 (noting that Myriad discovered the BRCA1 and BRCA1 genes and quoting Mayo, 566 U.S. 71, 101 USPQ2d at 1965); Flook, 437 U.S. at 591-92, 198 USPQ2d at 198 ("the novelty of the mathematical algorithm is not a determining factor at all"); Mayo, 566 U.S. 73-74, 78, 101 USPQ2d 1966, 1968 (noting that the claims embody the researcher's discoveries of laws of nature). The Supreme Court’s cited rationale for considering even "just discovered" judicial exceptions as exceptions stems from the concern that "without this exception, there would be considerable danger that the grant of patents would ‘tie up’ the use of such tools and thereby ‘inhibit future innovation premised upon them.’" Myriad, 569 U.S. at 589, 106 USPQ2d at 1978-79 (quoting Mayo, 566 U.S. at 86, 101 USPQ2d at 1971). See also Myriad, 569 U.S. at 591, 106 USPQ2d at 1979 ("Groundbreaking, innovative, or even brilliant discovery does not by itself satisfy the §101 inquiry."). The Federal Circuit has also applied this principle, for example, when holding a concept of using advertising as an exchange or currency to be an abstract idea, despite the patentee’s arguments that the concept was "new". Ultramercial, Inc. v. Hulu, LLC, 772 F.3d 709, 714-15, 112 USPQ2d 1750, 1753-54 (Fed. Cir. 2014). Cf. Synopsys, Inc. v. Mentor Graphics Corp., 839 F.3d 1138, 1151, 120 USPQ2d 1473, 1483 (Fed. Cir. 2016) ("a new abstract idea is still an abstract idea")” (emphasis added)).
If a claim limitation, under its broadest reasonable interpretation, covers performance of the limitation of mathematic operation but for the recitation of generic computer components, then it falls within the “Mathematical Operation” grouping of abstract ideas. Accordingly, the claim recites an abstract idea under Prong I step 2A.
Furthermore, claims 1, 4, and 7: The limitations of “generate a term, when a solution to a combinatorial optimization problem, an energy function, which is used to obtain the solution, of a model representing states of individual spins by a first value or a second value, and a pair of identification information of spin and degree of wish to change which indicates degree to which an user wishes to change state of spin corresponding to the identification information in the solution are given, wherein the term is generated for each pair of the identification information and the degree of wish to change, based on the state of spin corresponding to the identification information in the solution and the degree of wish to change” and “derive a new energy function by adding terms generated by the processor for each pair to the energy function”, as drafted, is a process that, but for the recitation of generic computing components, under its broadest reasonable interpretation, covers performance of the limitation in the mind or with pen and paper. For example, a person can mentally create or draw with pen and paper a term that represents each state of a system and along with its respective requested change of state for a function that describe states of a system using the initial solution, initial model, and requested degree of change to certain states of the system, and a person can mentally add or draw with pen and paper each term representing the changed states to the function to create a modified function.
If a claim limitation, under its broadest reasonable interpretation, covers performance of the limitation in the mind or with pen and paper but for the recitation of generic computer components, then it falls within the “Mental Processes” grouping of abstract ideas. Accordingly, the claim recites an abstract idea under Prong I step 2A.
Therefore, yes, claims 1, 4, and 7 recite judicial exceptions. The claims have been identified to recite judicial exceptions, Step 2A Prong 2 will evaluate whether the claims are directed to the judicial exception.
Step 2A Prong 2:
Claims 1, 4, and 7: The judicial exception is not integrated into a practical application. In particular, the claims recite the following additional elements: “A energy function derivation device comprising: a memory configured to store instructions; and a processor configured to execute the instructions” and “A non-transitory computer-readable recording medium in which an energy function derivation program is recorded, wherein the energy function derivation program causes a computer to execute” which is merely a recitation of generic computing components and functions being used as a tool to implement the judicial exception (see MPEP § 2106.05(f)) with the broadest reasonable interpretation, which does not integrate a judicial exception into elements.
Therefore, “Do the claims recite additional elements that integrate the judicial exception into a practical application?” No, these additional elements do not integrate the abstract idea into a practical application and they do not impose any meaningful limits on practicing the abstract idea. The claim is directed to an abstract idea.
After having evaluated the inquires set forth in Steps 2A Prong 1 and 2, it has been concluded that claims 1, 4, and 7 not only recite a judicial exception but that the claims are directed to the judicial exception as the judicial exception has not been integrated into practical application.
Step 2B:
Claims 1, 4, and 7: The claims do not include additional elements, alone or in combination, that are sufficient to amount to significantly more than the judicial exception. As discussed above with respect to integration of the abstract idea into a practical application, the additional elements amount to no more than generic computing components which do not amount to significantly more than the abstract idea.
Therefore, “Do the claims recite additional elements that amount to significantly more than the judicial exception?” No, these additional elements, alone or in combination, do not amount to significantly more than the judicial exception. Having concluded the analysis within the provided framework, claims 1, 4, and 7 do not recite patent eligible subject matter under 35 U.S.C. § 101.
Regarding claims 2, 5, and 8, they recite additional limitations of “wherein when given identification information is denoted as i, a value corresponding to the state of spin corresponding to the identification information in the solution or an inverted state of the state is denoted as ki”, “a variable representing the state of spin corresponding to the identification information is denoted as xi”, “a value according to the degree of wish to change paired with the identification information is denoted as α”, and “generates the term of form α × (ki - xi)2 for each pair of the identification information and the degree of wish to change”, as drafted, is an operation that, but for the recitation of generic computing components, under its broadest reasonable interpretation, covers performance of the limitation of mathematical evaluations. For example, calculating a term for an energy function that captures a current spin state and a user wish to change the spin state (target spin) can be accomplished using the relationship between the current spin state and the target spin of the form α × (ki - xi)2, where each state of a system from the solution is given as xi, its respective requested degree of change of state is given as α, and the target spin is given as ki (see Para. 0010-0016 and mathematical Expression (1) and (2) which show examples of the energy function, and further see Para. 0047 “The term generation unit 3 generates a term of the form α × (ki - xi)2 for each pair” and Para. 0059 show that the terms are also mathematical expressions).
If a claim limitation, under its broadest reasonable interpretation, covers performance of the limitation of mathematic evaluations but for the recitation of generic computer components, then it falls within the “Mathematical Operation” grouping of abstract ideas. Accordingly, the claim recites an abstract idea under Prong I step 2A.
Furthermore, regarding claims 2, 5, and 8, they recite additional limitations of “wherein when given identification information is denoted as i, a value corresponding to the state of spin corresponding to the identification information in the solution or an inverted state of the state is denoted as ki”, “a variable representing the state of spin corresponding to the identification information is denoted as xi”, “a value according to the degree of wish to change paired with the identification information is denoted as α”, and “generates the term of form α × (ki - xi)2 for each pair of the identification information and the degree of wish to change”, as drafted, is a process that, but for the recitation of generic computing components, under its broadest reasonable interpretation, covers performance of the limitation in the mind or with pen and paper. For example, a person can mentally create or draw with a pencil and paper a term of the form α × (ki - xi)2, where each state of a system from the solution is given as xi, its respective requested degree of change of state is given as α, and its target spin is given as ki, which can be easily be generated by a person since all variables are binary.
If a claim limitation, under its broadest reasonable interpretation, covers performance of the limitation in the mind or with pen and paper but for the recitation of generic computer components, then it falls within the “Mental Processes” grouping of abstract ideas. Accordingly, the claim recites an abstract idea under Prong I step 2A.
Furthermore, regarding claims 2, 5, and 8: they recite additional element recitations of “the processor” and “wherein the energy function derivation program causes the computer to execute” which is merely a recitation of generic computing components and functions being used as a tool to implement the judicial exception (see MPEP § 2106.05(f)) which does not integrate a judicial exception into practical application. Further, these claims do not recite any further additional elements and for the same reasons as above with regard to integration into practical application and whether additional elements amount to significantly more, these claims also fail both Step 2A prong 2, thus the claims are directed to the judicial exception as they have not been integrated into practical application, and fail Step 2B as not amounting to significantly more. Therefore, claims 2, 5, and 8 do not recite patent eligible subject matter under 35 U.S.C. § 101.
Regarding claims 3, 6, and 9, they recite additional limitations of:
“wherein the degree of wish to change is a continuous value ranging from a first predetermined value which means that the state of spin corresponding to the identification information paired with the degree of wish to change will be changed without fail, to a second predetermined value which means that the state of spin corresponding to the identification information paired with the degree of wish to change will never be changed”,
“an average of the first predetermined value and the second predetermined value is denoted as Vave”,
“when the degree of wish to change paired with given identification information i of spin is a value between Vave and the first predetermined value, or the first predetermined value, the processor sets ki to a value corresponding to the inverted state of the state of spin corresponding to the identification information in the solution”,
“when the degree of wish to change paired with given identification information i of spin is a value between Vave and the second predetermined value, or the second predetermined value, the processor sets ki to a value corresponding to the state of spin corresponding to the identification information in the solution”, and
“sets α to a larger value the larger absolute value of a difference between the degree of wish to change and Vave, and sets α to a smaller value the smaller absolute value of the difference between the degree of wish to change and Vave”,
as drafted, is an operation that, but for the recitation of generic computing components, under its broadest reasonable interpretation, covers performance of the limitation of mathematical evaluations. For example, calculating a term for an energy function that captures a current spin state and a user wish to change the spin state (target spin) can be accomplished using the relationship between the current spin state and the target spin state of the form α × (ki - xi)2, where each state of a system from the solution is given as xi, its respective requested degree of change of state is given as α, its target spin is given as ki , and α is determined based on its proximity to the degree of change or degree of unchanged (see Para. 0010-0016 and mathematical Expression (1) and (2) which show examples of the energy function, Para. 0047 “The term generation unit 3 generates a term of the form α × (ki - xi)2 for each pair” and Para. 0059 show that the terms are also mathematical expressions, and further see Para. 0053-0056 which describe how to calculate α).
If a claim limitation, under its broadest reasonable interpretation, covers performance of the limitation of mathematic evaluations but for the recitation of generic computer components, then it falls within the “Mathematical Operation” grouping of abstract ideas. Accordingly, the claim recites an abstract idea under Prong I step 2A.
Furthermore, regarding claims 3, 6, and 9, they recite additional limitations of:
“wherein the degree of wish to change is a continuous value ranging from a first predetermined value which means that the state of spin corresponding to the identification information paired with the degree of wish to change will be changed without fail, to a second predetermined value which means that the state of spin corresponding to the identification information paired with the degree of wish to change will never be changed”,
“an average of the first predetermined value and the second predetermined value is denoted as Vave”,
“when the degree of wish to change paired with given identification information i of spin is a value between Vave and the first predetermined value, or the first predetermined value, the processor sets ki to a value corresponding to the inverted state of the state of spin corresponding to the identification information in the solution”,
“when the degree of wish to change paired with given identification information i of spin is a value between Vave and the second predetermined value, or the second predetermined value, the processor sets ki to a value corresponding to the state of spin corresponding to the identification information in the solution”, and
“sets α to a larger value the larger absolute value of a difference between the degree of wish to change and Vave, and sets α to a smaller value the smaller absolute value of the difference between the degree of wish to change and Vave”,
as drafted, is a process that, but for the recitation of generic computing components, under its broadest reasonable interpretation, covers performance of the limitation in the mind or with pen and paper. For example, a person can mentally create or draw with pen and paper a term in form of α × (ki - xi)2 where each state of a system from the solution is given as xi, and where 1) its respective requested degree of change of state between absolutely change and absolutely do not change is given as α, 3) its target spin is given as ki which is the inverted state from the solution when the requested degree of change is given as absolutely change or 4) ki which is the state from the solution when the requested degree of change is given as absolutely do not change, and 2/5) α is equal to 1 when the requested degree of change is absolutely change or when the requested degree of change is absolutely do not change, and α is equal to 0 when the requested degree of change is the midpoint between absolutely change and absolutely do not change, e.g., 0.5, where the user does not particular require a changed or unchanged state.
If a claim limitation, under its broadest reasonable interpretation, covers performance of the limitation in the mind or with pen and paper but for the recitation of generic computer components, then it falls within the “Mental Processes” grouping of abstract ideas. Accordingly, the claim recites an abstract idea under Prong I step 2A.
Furthermore, regarding claims 3, 6, and 9: they recite additional element recitations of “the processor” and “wherein the energy function derivation program causes the computer to execute” which is merely a recitation of generic computing components and functions being used as a tool to implement the judicial exception (see MPEP § 2106.05(f)) which does not integrate a judicial exception into practical application. Further, these claims do not recite any further additional elements and for the same reasons as above with regard to integration into practical application and whether additional elements amount to significantly more, these claims also fail both Step 2A prong 2, thus the claims are directed to the judicial exception as they have not been integrated into practical application, and fail Step 2B as not amounting to significantly more. Therefore, claims 3, 6, and 9 do not recite patent eligible subject matter under 35 U.S.C. § 101.
Therefore, having concluded the analysis within the provided framework, claims 1-9 do not recite patent eligible subject matter and are rejected under 35 U.S.C. § 101 because the claimed invention is directed to judicial exception, an abstract idea, that has not been integrated into a practical application. The claims further do not recite significantly more than the judicial exception. Claims 2-3, 5-6, and 8-9 are also rejected for incorporating the deficiency of their dependent claims 1, 4, and 7, respectively.
Claim Rejections - 35 U.S.C. § 102
In the event the determination of the status of the application as subject to AIA 35 U.S.C. § 102 and 103 (or as subject to pre-AIA 35 U.S.C. § 102 and 103) is incorrect, any correction of the statutory basis (i.e., changing from AIA to pre-AIA ) for the rejection will not be considered a new ground of rejection if the prior art relied upon, and the rationale supporting the rejection, would be the same under either status.
The following is a quotation of the appropriate paragraphs of 35 U.S.C. § 102 that form the basis for the rejections under this section made in this Office action:
A person shall be entitled to a patent unless –
(a)(2) the claimed invention was described in a patent issued under section 151, or in an application for patent published or deemed published under section 122(b), in which the patent or application, as the case may be, names another inventor and was effectively filed before the effective filing date of the claimed invention.
Claims 1-9 are rejected under 35 U.S.C. § 102(a)(2) as being anticipated by US 2020/0401650 A1 Chen, Wei-Peng et al. [herein “Chen”].
As per claim 1, Chen teaches “A energy function derivation device comprising: a memory configured to store instructions; and a processor configured to execute the instructions”. (Para. 0036, “the electronic device 102 may be configured to provide a call to the optimization solver machine 108 of the annealer system 106 to generate a solution for the specific optimization problem based on the second user input. In order to generate the solution, the specific optimization problem may have to be submitted in a suitable format to the annealer system 106. The suitable format may include an objective function that needs to be minimized or optimized to generate the solution for the specific optimization problem…the electronic device 102 may be configured to formulate the objective function (also referred to as mathematical formulation/unconstrained mathematical formulation) for a plurality of attributes of the corresponding NP formulation constructed for the specific optimization problem” [A energy function derivation device]. Para. 0049, “The electronic device 102 may include a processor 204, a memory 206” [a memory and a processor]. Para. 0051, “The processor 204 may be configured to interpret and/or execute program instructions and/or process data stored in the memory 206” [a memory configured to store instructions; and a processor configured to execute the instructions]. Further see Para. 0036-0039 and 0049-0053. The examiner has interpreted that an electronic device that includes a processor that executes programs instructions stored in a memory and formulates the objective function for attributes of a NP formulation constructed for the specific optimization problem and generates a solution using for a solver of an annealer system as an energy function derivation device comprising: a memory configured to store instructions; and a processor configured to execute the instructions.)
Chen also teaches “generate a term, when a solution to a combinatorial optimization problem, an energy function, which is used to obtain the solution, of a model representing states of individual spins by a first value or a second value, and a pair of identification information of spin and degree of wish to change which indicates degree to which an user wishes to change state of spin corresponding to the identification information in the solution are given, wherein the term is generated for each pair of the identification information and the degree of wish to change, based on the state of spin corresponding to the identification information in the solution and the degree of wish to change”. (Para. 0034, “By selecting the specific combination of user-selectable options, the user 114 may select the first template for the specific optimization problem on the displayed electronic user interface 104. The selected first template may specify a plurality of parameters of the specific optimization problem. The plurality of parameters may include, but are not limited to, pre-defined variables, labels for the variables, values, constraints, objective function(s), and user-declarable variables” [when an energy function is given]. Para. 0150, “The AML format of the formulated first objective function may not be directly executed, but instead may be used by the optimization solver machine 108 or other external optimization solver machines to generate one or more solutions for the NP problem corresponding to the specific optimization problem” [when a solution to a combinatorial optimization problem, an energy function, which is used to obtain the solution, are given ]. Para. 0132-133, “the first objective function may be one of: a Quadratic Unconstrained Binary Optimization (QUBO) function” [e.g., energy function of a model representing states of individual spins by a first value or a second value]. Para. 0035, “The input data may include, but is not limited to, values for different parameters, constraints (e.g., at least two trucks), conditions (e.g., if-else conditions), and objective function(s). As an example, for a specific optimization problem in logistics industry that is related to a strategic planning for shipping product orders, the plurality of parameters may include, but are not limited to, a number of containers/trucks, a number of products to be shipped, a size/weight of each type of product to be shipped, and a shipping cost per product type. Also, for the specific optimization problem, the plurality of parameters may include a set of constraints, such as a time constraint, a cost constraint, or a weight constraint. The second user input may be used to specify values, constraints, conditions, and/or relationships (e.g., objective function(s)) among different parameters for the plurality of parameters of the specific optimization problem”. Para. 0046, “The set of user-specified conditions may include, but are not limited to, a manual trigger input from the user 114, a periodical/non-periodical change in values of one or more parameters of the specific optimization problem” [e.g., a pair of identification information of spin and degree of wish to change which indicates degree to which an user wishes to change state of spin corresponding to the identification information in the solution is given]. Para. 0165, “a penalty term may be appended to the formulated first objective function. The penalty term may be appended to convert the first objective function to the second objective function. In one or more embodiments, the processor 204 may be configured to append the penalty term to the formulated first objective function. The penalty term may be appended such that the effect of constraints pre-specified for the first objective function may alternatively be achieved while the optimization solver machine 108 generates the solution for the second objective function and avoids incurring penalties” [e.g., generate a term, wherein the term is generated for each pair of the identification information and the degree of wish to change, based on the state of spin corresponding to the identification information in the solution and the degree of wish to change]. Further see Para. 0034-0039, 0046, 0132-0133, 0150, and 0165-0173. The examiner has interpreted that when a user that selects an Quadratic Unconstrained Binary Optimization (QUBO) objective function which generates a solution to a NP optimization problem for a solver of an annealer system and that inputs data such as constraints and conditions used to implement a non-periodical change in the values of parameters of the optimization problem, then a penalty term is appended to the first objective function so that the constraint effects generate a solution that avoiding occurring penalties in the solution as generate a term, when a solution to a combinatorial optimization problem, an energy function, which is used to obtain the solution, of a model representing states of individual spins by a first value or a second value, and a pair of identification information of spin and degree of wish to change which indicates degree to which an user wishes to change state of spin corresponding to the identification information in the solution are given, wherein the term is generated for each pair of the identification information and the degree of wish to change, based on the state of spin corresponding to the identification information in the solution and the degree of wish to change.)
Chen also teaches “derive a new energy function by adding terms generated by the processor for each pair to the energy function.” (Para. 0165, “a penalty term may be appended to the formulated first objective function. The penalty term may be appended to convert the first objective function to the second objective function”. Para. 0173, “The penalty term may be appended to convert the first objective function to the second objective function. Also, the penalty term may be appended to the formulated first objective function based on a determination that the determined constraint type used in the formulated first objective function is one of the equality constraint type or the inequality constraint type. In one or more embodiments, the processor 204 may be configured to append the penalty term to the formulated first objective function based on the determination that the determined constraint type used in the formulated first objective function is one of the equality constraint type or the inequality constraint type. The penalty term may be specified in the second mapping table that includes a list of penalty terms mapped to a corresponding list of constraint types applicable for the formulated first objective function” [e.g., derive a new energy function by adding terms generated by the processor for each pair to the energy function]. Further see Para. 0165-0173. The examiner has that adding penalty terms for the constraints to the first objective function to convert the first objective function to a second objective function as derive a new energy function by adding terms generated by the processor for each pair to the energy function.)
As per claim 2, Chen teaches “wherein when given identification information is denoted as i, a value corresponding to the state of spin corresponding to the identification information in the solution or an inverted state of the state is denoted as ki”, “a variable representing the state of spin corresponding to the identification information is denoted as xi”, “a value according to the degree of wish to change paired with the identification information is denoted as α”, and “the processor generates the term of form α × (ki - xi)2 for each pair of the identification information and the degree of wish to change.” (Para. 0138, “The QUBO function may be given by equation (1), as follows: min(y=xT⋅Q⋅x), where x is a vector of binary decision variables and Q is a square matrix of constants” [e.g., wherein when given identification information is denoted as i, a variable representing the state of spin corresponding to the identification information is denoted as xi”]. Para. 0165, “At 912, a penalty term may be appended to the formulated first objective function. The penalty term may be appended to convert the first objective function to the second objective function. In one or more embodiments, the processor 204 may be configured to append the penalty term to the formulated first objective function. The penalty term may be appended such that the effect of constraints pre-specified for the first objective function may alternatively be achieved while the optimization solver machine 108 generates the solution for the second objective function and avoids incurring penalties” [the processor generates the term for each pair of the identification information and the degree of wish to change, displayed in the term as P]. “More specifically, the penalty term may be appended such that the penalties equal zero for feasible solutions and a positive value for infeasible solutions of the discrete solution space. The optimization solver machine 108 may be configured to generate the solution by solving the second objective function. The second objective function may equal the first objective function, in case the penalty term is zero” [e.g., penalty is minimized when equal to zero or when first object function equals second objective function]. Para. 0178, “It may be determined whether the summary inequality term for the first objective function includes exactly two variables, a penalty term may be appended to the first objective function based on the second mapping table”. Since x is the vector of binary decision variables being 0 or 1, the penalty is minimized when equal to 0, and for a vector of two variables, then A must equal to 1. Para. 0166, “As an example, the first objective function may be given by equation (9),
as follows: min(y=xTQx) such as A⋅x=b, x∈{0,1}n (9)”. Since the first objective function is met when Ax=b, therefore b is the target value, e.g., a value corresponding to the state of spin corresponding to the identification information in the solution or an inverted state of the state is denoted as ki. Para. 0166, “From equation (9), the first objective function may have the equality constraint type. Thus, a quadratic penalty term (P ⋅(Ax−b)T⋅(Ax−b)) may be appended to the first objective functions (given by equation (9) to obtain the second objective function, which may be given by equation (10), as follows: min(y=xTQx + P⋅(Ax−b)T⋅(Ax−b)) (10), x∈{0,1}n, P is a large number of constant” [P seeks to scale the penalty term, e.g., a value according to the degree of wish to change paired with the identification information is denoted as α]. The penalty term is the inner product which yields the squared Euclidean norm disclosed in NPL document1:
P
⋅
A
x
-
b
T
⋅
A
x
-
b
=
P
⋅
A
x
-
b
2
#
1
Lastly, since xi and ki are binary and a fundamental property of squares makes the place of these terms trivial since (a-b)2 = (b-a)2. Therefore, we arrive at the claimed “the term of form α × (ki - xi)2”:
P
⋅
A
x
-
b
2
=
P
⋅
b
-
A
x
2
#
2
Further see Para. 0138, 0165-0166, and 0178. The examiner has interpreted that the first objective function given as a QUBO function of the form y=xTQx where x is a vector of binary decision variables and Ax=b is met and a processor creating a penalty term to be added to a first objective function to create a second objective function where the penalty which equals zero for feasible solutions, when the second objective function equals the first object function when the penalty is zero, and where the second objective function is y=xTQx + P⋅(Ax−b)T⋅(Ax−b) where P is a large constant as wherein when given identification information is denoted as i, a value corresponding to the state of spin corresponding to the identification information in the solution or an inverted state of the state is denoted as ki, a variable representing the state of spin corresponding to the identification information is denoted as xi, a value according to the degree of wish to change paired with the identification information is denoted as α, and the processor generates the term of form α × (ki - xi)2 for each pair of the identification information and the degree of wish to change.
As per claim 3, Chen teaches “wherein the degree of wish to change is a continuous value ranging from a first predetermined value which means that the state of spin corresponding to the identification
information paired with the degree of wish to change will be changed without fail, to a second predetermined value which means that the state of spin corresponding to the identification information paired with the degree of wish to change will never be changed”. (Para. 0035, “The input data may include but is not limited to, values for different parameters, constraints (e.g., at least two trucks), conditions (e.g., if-else conditions), and objective function(s). As an example, for a specific optimization problem in logistics industry that is related to a strategic planning for shipping product orders, the plurality of parameters may include, but are not limited to, a number of containers/trucks, a number of products to be shipped, a size/weight of each type of product to be shipped, and a shipping cost per product type. Also, for the specific optimization problem, the plurality of parameters may include a set of constraints, such as a time constraint, a cost constraint, or a weight constraint. The second user input may be used to specify values, constraints, conditions, and/or relationships (e.g., objective function(s)) among different parameters for the plurality of parameters of the specific optimization problem”. Para. 0046, “The set of user-specified conditions may include, but are not limited to, a manual trigger input from the user 114, a periodical/non-periodical change in values of one or more parameters of the specific optimization problem” [user specifying a change, e.g. wherein the degree of wish to change is a continuous value ranging from a first predetermined value which means that the state of spin corresponding to the identification information paired with the degree of wish to change will be changed without fail, to a second predetermined value which means that the state of spin corresponding to the identification information paired with the degree of wish to change will never be changed]. Further see Para. 0034-0039, 0046, and 0192. The examiner has interpreted that inputs data such as constraints and conditions used to implement a non-periodical change in the values of parameters of the optimization problem as wherein the degree of wish to change is a continuous value ranging from a first predetermined value which means that the state of spin corresponding to the identification information paired with the degree of wish to change will be changed without fail, to a second predetermined value which means that the state of spin corresponding to the identification information paired with the degree of wish to change will never be changed.)
Chen also teaches “when the degree of wish to change paired with given identification information i of spin is a value between Vave and the first predetermined value, or the first predetermined value, the processor sets ki to a value corresponding to the inverted state of the state of spin corresponding to the identification information in the solution”. (Para. 0165, “At 912, a penalty term may be appended to the formulated first objective function. The penalty term may be appended to convert the first objective function to the second objective function. In one or more embodiments, the processor 204 may be configured to append the penalty term to the formulated first objective function. The penalty term may be appended such that the effect of constraints pre-specified for the first objective function may alternatively be achieved while the optimization solver machine 108 generates the solution for the second objective function and avoids incurring penalties. More specifically, the penalty term may be appended such that the penalties equal zero for feasible solutions and a positive value for infeasible solutions of the discrete solution space” [e.g., change results in a penalty, e.g., when the degree of wish to change paired with given identification information i of spin is the first predetermined value]. Para. 0166, “From equation (9), the first objective function may have the equality constraint type. Thus, a quadratic penalty term (P ⋅(Ax−b)T⋅(Ax−b)) may be appended to the first objective functions (given by equation (9) to obtain the second objective function, which may be given by equation (10), as follows: min(y=xTQx + P⋅(Ax−b)T⋅(Ax−b)) (10), x∈{0,1}n, P is a large number of constant”. In this case, since the first objective function is does not when Ax=b and a penalty is added, therefore, therefore b which is the target value, is different, e.g., the processor sets ki to a value corresponding to the inverted state of the state of spin corresponding to the identification information in the solution. Further see Para. 0165-0167. The examiner has interpreted that a processor that appends a positive value of a penalty term to the first objective function to create a second objective function so that the constraint effects generate a solution for the second objective function to obtain the target value as when the degree of wish to change paired with given identification information i of spin is the first predetermined value, the processor sets ki to a value corresponding to the inverted state of the state of spin corresponding to the identification information in the solution.)
Chen also teaches “when the degree of wish to change paired with given identification information i of spin is a value between Vave and the second predetermined value, or the second predetermined value, the processor sets ki to a value corresponding to the state of spin corresponding to the identification information in the solution”. (Para. 0165, “At 912, a penalty term may be appended to the formulated first objective function. The penalty term may be appended to convert the first objective function to the second objective function. In one or more embodiments, the processor 204 may be configured to append the penalty term to the formulated first objective function. The penalty term may be appended such that the effect of constraints pre-specified for the first objective function may alternatively be achieved while the optimization solver machine 108 generates the solution for the second objective function and avoids incurring penalties. More specifically, the penalty term may be appended such that the penalties equal zero for feasible solutions and a positive value for infeasible solutions of the discrete solution space. The optimization solver machine 108 may be configured to generate the solution by solving the second objective function. The second objective function may equal the first objective function, in case the penalty term is zero” [e.g., state remains the same as to not change the state, e.g., when the degree of wish to change paired with given identification information i of spin is the second predetermined value, the processor sets ki to a value corresponding to the state of spin corresponding to the identification information in the solution]. This is a case where Ax=b, thus state is not changed. Further see Para. 0034-0039, 0046, 0165-0166, and 0192. The examiner has interpreted that a processor creating a penalty term to be added to a first objective function to create a second objective function where the penalty which equals zero for feasible solutions and equal to the first objective function as when the degree of wish to change paired with given identification information i of spin is the second predetermined value, the processor sets ki to a value corresponding to the state of spin corresponding to the identification information in the solution.)
Chen also teaches “an average of the first predetermined value and the second predetermined value is denoted as Vave” and “the processor sets α to a larger value the larger absolute value of a difference between the degree of wish to change and Vave, and sets α to a smaller value the smaller absolute value of the difference between the degree of wish to change and Vave.” (Para. 0030, “The combinatorial optimization problem may be a known combinatorial/mathematical problem that may be formulated as an objective function based on which feasible solutions for the combinatorial optimization problem may be searched from a discrete solution space”. Para 0115, “the bin packing problem 604 may be related to the multiple knapsacks problem 606. The multiple knapsacks problem 606 may include a plurality of attributes (n, m, w, v, c). The multiple knapsacks problem 606 may be stated as: “we have a list of n objects, with the weight of each object given by w, and the value v. We have m knapsacks which can only carry weight capacity c. The problem is to maximize
the value of selected objects subject to the constraint that total weight of the selected objects is less than the weight capacity”. The multiple knapsacks problem 606 may be generalized to quadratic knapsacks problem 608 or reduced to the 0-1 knapsacks problem 610. In case Vij=0, for i≠j, where Vij is the value in case both object i and j are selected, the quadratic knapsacks problem 608 may be reduced to the 0-1 knapsacks problem 610. In case the weight w is equal to value v for i≠j, the 0-1 knapsacks problem 610 may be reduced to the subset sum problem 612. The subset sum problem 612 may be stated as: “Given a set of non-negative integers S, and a value sum VS, determine if there is a subset SN of the given set with sum VN equal to given sum”. In case, there are two subsets, the subset sum problem 612 may be reduced to number partition problem 614”. The “average of the first predetermined value and the second predetermined value is denoted as Vave” is a value in the middle between the spin is desired to change and the spin is desired to not change, e.g., a user does not particularly care if the spin changes or not. In a 0-1 knapsack problem, a discrete choice must be made, e.g., an object must be other chosen or not chosen as disclosed in NPL document2. If both objects are chosen at this instance, i.e., user does not particularly care which if the object is chose or not, e.g., average of the first predetermined value and the second predetermined value is denoted as Vav. Furthermore, at this instance since the decision to select one of the objects is indecisive, for this particular system mentioned in Para. 0115, the selected object must adhere to the constraint as the weight must equal the value when both objects are chosen, then the smaller weight is chosen, e.g., sets α to a smaller value. Para. 0165, “At 912, a penalty term may be appended to the formulated first objective function. The penalty term may be appended to convert the first objective function to the second objective function. In one or more embodiments, the processor 204 may be configured to append the penalty term to the formulated first objective function” [e.g., the processor sets]. Para. 0166, “From equation (9), the first objective function may have the equality constraint type. Thus, a quadratic penalty term (P⋅(Ax−b)T⋅(Ax−b)) may be appended to the first objective functions (given by equation (9) to obtain the second objective function, which may be given by equation (10), as follows: min(y=xTQx + P⋅(Ax−b)T⋅(Ax−b)) (10), x∈{0,1}n, P is a large number of constant”. In case where, Ax=b, as discussed above and the target value was not met, e.g., specifying a penalty to meet the change, then P is the larger constant, e.g., a larger value the larger absolute value of a difference between the degree of wish to change and Vave. Further see Para. 0030, 115, and 0165-0166. The examiner has interpreted that formulating an objective
function based on which feasible solutions for the combinatorial optimization problem may be searched from a discrete solution space to maximize the value of selected objects subject to the constraint that total weight of the selected objects is less than the weight capacity when both objects are selected in a 0-1 knapsack problem and using the processor to append the penalty term to the formulated first objective function having a larger number constant when the solution is not feasible as an average of the first predetermined value and the second predetermined value is denoted as Vave and the processor sets α to a larger value the larger absolute value of a difference between the degree of wish to change and Vave, and sets α to a smaller value the smaller absolute value of the difference between the degree of wish to change and Vave.)
Re Claim 4, it is a method claim, having similar limitations of claim 1. Thus, claim 4 is also rejected under the similar rationale as cited in the rejection of claim 1.
Re Claim 5, it is a method claim, having similar limitations of claim 2. Thus, claim 5 is also rejected under the similar rationale as cited in the rejection of claim 2.
Re Claim 6, it is a method claim, having similar limitations of claim 3. Thus, claim 6 is also rejected under the similar rationale as cited in the rejection of claim 3.
Re Claim 7, it is an article of manufacture claim, having similar limitations of claim 1. Thus, claim 7 is also rejected under the similar rationale as cited in the rejection of claim 1.
Furthermore, regarding claim 7, Chen teaches “A non-transitory computer-readable recording medium in which an energy function derivation program is recorded, wherein the energy function derivation program causes a computer to execute”. (Para. 0036, “the electronic device 102 may be configured to provide a call to the optimization solver machine 108 of the annealer system 106 to generate a solution for the specific optimization problem based on the second user input. In order to generate the solution, the specific optimization problem may have to be submitted in a suitable format to the annealer system 106. The suitable format may include an objective function that needs to be minimized or optimized to generate the solution for the specific optimization problem…the electronic device 102 may be configured to formulate the objective function (also referred to as mathematical formulation/unconstrained mathematical formulation) for a plurality of attributes of the corresponding NP formulation constructed for the specific optimization problem” [an energy function derivation program]. Para. 0049, “The electronic device 102 may include a processor 204, a memory 206, and a persistent data storage 208”. Para. 0050, “The processor 204 may include any suitable special-purpose or general-purpose computer, computing entity, or processing device including various computer hardware or software modules and may be configured to execute instructions stored on any applicable computer-readable storage media” [wherein the energy function derivation program causes a computer to execute]. Para. 0051, “The processor 204 may be configured to interpret and/or execute program instructions and/or process data stored in the memory 206”. Para. 0053, “computer-readable storage media may include tangible or non-transitory computer-readable storage media” [A non-transitory computer-readable recording medium in which an energy function derivation program is recorded]. Further see Para. 0036-0039 and 0049-0053. The examiner has interpreted that an electronic device that includes a processor that executes programs instructions stored in a memory and non-transitory computer-readable storage media and formulates the objective function for attributes of a NP formulation constructed for the specific optimization problem and generates a solution using for a solver of an annealer system as a non-transitory computer-readable recording medium in which an energy function derivation program is recorded, wherein the energy function derivation program causes a computer to execute.)
Re Claim 7, it is a method claim, having similar limitations of claim 2. Thus, claim 7 is also rejected under the similar rationale as cited in the rejection of claim 2.
Re Claim 8, it is a method claim, having similar limitations of claim 3. Thus, claim 8 is also rejected under the similar rationale as cited in the rejection of claim 3.
Conclusion
The prior art made of record and not relied upon is considered pertinent to applicant's disclosure.
Farhi, Edward, Jeffrey Goldstone, Sam Gutmann, and Hartmut Neven. "Quantum algorithms for fixed qubit architectures." arXiv preprint arXiv:1703.06199 (2017) using a modified objective function to model new parameters in generating a solution to a combinatorial optimization problem.
Vyskocil, Tomas, and Hristo Djidjev. "Simple constraint embedding for quantum annealers." In 2018 IEEE International Conference on Rebooting Computing (ICRC), pp. 1-11. IEEE, 2018 teaches adding constraints to an objective function as a penalty to optimality solve NP-hard Quadratic Unconstrained Binary Optimization (QUBO) problems.
Chapuis, Guillaume, Hristo Djidjev, Georg Hahn, and Guillaume Rizk. "Finding maximum cliques on a quantum annealer." In Proceedings of the Computing Frontiers Conference, pp. 63-70. 2017 teaches enhancing the solution to a quadratic unconstrained binary optimization problem by minimizing the coefficient and penalties of a Hamiltonian function.
Examiner’s Note: The examiner has cited particular columns and line numbers in the reference that applied to the claims above for the convenience of the applicant. Although the specified citations are representative of the art and are applied to specific limitations within the individual claim, other passages and figures may apply as well. It is respectfully requested from the applicant, to fully consider the references in their entirety as potentially teaching all or part of the claimed invention, as well as the context of the passage as taught by the prior art or disclosed by the examiner. In the case of amending the claimed invention, the applicant is respectfully requested to indicate the portion(s) of the specification which dictate(s) the structure relied on for the proper interpretation and also to verify and ascertain the metes and bound of the claimed invention.
Any inquiry concerning this communication or earlier communications from the examiner should be directed to Simeon P Drapeau whose telephone number is (571)-272-1173. The examiner can normally be reached Monday - Friday, 8 a.m. - 5 p.m. ET.
Examiner interviews are available via telephone, in-person, and video conferencing using a USPTO supplied web-based collaboration tool. To schedule an interview, applicant is encouraged to use the USPTO Automated Interview Request (AIR) at http://www.uspto.gov/interviewpractice.
If attempts to reach the examiner by telephone are unsuccessful, the examiner’s supervisor, Ryan Pitaro can be reached on (571) 272-4071. The fax phone number for the organization where this application or proceeding is assigned is 571-273-8300.
Information regarding the status of published or unpublished applications may be obtained from Patent Center. Unpublished application information in Patent Center is available to registered users. To file and manage patent submissions in Patent Center, visit: https://patentcenter.uspto.gov. Visit https://www.uspto.gov/patents/apply/patent-center for more information about Patent Center and https://www.uspto.gov/patents/docx for information about filing in DOCX format. For additional questions, contact the Electronic Business Center (EBC) at 866-217-9197 (toll-free). If you would like assistance from a USPTO Customer Service Representative, call 800-786-9199 (IN USA OR CANADA) or 571-272-1000.
/SIMEON P DRAPEAU/Examiner, Art Unit 2188
/RYAN F PITARO/Supervisory Patent Examiner, Art Unit 2188
Prosecution Insights