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-19 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.
Regarding claim 9, under the Alice framework Step 2A prong 1, the claim recites Mathematical concepts for generating an optimization function for solving an optimization problem. Specifically the claim recites the following mathematical concepts:
generate an optimization function for solving the combinatorial optimization problem using the input, wherein N is an integer equal to or greater than 1, Idx = {0, ..., N - 1} is a set of indexes indicating N states, and i satisfies i ϵ Idx, and
generate the optimization function using a quantum byte obtained by performing encoding so that digits when an index i is expressed as a binary number each match a corresponding quantum bit included in a quantum byte, the quantum byte being a sequence of log2N quantum bits.
See e.g., specification [0127-0131], which describes the claimed invention in terms of mathematical equations, specifically equation 28, which describes the encoding of the optimization function. For these reasons, the claim recites mathematical concepts, including mathematical relationships, and mathematical calculations.
Under the Alice framework Step 2A prong 2 analysis, additional elements not reciting Mathematical relationships and mathematical calculations thereof include: an optimization function generation apparatus comprising: input setting circuitry configured to set an input of a combinatorial optimization problem. These additional elements do no more than generally link the additional element to the mathematical relationships and mathematical calculations in a manner that in effect merely recites “apply it” in a computer, using generically recited apparatus and input setting circuitry. Furthermore the setting of an input of a combinatorial problem merely comprises an insignificant extra solution activity. For these reasons, the claim is not integrated into a practical application.
Moreover, under the Alice Framework Step 2B analysis, the claim, considered individually and as an ordered combination does not include additional elements that are sufficient to amount to significantly more than the abstract idea. As discussed in the Step 2A prong 2 analysis, the claim merely generally links the additional element to the math in a manner that merely recites “apply it’ in a computer. Furthermore, the setting of an input of a combinatorial problem comprises well understood, routine, and conventional activity. See MPEP 2106.05(d).i. receiving and gathering data. For these reasons the claim when considered as a whole does not amount to significantly more than the abstract idea.
Claims 2-16 are rejected for at least the reasons set forth with respect to claim 1. Claims 2-13 contain no further additional elements beyond those recited in claim 1 that would require further analysis under Step 2A prong 2 or Step 2B. For these reasons claims 2-13 are neither integrated into a practical application nor amounting to significantly more than the abstract idea.
Claims 14, 15, and 16 respectively include the further additional elements of wherein the combinatorial optimization problem is a graph coloring problem, a scheduling problem of generating a plan for an execution start time of a process, and a bandwidth allocation planning problem of generating a bandwidth allocation plan for a path satisfying a condition. Under the step 2A prong 2 and step 2B analysis, these further additional elements each merely generally link to a field of use. For these reasons claims 14-16 are neither integrated into a practical application nor amounting to significantly more than the abstract idea.
Claim 17 is directed to a method that would be practiced by the apparatus of claim 1. All steps recited in claim 17 are practiced by the apparatus of claim 1 as configured. The claim 1 analysis applies equally to claim 17.
Claim 18 is directed to a non-transitory computer readable medium storing a program that would cause a computer to practice the steps of the apparatus as in claim 1. The claim 1 analysis applies equally to claim 18.
Claim 19 is directed to a non-transitory computer readable medium storing a program that would cause a computer to perform the steps of the method as in claim 17. The claim 17 analysis applies equally to claim 19.
Allowable Subject Matter
Claims 1-19 would be allowable if rewritten to overcome the respective rejections under 35 USC 101. The following is a statement of reasons for the indication of allowable subject matter.
Applicant claims apparatus, a method and non-transitory computer-readable storage medium storing a program that causes a computer to function, wherein the apparatus as in claim 1 comprises:
input setting circuitry configured to set an input of a combinatorial optimization problem; and
optimization function generation circuitry configured to generate an optimization function for solving the combinatorial optimization problem using the input,
wherein N is an integer equal to or greater than 1, Idx = {0, ..., N - 1} is a set of indexes indicating N states, and i satisfies i ϵ Idx, and
the optimization function generation circuitry generates the optimization function using a quantum byte obtained by performing encoding so that digits when an index i is expressed as a binary number each match a corresponding quantum bit included in a quantum byte, the quantum byte being a sequence of log2N quantum bits.
The primary reason for indication of allowable subject matter are the limitations, taken in combination, and specifically the above highlighted limitations.
US 20140344322 A1 Ranjbar (hereinafter “Ranjbar”) discloses computational techniques for mapping a discrete variable objective function to facilitation determining a solution via a quantum processor (abstract, fig 3). Ranjbar further discloses defining a finite set of integers for an objective function with the values represented by indices, and determining Hamming distance between bit strings ([0037-0041]). Ranjbar does not, however, explicitly disclose the above highlighted limitations.
US 20190087388 A1 Venturelli et al., (hereinafter “Venturelli”) discloses using an Ising machine to run integer linear programming problems using quadratic unconstrained binary optimization (QUBO) mapping (abstract, [0004-0008], [0061], [0076]). Venturelli further discloses a penalty function with non-zero integer parameter encoding ([0078-0081]). Venturelli does not, however, explicitly disclose the above highlighted limitations.
A. Minimisawa et al., High-speed Sparse Ising Model on FPGA, 2019 IEEE 62nd International Midwest Symposium on Circuits and Systems (MWSCAS), IEEE 2019 (hereinafter “Minimisawa”) discloses solving a combinatorial optimization problem using an Ising model with binary mapping (Section II.D.E). Minimisawa does not, however, explicitly disclose the above highlighted limitations.
A. Butko et al., TIGER: Topology-aware Task Assignment Approach using Ising machines, Proceedings of the 16the conference on Computing Frontiers (CF’ 19), 2019 (hereinafter “Butko”), discloses task assignment optimization using QUBO based on a task communication graph approach (Introduction p. 107 left column). Butko further discloses a binary solution (fig 3, fig 4). Butko does not, however, explicitly disclose the above highlighted limitations.
K. Miyahara et al., Scalable Integer Encoding in Quadratic Unconstrained Binary Optimization, NTT Software Innovation Center, ISC High Performance, 21-25 June 2020, (hereinafter “Miyahar”), disclosure by Applicant of aspects of the claimed invention.
Conclusion
Any inquiry concerning this communication or earlier communications from the examiner should be directed to EMILY E LAROCQUE whose telephone number is (469)295-9289. The examiner can normally be reached on 10:00am - 1200pm, 2:00pm - 8pm ET M-F.
Examiner interviews are available via telephone, in-person, and video conferencing using a USPTO supplied web-based collaboration tool. To schedule an interview, applicant is encouraged to use the USPTO Automated Interview Request (AIR) at http://www.uspto.gov/interviewpractice.
If attempts to reach the examiner by telephone are unsuccessful, the examiner’s supervisor, Andrew Caldwell can be reached on 571 272 3702. The fax phone number for the organization where this application or proceeding is assigned is 571-273-8300.
Information regarding the status of an application may be obtained from the Patent Application Information Retrieval (PAIR) system. Status information for published applications may be obtained from either Private PAIR or Public PAIR. Status information for unpublished applications is available through Private PAIR only. For more information about the PAIR system, see http://pair-direct.uspto.gov. Should you have questions on access to the Private PAIR system, contact the Electronic Business Center (EBC) at 866-217-9197 (toll-free). If you would like assistance from a USPTO Customer Service Representative or access to the automated information system, call 800-786-9199 (IN USA OR CANADA) or 571-272-1000.
/EMILY E LAROCQUE/Primary Examiner, Art Unit 2182