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 . This action is responsive to the Application filed on 01/05/2024. Claims 1-20 are pending in the case. Claims 1, 10, and 19 are independent claims.
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-20 are rejected under 35 U.S.C. § 101 because the claimed invention is directed to an abstract idea without significantly more.
Step 1: Claims 1-9 are directed towards the statutory category of a machine. Claims 10-18 are directed towards the statutory category of a process. Claims 19-20 are directed towards the statutory category of an article of manufacture.
With respect to claim 1:
2A Prong 1: This claim is directed to a judicial exception.
a classical computation component that employs a quantum-classical hybrid algorithm to update one or more continuous variables in a higher-order mixed integer programming (MIP) problem using classical optimization (mathematical concept and/or mental process); and
a quantum computation component that employs the quantum-classical hybrid algorithm to update one or more binary variables in the higher-order MIP problem using quantum optimization (mathematical concept and/or mental process).
2A Prong 2: This judicial exception is not integrated into a practical application.
Additional elements:
A system, comprising: a memory that stores computer-executable components; and a processor that executes the computer-executable components stored in the memory, wherein the computer-executable components comprise (merely reciting the words "apply it" (or an equivalent) with the judicial exception, or merely including instructions to implement an abstract idea on a computer, or merely using a computer as a tool to perform an abstract idea, as discussed in MPEP § 2106.05(f)).
2B: The claim does not include additional elements that are sufficient to amount to significantly more than the judicial exception.
Additional elements:
A system, comprising: a memory that stores computer-executable components; and a processor that executes the computer-executable components stored in the memory, wherein the computer-executable components comprise (merely reciting the words "apply it" (or an equivalent) with the judicial exception, or merely including instructions to implement an abstract idea on a computer, or merely using a computer as a tool to perform an abstract idea, as discussed in MPEP § 2106.05(f)).
With respect to claim 2:
2A Prong 1: This claim is directed to a judicial exception.
the classical computation component updates the one or more continuous variables on a classical system by fixing the one or more binary variables (mathematical concept and/or mental process).
2A Prong 2: This judicial exception is not integrated into a practical application.
2B: The claim does not include additional elements that are sufficient to amount to significantly more than the judicial exception.
With respect to claim 3:
2A Prong 1: This claim is directed to a judicial exception.
the quantum computation component updates the one or more binary variables on a quantum system by fixing the one or more continuous variables (mathematical concept and/or mental process).
2A Prong 2: This judicial exception is not integrated into a practical application.
2B: The claim does not include additional elements that are sufficient to amount to significantly more than the judicial exception.
With respect to claim 4:
2A Prong 1: This claim is directed to a judicial exception.
a formulation component that formulates the higher-order MIP problem for applying an augmented Lagrange scheme (mathematical concept and/or mental process).
2A Prong 2: This judicial exception is not integrated into a practical application.
2B: The claim does not include additional elements that are sufficient to amount to significantly more than the judicial exception.
With respect to claim 5:
2A Prong 1: This claim is directed to a judicial exception.
a precomputation component that selects a solution of a relaxation problem as an initial value used by the quantum-classical hybrid algorithm to solve the higher-order MIP problem (mathematical concept and/or mental process).
2A Prong 2: This judicial exception is not integrated into a practical application.
2B: The claim does not include additional elements that are sufficient to amount to significantly more than the judicial exception.
With respect to claim 6:
2A Prong 1: This claim is directed to a judicial exception.
the precomputation component selects a result generated by applying a computationally cheap cut or lifting to a relaxed problem as the initial value (mathematical concept and/or mental process).
2A Prong 2: This judicial exception is not integrated into a practical application.
2B: The claim does not include additional elements that are sufficient to amount to significantly more than the judicial exception.
With respect to claim 7:
2A Prong 1: This claim is directed to a judicial exception.
employing the quantum-classical hybrid algorithm separates the higher-order MIP problem into a continuous optimization problem and a binary optimization problem (mathematical concept and/or mental process).
2A Prong 2: This judicial exception is not integrated into a practical application.
2B: The claim does not include additional elements that are sufficient to amount to significantly more than the judicial exception.
With respect to claim 8:
2A Prong 1: This claim is directed to a judicial exception.
a size of the binary optimization problem remains equal to a number of one or more binary variables in the higher-order MIP problem (mathematical concept and/or mental process).
2A Prong 2: This judicial exception is not integrated into a practical application.
2B: The claim does not include additional elements that are sufficient to amount to significantly more than the judicial exception.
With respect to claim 9:
2A Prong 1: This claim is directed to a judicial exception.
the binary optimization problem is solved using quantum algorithms and without introducing auxiliary binary variables (mathematical concept and/or mental process).
2A Prong 2: This judicial exception is not integrated into a practical application.
2B: The claim does not include additional elements that are sufficient to amount to significantly more than the judicial exception.
The remaining claims 10-20 are rejected under 35 U.S.C. § 101 because the claimed invention is directed to an abstract idea without significantly more for at least the same reasons as those given above with respect to claims 1-9 with only the addition of generic computer components under step 2A prong 1. Under the broadest reasonable interpretation, these limitations are process steps that cover mental processes including an observation, evaluation, judgment or opinion that could be performed in the human mind or with the aid of pencil and paper but for the recitation of a generic computer component. If a claim, under its broadest reasonable interpretation, covers a mental process but for the recitation of generic computer components, then it falls within the "Mental Process" grouping of abstract ideas. A person would readily be able to perform this process either mentally or with the assistance of pen and paper. See MPEP § 2106.04(a)(2). Limitations that merely reciting the words "apply it" (or an equivalent) with the judicial exception, or merely including instructions to implement an abstract idea on a computer, or merely using a computer as a tool to perform an abstract idea, as discussed in MPEP § 2106.05(f). These additional elements do not integrate the judicial exception into a practical application under step 2A prong 2. Refer to MPEP §2106.04(d). Moreover, the limitations are merely reciting the words "apply it" (or an equivalent) with the judicial exception, or merely including instructions to implement an abstract idea on a computer, or merely using a computer as a tool to perform an abstract idea, as discussed in MPEP § 2106.05(f). These additional elements do not recite any additional elements/limitations that amount to significantly more. Accordingly, the claimed invention recites an abstract idea without significantly more.
Claim Rejections - 35 U.S.C. § 103
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 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 35 U.S.C. § 103 which forms the basis for all obviousness rejections set forth in this Office action:
A patent for a claimed invention may not be obtained, notwithstanding that the claimed invention is not identically disclosed as set forth in section 102 of this title, if the differences between the claimed invention and the prior art are such that the claimed invention as a whole would have been obvious before the effective filing date of the claimed invention to a person having ordinary skill in the art to which the claimed invention pertains. Patentability shall not be negated by the manner in which the invention was made.
Claims 1-4, 7-13, and 16-20 are rejected under 35 U.S.C. § 103 as being unpatentable over Gambella et al. (Gambella, Claudio, and Andrea Simonetto. "Multiblock ADMM heuristics for mixed-binary optimization on classical and quantum computers." IEEE Transactions on Quantum Engineering 1 (2020): 1-22, hereinafter Gambella) in view of Woerner et al. (U.S. Pat. App. Pub. No. 2020/0226197, hereinafter Woerner) and Campbell et al. (Campbell, Colin, and Edward Dahl. "QAOA of the highest order." In 2022 IEEE 19th International Conference on Software Architecture Companion (ICSA-C), pp. 141-146. IEEE, 2022, hereinafter Campbell).
As to independent claims 1, 10, and 19, Gambella teaches:
… a classical computation component that employs a quantum-classical hybrid algorithm to update one or more continuous variables in a… mixed integer programming (MIP) problem using classical optimization (Abstract, "continuous constrained convex subproblems (that can be solved cheaply with classical optimization solvers)"); and
a quantum computation component that employs the quantum-classical hybrid algorithm to update one or more binary variables in the… MIP problem using quantum optimization (Abstract, "the alternating direction method of multipliers (ADMM) can split the MBO into a binary unconstrained problem (that can be solved with quantum algorithms)").
Gambella does not appear to expressly teach a system, comprising: a memory that stores computer-executable components; and a processor that executes the computer-executable components stored in the memory, wherein the computer-executable components comprise.
Woerner teaches a system, comprising (Title and abstract): a memory that stores computer-executable components (Figure 1, memory 124 and 144); and a processor that executes the computer-executable components stored in the memory, wherein the computer-executable components comprise (Figure 1, classical processor 122 and quantum processor 142).
Therefore, it would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention, having the quantum binary subproblem of Gambella to include the hybrid classical-quantum techniques of Woerner to solve mixed integer optimization problems using a quantum computing system (see Woerner at paragraph 11).
Gambella does not appear to expressly teach higher-order.
Campbell teaches higher-order (Page 141, "utilizing higher order terms (HOTs) in QAOA").
Therefore, it would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention, having the quantum binary subproblem of Gambella to include the higher order QAOA techniques of Campbell to limit the introduction of more variables and interactions (see Campbell at page 141). .
As to dependent claims 2 and 11, Gambella further teaches the classical computation component updates the one or more continuous variables on a classical system by fixing the one or more binary variable (Page 2, "makes use of the ADMM operator-splitting procedure to devise a decomposition for certain classes of MBOs into the following", "2) a convex constrained subproblem, which can be efficiently solved with classical optimization solvers").
As to dependent claims 3 and 12, Gambella further teaches the quantum computation component updates the one or more binary variables on a quantum system by fixing the one or more continuous variables (Page 2, "makes use of the ADMM operator-splitting procedure to devise a decomposition for certain classes of MBOs into the following", "a QUBO subproblem to be solved by a QUBO (approximate) solver, e.g., on noisy quantum devices via quantum variational algorithms, such as VQE [11], QAOA [8], or with Grover-search-based algorithms [43], or quantum-based semidefinite programming (SDP) relaxations [44]").
As to dependent claims 4 and 13, Gambella further teaches a formulation component that formulates the higher-order MIP problem for applying an augmented Lagrange scheme (Page 2, "the objective function, as a soft-constraint in an augmented Lagrangian fashion").
As to dependent claims 7 and 16, Gambella further teaches employing the quantum-classical hybrid algorithm separates the higher-order MIP problem into a continuous optimization problem and a binary optimization problem (Abstract, "the alternating direction method of multipliers (ADMM) can split the MBO into a binary unconstrained problem (that can be solved with quantum algorithms), and continuous constrained convex subproblems (that can be solved cheaply with classical optimization solvers)").
As to dependent claims 8 and 17, Campbell further teaches a size of the binary optimization problem remains equal to a number of one or more binary variables in the higher-order MIP problem (Page 142, "higher order Ising formulations offer an opportunity to enrich the applications space for QAOA").
Therefore, it would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention, having the quantum binary subproblem of Gambella to include the higher order QAOA techniques of Campbell to limit the introduction of more variables and interactions (see Campbell at page 141). .
As to dependent claims 9 and 18, Gambella further teaches the binary optimization problem is solved using quantum algorithms and without introducing auxiliary binary variables (Page 2, "a QUBO subproblem to be solved by a QUBO (approximate) solver, e.g., on noisy quantum devices via quantum variational algorithms, such as VQE [11], QAOA [8], or with Grover-search-based algorithms [43], or quantum-based semidefinite programming (SDP) relaxations [44]").
As to dependent claim 20, Gambella further teaches update, by the processor, the one or more continuous variables on a classical system by fixing the one or more binary variables (Page 2, "makes use of the ADMM operator-splitting procedure to devise a decomposition for certain classes of MBOs into the following", "2) a convex constrained subproblem, which can be efficiently solved with classical optimization solvers"); and update, by the processor, the one or more binary variables on a quantum system by fixing the one or more continuous variables (Page 2, "makes use of the ADMM operator-splitting procedure to devise a decomposition for certain classes of MBOs into the following", "a QUBO subproblem to be solved by a QUBO (approximate) solver, e.g., on noisy quantum devices via quantum variational algorithms, such as VQE [11], QAOA [8], or with Grover-search-based algorithms [43], or quantum-based semidefinite programming (SDP) relaxations [44]").
Claims 5 and 14 are rejected under 35 U.S.C. § 103 as being unpatentable over Gambella in view of Woerner, Campbell, and Egger et al. (Egger, Daniel J., Jakub Mareček, and Stefan Woerner. "Warm-starting quantum optimization." Quantum 5 (2021): 479, hereinafter Egger).
As to dependent claims 5 and 14, the respective rejections of claims 1 and 10 are incorporated.
Gambella does not appear to expressly teach a precomputation component that selects a solution of a relaxation problem as an initial value used by the quantum-classical hybrid algorithm to solve the higher-order MIP problem.
Egger teaches a precomputation component that selects a solution of a relaxation problem as an initial value used by the quantum-classical hybrid algorithm to solve the higher-order MIP problem (Abstract, "warm-start quantum optimization with an initial state corresponding to the solution of a relaxation of a combinatorial optimization problem").
Therefore, it would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention, having the quantum binary subproblem of Gambella to include the warm-starting quantum optimization techniques of Egger to allow the quantum algorithm to inherit the performance guarantees of the classical algorithm (see Egger at abstract).
Claims 6 and 15 are rejected under 35 U.S.C. § 103 as being unpatentable over Gambella in view of Woerner, Campbell, Egger, and Bonami et al. (Bonami, Pierre. "On optimizing over lift-and-project closures." Mathematical Programming Computation 4, no. 2 (2012): 151-179, hereinafter Bonami).
As to dependent claims 6 and 15, the respective rejections of claims 5 and 14 are incorporated.
Woerner does not appear to expressly teach the precomputation component selects a result generated by applying a computationally cheap cut or lifting to a relaxed problem as the initial value.
Bonami teaches the precomputation component selects a result generated by applying a computationally cheap cut or lifting to a relaxed problem as the initial value (Abstract, "intersecting all strengthened lift-and-project cuts obtained from its initial formulation").
Therefore, it would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention, having the quantum binary subproblem of Gambella to include the optimization techniques of Bonami to optimize over the lift-and-project closure and approximate the value obtained by optimizing over the strengthened lift-and-project closure (see Bonami at page 152).
Citation of Pertinent Prior Art
The prior art made of record and not relied upon is considered pertinent to applicant's disclosure. You et al. (Int’l. Pat. App. Pub. No. WO-2021072221-A1) teaches technologies for a quantum/classical hybrid approach to solving optimization problems. An optimization problem is decomposed into two sub-problems. The first 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 calculation is continued until an end condition is met.
Conclusion
The prior art made of record and not relied upon is considered pertinent to Applicant's disclosure. Applicant is required under 37 C.F.R. § 1.111(c) to consider these references fully when responding to this action.
It is noted that any citation to specific pages, columns, lines, or figures in the prior art references and any interpretation of the references should not be considered to be limiting in any way. A reference is relevant for all it contains and may be relied upon for all that it would have reasonably suggested to one having ordinary skill in the art. In re Heck, 699 F.2d 1331, 1332-33, 216 U.S.P.Q. 1038, 1039 (Fed. Cir. 1983) (quoting In re Lemelson, 397 F.2d 1006, 1009, 158 U.S.P.Q. 275, 277 (C.C.P.A. 1968)).
Any inquiry concerning this communication or earlier communications from the examiner should be directed to Casey R. Garner whose telephone number is 571-272-2467. The examiner can normally be reached Monday to Friday, 8am to 5pm, Eastern Time.
If attempts to reach the examiner by telephone are unsuccessful, the examiner’s supervisor, Alexey Shmatov can be reached on 571-270-3428. The fax phone number for the organization where this application or proceeding is assigned is 571-273-8300.
Information regarding the status of an application may be obtained from Patent Center and the Private Patent Application Information Retrieval (PAIR) system. Status information for published applications may be obtained from Patent Center or Private PAIR. Status information for unpublished applications is available through Patent Center and Private PAIR to authorized users only. Should you have questions about access to the Private PAIR system, contact the Electronic Business Center (EBC) at 866-217-9197 (toll-free).
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) Form at https://www.uspto.gov/patents/uspto-automated- interview-request-air-form.
/Casey R. Garner/Primary Examiner, Art Unit 2123
Prosecution Insights