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 Non-final and is in response to the claims filed 01/14/2022. Claims 1-20 are currently pending, of which claims 1-20 are currently rejected.
Drawings
The drawings are objected to because Figure 1 discloses a “Classical Comptuer Program 125”, when it should read “Classical Computer Program 125”. Corrected drawing sheets in compliance with 37 CFR 1.121(d) are required in reply to the Office action to avoid abandonment of the application. Any amended replacement drawing sheet should include all of the figures appearing on the immediate prior version of the sheet, even if only one figure is being amended. The figure or figure number of an amended drawing should not be labeled as “amended.” If a drawing figure is to be canceled, the appropriate figure must be removed from the replacement sheet, and where necessary, the remaining figures must be renumbered and appropriate changes made to the brief description of the several views of the drawings for consistency. Additional replacement sheets may be necessary to show the renumbering of the remaining figures. Each drawing sheet submitted after the filing date of an application must be labeled in the top margin as either “Replacement Sheet” or “New Sheet” pursuant to 37 CFR 1.121(d). If the changes are not accepted by the examiner, the applicant will be notified and informed of any required corrective action in the next Office action. The objection to the drawings will not be held in abeyance.
Claim Rejections - 35 USC § 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 they are directed to an abstract idea without significantly more.
Apparatus claims 11-20 will be addressed before corresponding method claims 1-10.
Regarding Claim 11, at Step 1 the claim is directed to a method, which is a statutory category of
invention.
At Step 2A, Prong 1, Examiner notes that the claims are directed to mathematical concepts:
A system, comprising:
a classical computer comprising:
a memory storing a classical computer program; and
a computer processor; and
a quantum computer;
wherein:
the classical computer program receives a branch and bound problem comprising a root, a depth, a maximum cost, a failure probability, an approximation margin, and a heuristic function that is depth based or cost based (mathematical calculations/relationships);
the classical computer program sets an upper bound, a value best bound, a value incumbent, and a counter i (mathematical relationships);
the classical computer program executes a subtree estimation procedure with the root, a value 2i, a BRANCH function, a COST function, the depth, the failure probability, the approximation margin, and the heuristic function, wherein the subtree estimation procedure returns value branch_m that represents a tree of size m with minimal value for the heuristic function (mathematical relationships/calculations);
the classical computer program determines a value branch_i and a value cost_i based on branch_m (mathematical relationships/calculations);
the classical computer program sets a variable cost_feas to a value COST(N) for feasible nodes N, and to +∞ for unfeasible nodes (mathematical relationships/calculations);
the classical computer program instructs the quantum computer to execute a QuantumMinimumLeaf procedure with the value branch_i, the value COST(N), the depth, the maximum cost, the failure probability, and the approximation margin (mathematical relationships/calculations);
the quantum computer executes the QuantumMinimumLeaf procedure and returns a node N (mathematical calculations);
the classical computer program sets a value incumbent' to equal to the value COST(N) (mathematical relationships);
the classical computer program instructs the quantum computer to execute the QuantumMinimumLeaf procedure with branch_i, cost_i, the depth, the maximum cost, the failure probability, and the approximation margin (mathematical relationships/calculations);
the quantum computer executes the QuantumMinimumLeaf procedure and returns a node N' (mathematical calculations);
the classical computer program sets a value best bound' to equal COST(N') (mathematical relationships); and
returning, by the classical computer program, the node N when an absolute value of a difference between a minimum of the value incumbent and the value incumbent' and a minimum of the value best bound and the value best bound' is less than the approximation margin (mathematical calculations/relationships).
At Step 2A Prong 2, the additional element is bolded above. This additional elements are merely
an “apply it” scenario using generically recited computer components. See MPEP 2106.05 (f).
The “A system, comprising: a classical computer comprising: a memory storing a classical computer program; and a computer processor” limitation simply uses generic computer components to perform the mathematical relationships/calculations (branch and bound problem). The “the classical computer program sets”, “the classical computer program executes”, “the classical computer program determines”, and “returning, by the classical computer program” limitations simply uses the generic program in the generic computer to perform the mathematical relationships/calculations (setting values to be used in the branch and bound problem, executing subtree estimation procedure, determining values based on branch value, and returning the result of an absolute value difference). Alternatively, even if not considered as merely an ”apply it” scenario, this type of architecture of a classical computer using a memory to store a program is well understood routine and conventional. See Step 2B analysis below.
Additionally, the italicized limitation “the classical computer program instructs the quantum computer to execute” above is merely an additional element that is generally linking the use of the judicial exception to a particular technological environment or a field of use. Examples of limitations that the courts have described as merely indicating a field of use or technological environments in which to apply a judicial exception include, as discussed in MPEP 2106.05(h):
iv. Specifying that the abstract idea of monitoring audit log data relates to transactions or activities that are executed in a computer environment, because this requirement merely limits the claims to the computer field, i.e., to execution on a generic computer, FairWarning v. Iatric Sys., 839 F.3d 1089, 1094-95, 120 USPQ2d 1293, 1295 (Fed. Cir. 2016); and
vi. Limiting the abstract idea of collecting information, analyzing it, and displaying certain results of the collection and analysis to data related to the electric power grid, because limiting application of the abstract idea to power-grid monitoring is simply an attempt to limit the use of the abstract idea to a particular technological environment, Electric Power Group, LLC v. Alstom S.A., 830 F.3d 1350, 1354, 119 USPQ2d 1739, 1742 (Fed. Cir. 2016);
At Step 2B, there are no additional elements claimed that amount to significantly more than the recited judicial exception. Regarding the architecture of the system, this is a well understood routine and conventional architecture known to be used in generic computers. As per the book “Computer Organization and Design: The Hardware/Software Interface, Chapter 1: Computer Abstractions and Technology”, “The memory is where the programs are kept when they are running; it also contains the data needed by the running programs.” (Page 20, Third paragraph), and “The processor is the active part of the board, following the instructions of a program to the letter. It adds numbers, tests numbers, signals I/O devices to activate, and so on” (Page 20, Fourth paragraph). These limitations therefore remain insignificant extra-solution activity even upon consideration. Thus, these limitations do not amount to significantly more.
Claim 12 is directed to the mathematical concept of estimating the depth and maximum cost (mathematical calculations). Under Steps 2A prong 2 and 2B, the claim does not recite any additional elements that integrate the abstract idea into a practical application nor do they amount to significantly more than the judicial exception.
Claim 13 is directed to the mathematical concept of estimating the depth and maximum cost using a highest price (mathematical calculations/relationships). Under Steps 2A prong 2 and 2B, the claim does not recite any additional elements that integrate the abstract idea into a practical application nor do they amount to significantly more than the judicial exception.
Claim 14 is directed to the mathematical concept of executing the subtree estimation procedure (mathematical calculations). Under Steps 2A prong 2 and 2B, the claim does not recite any additional elements that integrate the abstract idea into a practical application nor do they amount to significantly more than the judicial exception.
Claim 15 is directed to the mathematical concept of executing the subtree estimation procedure for each node (mathematical calculations/relationships). Under Steps 2A prong 2 and 2B, the claim does not recite any additional elements that integrate the abstract idea into a practical application nor do they amount to significantly more than the judicial exception.
Claim 16 is directed to the mathematical concept of executing the subtree estimation procedure by executing a quantum tree size procedure (mathematical calculations/relationships). As explained in the Step 2A prong 2 analysis of claim 11, instructing a quantum computer to perform mathematical calculations is merely an additional element that is generally linking the use of the judicial exception to a particular technological environment or a field of use. At Step 2B, the additional elements do not, alone or in combination, amount to significantly more than the recited judicial exception.
Claim 17 is directed to the mathematical concept of the subtree estimation procedure returning values (mathematical calculations/relationships). Under Steps 2A prong 2 and 2B, the claim does not recite any additional elements that integrate the abstract idea into a practical application nor do they amount to significantly more than the judicial exception.
Claim 18 is directed to the mathematical concept of the subtree estimation procedure estimating a tree size based on a wanted cost (mathematical calculations/relationships). Under Steps 2A prong 2 and 2B, the claim does not recite any additional elements that integrate the abstract idea into a practical application nor do they amount to significantly more than the judicial exception.
Claim 19 is directed to the mathematical concept of executing the subtree estimation procedure by executing a quantum tree size procedure (mathematical calculations/relationships). As explained in the Step 2A prong 2 analysis of claim 11, instructing a quantum computer to perform mathematical calculations is merely an additional element that is generally linking the use of the judicial exception to a particular technological environment or a field of use. At Step 2B, the additional elements do not, alone or in combination, amount to significantly more than the recited judicial exception.
Claim 20 is directed to the mathematical concept of repeating a branch and bound process disclosed in claim 11 and increasing a count value(mathematical calculations/relationships). As explained in the Step 2A prong 2 analysis of claim 11, instructing a quantum computer to perform mathematical calculations is merely an additional element that is generally linking the use of the judicial exception to a particular technological environment or a field of use. At Step 2B, the additional elements do not, alone or in combination, amount to significantly more than the recited judicial exception.
Claim 1 is a method version of the apparatus of claim 11 and is rejected for at least the same
reasons therein. Herein, Claim 1 is directed towards the statutory category of a method, thus also satisfying Step 1. At Step 2A prong 2, as discussed in method claims 1-17, none of the additional elements regarding the generic computer components (i.e., classical computer program, computer processor) are more than high level generic computer components that amount to mere instructions to apply the abstract idea on a generic computer. See MPEP 2106.05(f). As explained in the Step 2A prong 2 analysis of claim 11, instructing a quantum computer to perform mathematical calculations is merely an additional element that is generally linking the use of the judicial exception to a particular technological environment or a field of use. At Step 2B, the additional elements do not, alone or in combination, amount to significantly more than the recited judicial exception.
With regards to Claims 2-10, they are method version of the claimed system (claims 12-20, respectively). They are rejected for the same reasons as claims 12-20.
Allowable Subject Matter
Claims 1-20 would be allowable if rewritten to overcome the 35 U.S.C. 101 rejections discussed above.
The following is a statement of reasons for the indication of allowable subject matter:
Ashley Montanaro in NPL: “Quantum speedup of branch-and-bound algorithms” (https://arxiv.org/pdf/1906.10375), hereinafter “Montanaro” – teaches a quantum branch-and-bound algorithm that speeds up classical branch-and-bound algorithms. Montanaro further teaches the algorithm finding the minimal-cost valid solution using variables representing depth of the tree d, minimal cost Cmin of a valid solution, the size of the truncated tree Tmin with cost bound Cmin, a maximum cost Cmax, a large constant value K, and a failure parameter. See Pages 2-3 and Algorithm 2. Quantum branch-and-bound algorithm with failure parameter. Montanaro does not teach or suggest a classical computer receiving a heuristic function, the classical computer setting an upper bound, a value best bond, a value incumbent, and a counter, using a quantum computer to return a node to set incumbent values and best bond values, and the solution being the absolute difference of the minimum incumbent value and the minimum best bound value. Instead, Montanaro disclosed implementing a quantum algorithm for finding the minimal cost using only the variables listed above, and does not teach using a hybrid system using classical and quantum computers to solve this algorithm. Therefore, Montanaro does not teach or suggest the combination of claim 11, including the limitations of “a classical computer … a quantum computer; wherein: the classical computer program receives a branch and bound problem comprising a root, a depth, a maximum cost, a failure probability, an approximation margin, and a heuristic function that is depth based or cost based; the classical computer program sets an upper bound, a value best bound, a value incumbent, and a counter i;” and “the classical computer program instructs the quantum computer to execute a QuantumMinimumLeaf procedure with the value branch_i, the value COST(N), the depth, the maximum cost, the failure probability, and the approximation margin; the quantum computer executes the QuantumMinimumLeaf procedure and returns a node N; the classical computer program sets a value incumbent' to equal to the value COST(N); the classical computer program instructs the quantum computer to execute the QuantumMinimumLeaf procedure with branch_i, cost_i, the depth, the maximum cost, the failure probability, and the approximation margin; the quantum computer executes the QuantumMinimumLeaf procedure and returns a node N'; the classical computer program sets a value best bound' to equal COST(N'); and returning, by the classical computer program, the node N when an absolute value of a difference between a minimum of the value incumbent and the value incumbent' and a minimum of the value best bound and the value best bound' is less than the approximation margin.”
Delling et al. (U.S. Patent Application No.: US 20120254597 A1), hereinafter “Delling” – teaches a distributed data-parallel execution (DDPE) system that splits a computational problem into a plurality of sub-problems using a branch-and-bound algorithm. Delling further teaches the branch-and-bound algorithm reclusively executing: “(i) branch one node (or problem) into several smaller and computationally-easier nodes (sub-problems) and (ii) bound (or prune) the search tree when either the problem has become easy enough to directly solve or when it can be proven that the node (and, by implication, its descendants) cannot contribute to the optimal solution”, and further teaches finding the best solution of the nodes referred to as “incumbent”, using upper and/or lower bounds, using maximum lower bounds, and using heuristic determination. See ¶0020-0053 and Fig. 3A. Delling does not teach or suggest a classical computer receiving a heuristic function, the classical computer setting an upper bound, a value best bond, a value incumbent, and a counter, using a quantum computer to return a node to set incumbent values and best bond values, and the solution being the absolute difference of the minimum incumbent value and the minimum best bound value. Instead, Delling teaches implementing a branch-and-bound algorithm using a multiprocessor computer. Therefore, Delling does not teach or suggest the combination of claim 11, including the limitations of “a classical computer … a quantum computer; wherein: the classical computer program receives a branch and bound problem comprising a root, a depth, a maximum cost, a failure probability, an approximation margin, and a heuristic function that is depth based or cost based; the classical computer program sets an upper bound, a value best bound, a value incumbent, and a counter i;” and “the classical computer program instructs the quantum computer to execute a QuantumMinimumLeaf procedure with the value branch_i, the value COST(N), the depth, the maximum cost, the failure probability, and the approximation margin; the quantum computer executes the QuantumMinimumLeaf procedure and returns a node N; the classical computer program sets a value incumbent' to equal to the value COST(N); the classical computer program instructs the quantum computer to execute the QuantumMinimumLeaf procedure with branch_i, cost_i, the depth, the maximum cost, the failure probability, and the approximation margin; the quantum computer executes the QuantumMinimumLeaf procedure and returns a node N'; the classical computer program sets a value best bound' to equal COST(N'); and returning, by the classical computer program, the node N when an absolute value of a difference between a minimum of the value incumbent and the value incumbent' and a minimum of the value best bound and the value best bound' is less than the approximation margin.”
David R. Morrison in NPL: “Branch-and-bound algorithms: A survey of recent advances in
searching, branching, and pruning” (https://www.sciencedirect.com/science/article/pii/S1572528616000062), hereinafter “Morrison” – teaches a branch-and-bound algorithm for solving optimization problems. Morrison further teaches the algorithm using variables representing search depth d, branching factor b, root T, and subsets S representing nodes to determine x (incumbent solution). Morrison does not teach or suggest a classical computer receiving a heuristic function, the classical computer setting an upper bound, a value best bond, a value incumbent, and a counter, using a quantum computer to return a node to set incumbent values and best bond values, and the solution being the absolute difference of the minimum incumbent value and the minimum best bound value. Instead, Morrison teaches a branch-and-bound algorithm to find the optimal incumbent solution, and is silent on implementing it in any quantum system or hybrid system to find this solution. Therefore, Morrison does not teach or suggest the combination of claim 11, including the limitations of “a classical computer … a quantum computer; wherein: the classical computer program receives a branch and bound problem comprising a root, a depth, a maximum cost, a failure probability, an approximation margin, and a heuristic function that is depth based or cost based; the classical computer program sets an upper bound, a value best bound, a value incumbent, and a counter i;” and “the classical computer program instructs the quantum computer to execute a QuantumMinimumLeaf procedure with the value branch_i, the value COST(N), the depth, the maximum cost, the failure probability, and the approximation margin; the quantum computer executes the QuantumMinimumLeaf procedure and returns a node N; the classical computer program sets a value incumbent' to equal to the value COST(N); the classical computer program instructs the quantum computer to execute the QuantumMinimumLeaf procedure with branch_i, cost_i, the depth, the maximum cost, the failure probability, and the approximation margin; the quantum computer executes the QuantumMinimumLeaf procedure and returns a node N'; the classical computer program sets a value best bound' to equal COST(N'); and returning, by the classical computer program, the node N when an absolute value of a difference between a minimum of the value incumbent and the value incumbent' and a minimum of the value best bound and the value best bound' is less than the approximation margin.”
Disclosure by applicant of aspects of the claimed invention:
NPL “Universal Quantum Speedup for Branch-and-Bound, Branch-and-Cut, and Tree-Search Algorithms” (https://arxiv.org/pdf/2210.03210)
Conclusion
Any inquiry concerning this communication or earlier communications from the examiner should be directed to CARLOS H DE LA GARZA whose telephone number is (571)272-0474. The examiner can normally be reached Monday-Friday 9:30AM-6PM.
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, Andrew Caldwell can be reached at (571) 272-3702. 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.
/C.H.D./
Carlos H. De La Garza (571)272-0474
/EMILY E LAROCQUE/ Primary Examiner, Art Unit 2182
Prosecution Insights