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 .
Claims 1-20 are presented for examination.
Information Disclosure Statement
The information disclosure statements (IDS) submitted on May 16th and 17th in 2024 are in compliance with the provisions of 37 CFR 1.97. Accordingly, the information disclosure statements are being considered by the examiner.
Claim Objections
Claims 5-6, 8, and 11-20 are objected to because of the following informalities:
Claim 11 recites the limitation "inputting the set of patterns to a classical solver, wherein the solver generates and outputs a solution to the problem". The claim should be changed from “the solver” to “the classical solver”. Claims 12-20 are also objected to because the claims are directly or indirectly dependent on the base claim 11.
Claims 5-6, 8, 15-16, and 18 recite the limitation “the patterns”. The limitations should be changed from “the patterns” to “the set of patterns” or “the patterns of the set”.
Appropriate correction is required.
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 the claimed invention is directed to an
abstract idea without significantly more.
Claim 1
Step 1: The claim recites a method; therefore, it is directed to the statutory category of a process.
Step2A Prong 1: The claim recites:
performing pattern mining extraction on the pool of solutions to generate a set of patterns: This limitation encompasses a mathematical concept because it involves using algorithm(s) to perform the pattern mining. See paragraph 16 of the instant specification which states, “Pattern mining may be performed to find common structures in transactional datasets… Apriori is an example of an algorithm employed to mine patterns. However, Apriori can require longer running times for datasets with a large number of unique items. In one example, FP-Max and FP-Growth may be used to perform the data mining task.”
generating a pool of solutions to a problem: This limitation encompasses a mental process because it involves the evaluation/judgement/opinion to generate a pool of solutions to a problem, which can be performed mentally or by pen and paper.
the … solver generates and outputs a solution to the problem: This limitation recites a mental process because it involves the evaluation/judgement/opinion to generate a solution to a problem, which can be performed mentally or by pen and paper.
Step2A Prong 2: This judicial exception is not integrated into a practical application because the
additional elements are as follows:
…by a quantum computing system: Adding the words “apply it” (or an equivalent) with the judicial exception, or mere instructions to implement an abstract idea on a computer, or merely uses a computer as a tool to perform an abstract idea (MPEP 2106.05(f)).
inputting the set of patterns to a classical solver: Mere data gathering recited at a high level of generality, and thus is an insignificant extra-solution activity (MPEP 2106.05(g)).
wherein the classical solver…: Adding the words “apply it” (or an equivalent) with the judicial exception, or mere instructions to implement an abstract idea on a computer, or merely uses a computer as a tool to perform an abstract idea (MPEP 2106.05(f)).
Step 2B: The claim does not include additional elements that are sufficient to amount to significantly
more than the judicial exception because the additional elements are as follows:
…by a quantum computing system: Adding the words “apply it” (or an equivalent) with the judicial exception, or mere instructions to implement an abstract idea on a computer, or merely uses a computer as a tool to perform an abstract idea and cannot provide inventive concept (MPEP 2106.05(f)).
inputting the set of patterns to a classical solver: The additional element of “inputting” does not integrate the abstract idea into a practical application because it does not impose any meaningful limits on practicing the abstract idea. As discussed above with respect to integration of the abstract idea into a practical application, the additional element of receiving steps amounts to no more than mere data gathering. This element amounts to receiving data over a network and are well-understood, routine, conventional activity. See MPEP 2106.05(d), subsection II (i). This cannot provide an inventive concept.
wherein the classical solver…: Adding the words “apply it” (or an equivalent) with the judicial exception, or mere instructions to implement an abstract idea on a computer, or merely uses a computer as a tool to perform an abstract idea and cannot provide inventive concept (MPEP 2106.05(f)).
The elements in combination as an ordered whole still do not amount to significantly more than the judicial exception (i.e., the abstract idea of a mathematical concept for solving combinatorial optimization problems via pattern mining). The claim merely describes a process of applying known pattern mining techniques (Apriori, FP-Growth, FP-Max) on outputs from a generic quantum computing system, then performing standard data processing steps (inputting patterns to a solver). The recitation of a quantum computing system and a classical solver merely indicates a technological environment in which the abstract ideas are applied, without improving the functioning of either computer system or the field of quantum or classical computing itself.
Therefore, the claim as a whole remains focused on the abstract idea and fails Step 2B of the eligibility analysis.
Claim 2
Step 1: A process, as above.
Step2A Prong 1: This claim does not recite any abstract ideas, but the claim depends on claim 1, which recites an abstract idea.
Step2A Prong 2: This judicial exception is not integrated into a practical application because the
additional elements are as follows:
receiving the problem at the quantum computing system: Mere data gathering recited at a high level of generality, and thus is an insignificant extra-solution activity (MPEP 2106.05(g)).
wherein the quantum computing system comprises a quantum annealer and the problem comprises a combinatorial optimization problem in a format configured for the quantum annealer: Adding the words “apply it” (or an equivalent) with the judicial exception, or mere instructions to implement an abstract idea on a computer, or merely uses a computer as a tool to perform an abstract idea (MPEP 2106.05(f)).
Step 2B: The claim does not include additional elements that are sufficient to amount to significantly
more than the judicial exception because the additional elements are as follows:
receiving the problem at the quantum computing system: The additional element of “receiving” does not integrate the abstract idea into a practical application because it does not impose any meaningful limits on practicing the abstract idea. As discussed above with respect to integration of the abstract idea into a practical application, the additional element of receiving steps amounts to no more than mere data gathering. This element amounts to receiving data over a network and are well-understood, routine, conventional activity. See MPEP 2106.05(d), subsection II (i). This cannot provide an inventive concept.
wherein the quantum computing system comprises a quantum annealer and the problem comprises a combinatorial optimization problem in a format configured for the quantum annealer: Adding the words “apply it” (or an equivalent) with the judicial exception, or mere instructions to implement an abstract idea on a computer, or merely uses a computer as a tool to perform an abstract idea and cannot provide inventive concept (MPEP 2106.05(f)).
Even when considered in combination, these additional elements represent mere instructions to apply
an exception and therefore do not provide an inventive concept. The claim is ineligible.
Claim 3
Step 1: A process, as above.
Step2A Prong 1: The claim recites:
converting the combinatorial optimization problem to a QUBO format: This limitation recites a mathematical concept because it involves reformulating a problem’s constraints into a quadratic polynomial expression.
Step 2A Prong Two and Step 2B: The claim does not include additional elements that are sufficient to amount to significantly more than the judicial exception under step 2B. Thus, the judicial exception is not integrated into a practical application (see MPEP 2106.04(d) I.), failing step 2A prong 2. The claim is ineligible.
Even when considered in combination, these additional elements represent mere instructions to apply
an exception and therefore do not provide an inventive concept. The claim is ineligible.
Claim 4
Step 1: A process, as above.
Step2A Prong 1: This claim does not recite any abstract ideas, but the claim depends on claim 2 that depends on base claim 1, which recites an abstract idea.
Step2A Prong 2: This judicial exception is not integrated into a practical application because the
additional elements are as follows:
the pool of solutions from the quantum annealer comprise energy states that are converted to solutions: Insignificant extra-solution activity as the limitation amounts to necessary data outputting (MPEP 2106.05(g)(3)).
Step 2B: The claim does not include additional elements that are sufficient to amount to significantly
more than the judicial exception because the additional elements are as follows:
the pool of solutions from the quantum annealer comprise energy states that are converted to solutions: Insignificant extra-solution as the limitation amounts to necessary data outputting (MPEP 2106.05(g)(3)). This falls under Well-Understood, Routine, Conventional activity -see MPEP 2106.05(d)(II)(vi).
Even when considered in combination, these additional elements represent mere instructions to apply
an exception and therefore do not provide an inventive concept. The claim is ineligible.
Claim 5
Step 1: A process, as above.
Step2A Prong 1: The claim recites:
selecting the patterns from a reduced pool of solutions: This limitation encompasses a mental process of evaluation/judgement/opinion to identify and select patterns from a group of solutions, which can be performed mentally and/or with a pen and paper.
wherein the pool of solutions is reduced based on solution cost value or energy level or wherein the pool of solutions is reduced using Maximal frequent patterns: This limitation recites a mathematical concept because it involves ranking and filtering a set of mathematical objects (candidate solutions) using Maximal frequent patterns, which is a mathematical evaluation operation performed on numerical data. See Paragraph 47 of the instant specification which states, “…the pool of solutions is reduced based on solution cost value or energy level or wherein the pool of solutions is reduced using Maximal frequent patterns.”
Step 2A Prong Two and Step 2B: The claim does not include additional elements that are sufficient to amount to significantly more than the judicial exception under step 2B. Thus, the judicial exception is not integrated into a practical application (see MPEP 2106.04(d) I.), failing step 2A prong 2. The claim is ineligible.
Even when considered in combination, these additional elements represent mere instructions to apply
an exception and therefore do not provide an inventive concept. The claim is ineligible.
Claim 6
Step 1: A process, as above.
Step2A Prong 1: The claim recites:
reducing a number of the patterns based on a minimum support value or by mining maximum frequent patterns: This limitation recites a mathematical concept because it involves applying a mathematical algorithm (pattern mining) to filter and reduce a set of mathematical objects.
Step 2A Prong Two and Step 2B: The claim does not include additional elements that are sufficient to amount to significantly more than the judicial exception under step 2B. Thus, the judicial exception is not integrated into a practical application (see MPEP 2106.04(d) I.), failing step 2A prong 2. The claim is ineligible.
Even when considered in combination, these additional elements represent mere instructions to apply
an exception and therefore do not provide an inventive concept. The claim is ineligible.
Claim 7
Step 1: A process, as above.
Step2A Prong 1: This claim does not recite any abstract ideas, but the claim depends on base claim 1, which recites an abstract idea.
Step2A Prong 2: This judicial exception is not integrated into a practical application because the
additional elements are as follows:
the classical solver comprises a heuristic solver: Adding the words “apply it” (or an equivalent) with the judicial exception, or mere instructions to implement an abstract idea on a computer, or merely uses a computer as a tool to perform an abstract idea (MPEP 2106.05(f)).
Step 2B: The claim does not include additional elements that are sufficient to amount to significantly
more than the judicial exception because the additional elements are as follows:
the classical solver comprises a heuristic solver: Adding the words “apply it” (or an equivalent) with the judicial exception, or mere instructions to implement an abstract idea on a computer, or merely uses a computer as a tool to perform an abstract idea and cannot provide inventive concept (MPEP 2106.05(f)).
Even when considered in combination, these additional elements represent mere instructions to apply
an exception and therefore do not provide an inventive concept. The claim is ineligible.
Claim 8
Step 1: A process, as above.
Step2A Prong 1: The claim recites:
removing certain solution parts from the patterns: This limitation recites a mental process because it involves the evaluation/judgement/opinion of removing portions from the group of patterns, which can be performed by pen and paper.
Step 2A Prong Two and Step 2B: The claim does not include additional elements that are sufficient to amount to significantly more than the judicial exception under step 2B. Thus, the judicial exception is not integrated into a practical application (see MPEP 2106.04(d) I.), failing step 2A prong 2. The claim is ineligible.
Even when considered in combination, these additional elements represent mere instructions to apply
an exception and therefore do not provide an inventive concept. The claim is ineligible.
Claim 9
Step 1: A process, as above.
Step2A Prong 1: This claim does not recite any abstract ideas, but the claim depends on base claim 1, which recites an abstract idea.
Step2A Prong 2: This judicial exception is not integrated into a practical application because the
additional elements are as follows:
the classical solver comprises an exact solver: Adding the words “apply it” (or an equivalent) with the judicial exception, or mere instructions to implement an abstract idea on a computer, or merely uses a computer as a tool to perform an abstract idea (MPEP 2106.05(f)).
Step 2B: The claim does not include additional elements that are sufficient to amount to significantly
more than the judicial exception because the additional elements are as follows:
the classical solver comprises an exact solver: Adding the words “apply it” (or an equivalent) with the judicial exception, or mere instructions to implement an abstract idea on a computer, or merely uses a computer as a tool to perform an abstract idea and cannot provide inventive concept (MPEP 2106.05(f)).
Even when considered in combination, these additional elements represent mere instructions to apply
an exception and therefore do not provide an inventive concept. The claim is ineligible.
Claim 10
Step 1: A process, as above.
Step2A Prong 1: The claim recites:
fixing decision variables in the patterns such that search is focused on solution parts that are not present in the patterns: This limitation recites a mental process because it involves the evaluation/judgement/opinion of evaluating patterns and selecting constraining variables based on which solution parts are present or absent, which can be performed mentally and/or by pen and paper.
Step 2A Prong Two and Step 2B: The claim does not include additional elements that are sufficient to amount to significantly more than the judicial exception under step 2B. Thus, the judicial exception is not integrated into a practical application (see MPEP 2106.04(d) I.), failing step 2A prong 2. The claim is ineligible.
Even when considered in combination, these additional elements represent mere instructions to apply
an exception and therefore do not provide an inventive concept. The claim is ineligible.
Claim 11
Step 1: The claim recites a non-transitory computer medium; therefore, it is directed to the statutory
category of an article of manufacture.
Step2A Prong 1: The claim recites:
performing pattern mining extraction on the pool of solutions to generate a set of patterns: This limitation encompasses a mathematical concept because it involves using algorithm(s) to perform the pattern mining. See paragraph 16 of the instant specification which states, “Pattern mining may be performed to find common structures in transactional datasets… Apriori is an example of an algorithm employed to mine patterns. However, Apriori can require longer running times for datasets with a large number of unique items. In one example, FP-Max and FP-Growth may be used to perform the data mining task.”
generating a pool of solutions to a problem: This limitation encompasses a mental process because it involves the evaluation/judgement/opinion to generate a pool of solutions to a problem, which can be performed mentally or by pen and paper.
the … solver generates and outputs a solution to the problem: This limitation recites a mental process because it involves the evaluation/judgement/opinion to generate a solution to a problem, which can be performed mentally or by pen and paper.
Step2A Prong 2: This judicial exception is not integrated into a practical application because the
additional elements are as follows:
[a] non-transitory storage medium having stored therein instructions that are executable by one or more hardware processors to perform operations comprising…: Adding the words “apply it” (or an equivalent) with the judicial exception, or mere instructions to implement an abstract idea on a computer, or merely uses a computer as a tool to perform an abstract idea (MPEP 2106.05(f)).
…by a quantum computing system: Adding the words “apply it” (or an equivalent) with the judicial exception, or mere instructions to implement an abstract idea on a computer, or merely uses a computer as a tool to perform an abstract idea (MPEP 2106.05(f)).
inputting the set of patterns to a classical solver: Mere data gathering recited at a high level of generality, and thus is an insignificant extra-solution activity (MPEP 2106.05(g)).
wherein the classical solver…: Adding the words “apply it” (or an equivalent) with the judicial exception, or mere instructions to implement an abstract idea on a computer, or merely uses a computer as a tool to perform an abstract idea (MPEP 2106.05(f)).
Step 2B: The claim does not include additional elements that are sufficient to amount to significantly
more than the judicial exception because the additional elements are as follows:
[a] non-transitory storage medium having stored therein instructions that are executable by one or more hardware processors to perform operations comprising…: Adding the words “apply it” (or an equivalent) with the judicial exception, or mere instructions to implement an abstract idea on a computer, or merely uses a computer as a tool to perform an abstract idea and cannot provide inventive concept (MPEP 2106.05(f)).
…by a quantum computing system: Adding the words “apply it” (or an equivalent) with the judicial exception, or mere instructions to implement an abstract idea on a computer, or merely uses a computer as a tool to perform an abstract idea and cannot provide inventive concept (MPEP 2106.05(f)).
inputting the set of patterns to a classical solver: The additional element of “inputting” does not integrate the abstract idea into a practical application because it does not impose any meaningful limits on practicing the abstract idea. As discussed above with respect to integration of the abstract idea into a practical application, the additional element of receiving steps amounts to no more than mere data gathering. This element amounts to receiving data over a network and are well-understood, routine, conventional activity. See MPEP 2106.05(d), subsection II (i). This cannot provide an inventive concept.
wherein the classical solver…: Adding the words “apply it” (or an equivalent) with the judicial exception, or mere instructions to implement an abstract idea on a computer, or merely uses a computer as a tool to perform an abstract idea and cannot provide inventive concept (MPEP 2106.05(f)).
Even when considered in combination, these additional elements represent mere instructions to apply
an exception and therefore do not provide an inventive concept. The claim is ineligible.
Claim 12 recites similar limitations to claim 2. Therefore, claim 12 is rejected using the same rationale as claim 2.
Claim 13 recites similar limitations to claim 3. Therefore, claim 13 is rejected using the same rationale as claim 3.
Claim 14 recites similar limitations to claim 4. Therefore, claim 14 is rejected using the same rationale as claim 4.
Claim 15 recites similar limitations to claim 5. Therefore, claim 15 is rejected using the same rationale as claim 5.
Claim 16 recites similar limitations to claim 6. Therefore, claim 16 is rejected using the same rationale as claim 6.
Claim 17 recites similar limitations to claim 7. Therefore, claim 17 is rejected using the same rationale as claim 7.
Claim 18 recites similar limitations to claim 8. Therefore, claim 18 is rejected using the same rationale as claim 8.
Claim 19 recites similar limitations to claim 9. Therefore, claim 19 is rejected using the same rationale as claim 9.
Claim 20 recites similar limitations to claim 10. Therefore, claim 20 is rejected using the same rationale as claim 10.
Claim Rejections - 35 USC § 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 (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 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, 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.
The factual inquiries for establishing a background for determining obviousness under 35 U.S.C. 103 are summarized as follows:
1. Determining the scope and contents of the prior art.
2. Ascertaining the differences between the prior art and the claims at issue.
3. Resolving the level of ordinary skill in the pertinent art.
4. Considering objective evidence present in the application indicating obviousness or nonobviousness.
This application currently names joint inventors. In considering patentability of the claims the examiner presumes that the subject matter of the various claims was commonly owned as of the effective filing date of the claimed invention(s) absent any evidence to the contrary. Applicant is advised of the obligation under 37 CFR 1.56 to point out the inventor and effective filing dates of each claim that was not commonly owned as of the effective filing date of the later invention in order for the examiner to consider the applicability of 35 U.S.C. 102(b)(2)(C) for any potential 35 U.S.C. 102(a)(2) prior art against the later invention.
Claims 1-5, 9-15, and 19-20 are rejected under 35 U.S.C. 103 as being unpatentable over You (US 20220414518 A1) in view of Karimi ("Boosting quantum annealer performance via sample persistence", 2017).
Regarding claim 1,
You teaches [a] method comprising: generating a pool of solutions to a problem by a quantum computing system (Paragraph 60 of You, "The sub-problem solver 502... is configured to solve the sub-problem assigned to the quantum computer 104. In the illustrative embodiment, the sub-problem assigned to the quantum computer 104 is a QUBO problem… the QUBO problem may be larger than what can be represented on the quantum processor 302 at one time. In such embodiments, the QUBO problem may be partitioned into smaller sub-problems that are solved on the quantum processor 302, such as by using the qbsolv algorithm…", Paragraph 68, "the quantum processor 302 may solve a QUBO problem using the qbsolv algorithm described in "Partitioning Optimization Problems for Hybrid Classical/Quantum Execution" by Booth et al…"
You teaches solving a QUBO problem on the quantum processor by partitioning it into smaller sub-QUBOs and making multiple calls to the quantum hardware to minimize each sub-QUBO. The plurality of variable assignments returned across these calls corresponds to the pool of solutions.).
inputting the set of patterns to a classical solver, wherein the classical solver generates and outputs a solution to the problem (Paragraph 57 of You, "…the classical sub-problem solver 404 is configured to handle all operations of the optimization problem except the calculations performed on the quantum processor 302, such as updating upper and lower bounds, making integer cuts, updating parameter values, checking end conditions, etc.", Paragraph 69, "the quantum computer 104 sends a current result of the second algorithm to the classical computer 102. In some embodiments, the quantum computer 104 may send current values of the variables to the classical computer 102… the quantum computer 104 may send other results to the classical computer 102, such as integer cuts representing machines that could not be scheduled successfully based on the current results provided by the classical computer 102.", Paragraph 70, "the classical computer 102 determines whether an end condition is met. In some embodiments, the end condition is met when an exact optimal solution to the optimization problem is determined."
You teaches that the quantum computer transmits results from its sample (including variable values and integer cuts) to the classical sub-problem solver, which uses them to update bounds, make integer cuts, check end conditions, and output the optimal solution. The classical sub-problem solver corresponds to the classical solver.).
You does not teach explicitly performing pattern mining extraction on the pool of solutions to generate a set of patterns.
Karimi, in the same field of endeavor, teaches performing pattern mining extraction on the pool of solutions to generate a set of patterns (Section 2.1 of Karimi, "The basic idea behind our method is that, for a given problem, we obtain a sample from the quantum annealer, find the variables that have exactly the same value across the entire sample, and fix them to that value… a typical call to the machine involves at least hundreds, if not thousands, of quantum annealing cycles, resulting in a sample of low-energy solutions… many spins (variables) maintain their state (value) in the sample obtained from the quantum annealer.", Section 1.2 of Karimi, "An example of classical pre-processing is fixing variables within a heuristic algorithm by maintaining a reference set of elite solutions (typically obtained by performing a local search), and finding the variables that are often set to the same value, the idea being that they are likely to be set to that same value in the optimum…", Algorithm 1 of Karimi, "Obtain a sample of sample size from the sampler… Narrow down the solutions to the elite threshold percentile… Find the mean value of each variable in all solutions… Fix the variables for which the mean absolute value is larger than fixing threshold…"
Karimi teaches obtaining a pool of low-energy solutions from the quantum annealer and examining that pool to identify which variables consistently maintain the same value across the solution population. The set of consistently-valued variables extracted from the solution pool corresponds to the set of patterns, and the operation of examining the pool to identify those common variables corresponds to the pattern mining extraction. Paragraph 11 of the instant specification states that "a mined pattern... is a composition of common occurrences of solution parts," which is what Karimi's consistently-valued variables represent. Karimi also uses the term "backbone" (Section 1.2) to describe variables taking the same value across optimal solutions, which corresponds to identifying patterns common to a solution dataset.).
Therefore, it would have been obvious to one of ordinary skill in the art before the effective filing date to combine You's method of generating quantum processor sample solutions used by a classical solver with Karimi's extraction of consistently-valued variables from the pool of returned solutions in order to reduce the working problem size handed to the classical solver and improve convergence (Section 2.1 of Karimi).
Regarding claim 2,
You teaches receiving the problem at the quantum computing system, wherein the quantum computing system comprises a quantum annealer and the problem comprises a combinatorial optimization problem in a format configured for the quantum annealer (Paragraph 53 of You, "The quantum processor 302 may be any suitable quantum processor. In the illustrative embodiment, the quantum processor 302 is a quantum annealing processor, such as a D-Wave One™… or D-Wave Advantage processor.", Paragraph 64, "…the second sub-problem to be solved on the quantum computer 104 is expressed in the form of a quadratic unconstrained binary optimization (QUBO) problem with several binary variables."
You teaches that the quantum component is a D-Wave quantum annealing processor and the sub-problem submitted to it is formulated as a QUBO problem with binary variables. The QUBO sub-problem on the D-Wave quantum annealing processor corresponds to the combinatorial optimization problem in a format configured for the quantum annealer.).
Regarding claim 3,
You teaches converting the combinatorial optimization problem to a QUBO format (Paragraph 64 of You, "the classical computer 102 decomposes the optimization problem into a first sub-problem to be solved on the classical computer 102 and a second sub-problem to be solved on the quantum computer 104. The classical computer 102 determines a first set of variables for the first sub-problem in block 612, and determines a second set of variables for the second sub-problem in block 614… In the illustrative embodiment, the second sub-problem to be solved on the quantum computer 104 is expressed in the form of a quadratic unconstrained binary optimization (QUBO) problem with several binary variables."
You teaches decomposing the optimization problem and reformulating the quantum-side sub-problem into QUBO form with binary variables. The reformulation step corresponds to the converting portion of the limitation.).
Regarding claim 4,
You teaches the pool of solutions from the quantum annealer comprise energy states that are converted to solutions (Paragraph 53 of You, "the quantum processor 302 is a quantum annealing processor, such as a D-Wave One™… or D-Wave Advantage processor.", Paragraph 68, "…the quantum processor 302 may process one part of the optimization problem at a time, such as by using a partitioning algorithm... It should further be appreciated that, in some embodiments, the quantum computer 104 may provide an approximate solution to the QUBO problem instead of an exact solution.", Paragraph 69, "…the quantum computer 104 sends a current result of the second algorithm to the classical computer 102. In some embodiments, the quantum computer 104 may send current values of the variables to the classical computer 102."
You teaches that the D-Wave annealer processes the QUBO and returns current variable values to the classical computer, where annealing hardware inherently reads out final low-energy qubit states as those variable values. This readout-and-output corresponds to the energy states being converted to solutions. Paragraph 25 of the instant specification states that "the quantum annealer 306 solves 316 the QUBO and returns 318 a pool energy states" which is then "convert[ed]... to solutions.".).
Regarding claim 5,
You does not teach selecting the patterns from a reduced pool of solutions, wherein the pool of solutions is reduced based on solution cost value or energy level.
Karimi, in the same field of endeavor, teaches selecting the patterns from a reduced pool of solutions, wherein the pool of solutions is reduced based on solution cost value or energy level (Section 2.1 of Karimi, "Trimming the sample. We gave more weight to lower-energy solutions by ignoring higher-energy solutions of the sample, based on a given elite_threshold percentile.", Algorithm 1 of Karimi, "Narrow down the solutions to the elite threshold percentile… Find the mean value of each variable in all solutions… Fix the variables for which the mean absolute value is larger than fixing threshold."
Karimi teaches trimming the sample to the lowest-energy fraction (the elite_threshold percentile) before identifying and fixing variables. The elite-threshold-restricted low-energy fraction corresponds to the reduced pool reduced based on energy level, and the subsequent variable identification corresponds to selecting the patterns from the reduced pool. Paragraph 22 of the instant specification states that the pool is reduced "…according to a quality measure, such as the cost value or energy level given by the quantum annealer," which is Karimi's elite-threshold filter.).
Therefore, it would have been obvious to one of ordinary skill in the art before the effective filing date to combine You’s teaching with Karimi's energy-based trimming of the solution pool prior to pattern extraction in order to ensure that the patterns identified are derived only from the highest-quality low-energy solutions, thus increasing the reliability of the variable fixing step and improving the overall solution quality by the classical solver (Section 2.1 of Karimi).
Regarding claim 9,
You teaches the classical solver comprises an exact solver (Paragraph 57 of You, "The classical computer 102 may use any suitable algorithm, such as one chosen from the Gurobi solver to solve a MILP. Gurobi is an optimization solver provides a plurality of algorithms (e.g. simplex algorithm, barrier algorithm, or concurrent optimization) to solve certain types of optimization problems including the continuous relaxations of mixed-integer problems (e.g. MILP) or continuous problems (e.g. LP, QP, QCP)… the classical sub-problem solver 404 is configured to handle all operations of the optimization problem except the calculations performed on the quantum processor 302, such as updating upper and lower bounds, making integer cuts, updating parameter values, checking end conditions, etc."
You teaches the use of a Gurobi MILP solver, which uses the simplex and barrier algorithms with upper and lower-bound updates to produce a certified optimal solution. The Gurobi MILP solver corresponds to the exact solver.).
Regarding claim 10,
You does not teach fixing decision variables in the patterns such that search is focused on solution parts that are not present in the patterns.
Karimi, in the same field of endeavor, teaches fixing decision variables in the patterns such that search is focused on solution parts that are not present in the patterns (Section 2.1 of Karimi, "The basic idea behind our method is that, for a given problem, we obtain a sample from the quantum annealer, find the variables that have exactly the same value across the entire sample, and fix them to that value… Fixing variables in this way can drastically reduce the size of the effective problem to be solved.", Section 1.2 of Karimi, "An example of classical pre-processing is fixing variables within a heuristic algorithm by maintaining a reference set of elite solutions (typically obtained by performing a local search), and finding the variables that are often set to the same value, the idea being that they are likely to be set to that same value in the optimum…"
Karimi teaches finding the variables that have the same value across the sample, fixing them to that value, and solving the reduced problem so that only the unfixed variables remain to be searched. The fixed variables correspond to the decision variables fixed in the patterns, and the unfixed variables correspond to the solution parts not present in the patterns. Paragraph 32 of the instant specification states that "a pattern to fix decision variables can be selected" which makes "the solver focus on the non-fixed variables," which is what Karimi's variable fixing performs.).
Therefore, it would have been obvious to one of ordinary skill in the art before the effective filing date to combine You’s teaching with Karimi's variable fixing technique in order to reduce the combinatorial search space that the exact solver must traverse (Section 2.1 of Karimi).
Regarding claim 11,
You teaches [a] non-transitory storage medium having stored therein instructions that are executable by one or more hardware processors to perform operations comprising (Paragraph 38 of You, "The disclosed embodiments may also be implemented as instructions carried by or stored on one or more transitory or non-transitory machine-readable (e.g., computer-readable) storage medium, which may be read and executed by one or more processors. A machine-readable storage medium may be embodied as any storage device, mechanism, or other physical structure for storing or transmitting information in a form readable by a machine (e.g., a volatile or non-volatile memory, a media disc, or other media device).").
generating a pool of solutions to a problem by a quantum computing system (Paragraph 60 of You, "The sub-problem solver 502... is configured to solve the sub-problem assigned to the quantum computer 104. In the illustrative embodiment, the sub-problem assigned to the quantum computer 104 is a QUBO problem… the QUBO problem may be larger than what can be represented on the quantum processor 302 at one time. In such embodiments, the QUBO problem may be partitioned into smaller sub-problems that are solved on the quantum processor 302, such as by using the qbsolv algorithm…", Paragraph 68, "the quantum processor 302 may solve a QUBO problem using the qbsolv algorithm described in "Partitioning Optimization Problems for Hybrid Classical/Quantum Execution" by Booth et al…"
You teaches solving a QUBO problem on the quantum processor by partitioning it into smaller sub-QUBOs and making multiple calls to the quantum hardware to minimize each sub-QUBO. The plurality of variable assignments returned across these calls corresponds to the pool of solutions.).
inputting the set of patterns to a classical solver, wherein the solver generates and outputs a solution to the problem (Paragraph 57 of You, "…the classical sub-problem solver 404 is configured to handle all operations of the optimization problem except the calculations performed on the quantum processor 302, such as updating upper and lower bounds, making integer cuts, updating parameter values, checking end conditions, etc.", Paragraph 69, "the quantum computer 104 sends a current result of the second algorithm to the classical computer 102. In some embodiments, the quantum computer 104 may send current values of the variables to the classical computer 102… the quantum computer 104 may send other results to the classical computer 102, such as integer cuts representing machines that could not be scheduled successfully based on the current results provided by the classical computer 102.", Paragraph 70, "the classical computer 102 determines whether an end condition is met. In some embodiments, the end condition is met when an exact optimal solution to the optimization problem is determined."
You teaches that the quantum computer transmits results from its sample (including variable values and integer cuts) to the classical sub-problem solver, which uses them to update bounds, make integer cuts, check end conditions, and output the optimal solution. The classical sub-problem solver corresponds to the classical solver.).
You does not teach explicitly performing pattern mining extraction on the pool of solutions to generate a set of patterns.
Karimi, in the same field of endeavor, teaches performing pattern mining extraction on the pool of solutions to generate a set of patterns (Section 2.1 of Karimi, "The basic idea behind our method is that, for a given problem, we obtain a sample from the quantum annealer, find the variables that have exactly the same value across the entire sample, and fix them to that value… a typical call to the machine involves at least hundreds, if not thousands, of quantum annealing cycles, resulting in a sample of low-energy solutions… many spins (variables) maintain their state (value) in the sample obtained from the quantum annealer.", Section 1.2 of Karimi, "An example of classical pre-processing is fixing variables within a heuristic algorithm by maintaining a reference set of elite solutions (typically obtained by performing a local search), and finding the variables that are often set to the same value, the idea being that they are likely to be set to that same value in the optimum…", Algorithm 1 of Karimi, "Obtain a sample of sample size from the sampler… Narrow down the solutions to the elite threshold percentile… Find the mean value of each variable in all solutions… Fix the variables for which the mean absolute value is larger than fixing threshold…"
Karimi teaches obtaining a pool of low-energy solutions from the quantum annealer and examining that pool to identify which variables consistently maintain the same value across the solution population. The set of consistently-valued variables extracted from the solution pool corresponds to the set of patterns, and the operation of examining the pool to identify those common variables corresponds to the pattern mining extraction. Paragraph 11 of the instant specification states that "a mined pattern... is a composition of common occurrences of solution parts," which is what Karimi's consistently-valued variables represent. Karimi also uses the term "backbone" (Section 1.2) to describe variables taking the same value across optimal solutions, which corresponds to identifying patterns common to a solution dataset.).
Therefore, it would have been obvious to one of ordinary skill in the art before the effective filing date to combine You's method of generating quantum processor sample solutions consumed by a classical solver with Karimi's extraction of consistently-valued variables from the pool of returned solutions in order to reduce the working problem size handed to the classical solver and improve convergence (Section 2.1 of Karimi).
Claim 12 recites similar limitations to claim 2. Therefore, claim 12 is rejected using the same rationale as claim 2.
Claim 13 recites similar limitations to claim 3. Therefore, claim 13 is rejected using the same rationale as claim 3.
Claim 14 recites similar limitations to claim 4. Therefore, claim 14 is rejected using the same rationale as claim 4.
Claim 15 recites similar limitations to claim 5. Therefore, claim 15 is rejected using the same rationale as claim 5.
Claim 19 recites similar limitations to claim 9. Therefore, claim 19 is rejected using the same rationale as claim 9.
Claim 20 recites similar limitations to claim 10. Therefore, claim 20 is rejected using the same rationale as claim 10.
Claims 7-8 and 17-18 are rejected under 35 U.S.C. 103 as being unpatentable over You (US 20220414518 A1) in view of Karimi ("Boosting quantum annealer performance via sample persistence", 2017) and in further view of Hamze (US 20170255872 A1).
Regarding claim 7,
You in view of Karimi does not teach the classical solver comprises a heuristic solver.
Hamze, in the same field of endeavor, teaches the classical solver comprises a heuristic solver (Paragraph 29 of Hamze, "This approach employs highly suitable solvers and hardware, including classical or non-quantum computation and quantum computation. For example, a tabu search run using field programmable gate arrays (FPGAs) may be much faster than a tabu search run on standard microprocessors.", Paragraphs 151 and 152 of Hamze, "Iterated Tabu Search (ITS)… The ITS approach is based on the multistart tabu search method, however the starting solutions are not generated randomly but are instead perturbed in a specific way from found "good" solutions.", Paragraph 177 of Hamze, "Local searching instructions 328b may implement a combination of majority voting with a greedy local search."
Hamze teaches tabu search, Iterated Tabu Search (ITS), and greedy local search operating on the quantum samples. These are heuristic solvers and correspond to the heuristic solver of the limitation.).
Therefore, it would have been obvious to one of ordinary skill in the art before the effective filing date to implement You in view of Karimi's teaching with Hamze's tabu search heuristic solver in order to produce a faster local search and improve the post-processing of the quantum sample (Paragraph 29 of Hamze).
Regarding claim 8,
You in view of Karimi does not teach removing certain solution parts from the patterns.
Hamze, in the same field of endeavor, teaches removing certain solution parts from the patterns (Paragraph 193 of Hamze, "…we may "clamp" variables in the chain and re-run the problem (i.e., hold one or more variables at particular values while allowing other variables to accommodate the fixed variables)… (1) apply a local h to the members of the chain in order to make it inflexible, or (2) set it as a constant in the Ising problem, and convert the incident J entries to h entries on those chains coupled with the variable being clamped."
Hamze teaches clamping identified variables, setting them as constants in the Ising problem, and converting the incident J entries to h entries, thereby removing them from the active problem while the remaining variables continue to be solved. The clamped and removed variables correspond to the certain solution parts removed from the patterns. Paragraph 29 of the instant specification states that "…solution parts are simply removed from I, creating a reduced version of I…" which is what Hamze's clamping does.).
Therefore, it would have been obvious to one of ordinary skill in the art before the effective filing date to combine You in view of Karimi's hybrid quantum-classical pipeline with Hamze's clamping technique in order to reduce the search space and direct the solver's effort toward solution parts not already captured in the patterns (Paragraph 193 of Hamze).
Claim 17 recites similar limitations to claim 7. Therefore, claim 17 is rejected using the same rationale as claim 7.
Claim 18 recites similar limitations to claim 8. Therefore, claim 18 is rejected using the same rationale as claim 8.
Claims 6 and 16 are rejected under 35 U.S.C. 103 as being unpatentable over You (US 20220414518 A1) in view of Karimi ("Boosting quantum annealer performance via sample persistence", 2017) and in further view of Nüßlein ("Frequent Itemset Mining using QUBO", 2019).
Regarding claim 6,
You in view of Karimi does not teach reducing a number of the patterns based on a minimum support value or by mining maximum frequent patterns.
Nüßlein, in the same field of endeavor, teaches reducing a number of the patterns based on a minimum support value or by mining maximum frequent patterns (Section 3 of Nüßlein, "We then conduct a R-step approximation: we set the threshold to τ = 0.5 then we remove all edges from a graph G with edge weight lower than τ.", Section 3 of Nüßlein, "If the size of the found maximum clique is lower then N then we reduce τ, if the clique size was larger then N then we increase τ.", Section 1 of Nüßlein, "The goal is then to find a set of objects of size k, which were frequently bought together."
Nüßlein teaches removing candidate edges whose co-occurrence frequency falls below an adjustable threshold τ and iteratively adjusting τ until only the maximum frequent itemset of size N remains. The frequency threshold τ corresponds to the minimum support value, and the resulting itemset of size N corresponds to the maximum frequent pattern. Paragraph 16 of the instant specification states that minimum support "measures the minimum appearance of a pattern" and that "maximal frequent patterns may be mined," which is what Nüßlein's threshold and maximum-clique search perform.).
Therefore, it would have been obvious to one of ordinary skill in the art before the effective filing date to combine You in view of Karimi's hybrid quantum-classical pipeline with Nüßlein's minimum-support reduction of candidate itemsets in order to retain only the most representative patterns extracted from the quantum sample pool (Section 3 of Nüßlein).
Claim 16 recites identical limitations to claim 6. Therefore, claim 16 is rejected using the same rationale as claim 6.
Conclusion
Any inquiry concerning this communication or earlier communications from the examiner should be directed to MAJD MAHER HADDAD whose telephone number is (571)272-2265. The examiner can normally be reached Mon-Friday 8-5 pm.
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.
/M.M.H./Examiner, Art Unit 2125
/KAMRAN AFSHAR/Supervisory Patent Examiner, Art Unit 2125
Prosecution Insights