DETAILED ACTION
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 .
This Action is non-final and is in response to the claims filed December 5th, 2022. Claims 1-20 are pending, of which claims 1-20 are currently rejected.
Information Disclosure Statement
The information disclosure statement (IDS) submitted on 12/05/2022 is in compliance with the provisions of 37 CFR 1.97. It has been placed in the application file, and the information referred to therein has been considered as to the merits.
Claim Rejections - 35 USC § 112
The following is a quotation of 35 U.S.C. 112(d):
(d) REFERENCE IN DEPENDENT FORMS.—Subject to subsection (e), a claim in dependent form shall contain a reference to a claim previously set forth and then specify a further limitation of the subject matter claimed. A claim in dependent form shall be construed to incorporate by reference all the limitations of the claim to which it refers.
The following is a quotation of pre-AIA 35 U.S.C. 112, fourth paragraph:
Subject to the following paragraph [i.e., the fifth paragraph of pre-AIA 35 U.S.C. 112], a claim in dependent form shall contain a reference to a claim previously set forth and then specify a further limitation of the subject matter claimed. A claim in dependent form shall be construed to incorporate by reference all the limitations of the claim to which it refers.
Claim 8 is rejected under 35 U.S.C. 112(d) or pre-AIA 35 U.S.C. 112, 4th paragraph, as being of improper dependent form for failing to further limit the subject matter of the claim upon which it depends, or for failing to include all the limitations of the claim upon which it depends. Claim 8 depends upon a claim following it, further limiting recited elements that haven’t been claimed up to the point of claim 8. Applicant may cancel the claim(s), amend the claim(s) to place the claim(s) in proper dependent form, rewrite the claim(s) in independent form, or present a sufficient showing that the dependent claim(s) complies with the statutory requirements. For examination purposes, claim 8 will be construed to depend upon claim 7 instead.
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.
Regarding claim 1, at Step 1, the claim is directed to a statutory category of invention (machine).
At Step 2A, Prong 1, Examiner notes that the claim recites an abstract idea. Claim language recites generating random replicas for permutation-based optimization problem computation having an unconstrainted objective function and performing an optimization algorithm to achieve convergence. Below are the limitations of claim 1 that recite an abstract idea under mathematical concepts or mental steps:
generate a set of random replicas for a permutation-based optimization problem having an objective function representing only an original unconstrained objective, wherein each replica is a sequence of n symbols (mathematical concepts);
define a neighborhood for each replica within a domain of the objective function; and (mathematical concepts)
iteratively perform steps of an optimization algorithm to: (mathematical concepts)
perform local operations with probabilistic acceptance criterion to transform a first replica to a second replica within a neighborhood of the first replica; (mathematical concepts)
compare a least cost of the second replica to a previously stored overall minimum cost (mathematical concepts);
when the least cost of the second replica is less than the previously stored overall minimum cost; and (mathematical concepts)
perform a next iteration until a convergence or a maximum number of iterations is achieved. (mathematical concepts).
All limitations as indicated describe “mathematical concepts”.
At Step 2A Prong 2, these are the additional elements recited in claim 1:
A system comprising a computer
Including a processor and a memory,
The memory storing instructions executable by the processor
Store the second replicas as new overall minimum cost (insignificant extra-solution activity)
The processor and memory are generic computer components and do not integrate the judicial exception into a practical application of the exception. See MPEP 2106.05(f). All additional elements represent no more than mere instructions to apply the judicial exception on a computer. Even when viewed in combination, these additional elements do not integrate the recited judicial exception into a practical application and the claim is directed to the judicial exception.
There are insignificant extra-solution activities that must be made of note:
Store the second replicas as new overall minimum cost (insignificant extra-solution activity)
At Step 2B, there are no additional elements claimed that amount to significantly more than the recited judicial exception. These additional elements are at best the equivalent of merely adding the words “apply it” to the judicial exception. Mere instructions to apply an exception cannot provide an inventive concept.
In regards to the insignificant extra-solution activity found in this limitation “store the second replicas as new overall minimum cost”, this action describes mere data gathering that is recited at a high level of generality. Per MPEP 2106.05(d)(II), the courts have recognized the following computer functions as well‐understood, routine, and conventional functions when they are claimed in a merely generic manner (e.g., at a high level of generality) or as insignificant extra-solution activity: iv. Storing and retrieving information in memory, Versata Dev. Group, Inc. v. SAP Am., Inc., 793 F.3d 1306, 1334, 115 USPQ2d 1681, 1701 (Fed. Cir. 2015); OIP Techs., 788 F.3d at 1363, 115 USPQ2d at 1092-93. This limitation therefore remains well, understood, routine and conventional even upon reconsideration. Thus, this limitation does not amount to significantly more.
Even when considered in combination, these additional elements represent mere instructions to apply an exception, which do not provide an inventive concept. The claim is not eligible.
Regarding claim 2, at Step 1, the claim is directed to a statutory category of invention (machine).
At Step 2A, Prong 1, Examiner notes that the claim recites an abstract idea. Below are the limitations of claim 2 that recite an abstract idea under mathematical concepts or mental steps:
wherein the instructions to generate the set of random replicas includes instructions to generate the replicas sampled from a uniform distribution of permutations (mathematical concepts);
All limitations as indicated describe “mathematical concepts”.
At Step 2A Prong 2, these are the no additional elements beyond those recited in claim 1.
The claim is not eligible.
Regarding claim 3, at Step 1, the claim is directed to a statutory category of invention (machine).
At Step 2A, Prong 1, Examiner notes that the claim recites an abstract idea. Below are the limitations of claim 3 that recite an abstract idea under mathematical concepts or mental steps:
wherein the instructions to generate the set of random replicas using Durstenfeld’s implementation for a Fisher-Yates algorithm.
All limitations as indicated describe “mathematical concepts”.
At Step 2A Prong 2, these are the no additional elements beyond those recited in claim 2.
The claim is not eligible.
Regarding claim 4, at Step 1, the claim is directed to a statutory category of invention (machine).
At Step 2A, Prong 1, Examiner notes that the claim recites an abstract idea. Below are the limitations of claim 4 that recite an abstract idea under mathematical concepts or mental steps:
wherein the local operations comprise a transposition of an adjacent pair of symbols. (mathematical concepts)
All limitations as indicated describe “mathematical concepts”.
At Step 2A Prong 2, these are the no additional elements beyond those recited in claim 1.
The claim is not eligible.
Regarding claim 5, at Step 1, the claim is directed to a statutory category of invention (machine).
At Step 2A, Prong 1, Examiner notes that the claim recites an abstract idea. Below are the limitations of claim 5 that recite an abstract idea under mathematical concepts or mental steps:
wherein the adjacent pair of symbols are selected randomly. (mental steps)
All limitations as indicated describe “mental steps”. Random selection of symbols can be practically carried out in the human mind or with the aid of pen and paper.
At Step 2A Prong 2, these are the no additional elements beyond those recited in claim 4.
The claim is not eligible.
Regarding claim 6, at Step 1, the claim is directed to a statutory category of invention (machine).
At Step 2A, Prong 1, Examiner notes that the claim recites an abstract idea. Below are the limitations of claim 6 that recite an abstract idea under mathematical concepts or mental steps:
Wherein the optimizing algorithm is a Quantum-Inspired Optimization technique including Parallel Tempering. (mathematical concepts)
All limitations as indicated describe “mathematical concepts”.
At Step 2A Prong 2, these are the no additional elements beyond those recited in claim 1.
The claim is not eligible.
Regarding claim 7, at Step 1, the claim is directed to a statutory category of invention (machine).
At Step 2A, Prong 1, Examiner notes that the claim recites an abstract idea. Below are the limitations of claim 7 that recite an abstract idea under mathematical concepts or mental steps:
Initialize a temperature space from Tmin to Tmax in accordance with a profile function with Tnum distinct temperatures; (mathematical concepts)
Initialize a random replica for each temperature in the temperature space; (mathematical concepts)
Initialize an overall minimum cost to infinity; and (mathematical concepts)
Initialize an iteration number to 0; (mathematical concepts)
Wherein each iteration further includes instructions to swap random neighboring replicas (mental steps)
All limitations as indicated describe “mathematical concepts” or “mental steps” as indicated. Swapping random neighboring replicas can be practically done in the human mind or with the aid of pen and paper.
At Step 2A Prong 2, these are the no additional elements beyond those recited in claim 6.
The claim is not eligible.
Regarding claim 8, at Step 1, the claim is directed to a statutory category of invention (machine).
At Step 2A, Prong 1, Examiner notes that the claim recites an abstract idea. Below are the limitations of claim 8 that recite an abstract idea under mathematical concepts or mental steps:
Wherein the probabilistic acceptance criterion is a Metropolis acceptance criterion, (mathematical concepts)
The instructions to iteratively swap random neighboring replicas swaps random neighboring replicas with Metropolis acceptance criterion (mental steps)
All limitations as indicated describe “mathematical concepts” or “mental steps” as indicated. The swapping of random neighboring replicas with Metropolis acceptance criterion could be practically done in the human mind or with the aid of pen and paper.
At Step 2A Prong 2, these are the no additional elements beyond those recited in claim 7.
The claim is not eligible.
Regarding claim 9, at Step 1, the claim is directed to a statutory category of invention (machine).
At Step 2A, Prong 1, Examiner notes that the claim recites an abstract idea. Below are the limitations of claim 9 that recite an abstract idea under mathematical concepts or mental steps:
wherein the optimizing algorithm is a Quantum-Inspired Optimization technique including Population Annealing. (mathematical concepts)
All limitations as indicated describe “mathematical concepts”.
At Step 2A Prong 2, these are the no additional elements beyond those recited in claim 1.
Regarding claim 10, at Step 1, the claim is directed to a statutory category of invention (machine).
At Step 2A, Prong 1, Examiner notes that the claim recites an abstract idea. Below are the limitations of claim 10 that recite an abstract idea under mathematical concepts or mental steps:
wherein the optimizing algorithm is a Quantum-Inspired Optimization technique including Substochastic Monte Carlo. (mathematical concepts)
All limitations as indicated describe “mathematical concepts”.
At Step 2A Prong 2, these are the no additional elements beyond those recited in claim 1.
The claim is not eligible.
Because claims 11-20 recite the method practiced by the apparatus of claims 1-10 respectively, claims 11-20 are rejected for the same reasons therein.
Claim Rejections - 35 USC § 103
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 1, 4-8, 11, and 14-18 are rejected under 35 U.S.C. 103 as being unpatentable over M. Aramon et al. ("Physics-Inspired Optimization for Quadratic Unconstrained Problems Using a Digital Annealer", 2019) (hereinafter “Aramon”).
Regarding claim 1, Aramon teaches:
A system comprising a computer including a processor and a memory (Aramon: Pg. 4 section 2.4 performed on a CPU, which would include a processor and a memory as is known in the art),
The memory storing instructions executable by the processor programmed to (Aramon: Pg. 4 section 2.4 performed on a CPU, which contains a processor or memory, instructions of the CPU would be stored in the memory to be executed, as is known in the art):
generate a set of random replicas for a permutation-based optimization problem having an objective function representing only an original unconstrained objected (Aramon: Pg. 4 Algorithm 3 line 1, all replicas initialized with a random initial state i.e., random replicas; Abstract used for QUBO (quadratic unconstrainted binary optimization problems) i.e., unconstrained objective function, for swap based optimization (swap i.e., permutation)),
wherein each replica is a sequence of n symbols (Aramon: Pg. 4 Algorithm 3 and Col. 2 first paragraph each replica has variables. i.e., temperatures i.e., trials, the n symbols within);
define a neighborhood for each replica within a domain of the objective function (Aramon: Pg. 4 Col. 2 first paragraph - keeping track of neighbors, i.e., neighborhood of replica is defined); and
iteratively perform steps of an optimization algorithm to (Aramon: Pg. 4 Algorithm 3):
perform local operations with probabilistic acceptance criterion to transform a first replica to a second replica with in a neighborhood of the first replica (Aramon: Pg. 4 Algorithm 3 lines 7-9 replica exchange, replicas transform into one another within neighborhood as discussed in Pg. 4 Col. 2 first paragraph; Pg. 3 Col 2 Section 2.3 local operations= exchange of neighboring temperatures i.e., adjacent symbols using metropolis criterion i.e., probabilistic acceptance criterion).
The embodiment of parallel as taught by Aramon does not explicitly teach:
compare a least cost of the second replica to a previously stored overall minimum cost.
store the second replica as a new overall minimum cost when the least cost of the second replica is less than the previously stored overall minimum cost; and
perform a next iteration until a convergence or a maximum number of iterations is achieved.
However, the embodiment discussed on Pg. 6 Section 5 onwards of Aramon teaches:
compare a least cost of the second replica to a previously stored overall minimum cost (Aramon: Pg. 6 Section 5, digital annealer can solve QUBO problems in the form of Ising models (cost function), minimum cost is updated i.e., stored);
store the second replica as a new overall minimum cost when the least cost of the second replica is less than the previously stored overall minimum cost (Aramon: Pg. 2 Col. 2 Section 2.1 starts at high temperature, decrease of temperature with each update (swap), Algorithm 1 lines 4-10 update i.e., storing of minimum; temperature = cost, Pg. 6 Section 5 discusses same dynamic except with spin glass Hamiltonian scenario (cost function)); and
perform a next iteration until a convergence or a maximum number of iterations is achieved (Pg. 5 Fig. 1 and Fig. 2 shows iterations occurring until results are converging, also discuss maximum number of iterations to occur, number of iterations also shown in Algorithm 2 on Pg. 3).
It would be obvious before the effective filing date of the claimed invention to apply the techniques discussed with respect to the second embodiment of Aramon with the techniques discussed with respect to the first embodiment of Aramon because both embodiments seek to find an optimal solution for a QUBO problem. One with ordinary skill in the art would be motivated to combine the techniques because doing so would allow for increased efficiency in terms of finding an optimal solution (Aramon: Pg. 6 Section 5).
Regarding claim 4, Aramon teaches:
The system of claim 1, wherein the local operations comprise a transposition of an adjacent pair of symbols (Aramon: Pg. 3 Col. 2 Section 2.3 exchange i.e., transposition between neighboring temperatures i.e., adjacent symbols).
Regarding claim 5, Aramon teaches:
The system of claim 4, wherein the adjacent pair of symbols are selected randomly (Aramon: Pg. 3 Col. 2 Section 2.3 random walk in temperatures are carried out -> random selection of adjacent symbols).
Regarding claim 6, Aramon teaches:
The system of claim 1, wherein the optimizing algorithm is a Quantum-Inspired Optimization technique including Parallel Tempering (Aramon: method disclosed is parallel tempering Sections 2.3, 2.4 state this explicitly in header).
Regarding claim 7, Aramon teaches:
The system of claim 6, further comprising instructions to:
initialize a temperature space from Tmin to Tmax in accordance with a profile function with Tnum distinct temperatures (Aramon: Pg. 3 Section 2.3 temperature space initialized, within which random walks are performed for optimization algorithms);
initialize a random replica for each temperature in the temperature space (Aramon: Pg. 3 Section 2.3 temperature space initialized, within which random walks are performed for optimization algorithms, replicas initialized for the various temperatures);
initialize an overall minimum cost to infinity (Aramon: Pg. 2 Col. 2 Section 2.1 initialized at a high temperature (infinity)); and
initialize an iteration number to 0 (Aramon: Pg. 3 Alg 2 initialize state (to 0));
wherein each iteration further includes instructions to swap random neighboring replicas (Pg. 4 Algorithm 3 shows at each iteration swaps occurring).
Regarding claim 8, Aramon teaches:
The system of claim 7, wherein the probabilistic acceptance criterion is a Metropolis acceptance criterion, and the instructions to iteratively swap random neighboring replicas swaps random neighboring replicas with Metropolis acceptance criterion (Aramon: Pg. 3 Col 2 Section 2.3 local operations= exchange of neighboring temperatures i.e., adjacent symbols using metropolis criterion i.e., probabilistic acceptance criterion).
Claims 11 and 14-18 recite the method practiced by the apparatus of claims 1 and 4-8 respectively and are therefore rejected for the same reasons therein.
Claims 2-3 and 12-13 are rejected under 35 U.S.C. 103 as being unpatentable over Aramon further in view of P. Wojnowski ("Fisher-Yates Shuffle Algorithm", 2017) (hereinafter “Wojnowski”).
Regarding claim 2, while Aramon teaches the system of claim 1, Aramon does not explicitly teach the instructions to generate the set of random replicas being sampled from a uniform distribution of permutations.
However, Wojnowski teaches:
instructions to generate the replicas sampled from a uniform distribution of permutations (Wojnowski: Pg. 1 Shuffling Traps Section, Fisher-Yates algorithm is example of shuffling algorithm that samples and shuffles permutations with equal probability i.e., uniform distribution).
It would be obvious before the effective filing date of the claimed invention to combine the sampling at a uniform distribution as taught by Wojnowski with the system as taught by Aramon as both teachings are directed towards optimization through permutations. One with ordinary skill in the art would be motivated to combine the teachings because doing would allow for operation of the algorithm O(n) time and operations in place, thus allowing for memory efficiency (Wojnowski: Pg. 1).
Regarding claim 3, Aramon in view of Wojnowski further teaches:
The system of claim 2, wherein the instructions to generate the set of random replicas using Durstenfeld’s implementation for a Fisher-Yates algorithm (Wojnowski: Pgs. 1-2 Fisher Yates Shuffle Section and Durstenfeld Implementation Section).
The motivation to combine with respect to claim 2 applies equally to claim 3.
Claims 12-13 recite the method practiced by the apparatus of claims 2-3 respectively and are therefore rejected for the same reasons therein.
Claims 9-10 and 19-20 are rejected under 35 U.S.C. 103 as being unpatentable over Aramon further in view of M. Jarret et al. ("Adiabatic optimization versus diffusion Monte Carlo methods", 2016) (hereinafter “Jarret”).
Regarding claim 9, while Aramon teaches the system of claim 1, Aramon does not explicitly teach Population Annealing.
However, Jarret teaches:
wherein the optimizing algorithm is a Quantum-Inspired Optimization technique including Population Annealing (Jarret: Pg. 042318-2 Section III).
It would be obvious before the effective filing date of the claimed invention to combine the population annealing as taught by Jarret with the system as taught by Aramon as both teachings are directed towards finding the optimal solution for a combinatorial optimization problem. One with ordinary skill in the art would be motivated to combine the teachings because these techniques would be more helpful for larger datasets (Jarret: Pg. 042318-2 Section III and Pg. 042318-3 second paragraph).
Regarding claim 10, while Aramon teaches the system of claim 1, Aramon does not explicitly teach the algorithm being a Substochastic Monte Carlo.
However, Jarret teaches:
wherein the optimizing algorithm is a Quantum-Inspired Optimization technique including Substochastic Monte Carlo (Jarret: Pg. 042318-2 Section III).
Claim 19-20 recites the method practiced by the apparatus of claim 10 and is therefore rejected for the same reasons therein.
Prior Art Made of Record
The prior art made of record and not relied upon is considered pertinent to applicant's disclosure.
H. Katzgraber et al. (“Feedback-optimized parallel tempering Monte Carlo”, 2006) teaches optimizing parallel tempering Monte Carlo simulations by sampling from the temperature set in order to increase acceptance rates of swaps or exchanges.
Tomita (US 2020/0380065 A1) teaches an apparatus for finding an optimal solution for a combinatorial optimization problem by searching for a ground state of an Ising model and converting this model into a combinatorial optimization problem, followed by execution of a simulation and evaluation of the result of the simulation based on an evaluation criterion. This then helps to update the Ising model and further add constraints if needed in order to attain the most optimal solution.
Z. Zhu et al. ("borealis - A generalized global update algorithm for Boolean optimization problems", 2020) teaches parallel tempering via a series of Monte Carlo sweeps and exchanging of temperatures using a Metropolis criterion.
Conclusion
Any inquiry concerning this communication or earlier communications from the examiner should be directed to MARIA DE JESUS RIVERA whose telephone number is (571)272-2793. The examiner can normally be reached Monday-Friday 7:30AM-5PM.
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, James Trujillo can be reached at (571) 272-3677. 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.D.R./Examiner, Art Unit 2151
/EMILY E LAROCQUE/Primary Examiner, Art Unit 2182
Prosecution Insights