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 .
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-24 are rejected under 35 U.S.C. 101 because the claimed invention is directed to a judicial exception (i.e., a law of nature, a natural phenomenon, or an abstract idea) without significantly more.
101 Subject Matter Eligibility Analysis
Step 1: Claims 1-24 are within the four statutory categories (a process, machine, manufacture or composition of matter).
Step 2A Prong One, Step 2A Prong Two, and Step 2B Analysis:
Step 2A Prong One asks if the claim recites a judicial exception (abstract idea, law of nature, or natural phenomenon). If the claim recites a judicial exception, analysis proceeds to Step 2A Prong Two, which asks if the claim recites additional elements that integrate the abstract idea into a practical application. If the claim does not integrate the judicial exception, analysis proceeds to Step 2B, which asks if the claim amounts to significantly more than the judicial exception. If the claim does not amount to significantly more than the judicial exception, the claim is not eligible subject matter under 35 U.S.C. 101.
None of the claims represent an improvement to technology.
Claims 1-8 are directed to a method consisting of a series of steps, meaning that it is directed to the statutory category of process. Claims 9-24 are directed to storage mediums and processors which are machines or manufacture.
Regarding claim 1, the following claim elements are abstract ideas:
segmenting… the combinatorial optimization task into a plurality of sub-tasks (This is an abstract idea of a mental process. The limitation involves analyzing the mathematical optimization task, identifying components that can addressed separately, and using evaluation and judgement to organize these components into smaller sub-tasks. A person could review variables, constraints, or portions of the task, determine which portions are separable, and group them accordingly. These observations, evaluations, and judgements can be practically performed in the human mind, with the aid of pen and paper or basic computational tools, and therefore falls within the mental process grouping of abstract ideas. See MPEP 2106.04(a)(2)(III).);
for each sub-task, accessing… a database of precomputed solutions to identify a pre-computed solution for the sub-task and, in an instance in which the pre-computed solution is not identified for the sub-task (This is an abstract idea of a mental process. The limitation involves reviewing a collection of previously determined solutions, comparing the characteristics or requirements of each sub-task with the stored solutions, and exercising judgement to identify whether a corresponding solution exists. A person could examine a list of pre-computed solutions, compare each solution with the particular sub-task, and conclude that a matching solution either is or is not present. These observations, comparisons, evaluations, and judgements can be practically performed in the human mind, with the aid of pen and paper or basic computational tools, and therefore falls within the mental process grouping of abstract ideas.),
computing… a solution for the sub-task using a quantum optimization algorithm (This is an abstract idea of a mental process and mathematical concept. The limitation involves applying an optimization procedure to the sub-task, calculating or estimating possible values for possible solutions, comparing the resulting values, and selecting a solution that satisfies or optimizes an objective. A person could evaluate candidate solutions, perform the associated calculations, compare the results, and select an optimal or approximate solution in the human mind, with the aid of pen and paper or basic computational tools. These mathematical calculations, evaluations, and judgements fall within the mental process and mathematical concepts groupings of abstract ideas. See MPEP 2106.04(a)(2)(III) and 2106.04(a)(2)(I).);
The following claim elements are additional elements which, taken alone or in combination with the other elements, do not integrate the judicial exception into a practical application nor amount to significantly more than the judicial exception:
receiving, at a classical computing unit, a combinatorial optimization task (The step of “receiving” the combinatorial optimization task is a generic data transmission and data gathering operation performed by a conventional computing unit. Receiving data for subsequent analysis constitutes well-understood, routine, and conventional computer activity and adds only insignificant extras-solution activity to the judicial exception.);
using the classical computing unit (This limitation constitutes mere instructions to apply the abstract idea and insignificant extra-solution activity. See MPEP 2106.05(f) and 2106.05(g).),
transmitting the sub-task from the classical computing unit to a quantum computing unit (This is a generic data transmission operation that constitutes well-understood, routine, and conventional computer activity. See MPEP 2106.05(d)(II)(i).);
using the quantum computing unit (This limitation constitutes mere instructions to apply the abstract idea and insignificant extra-solution activity. See MPEP 2106.05(f) and 2106.05(g).),
transmitting the computed solution for the sub-task from the quantum computing unit to the classical computing unit (This is a generic data transmission operation that constitutes well-understood, routine, and conventional computer activity. See MPEP 2106.05(d)(II)(i).);
implementing, using the classical computing unit, each pre-computed and computed solution on the combinatorial optimization task (This limitation constitutes mere instructions to apply the abstract idea and insignificant extra-solution activity. See MPEP 2106.05(f) and 2106.05(g).).
Regarding claim 2, the rejection of claim 1 is incorporated herein. Further, claim 2 recites the following additional elements, which taken alone or in combination with other elements, do not integrate the judicial exception into a practical application nor amount to significantly more than the judicial exception:
storing, using the classical computing unit, the computed solution in the database (The step of “storing” the computed solution is a generic function of storing information in memory that is well-understood, routine, and conventional activity. See MPEP 2106.05(d)(II)(iv).).
Regarding claim 3, the rejection of claim 1 is incorporated herein. Further, claim 3 recites the following additional elements, which taken alone or in combination with other elements, do not integrate the judicial exception into a practical application nor amount to significantly more than the judicial exception:
retrieving, using the classical computing unit, the pre-computed solution from the database (The step of “retrieving” the pre-computed solution is a generic function of retrieving information from memory that is well-understood, routine, and conventional activity. See MPEP 2106.05(d)(II)(iv).).
Regarding claim 4, the rejection of claim 1 is incorporated herein. Further, claim 4 recites the following abstract ideas:
aggregating…the pre-computed solution and the computed solution for each sub-task to generate a solution for the combinatorial optimization task (This an abstract idea of a mental process. The limitation involves reviewing the individual sub-tasks solutions, evaluating how the solution related to another, and using judgement to combine them into an overall solution for the task. A person could list the respective solutions, organize them according to their corresponding sub-tasks, and combine the results into a complete solution. These observations, evaluations, and judgements can be practically performed in the human mind, with the aid of pen and paper or basic computational tools, and therefore fall within the mental process grouping of abstract ideas.); and
The following claim elements are additional elements which, taken alone or in combination with the other elements, do not integrate the judicial exception into a practical application nor amount to significantly more than the judicial exception:
implementing, using the classical computing unit, the solution on the combinatorial optimization task (This limitation constitutes mere instructions to apply the abstract idea and insignificant extra-solution activity. See MPEP 2106.05(f) and 2106.05(g).).
Regarding claim 5, the rejection of claim 1 is incorporated herein. Further, claim 5 recites the following abstract ideas:
accessing…an alternate pre-computed solution, wherein the alternate pre-computed solution is a pre-computed solution for an alternate sub-task having similar structure as the sub-task (This is an abstract idea of a mental process. The limitation involves reviewing previously determined solutions, comparing the structure of the current sub-task with alternative sub-tasks, and using evaluation and judgement to select a solution associated with a structurally similar sub-task. A person could compare the characteristics of the sub-tasks, identify one having a similar structure, and select its corresponding solution. These comparisons, evaluations, and judgements can be practically performed in the human mind, with the aid of pen and paper or basic computational tools, and therefore falls within the mental process grouping of abstract ideas.),
The following claim elements are additional elements which, taken alone or in combination with the other elements, do not integrate the judicial exception into a practical application nor amount to significantly more than the judicial exception:
wherein implementing, using the classical computing unit, each pre-computed and computed solution on the combinatorial optimization task comprises implementing each alternate pre-computed solution on the combinatorial optimization task (This limitation constitutes mere instructions to apply the abstract idea and insignificant extra-solution activity. See MPEP 2106.05(f) and 2106.05(g).).
Regarding claim 6, the rejection of claim 1 is incorporated herein. Further, claim 6 recites the following abstract ideas:
wherein the combinatorial optimization task is a graph associated with a Max-Cut problem, and wherein each sub-task is a sub-graph (This is an abstract idea of a mental process. The limitation involves reviewing a graph, evaluating its vertices and edges, and using judgement to identify portions of the graph as respective sub-graphs. A person could visually examine the graph and designate groups of vertices and connecting edges as individual sub-graphs. These observations, evaluations, and judgements can be practically performed in the human mind, with the aid of pen and paper or basic computational tools, and therefore falls within the mental process grouping of abstract ideas.).
Regarding claim 7, the rejection of claim 1 is incorporated herein. Further, claim 7 recites the following abstract ideas:
wherein each pre-computed solution and computed solution is computed using an optimization algorithm (This is an abstract idea of a mental process and mathematical concept. The limitation involves applying mathematical rules to evaluate candidate solutions, comparing the resulting values, and selecting a solution that optimizes the objective. A person could perform these calculations, comparisons, and judgements in the human mind, with the aid of pen and paper or basic computational tools.).
Regarding claim 8, the rejection of claim 7 is incorporated herein. Further, claim 8 recites the following abstract ideas:
wherein the optimization algorithm is a Quantum Approximate Optimization Algorithm (QAOA) (This is an abstract idea of a mathematical concept. QAOA applies mathematical relationships and calculations to evaluate candidate solutions and approximate an optimized result.).
Regarding claim 9, the following claim elements are abstract ideas:
segment the combinatorial optimization task into a plurality of sub-tasks (This is an abstract idea of a mental process. The limitation involves analyzing the mathematical optimization task, identifying components that can addressed separately, and using evaluation and judgement to organize these components into smaller sub-tasks. A person could review variables, constraints, or portions of the task, determine which portions are separable, and group them accordingly. These observations, evaluations, and judgements can be practically performed in the human mind, with the aid of pen and paper or basic computational tools, and therefore falls within the mental process grouping of abstract ideas. See MPEP 2106.04(a)(2)(III).);
for each sub-task, access a database of precomputed solutions to identify a pre-computed solution for the sub-task…in an instance in which the pre-computed solution is not identified for the sub-task (This is an abstract idea of a mental process. The limitation involves reviewing a collection of previously determined solutions, comparing the characteristics or requirements of each sub-task with the stored solutions, and exercising judgement to identify whether a corresponding solution exists. A person could examine a list of pre-computed solutions, compare each solution with the particular sub-task, and conclude that a matching solution either is or is not present. These observations, comparisons, evaluations, and judgements can be practically performed in the human mind, with the aid of pen and paper or basic computational tools, and therefore falls within the mental process grouping of abstract ideas.),
compute a solution for the sub-task using a quantum optimization algorithm (This is an abstract idea of a mental process and mathematical concept. The limitation involves applying an optimization procedure to the sub-task, calculating or estimating possible values for possible solutions, comparing the resulting values, and selecting a solution that satisfies or optimizes an objective. A person could evaluate candidate solutions, perform the associated calculations, compare the results, and select an optimal or approximate solution in the human mind, with the aid of pen and paper or basic computational tools. These mathematical calculations, evaluations, and judgements fall within the mental process and mathematical concepts groupings of abstract ideas. See MPEP 2106.04(a)(2)(III) and 2106.04(a)(2)(I).);
The following claim elements are additional elements which, taken alone or in combination with the other elements, do not integrate the judicial exception into a practical application nor amount to significantly more than the judicial exception:
a classical computing unit (This a high-level recitation of generic computer components for performing the abstract idea. See MPEP 2106.05(f).),
a processing device (This a high-level recitation of generic computer components for performing the abstract idea. See MPEP 2106.05(f).);
a non-transitory storage device (This a high-level recitation of generic computer components for performing the abstract idea. See MPEP 2106.05(f).)
receive, from a computing device of a user, a combinatorial optimization task (The step of “receiving” the combinatorial optimization task is a generic data transmission and data gathering operation performed by a conventional computing unit. Receiving data for subsequent analysis constitutes well-understood, routine, and conventional computer activity and adds only insignificant extras-solution activity to the judicial exception.);
a quantum computing unit operatively coupled to the classical computing unit (This a high-level recitation of generic computer components for performing the abstract idea. See MPEP 2106.05(f).),
the classical computing unit is configured to transmit the sub-task to the quantum computing unit for processing and the quantum computing unit is configured to (This limitation constitutes mere instructions to apply the abstract idea and insignificant extra-solution activity. See MPEP 2106.05(f) and 2106.05(g).):
transmit the computed solution for the sub-task from the quantum computing unit to the classical computing unit (This is a generic data transmission operation that constitutes well-understood, routine, and conventional computer activity. See MPEP 2106.05(d)(II)(i).);
wherein the instructions, when executed by the processing device, cause the processing device to implement each pre-computed and computed solution on the combinatorial optimization task (This limitation constitutes mere instructions to apply the abstract idea and insignificant extra-solution activity. See MPEP 2106.05(f) and 2106.05(g).).
Regarding claim 10, the rejection of claim 9 is incorporated herein. The claim recites similar limitations corresponding to claim 2. Therefore, the same subject matter analysis that was utilized for claim 2, as described above, is equally applicable to claim 10.
Therefore, claim 10 is ineligible.
Regarding claim 11, the rejection of claim 9 is incorporated herein. The claim recites similar limitations corresponding to claim 3. Therefore, the same subject matter analysis that was utilized for claim 3, as described above, is equally applicable to claim 11.
Therefore, claim 11 is ineligible.
Regarding claim 12, the rejection of claim 9 is incorporated herein. The claim recites similar limitations corresponding to claim 4. Therefore, the same subject matter analysis that was utilized for claim 4, as described above, is equally applicable to claim 12.
Therefore, claim 12 is ineligible.
Regarding claim 13, the rejection of claim 9 is incorporated herein. The claim recites similar limitations corresponding to claim 5. Therefore, the same subject matter analysis that was utilized for claim 5, as described above, is equally applicable to claim 13.
Therefore, claim 13 is ineligible.
Regarding claim 14, the rejection of claim 9 is incorporated herein. The claim recites similar limitations corresponding to claim 6. Therefore, the same subject matter analysis that was utilized for claim 6, as described above, is equally applicable to claim 14.
Therefore, claim 14 is ineligible.
Regarding claim 15, the rejection of claim 9 is incorporated herein. The claim recites similar limitations corresponding to claim 7. Therefore, the same subject matter analysis that was utilized for claim 7, as described above, is equally applicable to claim 15.
Therefore, claim 15 is ineligible.
Regarding claim 16, the rejection of claim 15 is incorporated herein. The claim recites similar limitations corresponding to claim 8. Therefore, the same subject matter analysis that was utilized for claim 8, as described above, is equally applicable to claim 16.
Therefore, claim 16 is ineligible.
Regarding claim 17, the following claim elements are abstract ideas:
segment… the combinatorial optimization task into a plurality of sub-tasks (This is an abstract idea of a mental process. The limitation involves analyzing the mathematical optimization task, identifying components that can addressed separately, and using evaluation and judgement to organize these components into smaller sub-tasks. A person could review variables, constraints, or portions of the task, determine which portions are separable, and group them accordingly. These observations, evaluations, and judgements can be practically performed in the human mind, with the aid of pen and paper or basic computational tools, and therefore falls within the mental process grouping of abstract ideas. See MPEP 2106.04(a)(2)(III).);
for each sub-task, access… a database of precomputed solutions to identify a pre-computed solution for the sub-task and, in an instance in which the pre-computed solution is not identified for the sub-task (This is an abstract idea of a mental process. The limitation involves reviewing a collection of previously determined solutions, comparing the characteristics or requirements of each sub-task with the stored solutions, and exercising judgement to identify whether a corresponding solution exists. A person could examine a list of pre-computed solutions, compare each solution with the particular sub-task, and conclude that a matching solution either is or is not present. These observations, comparisons, evaluations, and judgements can be practically performed in the human mind, with the aid of pen and paper or basic computational tools, and therefore falls within the mental process grouping of abstract ideas.),
computing… a solution for the sub-task using a quantum optimization algorithm (This is an abstract idea of a mental process and mathematical concept. The limitation involves applying an optimization procedure to the sub-task, calculating or estimating possible values for possible solutions, comparing the resulting values, and selecting a solution that satisfies or optimizes an objective. A person could evaluate candidate solutions, perform the associated calculations, compare the results, and select an optimal or approximate solution in the human mind, with the aid of pen and paper or basic computational tools. These mathematical calculations, evaluations, and judgements fall within the mental process and mathematical concepts groupings of abstract ideas. See MPEP 2106.04(a)(2)(III) and 2106.04(a)(2)(I).);
The following claim elements are additional elements which, taken alone or in combination with the other elements, do not integrate the judicial exception into a practical application nor amount to significantly more than the judicial exception:
a non-transitory computer-readable medium (This a high-level recitation of generic computer components for performing the abstract idea. See MPEP 2106.05(f).)
receive, at a classical computing unit, a combinatorial optimization task (The step of “receiving” the combinatorial optimization task is a generic data transmission and data gathering operation performed by a conventional computing unit. Receiving data for subsequent analysis constitutes well-understood, routine, and conventional computer activity and adds only insignificant extras-solution activity to the judicial exception.);
using the classical computing unit (This limitation constitutes mere instructions to apply the abstract idea and insignificant extra-solution activity. See MPEP 2106.05(f) and 2106.05(g).),
transmitting the sub-task from the classical computing unit to a quantum computing unit (This is a generic data transmission operation that constitutes well-understood, routine, and conventional computer activity. See MPEP 2106.05(d)(II)(i).);
using the quantum computing unit (This limitation constitutes mere instructions to apply the abstract idea and insignificant extra-solution activity. See MPEP 2106.05(f) and 2106.05(g).),
transmitting the computed solution for the sub-task from the quantum computing unit to the classical computing unit (This is a generic data transmission operation that constitutes well-understood, routine, and conventional computer activity. See MPEP 2106.05(d)(II)(i).);
implement, using the classical computing unit, each pre-computed and computed solution on the combinatorial optimization task (This limitation constitutes mere instructions to apply the abstract idea and insignificant extra-solution activity. See MPEP 2106.05(f) and 2106.05(g).).
Regarding claim 18, the rejection of claim 17 is incorporated herein. The claim recites similar limitations corresponding to claim 2. Therefore, the same subject matter analysis that was utilized for claim 2, as described above, is equally applicable to claim 18.
Therefore, claim 18 is ineligible.
Regarding claim 19, the rejection of claim 17 is incorporated herein. The claim recites similar limitations corresponding to claim 3. Therefore, the same subject matter analysis that was utilized for claim 3, as described above, is equally applicable to claim 19.
Therefore, claim 19 is ineligible.
Regarding claim 20, the rejection of claim 17 is incorporated herein. The claim recites similar limitations corresponding to claim 4. Therefore, the same subject matter analysis that was utilized for claim 4, as described above, is equally applicable to claim 20.
Therefore, claim 20 is ineligible.
Regarding claim 21, the rejection of claim 17 is incorporated herein. The claim recites similar limitations corresponding to claim 5. Therefore, the same subject matter analysis that was utilized for claim 5, as described above, is equally applicable to claim 21.
Therefore, claim 21 is ineligible.
Regarding claim 22, the rejection of claim 17 is incorporated herein. The claim recites similar limitations corresponding to claim 6. Therefore, the same subject matter analysis that was utilized for claim 6, as described above, is equally applicable to claim 22.
Therefore, claim 22 is ineligible.
Regarding claim 23, the rejection of claim 17 is incorporated herein. The claim recites similar limitations corresponding to claim 7. Therefore, the same subject matter analysis that was utilized for claim 7, as described above, is equally applicable to claim 23.
Therefore, claim 23 is ineligible.
Regarding claim 24, the rejection of claim 23 is incorporated herein. The claim recites similar limitations corresponding to claim 8. Therefore, the same subject matter analysis that was utilized for claim 8, as described above, is equally applicable to claim 24.
Therefore, claim 24 is ineligible.
Claim Rejections - 35 USC § 102
In the event the determination of the status of the application as subject to AIA 35 U.S.C. 102 and 103 (or as subject to pre-AIA 35 U.S.C. 102 and 103) is incorrect, any correction of the statutory basis (i.e., changing from AIA to pre-AIA ) for the rejection will not be considered a new ground of rejection if the prior art relied upon, and the rationale supporting the rejection, would be the same under either status.
The following is a quotation of the appropriate paragraphs of 35 U.S.C. 102 that form the basis for the rejections under this section made in this Office action:
A person shall be entitled to a patent unless –
(a)(1) the claimed invention was patented, described in a printed publication, or in public use, on sale, or otherwise available to the public before the effective filing date of the claimed invention.
Claims 1-5, 7, 9-13, 15, 17-21, and 23 are rejected under 35 U.S.C. 102(a)(1) as being anticipated by Garrison et al., (Pub. No.: US 20180276556 A1 (Filed: 2017)).
Regarding claim 1, Garrison discloses:
A method for enhanced combinatorial optimization, the method comprising: receiving, at a classical computing unit, a combinatorial optimization task (Garrison, [0058] “The subgraph module 122 may be configured to partition an optimization task into multiple sub-tasks. For example, the subgraph module 122 may be configured to analyze data specifying an optimization task to be solved, and to map the optimization task to multiple minimally connected subgraphs.” [0072] “ During operation (A), the global optimization engine 106 is configured to receive input data 102 specifying an optimization task to be solved” [0095] “For convenience, the process 200 will be described as being performed by a system of one or more classical or quantum computing devices located in one or more locations. For example, an optimization engine, e.g., the multi-state quantum optimization engine 100 of FIG. 1A, appropriately programmed in accordance with this specification, can perform the process 300” – teaches receiving an optimization task that is a graph-based and mapped to multiple minimally connected subgraphs, corresponding to a combinatorial optimization task. Garrison further teaches an implementation in which the optimization engine performing the process is implemented using classical computing devices.)
segmenting, using the classical computing unit, the combinatorial optimization task into a plurality of sub-tasks (Garrison, paragraph [0058] “ The subgraph module 122 may be configured to partition an optimization task into multiple sub-tasks. For example, the subgraph module 122 may be configured to analyze data specifying an optimization task to be solved, and to map the optimization task to multiple minimally connected subgraphs.” [0095] “For convenience, the process 200 will be described as being performed by a system of one or more classical or quantum computing devices located in one or more locations. For example, an optimization engine, e.g., the multi-state quantum optimization engine 100 of FIG. 1A, appropriately programmed in accordance with this specification, can perform the process 300” – teaches the subgraph module partitioning the received optimization task into multiple sub-tasks.);
for each sub-task, accessing, using the classical computing unit, a database of precomputed solutions to identify a pre-computed solution for the sub-task and, in an instance in which the pre-computed solution is not identified for the sub-task, transmitting the sub-task from the classical computing unit to a quantum computing unit (Garrison, paragraph [0059] “The cache 124 is configured to store previously generated initial solutions and global solutions to optimization tasks that the multi-state quantum optimization engine has previously been used to solve…The cache may store the initial and global solutions with a corresponding label that identifies the optimization task to which the solutions belong, the task objectives associated with the initial and global solutions, and the system input data associated with the optimization task.” [0060] “During operation, the global optimization engine 106 and local optimization engine 108 may be configured to query the cache 124 to determine whether existing initial or global solutions to a received optimization task with corresponding task objectives exists in the cache… If it is determined that existing initial or global solutions do not exist, the local optimization engine 106 and global optimization engine 108 may process the received data as described above.” [0074] “initial solutions to the optimization task may include solutions to sub-tasks of the optimization task.” [0075] “The local optimization engine 108 may then be configured to route data representing each sub-task with its respective identified local task objectives to respective computing resources included in the system. The computing resources included in the system may process received tasks using a first set of algorithms, e.g., classical or quantum algorithms.” [0076] “At least one of the obtained one or more initial solutions may be obtained from a quantum computing resource, e.g., quantum computing resource 204.” [0078] “During operation (B), the local optimization engine 108 may be configured to provide the quantum annealer with data representing a sub-task of the optimization task 210. For example, the local optimization engine 108 may apply local task objectives to the data received at stage (A), and transmit data representing the complex task to the quantum computing resource 204.” – Garrison teaches cache 124 storing previously generated initial solutions and the optimization engines querying the cache to determine whether an existing initial solution is available. Garrison further teaches that initial solutions may include solutions to sub-tasks. When an existing solution is not identified, the optimization engines process the received data, including routing data representing each sub-task to computing resources that may use quantum algorithms. Garrison further teaches the local optimization engine providing data representing a sub-task to a quantum annealer and transmitting the data to quantum computing resource 204. Thus, Garrison teaches accessing a database of pre-computed solutions for the sub-tasks and, when a pre-computed solution is not identified, transmitting the corresponding sub-task from the classical computing unit to a quantum computing unit.);
computing, using the quantum computing unit, a solution for the sub-task using a quantum optimization algorithm (Garrison, paragraph [0075] “ The local optimization engine 108 may then be configured to route data representing each sub-task with its respective identified local task objectives to respective computing resources included in the system. The computing resources included in the system may process received tasks using a first set of algorithms, e.g., classical or quantum algorithms.” [0076] “At least one of the obtained one or more initial solutions may be obtained from a quantum computing resource, e.g., quantum computing resource 204.” [0077] “To solve an optimization task using a quantum annealer, e.g., quantum computing resource 204, quantum hardware 208 included in the quantum annealer may be constructed and programmed to encode a solution to the optimization task into an energy spectrum of a many-body quantum Hamiltonian H.sub.p that characterizes the quantum hardware 208…The solution to the optimization task may then be readout by measuring the quantum hardware 208.” [0078] “During operation (B), the local optimization engine 108 may be configured to provide the quantum annealer with data representing a sub-task of the optimization task 210.” [0080] “ During operation (C), the global optimization engine 106 is configured to receive data representing the initial solution to the sub-task 212, e.g., a solution set for a local optimization task, from the quantum computing resource 204.” – teaches providing a sub-task to quantum computing resource 204 for processing using a quantum algorithm. The quantum annealer computes the solution by encoding the optimization task in a quantum Hamiltonian and reading out the resulting solution from the quantum hardware. The resulting initial solution is a solution to the sub-task. Thus, Garrison teaches computing, using the quantum computing unit, a solution for a sub-task using a quantum optimization algorithm.) ; and
transmitting the computed solution for the sub-task from the quantum computing unit to the classical computing unit (Garrison, paragraph[0071] “ The example global optimization engine 106 includes a local optimization engine 108 and a comparison module 206. As described above with reference to FIG. 1A, the global optimization engine 106 is in communication with at least one or more additional computing resources, e.g., quantum computing resource 204,” [0080] “During operation (C), the global optimization engine 106 is configured to receive data representing the initial solution to the sub-task 212, e.g., a solution set for a local optimization task, from the quantum computing resource 204” [0095] “For convenience, the process 200 will be described as being performed by a system of one or more classical or quantum computing devices located in one or more locations. For example, an optimization engine, e.g., the multi-state quantum optimization engine 100 of FIG. 1A, appropriately programmed in accordance with this specification, can perform the process 300.” – teaches quantum computing resource 204 transmitting the computed solution to the sub-task to global optimization engine 106, which receives and processes the solution and may be implemented on classical computing devices. Thus, Garrison teaches transmitting the computed solution for the sub-task from the quantum computing unit to the classical computing unit.); and
implementing, using the classical computing unit, each pre-computed and computed solution on the combinatorial optimization task (Garrison, paragraph [0060] “During operation, the global optimization engine 106 and local optimization engine 108 may be configured to query the cache 124 to determine whether existing initial or global solutions to a received optimization task with corresponding task objectives exists in the cache. If it is determined that existing initial or global solutions do exist, the local optimization engine and global optimization engine may retrieve the solutions and provide the solutions directly as output, e.g., as output data 104” [0101] “The system obtains respective solutions to each of the sub-tasks from the respective computing resources included in the system.” [0102] “ The system processes the generated one or more initial solutions using a second quantum computing resource to generate a global solution to the optimization task based on the global task objectives” [0105] “The generated global solution may be used to determine one or more actions to be taken in a system corresponding to the optimization task, i.e., one or more adjustments to system parameter values.” – teaches using previously generated solutions retrieved from the cache and newly computed solutions for respective sub-tasks. The sub-task solutions are processed to generate a global solution to the optimization task. Thus, Garrison teaches implementing each pre-computed and computed solution on the combinatorial optimization task.).
Regarding claim 2, Garrison discloses:
The method of Claim 1, wherein the method further comprises: storing, using the classical computing unit, the computed solution in the database (Garrison, paragraph [0059] “Optionally, the multi-state quantum optimization engine 100 may include a cache 124. The cache 124 is configured to store previously generated initial solutions and global solutions to optimization tasks that the multi-state quantum optimization engine has previously been used to solve…The cache may store the initial and global solutions with a corresponding label that identifies the optimization task to which the solutions belong, the task objectives associated with the initial and global solutions, and the system input data associated with the optimization task.” [0074] “As described above with reference to FIG. 1A, initial solutions to the optimization task may include solutions to sub-tasks of the optimization task. For example, initial solutions may include solutions that are optimal over a subset of parameters associated with the optimization task, or, in cases where the optimization task is a separable task that may be written as a sum of sub-tasks, solutions to the sub-tasks.” [0080] “During operation (C), the global optimization engine 106 is configured to receive data representing the initial solution to the sub-task 212, e.g., a solution set for a local optimization task, from the quantum computing resource 204.” [0095] “ FIG. 3 is a flowchart of an example process 300 for solving an optimization task using a system including multiple computing resources, where the multiple computing resources include at least one quantum computing resource. For convenience, the process 200 will be described as being performed by a system of one or more classical or quantum computing devices located in one or more locations. For example, an optimization engine, e.g., the multi-state quantum optimization engine 100 of FIG. 1A, appropriately programmed in accordance with this specification, can perform the process 300.” – teaches the optimization engine receiving a computed initial solution to the sub-task from quantum computing resource 204. Garrison further teaches that the optimization engine may be implemented on classical computing devices and includes cache 124, which stores previously generated initial solutions, including solutions to sub-tasks, together with identifying information. Under the broadest reasonable interpretation, cache 124 corresponds to the claimed database.).
Regarding claim 3, Garrison discloses:
The method of Claim 1, wherein the method further comprises, in an instance in which the pre-computed solution is identified for the sub-task: retrieving, using the classical computing unit, the pre-computed solution from the database (Garrison, paragraph [0059] “ Optionally, the multi-state quantum optimization engine 100 may include a cache 124. The cache 124 is configured to store previously generated initial solutions and global solutions to optimization tasks that the multi-state quantum optimization engine has previously been used to solve.” [0060] “During operation, the global optimization engine 106 and local optimization engine 108 may be configured to query the cache 124 to determine whether existing initial or global solutions to a received optimization task with corresponding task objectives exists in the cache. If it is determined that existing initial or global solutions do exist, the local optimization engine and global optimization engine may retrieve the solutions and provide the solutions directly as output, e.g., as output data 104.” [0074] “initial solutions to the optimization task may include solutions to sub-tasks of the optimization task. “ [0095] “For convenience, the process 200 will be described as being performed by a system of one or more classical or quantum computing devices located in one or more locations. For example, an optimization engine, e.g., the multi-state quantum optimization engine 100 of FIG. 1A, appropriately programmed in accordance with this specification, can perform the process 300.” – teaches the optimization engine querying cache 124 to identify whether an existing initial solution is stored and retrieving the solution when it is identified. Garrison further teaches that initial solutions may include solutions to sub-tasks and that the optimization engine may be implemented on classical computing devices. Under BRI, cache 124 corresponds to the claimed database. Thus, Garrison teaches retrieving, using the classical computing unit, the pre-computed solution from the database when the solution is identified for the sub-task.).
Regarding claim 4, Garrison discloses:
The method of Claim 1, wherein implementing, using the classical computing unit, each pre-computed and computed solution on the combinatorial optimization task comprises: aggregating, using the classical computing unit, the pre-computed solution and the computed solution for each sub-task to generate a solution for the combinatorial optimization task (Garrison, paragraph [0057] “The local optimization engine 108 is configured to provide the one or more obtained initial solutions to the optimization task to the global optimization engine 106. The global optimization engine 106 is configured to process the received one or more initial solutions to the optimization task using a quantum computing resource to generate a global solution to the optimization task based on the global task objectives 112b.” [0059] “The cache 124 is configured to store previously generated initial solutions and global solutions to optimization tasks that the multi-state quantum optimization engine has previously been used to solve.” [0060] “If it is determined that existing initial or global solutions do exist, the local optimization engine and global optimization engine may retrieve the solutions and provide the solutions directly as output, e.g., as output data 104.” [0074] “As described above with reference to FIG. 1A, initial solutions to the optimization task may include solutions to sub-tasks of the optimization task.” [0101] “The system obtains respective solutions to each of the sub-tasks from the respective computing resources included in the system.” [0102] “The system processes the generated one or more initial solutions using a second quantum computing resource to generate a global solution to the optimization task based on the global task objectives (step 306).” – teaches that the initial solution may include solutions to the individual sub-tasks, including previously generated solutions retrieved from cache 124 and newly computed solutions obtained from respective computing resources. The local optimization engine provides the obtained sub-task solutions to the global optimization engine, which processes the solutions to generate a global solution for the optimization task. Under BRI, processing the collection of sub-task solutions to generate the global solution corresponds to aggregating the pre-computed and computed solutions for the sub-tasks. Thus, Garrison teaches aggregating, using the classical computing unit, the pre-computed solution and the computed solution for each sub-task to generate a solution for the combinatorial optimization task.); and
implementing, using the classical computing unit, the solution on the combinatorial optimization task (Garrison, paragraph [0033] “The multi-state quantum optimization engine 100 is an example of a system implemented as computer programs on one or more classical or quantum computing devices in one or more locations, in which the systems, components, and techniques described below can be implemented.” [0043] “The output data 104 may be used to initiate one or more actions associated with the optimization task specified by the input data 102, e.g., actions 138. For example, continuing the above example of the task of optimizing a water network, the output data 104 may be used to adjust one or more parameters in the water network…” [0045] “The broker 136 may be configured to receive output data 104 from the multi-state quantum optimization engine and to generate one or more actions to be taken, e.g., actions 138.” – teaches an implementation in which the optimization engine operates on classical computing devices and uses output data representing the solution to initiate actions associated with the optimization task, including adjusting parameters of the system being optimized. Thus, Garrison teaches implementing, using the classical computing unit, the solution on the combinatorial optimization task.).
Regarding claim 5, Garrison discloses:
The method of Claim 1, wherein the method further comprises, for each sub-task, in an instance in which the pre-computed solution for the sub-task is not identified: accessing, using the classical computing unit, an alternate pre-computed solution, wherein the alternate pre-computed solution is a pre-computed solution for an alternate sub-task having similar structure as the sub-task (Garrison, paragraph [0041] “ As another example, in cases where the optimization task is a separable task, e.g., a task that may be written as the sum of multiple sub-tasks, local solutions may include optimal solutions to each of the sub-tasks in the sum of sub-tasks” [0059] “The cache 124 is configured to store previously generated initial solutions and global solutions to optimization tasks that the multi-state quantum optimization engine has previously been used to solve. In some cases this may include initial and global solutions to a same optimization task, e.g., with different task objectives or different dynamic input data. In other cases this may include initial and global solutions to different optimization tasks.” [0060] “ If it is determined that existing initial or global solutions do not exist, the local optimization engine 106 and global optimization engine 108 may process the received data as described above.” [0061] “ In some implementations, the system 100 may be configured to determine whether a solution to a similar optimization task is stored in the cache 124. For example, the system 100 may be configured to compare a received optimization task to one or more other optimization tasks, e.g., optimization tasks that have previously received by the system 100, and determine one or more respective optimization task similarity scores. If one or more of the determined similarity scores exceed a predetermined similarity threshold, the system 100 may determine that the optimization task is similar to another optimization task, and may use a previously obtained solution to the optimization task as an initial solution to the optimization task, or as a final solution to the optimization task.” – teaches that the optimization task may comprise multiple sub-tasks and that cache 124 stores previously generated solutions for different optimization tasks. When an existing solution is not identified, Garrison determines whether the cache contains a solution for another similar optimization task by comparing the tasks and determining similarity scores. When the tasks are sufficiently similar, Garrison accesses and uses the previously obtain solution. Under BRI, the similar previously received optimization task corresponds to the alternate pre-computed solution. Thus, Garrison teaches accessing an alternate pre-computed solution for an alternate sub-task having similar structure as the current sub-task.),
wherein implementing, using the classical computing unit, each pre-computed and computed solution on the combinatorial optimization task comprises implementing each alternate pre-computed solution on the combinatorial optimization task (Garrison, paragraph [0033] “The multi-state quantum optimization engine 100 is an example of a system implemented as computer programs on one or more classical or quantum computing devices in one or more locations, in which the systems, components, and techniques described below can be implemented.” [0061] “In some implementations, the system 100 may be configured to determine whether a solution to a similar optimization task is stored in the cache 124… If one or more of the determined similarity scores exceed a predetermined similarity threshold, the system 100 may determine that the optimization task is similar to another optimization task, and may use a previously obtained solution to the optimization task as an initial solution to the optimization task, or as a final solution to the optimization task.” – teaches identifying a previously obtained solution for a similar optimization task and using that solution as an initial or final solution for the current optimization task. Under BRI, the previously obtained solution for similar alternate sub-task corresponds to the alternate pre-computed solution. Thus, Garrison teaches implementing, using the classical computing unit, the alternate pre-computed solution on the combinatorial optimization task.).
Regarding claim 7, Garrison discloses:
The method of Claim 1, wherein each pre-computed solution and computed solution is computed using an optimization algorithm (Garrison, paragraph [0041] “As another example, in cases where the optimization task is a separable task, e.g., a task that may be written as the sum of multiple sub-tasks, local solutions may include optimal solutions to each of the sub-tasks in the sum of sub-tasks” [0059] “The cache 124 is configured to store previously generated initial solutions and global solutions to optimization tasks that the multi-state quantum optimization engine has previously been used to solve.” [0075] “The local optimization engine 108 may then be configured to route data representing each sub-task with its respective identified local task objectives to respective computing resources included in the system. The computing resources included in the system may process received tasks using a first set of algorithms, e.g., classical or quantum algorithms.” – teaches that the solutions stored in cache 124 are previously generated solutions to an optimization task, corresponding to pre-computed solutions, and that solutions for the current sub-tasks are generated by computing resources using classical or quantum algorithms. In the context of Garrison’s optimization engine, these algorithms are optimization algorithms used to produce optimal solutions for the respective sub-task. Thus, Garrison teaches that each pre-computed solution and computed solution is computed using an optimization algorithm.).
Regarding claim 9, Garrison discloses:
A system for enhanced combinatorial optimization, the system comprising: a classical computing unit, the classical computing unit comprising: a processing device; and a non-transitory storage device containing instructions that, when executed by the processing device, cause the processing device to (Garrison, paragraph [0168] “The classical computer component may be a machine implemented according to the general computing model established by John Von Neumann, in which programs are written in the form of ordered lists of instructions and stored within a classical (e.g., digital) memory 310 and executed by a classical (e.g., digital) processor 308 of the classical computer.“ [0179] “A classical computer can generally also receive (read) programs and data from, and write (store) programs and data to, a non-transitory computer-readable storage medium such as an internal disk (not shown) or a removable disk.” :
receive, from a computing device of a user, a combinatorial optimization task (Garrison, [0058] “The subgraph module 122 may be configured to partition an optimization task into multiple sub-tasks. For example, the subgraph module 122 may be configured to analyze data specifying an optimization task to be solved, and to map the optimization task to multiple minimally connected subgraphs.” [0072] “ During operation (A), the global optimization engine 106 is configured to receive input data 102 specifying an optimization task to be solved” [0095] “For convenience, the process 200 will be described as being performed by a system of one or more classical or quantum computing devices located in one or more locations. For example, an optimization engine, e.g., the multi-state quantum optimization engine 100 of FIG. 1A, appropriately programmed in accordance with this specification, can perform the process 300” [0168] “For example, the processor 308 may read instructions from the computer program in the memory 310, and may optionally receive input data 316 from a source external to the computer 302, such as from a user input device such as a mouse, keyboard, or any other input device.” – teaches receiving an optimization task that is a graph-based and mapped to multiple minimally connected subgraphs, corresponding to a combinatorial optimization task. Garrison further teaches an implementation in which the optimization engine performing the process is implemented using classical computing devices.)
segment the combinatorial optimization task into a plurality of sub-tasks (Garrison, paragraph [0058] “ The subgraph module 122 may be configured to partition an optimization task into multiple sub-tasks. For example, the subgraph module 122 may be configured to analyze data specifying an optimization task to be solved, and to map the optimization task to multiple minimally connected subgraphs.” [0095] “For convenience, the process 200 will be described as being performed by a system of one or more classical or quantum computing devices located in one or more locations. For example, an optimization engine, e.g., the multi-state quantum optimization engine 100 of FIG. 1A, appropriately programmed in accordance with this specification, can perform the process 300” – teaches the subgraph module partitioning the received optimization task into multiple sub-tasks.);
for each sub-task access a database of pre-computed solutions to identify a pre-computed solution for the sub-task; and a quantum computing unit operatively coupled to the classical computing unit, wherein, in an instance in which the pre-computed solution is not identified for the subtask, the classical computing unit is configured to transmit the sub-task to the quantum computing unit for processing and the quantum computing unit is configured to: (Garrison, paragraph [0021] “ A multi-state quantum optimization engine, as described in this specification, uses nested calls to quantum computing devices to solve optimization tasks. The multi-state quantum optimization engine uses both classical and quantum computing devices, increasing the computational capabilities of the optimization engine compared to optimization engines that do not include both classical and quantum computing devices.” [0059] “Optionally, the multi-state quantum optimization engine 100 may include a cache 124. The cache 124 is configured to store previously generated initial solutions and global solutions to optimization tasks that the multi-state quantum optimization engine has previously been used to solve… The cache may store the initial and global solutions with a corresponding label that identifies the optimization task to which the solutions belong, the task objectives associated with the initial and global solutions, and the system input data associated with the optimization task.” [0060] “ During operation, the global optimization engine 106 and local optimization engine 108 may be configured to query the cache 124 to determine whether existing initial or global solutions to a received optimization task with corresponding task objectives exists in the cache… If it is determined that existing initial or global solutions do not exist, the local optimization engine 106 and global optimization engine 108 may process the received data as described above.” [0071] “The example global optimization engine 106 includes a local optimization engine 108 and a comparison module 206. As described above with reference to FIG. 1A, the global optimization engine 106 is in communication with at least one or more additional computing resources, e.g., quantum computing resource 204” [0074] “As described above with reference to FIG. 1A, initial solutions to the optimization task may include solutions to sub-tasks of the optimization task.” [0075] “The local optimization engine 108 may then be configured to route data representing each sub-task with its respective identified local task objectives to respective computing resources included in the system.” [0078] “ During operation (B), the local optimization engine 108 may be configured to provide the quantum annealer with data representing a sub-task of the optimization task 210.” – teaches a hybrid optimization engine that uses both classical and quantum computing devices and makes nested calls to the quantum computing devices, thereby establishing that the quantum computing unit it operatively coupled to the classical computing unit. Cache 124 stores previously generated solutions and corresponding labels and is queried to identify an existing solution for a received optimization task, including a sub-task. When an existing solution is not identified, the engines process the received data by routing data representing the sub-task to a computing resource, including providing the sub-task to quantum computing resource 204 for processing.);
compute a solution for the sub-task using a quantum optimization algorithm (Garrison, paragraph [0075] “ The local optimization engine 108 may then be configured to route data representing each sub-task with its respective identified local task objectives to respective computing resources included in the system. The computing resources included in the system may process received tasks using a first set of algorithms, e.g., classical or quantum algorithms.” [0076] “At least one of the obtained one or more initial solutions may be obtained from a quantum computing resource, e.g., quantum computing resource 204.” [0077] “To solve an optimization task using a quantum annealer, e.g., quantum computing resource 204, quantum hardware 208 included in the quantum annealer may be constructed and programmed to encode a solution to the optimization task into an energy spectrum of a many-body quantum Hamiltonian H.sub.p that characterizes the quantum hardware 208…The solution to the optimization task may then be readout by measuring the quantum hardware 208.” [0078] “During operation (B), the local optimization engine 108 may be configured to provide the quantum annealer with data representing a sub-task of the optimization task 210.” [0080] “ During operation (C), the global optimization engine 106 is configured to receive data representing the initial solution to the sub-task 212, e.g., a solution set for a local optimization task, from the quantum computing resource 204.” – teaches providing a sub-task to quantum computing resource 204 for processing using a quantum algorithm. The quantum annealer computes the solution by encoding the optimization task in a quantum Hamiltonian and reading out the resulting solution from the quantum hardware. The resulting initial solution is a solution to the sub-task. Thus, Garrison teaches computing, using the quantum computing unit, a solution for a sub-task using a quantum optimization algorithm.) ; and
transmit the computed solution to the classical computing unit (Garrison, paragraph[0071] “ The example global optimization engine 106 includes a local optimization engine 108 and a comparison module 206. As described above with reference to FIG. 1A, the global optimization engine 106 is in communication with at least one or more additional computing resources, e.g., quantum computing resource 204,” [0080] “During operation (C), the global optimization engine 106 is configured to receive data representing the initial solution to the sub-task 212, e.g., a solution set for a local optimization task, from the quantum computing resource 204” [0095] “For convenience, the process 200 will be described as being performed by a system of one or more classical or quantum computing devices located in one or more locations. For example, an optimization engine, e.g., the multi-state quantum optimization engine 100 of FIG. 1A, appropriately programmed in accordance with this specification, can perform the process 300.” – teaches quantum computing resource 204 transmitting the computed solution to the sub-task to global optimization engine 106, which receives and processes the solution and may be implemented on classical computing devices. Thus, Garrison teaches transmitting the computed solution for the sub-task from the quantum computing unit to the classical computing unit.); and
wherein the instructions, when executed by the processing device, cause the processing device to implement each pre-computed and computed solution on the combinatorial optimization task (Garrison, paragraph [0060] “During operation, the global optimization engine 106 and local optimization engine 108 may be configured to query the cache 124 to determine whether existing initial or global solutions to a received optimization task with corresponding task objectives exists in the cache. If it is determined that existing initial or global solutions do exist, the local optimization engine and global optimization engine may retrieve the solutions and provide the solutions directly as output, e.g., as output data 104” [0101] “The system obtains respective solutions to each of the sub-tasks from the respective computing resources included in the system.” [0102] “ The system processes the generated one or more initial solutions using a second quantum computing resource to generate a global solution to the optimization task based on the global task objectives” [0105] “The generated global solution may be used to determine one or more actions to be taken in a system corresponding to the optimization task, i.e., one or more adjustments to system parameter values.” – teaches using previously generated solutions retrieved from the cache and newly computed solutions for respective sub-tasks. The sub-task solutions are processed to generate a global solution to the optimization task. Thus, Garrison teaches implementing each pre-computed and computed solution on the combinatorial optimization task.).
Regarding claim 10, Garrison teaches all the elements of claim 9, therefore is rejected for the same reasons as those presented for claim 9. The claim recites similar limitations corresponding to claim 2 and is rejected for similar reasons as claim 2 using similar teachings and rationale.
Regarding claim 11, Garrison teaches all the elements of claim 9, therefore is rejected for the same reasons as those presented for claim 9. The claim recites similar limitations corresponding to claim 3 and is rejected for similar reasons as claim 3 using similar teachings and rationale.
Regarding claim 12, Garrison teaches all the elements of claim 9, therefore is rejected for the same reasons as those presented for claim 9. The claim recites similar limitations corresponding to claim 4 and is rejected for similar reasons as claim 4 using similar teachings and rationale.
Regarding claim 13, Garrison teaches all the elements of claim 9, therefore is rejected for the same reasons as those presented for claim 9. The claim recites similar limitations corresponding to claim 5 and is rejected for similar reasons as claim 5 using similar teachings and rationale.
Regarding claim 15, Garrison teaches all the elements of claim 9, therefore is rejected for the same reasons as those presented for claim 9. The claim recites similar limitations corresponding to claim 7 and is rejected for similar reasons as claim 7 using similar teachings and rationale.
Regarding claim 17, Garrison discloses:
A computer program product for enhanced combinatorial optimization, the computer program product comprising a non-transitory computer-readable medium comprising code configured to cause an apparatus to (Garrison, paragraph [0123] “Control of the various systems described in this specification, or portions of them, can be implemented in a digital and/or quantum computer program product that includes instructions that are stored on one or more non-transitory machine-readable storage media, and that are executable on one or more digital and/or quantum processing devices. The systems described in this specification, or portions of them, can each be implemented as an apparatus, method, or system that may include one or more digital and/or quantum processing devices and memory to store executable instructions to perform the operations described in this specification.”):
receive, at a classical computing unit, a combinatorial optimization task (Garrison, [0058] “The subgraph module 122 may be configured to partition an optimization task into multiple sub-tasks. For example, the subgraph module 122 may be configured to analyze data specifying an optimization task to be solved, and to map the optimization task to multiple minimally connected subgraphs.” [0072] “ During operation (A), the global optimization engine 106 is configured to receive input data 102 specifying an optimization task to be solved” [0095] “For convenience, the process 200 will be described as being performed by a system of one or more classical or quantum computing devices located in one or more locations. For example, an optimization engine, e.g., the multi-state quantum optimization engine 100 of FIG. 1A, appropriately programmed in accordance with this specification, can perform the process 300” – teaches receiving an optimization task that is a graph-based and mapped to multiple minimally connected subgraphs, corresponding to a combinatorial optimization task. Garrison further teaches an implementation in which the optimization engine performing the process is implemented using classical computing devices.)
segment, using the classical computing unit, the combinatorial optimization task into a plurality of sub-tasks (Garrison, paragraph [0058] “ The subgraph module 122 may be configured to partition an optimization task into multiple sub-tasks. For example, the subgraph module 122 may be configured to analyze data specifying an optimization task to be solved, and to map the optimization task to multiple minimally connected subgraphs.” [0095] “For convenience, the process 200 will be described as being performed by a system of one or more classical or quantum computing devices located in one or more locations. For example, an optimization engine, e.g., the multi-state quantum optimization engine 100 of FIG. 1A, appropriately programmed in accordance with this specification, can perform the process 300” – teaches the subgraph module partitioning the received optimization task into multiple sub-tasks.);
for each sub-task, accessing, using the classical computing unit, a database of precomputed solutions to identify a pre-computed solution for the sub-task and, in an instance in which the pre-computed solution is not identified for the sub-task, transmitting the sub-task from the classical computing unit to a quantum computing unit (Garrison, paragraph [0059] “The cache 124 is configured to store previously generated initial solutions and global solutions to optimization tasks that the multi-state quantum optimization engine has previously been used to solve…The cache may store the initial and global solutions with a corresponding label that identifies the optimization task to which the solutions belong, the task objectives associated with the initial and global solutions, and the system input data associated with the optimization task.” [0060] “During operation, the global optimization engine 106 and local optimization engine 108 may be configured to query the cache 124 to determine whether existing initial or global solutions to a received optimization task with corresponding task objectives exists in the cache… If it is determined that existing initial or global solutions do not exist, the local optimization engine 106 and global optimization engine 108 may process the received data as described above.” [0074] “initial solutions to the optimization task may include solutions to sub-tasks of the optimization task.” [0075] “The local optimization engine 108 may then be configured to route data representing each sub-task with its respective identified local task objectives to respective computing resources included in the system. The computing resources included in the system may process received tasks using a first set of algorithms, e.g., classical or quantum algorithms.” [0076] “At least one of the obtained one or more initial solutions may be obtained from a quantum computing resource, e.g., quantum computing resource 204.” [0078] “During operation (B), the local optimization engine 108 may be configured to provide the quantum annealer with data representing a sub-task of the optimization task 210. For example, the local optimization engine 108 may apply local task objectives to the data received at stage (A), and transmit data representing the complex task to the quantum computing resource 204.” – Garrison teaches cache 124 storing previously generated initial solutions and the optimization engines querying the cache to determine whether an existing initial solution is available. Garrison further teaches that initial solutions may include solutions to sub-tasks. When an existing solution is not identified, the optimization engines process the received data, including routing data representing each sub-task to computing resources that may use quantum algorithms. Garrison further teaches the local optimization engine providing data representing a sub-task to a quantum annealer and transmitting the data to quantum computing resource 204. Thus, Garrison teaches accessing a database of pre-computed solutions for the sub-tasks and, when a pre-computed solution is not identified, transmitting the corresponding sub-task from the classical computing unit to a quantum computing unit.);
computing, using the quantum computing unit, a solution for the sub-task using a quantum optimization algorithm (Garrison, paragraph [0075] “ The local optimization engine 108 may then be configured to route data representing each sub-task with its respective identified local task objectives to respective computing resources included in the system. The computing resources included in the system may process received tasks using a first set of algorithms, e.g., classical or quantum algorithms.” [0076] “At least one of the obtained one or more initial solutions may be obtained from a quantum computing resource, e.g., quantum computing resource 204.” [0077] “To solve an optimization task using a quantum annealer, e.g., quantum computing resource 204, quantum hardware 208 included in the quantum annealer may be constructed and programmed to encode a solution to the optimization task into an energy spectrum of a many-body quantum Hamiltonian H.sub.p that characterizes the quantum hardware 208…The solution to the optimization task may then be readout by measuring the quantum hardware 208.” [0078] “During operation (B), the local optimization engine 108 may be configured to provide the quantum annealer with data representing a sub-task of the optimization task 210.” [0080] “ During operation (C), the global optimization engine 106 is configured to receive data representing the initial solution to the sub-task 212, e.g., a solution set for a local optimization task, from the quantum computing resource 204.” – teaches providing a sub-task to quantum computing resource 204 for processing using a quantum algorithm. The quantum annealer computes the solution by encoding the optimization task in a quantum Hamiltonian and reading out the resulting solution from the quantum hardware. The resulting initial solution is a solution to the sub-task. Thus, Garrison teaches computing, using the quantum computing unit, a solution for a sub-task using a quantum optimization algorithm.) ; and
transmitting the computed solution for the sub-task from the quantum computing unit to the classical computing unit (Garrison, paragraph[0071] “ The example global optimization engine 106 includes a local optimization engine 108 and a comparison module 206. As described above with reference to FIG. 1A, the global optimization engine 106 is in communication with at least one or more additional computing resources, e.g., quantum computing resource 204,” [0080] “During operation (C), the global optimization engine 106 is configured to receive data representing the initial solution to the sub-task 212, e.g., a solution set for a local optimization task, from the quantum computing resource 204” [0095] “For convenience, the process 200 will be described as being performed by a system of one or more classical or quantum computing devices located in one or more locations. For example, an optimization engine, e.g., the multi-state quantum optimization engine 100 of FIG. 1A, appropriately programmed in accordance with this specification, can perform the process 300.” – teaches quantum computing resource 204 transmitting the computed solution to the sub-task to global optimization engine 106, which receives and processes the solution and may be implemented on classical computing devices. Thus, Garrison teaches transmitting the computed solution for the sub-task from the quantum computing unit to the classical computing unit.); and
implement, using the classical computing unit, each pre-computed and computed solution on the combinatorial optimization task (Garrison, paragraph [0060] “During operation, the global optimization engine 106 and local optimization engine 108 may be configured to query the cache 124 to determine whether existing initial or global solutions to a received optimization task with corresponding task objectives exists in the cache. If it is determined that existing initial or global solutions do exist, the local optimization engine and global optimization engine may retrieve the solutions and provide the solutions directly as output, e.g., as output data 104” [0101] “The system obtains respective solutions to each of the sub-tasks from the respective computing resources included in the system.” [0102] “ The system processes the generated one or more initial solutions using a second quantum computing resource to generate a global solution to the optimization task based on the global task objectives” [0105] “The generated global solution may be used to determine one or more actions to be taken in a system corresponding to the optimization task, i.e., one or more adjustments to system parameter values.” – teaches using previously generated solutions retrieved from the cache and newly computed solutions for respective sub-tasks. The sub-task solutions are processed to generate a global solution to the optimization task. Thus, Garrison teaches implementing each pre-computed and computed solution on the combinatorial optimization task.).
Regarding claim 18, Garrison teaches all the elements of claim 17, therefore is rejected for the same reasons as those presented for claim 17. The claim recites similar limitations corresponding to claim 2 and is rejected for similar reasons as claim 2 using similar teachings and rationale.
Regarding claim 19, Garrison teaches all the elements of claim 17, therefore is rejected for the same reasons as those presented for claim 17. The claim recites similar limitations corresponding to claim 3 and is rejected for similar reasons as claim 3 using similar teachings and rationale.
Regarding claim 20, Garrison teaches all the elements of claim 17, therefore is rejected for the same reasons as those presented for claim 17. The claim recites similar limitations corresponding to claim 4 and is rejected for similar reasons as claim 4 using similar teachings and rationale.
Regarding claim 21, Garrison teaches all the elements of claim 17, therefore is rejected for the same reasons as those presented for claim 17. The claim recites similar limitations corresponding to claim 5 and is rejected for similar reasons as claim 5 using similar teachings and rationale.
Regarding claim 23, Garrison teaches all the elements of claim 17, therefore is rejected for the same reasons as those presented for claim 17. The claim recites similar limitations corresponding to claim 7 and is rejected for similar reasons as claim 7 using similar teachings and rationale.
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.
Claims 6, 8, 14, 16, 22, and 24 are rejected under the 35 U.S.C. 103 as being unpatentable over Garrison et al., (Pub. No.: US 20180276556 A1 (Filed: 2017)) in view of Wang (Pub. No.: US 20230153373 A1 (Filed: 2022)).
Regarding claim 6, Garrison teaches all the elements of claim 1, therefore is rejected for the same reasons as those presented for claim 1. However, Garrison does not teach but Garrison in view of Wang teaches the following limitations:
wherein the combinatorial optimization task is a graph associated with a Max-Cut problem, and wherein each sub-task is a sub-graph (Garrison, paragraph [0058] “The subgraph module 122 may be configured to partition an optimization task into multiple sub-tasks. For example, the subgraph module 122 may be configured to analyze data specifying an optimization task to be solved, and to map the optimization task to multiple minimally connected subgraphs.” Wang, paragraph [0006] “The disclosed technology combines classical computing methods and quantum computing methods to solve combinatorial optimization problems.“ [0066] “This assumption holds for a wide range of combinatorial optimization problems, including all unconstrained problems (e.g., Max Cut, Max 3SAT)” [0090] “ In the Max Bisection problem, a graph is provided for G = (V, E, w) such that |V| = n is even and w: E .fwdarw. ℝ assigns a weight to each edge, and need to find a subset S ⊂ V such that |S| = n/2 and the total weight of the edges between S and Vt minus S is maximized. Namely, Max Bisection is almost the same as Max Cut, except that it has the extra constraint |S| = |V \ S|.” – Garrison teaches partitioning a graph-based optimization task into multiple sub-tasks represented by subgraphs. Wang teaches that Max-Cut is a combinatorial optimization problem and explains that Max Bisection is a graph problem that is substantially the same as Max-Cut expect for an additional equal-partition constraint. Accordingly, Garrison in view of Wang teaches that the combinatorial optimization task is a subgraph associated with a Max-cut problem and that each sub-task is a subgraph.).
Accordingly, it would have been obvious to a person of ordinary skill in the art, before the effective filing date of the claimed invention, having a combination of Garrison and Wang before them, to use the Max-Cut problem taught by Wang as the graph-based combinatorial optimization task processed by the hybrid optimization system of Garrison. One would have been motivated to make such a combination in order to apply Garrison’s known subgraph-partitioning technique to a known combinatorial optimization problem identified by Wang as suitable for quantum-classical optimization. This would predictably divide the Max-Cut graph into smaller subgraph tasks that could be distributed among the available computing resources for more manageable processing.
Regarding claim 8, Garrison teaches all the elements of claim 7, therefore is rejected for the same reasons as those presented for claim 7. However, Garrison does not teach but Garrison in view of Wang teaches the following limitations:
wherein the optimization algorithm is a Quantum Approximate Optimization Algorithm (QAOA) (Garrison, paragraph [0075] “The local optimization engine 108 may then be configured to route data representing each sub-task with its respective identified local task objectives to respective computing resources included in the system. The computing resources included in the system may process received tasks using a first set of algorithms, e.g., classical or quantum algorithms.” Wang, paragraph [0006] “The disclosed technology combines classical computing methods and quantum computing methods to solve combinatorial optimization problems.” [0036] “A number of variational quantum algorithms have been proposed to solve combinatorial optimization problems. Referring to FIG. 4, a comparison of known approaches is illustrated, showing that the disclosed technology is the only algorithm with favorable properties for multiple applications. The various algorithms include: [0037] a. Quantum Approximation Optimization Algorithm (QAOA)” – Garrison teaches computing solutions to the sub-tasks using quantum algorithms. Wang further identifies QAOA as quantum algorithm used to solve combinatorial optimization problems.).
Regarding claim 14, Garrison teaches all the elements of claim 9, therefore is rejected for the same reasons as those presented for claim 9. The claim recites similar limitations corresponding to claim 6 and is rejected for similar reasons as claim 6 using similar teachings and rationale.
Regarding claim 16, Garrison teaches all the elements of claim 15, therefore is rejected for the same reasons as those presented for claim 15. The claim recites similar limitations corresponding to claim 8 and is rejected for similar reasons as claim 8 using similar teachings and rationale.
Regarding claim 22, Garrison teaches all the elements of claim 17, therefore is rejected for the same reasons as those presented for claim 17. The claim recites similar limitations corresponding to claim 6 and is rejected for similar reasons as claim 6 using similar teachings and rationale.
Regarding claim 24, Garrison teaches all the elements of claim 23, therefore is rejected for the same reasons as those presented for claim 23. The claim recites similar limitations corresponding to claim 8 and is rejected for similar reasons as claim 8 using similar teachings and rationale.
Conclusion
The prior art of record and not relied upon is considered pertinent to Applicant’s disclosure:
1. Ghimire, B., Mahmood, A., & Elleithy, K. (2023). Hybrid parallel ant colony optimization for application to quantum computing to solve large-scale combinatorial optimization problems. Applied Sciences, 13(21), 11817. – is considered pertinent for its teaching of a hybrid quantum-classical approach that partitions a large combinatorial optimization graph into subgraphs, optimizes each subgraph on a quantum computer using QAOA, and assembles the optimized subgraphs to obtain a solution for the complete graph.
2. Bass, G., Henderson, M., Heath, J., & Dulny III, J. (2021). Optimizing the optimizer: decomposition techniques for quantum annealing. Quantum Machine Intelligence, 3(1), 10. – is considered pertinent for its teaching of heterogeneous classical-quantum optimization techniques that partition a large optimization problem into quantum-solvable subproblems, process the subproblems using a quantum annealer, and combine the resulting subproblem solutions into global solutions.
Any inquiry concerning this communication or earlier communications from the examiner should be directed to Daravanh Phakousonh whose telephone number is (571)272-6324. The examiner can normally be reached Mon - Thurs 7 AM - 5 PM, Every other Friday 7 AM - 4PM.
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, Li B Zhen can be reached at 571-272-3768. 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.
/Daravanh Phakousonh/Examiner, Art Unit 2121
/Li B. Zhen/Supervisory Patent Examiner, Art Unit 2121
Prosecution Insights