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 .
Specification
The disclosure is objected to because of the following informalities:
At [00129], the description of the vehicle routing method (method 1100 of FIG. 11) incorrectly states that, if no feasible vehicle routes are found, “the algorithms stops in block 908.” Block 908 belongs to the cellular manufacturing method (method 900 of FIG. 9). The correct block for the IQFP vehicle routing method is block 1108 as depicted in FIG. 11.
At [00132], the description of the vehicle routing method incorrectly refers to “the method 800” twice — “if the end condition is met, the method 800 proceeds to block 1120 to return the assigned vehicle routes” and “the method 800 loops back to block 1104 to resolve the QUBO problem.” Method 800 is the MILP job-shop scheduling method of FIG. 8; blocks 1104 and 1120 belong to method 1100. Both references should read “the method 1100.” Appropriate correction is required.
The specification is objected to as failing to provide proper antecedent basis for the claimed subject matter. See 37 CFR 1.75(d)(1) and MPEP § 608.01(o). Correction of the following is required: Independent claims 1, 15, and 18 each recite “each of the two or more sub-problems being associated with a disjoint subset of a plurality of variables.” The term “disjoint” (and “disjoint subset”) does not appear anywhere in the specification. The specification describes the sub-problem variable sets as being “different from” each other (e.g., paragraphs [0004] and [0013]) but does not use the term “disjoint” to characterize the relationship between them. Applicant is requested to amend the claims to recite language supported by the specification as filed.
Claim Rejections - 35 USC § 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 1-20 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.
Per claim 1, the claim recites the limitation "the first sub-problem" in the first wherein clause ("execution of the first algorithm for the first sub-problem on the classical computing device...") and in the second wherein clause ("execution of the second algorithm for the second sub-problem on the quantum computing device... of execution of the first algorithm for the first sub-problem on the classical computing device"). There is insufficient antecedent basis for the limitation "the first sub-problem" in the claim. No prior recitation of "a first sub-problem" appears in claim 1. The claim's performing limitation introduced "a first one of the two or more sub-problems" and "a second one of the two or more sub-problems," but not "a first sub-problem" or "a second sub-problem." The abbreviated shorthand "the first sub-problem" and "the second sub-problem" as used in the wherein clauses have no explicit antecedent introduction in the claim. Because a PHOSITA cannot determine with reasonable certainty whether "the first sub-problem" refers to any sub-problem that is first in some ordering, or specifically to "a first one of the two or more sub-problems" recited in the performing limitation, the claim is indefinite.
Claims 2-14 are rejected as being dependent upon the rejected base claim.
For purposes of examination, "the first sub-problem" is interpreted under BRI as referring to "a first one of the two or more sub-problems" introduced in claim 1's performing limitation, i.e., the sub-problem solved by the first algorithm on the classical computing device comprising a classical processor. "The second sub-problem" is interpreted as referring to "a second one of the two or more sub-problems," i.e., the sub-problem solved by the second algorithm on the quantum computing device comprising a quantum processor.
Per claim 15, the claim recites the limitation "the first sub-problem" and "the second sub-problem" in the first and second wherein clauses, in the same structural context as claim 1. The claim's performing step introduced "a first one of the two or more sub-problems" and "a second one of the two or more sub-problems," but not "a first sub-problem" or "a second sub-problem." There is insufficient antecedent basis for the limitations "the first sub-problem" and "the second sub-problem" in claim 15 for the same reasons as identified for claim 1 above.
Claims 16 and 17 are rejected as being dependent upon the rejected base claim.
For purposes of examination, "the first sub-problem" in claim 15 is interpreted under BRI as referring to "a first one of the two or more sub-problems" introduced in claim 15's performing step. "The second sub-problem" is interpreted as referring to "a second one of the two or more sub-problems."
Per claim 18, the claim recites the limitations "the first sub-problem" and "the second sub-problem" in the first and second wherein clauses, in the same structural context as claims 1 and 15. The claim's performing limitation introduced "a first one of the two or more sub-problems" and "a second one of the two or more sub-problems," but not "a first sub-problem" or "a second sub-problem." There is insufficient antecedent basis for these limitations in claim 18 for the same reasons as identified for claims 1 and 15 above.
Claims 19 and 20 are rejected as being dependent upon the rejected base claim.
For purposes of examination, "the first sub-problem" in claim 18 is interpreted under BRI as referring to "a first one of the two or more sub-problems" introduced in claim 18's performing limitation. "The second sub-problem" is interpreted as referring to "a second one of the two or more sub-problems."
Appropriate correction is required.
Claim Rejections - 35 USC § 103
Claims 1-7, 9, 10, 14-20 are rejected under 35 U.S.C. 103 as being unpatentable over Methods and Systems for Quantum Computing to US Pat. Pub. No. 2018/0091440 to Dadashikelayeh et al. (hereinafter Dadashikelayeh) in view of A Hybrid Quantum-Classical Approach to Solving Scheduling Problems to Tran et al. (hereinafter Tran).
Per claim 1, Dadashikelayeh discloses an apparatus (Dadashikelayeh: ¶[0094]-[0095]…Dadashikelayeh discloses an architecture configured to realize a hybrid quantum-enabled computing apparatus comprising an API gateway, an arbiter, a quantum-ready service, and a classical service, "The methods and systems described here may comprise an architecture configured to realize a cloud-based framework to provide hybrid quantum-enabled computing solutions to complex computational problems"), comprising:
at least one processing device comprising a processor coupled to a memory (Dadashikelayeh: ¶[0098] — arbiter implemented in a centralized or distributed classical processing environment; a PHOSITA would understand this comprises at least one processor coupled to a memory, "The arbiter 602 may comprise one or more intelligent algorithms operating in a centralized or distributed classical processing environment"); the at least one processing device being configured:
to identify an optimization problem (Dadashikelayeh: ¶[0093]…Dadashikelayeh expressly discloses the hybrid architecture addresses hard optimization problems, "A hybrid architecture of quantum-enabled computation can be very efficient for addressing complex computational tasks, such as hard optimization problems");
to decompose the identified optimization problem into two or more sub-problems, each of the two or more sub-problems being associated with a disjoint subset of a plurality of variables (Dadashikelayeh: ¶[0100]… intelligent algorithms model a feasible solution space as a search tree wherein each node decomposes an original computing problem into sub-problems with disjoint or overlapping sets of variables, "Each node of the tree may be used to decompose an original computing problem into corresponding sub-problems including disjoint or overlapping sets of variables"; ¶[0098]…"Breaking down (e.g., decomposing) a given problem into sub-problems");
to perform two or more iterations of (i) executing a first algorithm for a first one of the two or more sub-problems with a first subset of the plurality of variables on a classical computing device comprising a classical processor and (ii) executing a second algorithm for a second one of the two or more sub-problems with a second subset of the plurality of variables on a quantum computing device comprising a quantum processor (Dadashikelayeh: ¶[0098]…six-operation iterative workflow in which sub-problems are identified, distributed between a classical service and a quantum-ready service, solved on the respective service, and then the process iterates for the remaining portion of the reduced problem, "(1)Breaking down (e.g., decomposing) a given problem into sub-problems; (2) Identifying the sub-problems that can be solved using a quantum-ready service 603; (3) Distributing tasks between the classical and quantum-ready services 603 and 604, respectively, accordingly; (4) Collecting solutions of the sub-problems from the classical and quantum-ready services 603 and 604, respectively; (5) Reducing the original computational tasks using the collected solutions to sub-problems; (6) If the original problem is completely solved, the system may provide an indication of the solution and terminate; otherwise, the system may repeat operation (1) for the remaining portion of the reduced problem"); and
to determine a solution for the optimization problem based at least in part on results of execution of the first algorithm and the second algorithm in at least one of the two or more iterations (Dadashikelayeh: ¶[0098]…system reduces the original computational task using collected solutions from both classical and quantum-ready services and provides an indication of the solution upon completion, "(5) Reducing the original computational tasks using the collected solutions to sub-problems; (6) If the original problem is completely solved, the system may provide an indication of the solution and terminate; otherwise, the system may repeat operation (1) for the remaining portion of the reduced problem").
Dadashikelayeh does not expressly disclose, but with Tran does teach:
wherein, in each of at least a first subset of the two or more iterations, execution of the first algorithm for the first sub-problem on the classical computing device is based at least in part on at least one result from a previously completed one of the two or more iterations of execution of the second algorithm for the second sub-problem on the quantum computing device (Tran: pg. 100… Solving the subproblem, the classical subproblem solver receives the configuration x returned by the quantum annealer in the prior iteration of the master problem and uses that quantum result as input to evaluate the constraint and objective expression, "Using the returned quantum annealing configurations as input, the subproblem will calculate the expression (5) and send the result to the global tree manager to update to the correct values");
wherein, in each of at least a second subset of the two or more iterations, execution of the second algorithm for the second sub-problem on the quantum computing device is based at least in part on at least one result from a previously completed one of the two or more iterations of execution of the first algorithm for the first sub-problem on the classical computing device (Tran: pg. 101…to expand a partial-tree node already containing a partial configuration, the master problem (i.e., the QUBO submitted to the quantum annealer) is updated by fixing the variables x̄ that the classical tree manager has already set, with only the remaining variables x̂ left for the quantum annealer, "the QUBO is updated with x̄ and the rest of the decision variables x̂ are solved for in the master problem… the master problem and subproblem are solved again to create a new partial sub-tree and the process is repeated"; pg. 101…Algorithm 1…pseudocode confirms the bidirectional iteration in a while-loop, "while open nodes ≠ NULL do … Ψ = solve master problem(n) … solve subproblem(x) … build partial tree(Ψ)").
Dadashikelayeh and Tran are analogous art because they are both within the same field of endeavor, namely hybrid quantum-classical computational architectures for solving combinatorial and discrete optimization problems by decomposition. They address the same problem-solving area of overcoming current quantum-hardware size and connectivity limitations by partitioning a hard optimization problem so that some sub-problems are dispatched to a quantum processor and the remaining sub-problems are handled on a classical processor, with iterative coordination between the two. Dadashikelayeh expressly contemplates this very split, "a cloud-based framework to provide hybrid quantum-enabled computing solutions to complex computational problems (such as complex discrete optimization) using a classical computer for some portion of the work and a quantum (or quantum-like) computer (e.g., quantum-ready or quantum-enabled) for the remaining portion of the work" (Dadashikelayeh: ¶[0094]), and identifies that the arbiter "may decompose a given problem using an intelligent algorithm" with iterative repetition until the original problem is completely solved (Dadashikelayeh: ¶[0098]). Tran provides the seminal worked-out instance of that split in which the quantum annealer's prior-iteration result drives the classical subproblem solver and, conversely, the classical tree manager's prior-iteration result drives what variables are fixed for the next quantum-annealer call (Tran: pg. 100, Solving the subproblem; pg. 101 with Algorithm 1).
Before the effective filing date of the claimed invention, it would have been obvious to a person having ordinary skill in the art to combine Tran's bidirectional iteration in which the classical solver consumes prior-iteration quantum results and the quantum solver in turn consumes prior-iteration classical results, with Dadashikelayeh's hybrid quantum-classical decomposition apparatus that splits the original optimization problem into sub-problems with disjoint variable sets dispatched to a classical service and a quantum-ready service. Combining prior-art elements according to known methods to yield predictable results (KSR rationale (a)) applies because Tran's iterative master-subproblem feedback is the canonical mechanism by which Dadashikelayeh's arbiter "may repeat operation (1) for the remaining portion of the reduced problem" (Dadashikelayeh: ¶[0098]): a PHOSITA looking for a concrete realization of how to make Dadashikelayeh's iterate-until-solved loop converge would naturally adopt Tran's explicit pattern of feeding each side's prior result into the other side's next call (KSR rationale (g) — some teaching, suggestion, or motivation in the prior art — also applies, as Dadashikelayeh expressly invites further sub-problem refinement based on prior-iteration sub-solutions (Dadashikelayeh: ¶[0100], "Based on partial results of sub-problems received from the quantum or classical computing resources, the intelligent algorithms may be able to reduce the search tree by pruning certain nodes"), and Tran provides the working bidirectional protocol that realizes that invitation.
The suggestion/motivation for doing so would have been to enable Dadashikelayeh's hybrid quantum-classical apparatus to converge on a global solution despite current quantum-hardware limitations, by exploiting the complementary strengths of the quantum annealer (good at sampling the relaxed master problem) and the classical processor (good at enforcing constraints and objective evaluation on the returned configurations) — exactly the motivation Tran articulates: "Our framework takes advantage of the strength of quantum annealing dedicated quantum hardware, and complements it with classical processing to enable the entire algorithm to be complete" (Tran: page 98). The combination produces predictable results because each component (Dadashikelayeh's decomposition framework and Tran's master-subproblem feedback loop) was already shown to operate as claimed in its respective reference.
Per claim 2, Dadashikelayeh combined with Tran discloses claim 1. Dadashikelayeh with Tran further teaches the two or more iterations are performed until at least one designated end condition is reached (Tran: pg. 101…Conditions for Termination — iterative master-subproblem search continues until a designated end condition is reached, including either a feasible solution being found or the open node list being empty, "For decision problems, once a feasible solution has been found or the open node list is empty, the search is terminated. For optimization problems, the search is terminated as soon as the open node list is empty, indicating that all nodes have been either explored or pruned"; Dadashikelayeh: ¶[0098]…iteration terminates upon problem completion, "(6) If the original problem is completely solved, the system may provide an indication of the solution and terminate"). The rationale to combine Tran with Dadashikelayeh is the same as the parent claim.
Per claim 3, Dadashikelayeh combined with Tran discloses claim 2. Tran further teaches the at least one designated end condition comprises determining that a number of the two or more iterations which have been performed exceeds a designated iteration threshold (Tran: pg. 100 …."K anneals are performed and K̄ ≤ K unique configurations are returned" is a designated iteration-count threshold for terminating the inner anneal loop per master-problem call; Tran: pg. 101, Algorithm 1…bounded-queue tree search in which the open-node priority queue terminates when empty, which designated iteration threshold being the queue's bounded size as itself a counted iteration limit). The rationale to combine Tran with Dadashikelayeh is the same as the parent claim.
Per claim 4, Dadashikelayeh combined with Tran discloses claim 2. Tran further teaches the at least one designated end condition comprises one or more preset convergence criteria, the one or more preset convergence criteria being based at least in part on at least one of: a gap between a solution for the first sub-problem and a solution for the second sub-problem for a most recently completed one of the two or more iterations; and a gap between a first data value derived from the first sub-problem and a second data value derived from the solution for the second sub-problem for the most recently completed one of the two or more iterations (Tran: pg. 100-101…bounding-function check h(x̄) = minx̂ g(x̄) computed at each open node and a separate lower-bound calculation derived from the partial configuration's negative objective contributions, with pruning when the lower bound exceeds the incumbent solution objective, "we can also calculate a simple lower bound by instantiating all committed variables in the partial configuration, and then including the value of any negative terms in the objective function … open node (B) has a lower bound of 0, which is not pruned as the current incumbent is 3"). The rationale to combine Tran with Dadashikelayeh is the same as the parent claim.
Per claim 5, Dadashikelayeh combined with Tran discloses claim 2. Tran combined with Dadashikelayeh further teaches the at least one designated end condition comprises one or more preset convergence criteria, the one or more preset convergence criteria being based at least in part on determining that an improvement of at least one of a solution for the first sub-problem and a solution for the second sub-problem in a designated number of most recently completed ones of the two or more iterations is less than a designated improvement threshold (Tran: pg. 100-101…bounding test prunes a node whenever the lower bound is no better than the current incumbent solution, i.e., whenever the candidate sub-solution provides no improvement over the most recent incumbent, "to remove partial configurations that would lead to sub-optimal solutions when the bounding function on the objective is greater than the current incumbent solution objective"). The rationale to combine Tran with Dadashikelayeh is the same as the parent claim.
Per claim 6, Dadashikelayeh combined with Tran discloses claim 1. Dadashikelayeh further discloses the at least one processing device is implemented at least in part internally to at least one of the classical computing device and the quantum computing device (Dadashikelayeh: ¶[0098]…arbiter (i.e., the at least one processing device) is implemented in a classical processing environment that operates as part of the cloud-based hybrid system together with the classical service 604, "The arbiter 602 may comprise one or more intelligent algorithms operating in a centralized or distributed classical processing environment").
Per claim 7, Dadashikelayeh combined with Tran discloses claim 1. Tran further teaches in at least a given one of the two or more iterations: said at least one result from the previously completed one of the two or more iterations of execution of the second algorithm for the second sub-problem on the quantum computing device is utilized as a parameter for the first sub-problem; and said at least one result from the previously completed one of the two or more iterations of execution of the first algorithm for the first sub-problem on the classical computing device is utilized as a parameter for the second sub-problem (Tran: pg. 100…Solving the subproblem, where prior-iteration quantum-annealer configuration x is supplied to the classical subproblem solver as the input parameter on which the constraint/objective expression is evaluated, "Using the returned quantum annealing configurations as input, the subproblem will calculate the expression (5)"; Tran: pg. 101… to expand an open node, the QUBO of the master problem is updated by fixing the partial configuration x̄ already determined by the classical tree manager and only x̂ is left to the quantum annealer, "the QUBO is updated with x̄ and the rest of the decision variables x̂ are solved for in the master problem"). The rationale to combine Tran with Dadashikelayeh is the same as the parent claim.
Per claim 9, Dadashikelayeh combined with Tran discloses claim 1. Tran further teaches said at least one result from the previously completed one of the two or more iterations of execution of the first algorithm for the first sub-problem on the classical computing device comprises one of an upper bound and a lower bound on at least one objective of the optimization problem; and said at least one result from the previously completed one of the two or more iterations of execution of the second algorithm for the second sub-problem on the quantum computing device comprises the other one of the upper bound and the lower bound on the at least one objective of the optimization problem (Tran: pg. 101…classical subproblem computes a lower bound on the objective function of each open node based on its partial configuration, while the quantum annealer's returned feasible configurations supply candidate incumbent solutions that establish upper bounds on the objective, "a simple lower bound by instantiating all committed variables in the partial configuration … open node (B) has a lower bound of 0, which is not pruned as the current incumbent is 3”; pg. 100…” Where a configuration x* is feasible, i.e., C(x*) = 0, the true objective function f(x*) is presented in brackets below the node"). The rationale to combine Tran with Dadashikelayeh is the same as the parent claim.
Per claim 10, Dadashikelayeh combined with Tran discloses claim 1. Tran combined with Dadashikelayeh further teaches at least one of (i) said at least one result from the previously completed one of the two or more iterations of execution of the first algorithm for the first sub-problem and (ii) said at least one result from the previously completed one of the two or more iterations of execution of the second algorithm for the second sub-problem comprises at least one of an integer cut, a cutting plane, a partial optimal solution for the optimization problem, an optimal solution for the optimization problem, and a feasible optimal solution for the optimization problem (Tran: page 100-101…classical subproblem evaluates feasibility of the quantum-returned configurations and the global tree manager prunes infeasible/sub-optimal partial configurations from the search tree, which constitutes a partial optimal solution and/or a feasible optimal solution, " pg. 100…”Where a configuration x* is feasible, i.e., C(x*) = 0, the true objective function f(x*) is presented in brackets below the node"; Tran: page 101…next quantum master problem is constrained by the partial configuration x̄ already fixed (a cutting-plane-style restriction on the QUBO), which constitutes a cutting plane and/or an integer cut, "the QUBO is updated with x̄ and the rest of the decision variables x̂ are solved for in the master problem"). The rationale to combine Tran with Dadashikelayeh is the same as the parent claim.
Per claim 14, Dadashikelayeh combined with Tran discloses claim 1. Tran further teaches the second algorithm comprises a quadratic unconstrained binary optimization (QUBO) problem solver (Tran: pg. 99…quantum annealer minimizes QUBO problems and that an application problem must be mapped to a QUBO to be solved on the quantum annealer, "A quantum annealer minimizes Quadratic Unconstrained Binary Optimization (QUBO) problems of the form C(x) = Σ ci xi + Σ ci,j xi xj … An application problem must be mapped to a QUBO problem to be solved on a quantum annealer"). The rationale to combine Tran with Dadashikelayeh is the same as the parent claim.
Claims 15-17 and 18-20 are substantially similar in scope and spirit to claims 1, 9 and 10. Claim 15 is a method claim and claim 18 is a computer program product claim each reciting the same operational steps recited in claim 1 (identifying, decomposing, performing iterations, determining a solution) plus the bidirectional iteration limitations of the wherein clauses; Dadashikelayeh expressly discloses both a method (¶[0093]-[0100]) and a non-transitory computer-readable storage medium implementing the disclosed framework (Dadashikelayeh: ¶[0028] — "a non-transitory computer-readable storage medium for storing computer-executable instructions which, when executed, cause a digital computer to perform arithmetic and logical operations"). Claims 16 and 19 recite the same upper-bound/lower-bound limitation as claim 9. Claims 17 and 20 recite the same integer-cut/cutting-plane/partial-solution limitation as claim 10. Therefore the rejections of claims 1, 9 and 10 are applied accordingly.
Allowable Subject Matter
Claims 8, 11, 12 and 13 would be allowable if rewritten to overcome the rejection(s) under 35 U.S.C. 112 set forth in this Office action and to include all of the limitations of the base claim and any intervening claims.
The following is the statement of reasons for the indication of allowable subject matter: The prior art disclosed by the applicant and cited by the Examiner fail to teach or suggest, alone or in combination, all the limitations of the independent claim 1, further including the particular notable limitations provided below:
Claim 8: decomposing the identified optimization problem into the two or more sub-problems comprises decomposing the identified optimization problem such that: the first subset of the plurality of variables associated with the first sub-problem to be solved by the classical computing device comprises more continuous variables than discrete variables; and the second subset of the plurality of variables associated with the second sub-problem to be solved by the quantum computing device comprises one of (i) more discrete variables than continuous variables and (ii) all discrete variables and no continuous variables.
Claim 11: the optimization problem comprises a job scheduling problem, and wherein the first algorithm comprises a relaxed mixed-integer linear programming (MILP) solver configured to solve a MILP problem.
Claim 12: the optimization problem comprises a manufacturing problem, and wherein the first algorithm comprises a dual linear programming (LP) solver configured to solve a LP problem.
Claim 13: the optimization problem comprises a vehicle routing problem, and wherein the first algorithm comprises an operation for assigning a value to a parameter of an integer quadratic fractional program (IQFP) problem.
Conclusion
Any inquiry concerning this communication or earlier communications from the examiner should be directed to ALAN CHEN whose telephone number is (571)272-4143. The examiner can normally be reached M-F 10-7.
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, Kamran Afshar can be reached at (571) 272-7796. 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.
/ALAN CHEN/Primary Examiner, Art Unit 2125
Prosecution Insights