Ur 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 .
Priority
Receipt is acknowledged of certified copies of papers required by 37 CFR 1.55.
This office action is in response to submission of application on 3/13/2023
Claims 1-8 are presented for examination.
Claim Rejections - 35 USC § 112
The following is a quotation of 35 U.S.C. 112(b):
(b) CONCLUSION.—The specification shall conclude with one or more claims particularly pointing out and distinctly claiming the subject matter which the inventor or a joint inventor regards as the invention.
The following is a quotation of 35 U.S.C. 112 (pre-AIA ), second paragraph:
The specification shall conclude with one or more claims particularly pointing out and distinctly claiming the subject matter which the applicant regards as his invention.
Claim 1-8 are rejected under 35 U.S.C. 112, second paragraph, as being indefinite for failing to particularly point out and distinctly claim the subject matter which applicant regards as the invention.
Claim 1 includes the limitation “compare a data amount of a QUBO model to be processed by an annealing engine and a data amount of a program representing the QUBO model;” Claim 1 recites, a “QUBO model” without defining the abbreviation “QUBO.” As well as the second recitation of “a data amount” is indefinite through antecedent basis. It is unclear whether it refers back to the data amount already recited or introduces a second, distinct data amount. Additionally, claim 1 includes another limitation, “transmit whichever has a lower data amount to the annealing engine.” This limitation is indefinite because “lower” is a comparative term recited without an express basis of comparison. The claim does not state what the data amount must be lower than.
Claim 2 includes the limitation of “convert the extracted Hamiltonian to a Hamiltonian with a lower data amount by mathematical formula manipulation” Claim 1 recites, “a lower data amount” which is indefinite due to what constitutes as “lower” and lack antecedent basis since claim 1 already introduces this such that it’s unclear if it’s the same “lower data amount” or a different amount.
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-8 are rejected under 35 U.S.C. 101 because the claimed invention is directed to an abstract idea without significantly more.
Step 1: Is the claim to a process, machine, manufacture, or composition of matter?
Claims 1-6 are directed to a device; claim 7 is directed to a system; and claim 8 is directed to a method; therefore, all claims are directed to one of the four statutory categories.
Step 2A Prong One: Does the claim recite an abstract idea, law of nature, or natural phenomenon?
Claim 1 recites limitations of:
compare a data amount of a QUBO model to be processed by an annealing engine and a data amount of a program representing the QUBO model; - mental process (observation, evaluation, judgement) as a human mind can compare a data amount to be processed.
Step 2A Prong Two: Does the claim recite additional elements that integrate the judicial
exception into a practical application?
Claim 1 recites additional elements of:
at least one memory confiqured to store instructions, and at least one processor configured to execute the instructions to: – components recited at a high level are construed as generic computer components used to implement the abstract idea. See MPEP 2106.05(f)(2).
transmit whichever has a lower data amount to the annealing engine. – transmitting whichever has a lower data amount merely amounts to transmitting data which is insignificant extra-solution activity. See MPEP §2106.05(g), item (3), which identifies transmitting data as an example of extra-solution activity.
The additional elements do not integrate the abstract idea into a practical application.
Step 2B: Does the claim recite additional elements that amount to significantly more than the
judicial exception?
The additional elements are:
at least one memory confiqured to store instructions, and at least one processor configured to execute the instructions to: – components recited at a high level are construed as generic computer components used to implement the abstract idea. See MPEP 2106.05(f)(2).
transmit whichever has a lower data amount to the annealing engine. – transmitting whichever has a lower data amount merely amounts to transmitting data which is insignificant extra-solution activity. See MPEP §2106.05(g). Transmitting data is well-understood, routine, and conventional. See MPEP 2106.05(d)(II)(i)
The additional elements do not amount to significantly more than the abstract idea. Therefore,
the claim is not patent eligible.
Independent claims 7 and 8 recite the same relevant limitations and a similar analysis applies. Claim 7 recites the additional elements of, “An information processing system comprising: an information processing; device; and an annealing engine, wherein the information processing device comprises: at least one memory configured to store instructions, and at least one processor configured to execute the instructions to:” – components recited at a high level are construed as generic computer components used to implement the abstract idea. See MPEP 2106.05(f)(2). Claim 8 does not recite any additional elements. They do not integrate the abstract idea into a practical application. Nor do they amount to significantly more. Therefore, the independent claims are not patent eligible.
The above analysis similarly applies to the dependent claims.
Dependent claim 2 recites,
extract, from the program, a Hamiltonian among processes to be performed in the annealing - extracting a Hamiltonian merely amounts to data gathering which is insignificant extra-solution activity. See MPEP § 2106.05(g). Data gathering is well-understood, routine, and conventional. See MPEP 2106.05(d)(II)(iv),
convert the extracted Hamiltonian to a Hamiltonian with a lower data amount by mathematical formula manipulation; - mathematical concept (relationships, formulas or equations, calculations) of using a mathematical formula
and convert a process represented by the converted Hamiltonian to a program. - converting a process merely amounts to recalculate, readjust which is insignificant extra-solution activity. See MPEP § 2106.05(g). Recalculating and readjusting is well-understood, routine, and conventional. See MPEP 2106.05(d)(II)(ii)
Dependent claim 3 recites,
convert the process represented by the Hamiltonian to the program by using a condition that a square of a quantum bit is equal to said quantum bit. - mathematical concept (relationships, formulas or equations, calculations) of using a condition that a square of quantum bit is equal to a said quantum bit
Dependent claim 4 recites,
convert, in a case in which a process for computing the Hamiltonian is described by an iterative process in the program, the iterative process to a function representing a process equivalent to said iterative process. - mathematical concept (relationships, formulas or equations, calculations) of using an iterative process
Dependent claim 5 recites,
convert, in a case in which the Hamiltonian in the program includes second spin introduced such that a product of three or more spins becomes a product of two or fewer spins, the program to a second program not including the second spin - converting a process merely amounts to recalculate, readjust which is insignificant extra-solution activity. See MPEP § 2106.05(g). Recalculating and readjusting is well-understood, routine, and conventional. See MPEP 2106.05(d)(II)(ii)
Dependent claim 6 recites,
determine whether or not a matrix representing the QUBO model satisfies a criterion for determining whether to execute a compression process on the matrix; - mental process (observation, evaluation, judgement) as a human mind can determine if a matrix satisfies a criterion
and convert, if the matrix satisfies the criterion, the matrix to information represented in a prescribed compression format. - converting a process merely amounts to recalculate, readjust which is insignificant extra-solution activity. See MPEP § 2106.05(g). Recalculating and readjusting is well-understood, routine, and conventional. See MPEP 2106.05(d)(II)(ii)
The dependent claims do not integrate the abstract idea into a practical application, nor do they
amount to significantly more than the abstract idea.
Claim Rejections - 35 USC § 103
In the event the determination of the status of the application as subject to AIA 35 U.S.C. 102 and 103 (or as subject to pre-AIA 35 U.S.C. 102 and 103) is incorrect, any correction of the statutory basis (i.e., changing from AIA to pre-AIA ) for the rejection will not be considered a new ground of rejection if the prior art relied upon, and the rationale supporting the rejection, would be the same under either status.
The following is a quotation of 35 U.S.C. 103 which forms the basis for all obviousness rejections set forth in this Office action:
A patent for a claimed invention may not be obtained, notwithstanding that the claimed invention is not identically disclosed as set forth in section 102, if the differences between the claimed invention and the prior art are such that the claimed invention as a whole would have been obvious before the effective filing date of the claimed invention to a person having ordinary skill in the art to which the claimed invention pertains. Patentability shall not be negated by the manner in which the invention was made.
The following are the references being used:
Ueda et al. (Data Structure for Quantum Annealing Emulator, herein Ueda)
Kim et al. (Leveraging Quantum Annealing for Large MIMO Processing in Centralized Radio Access Networks, herein Kim)
Tanahashi et al. (Application of Ising Machines and a Software Development for Ising Machines, herein Tanahashi)
Hauke et al. (Perspectives of quantum annealing: Methods and implementations, herein Hauke)
Claim(s) 1, 6, 7, and 8 is/are rejected under 35 U.S.C. 103 as being unpatentable over Ueda in
view Kim.
Regarding claim 1,
Ueda teaches,
An information processing device comprising: at least one memory confiqured to store instructions, and at least one processor configured to execute the instructions to: (Ueda, page 5, section 4.2, “This study was conducted using a Linux OS on a computer with an Intel Core i5-8400CPU@2.80G Hz and 8.0 GB of main memory” and section 4.1, “From input to compression and finding the optimal solution, four programs – input, duplicate, compress, and h file creation – were implemented using the C language.”)
compare a data amount of a QUBO model to be processed by an annealing engine and a data amount of a program representing the QUBO model; (Ueda, abstract, “To specify an ising model or an equivalent QUBO (Quadrative Unconstrained Binary Optimization) model, all coefficients between a pair of quantums and the self energy of each quantum need to be described. The data size between large and its reduction is important for the emulation since the usable memory size is limited.”, page 5, section 4.1, “Compression is performed on inputs based on the Ising model (QUBO)… A program has also been created to generate an Ising model description from the distance between cities.”, section 4.2, “Table 2 shows the evaluation of the file size before and after compression… Next, we compare the size of each data point within the emulation, taking into account the bit length”, page 3, section 3.1, “Note that this representation method focusing on non-elements increases the amount of description when there are few 0s, due to the explicit display of information in the index part.” and section 3.3, “when the original amount of data is small, the amount of description actually increases” note: Ueda defines the QUBO model as the set of coefficients between spin pairs plus each spin’s self energy. Ueda also states that an Ising model and a QUBO model are the same thing described two ways. This is important because Ueda uses Ising throughout the reference which is equivalent to QUBO in the claim. Ueda’s whole reference is about a quantum annealing engine and it states that the compressed input file is passed to that emulator, which then goes on the solve the problem. Ueda also wrote a program that takes city distances in and puts an Ising model description out because the description that program produces is the QUBO model, the program is a second way of expressing a program representing the QUBO model. Comparing the data amounts maps to how Ueda takes one description of a QUBO problem, produces a second description of the same problem, measures both in bytes, and puts the number next to each other in Table 2. This is the comparing step as it compares the sizes.)
Ueda does not teach, transmit whichever has a lower data amount to the annealing engine.
Kim teaches,
transmit whichever has a lower data amount to the annealing engine. (Kim, page 5, section 3.2.1, “It has the desirable property that it maps solution variables to symbols linearly… thus results in a QUBO form… The transform vI i =2(2q4i−3−1)+ 2(q4i−3−q4i−2)2−1 would map between a 4-PAM symbol vI i and two QUBO variables q4i−3,q4i−2, but the resulting expansion of the ML norm would yield cubic and quartic terms qr qkql(qp) for r k l( p), requiring quadratization with additional variables to represent the problem in QUBO form[8,33]. Instead, we retain Gray coding at the transmitter and the QuA Max transform at the receiver”, page 6, section 3.3, “Once Ising coefficients are passed to the annealer, the hardware assigns them to the edges of the Chimera graph, which are divided (along with their connected nodes) into unit cells” page 12, section 7, “The scenario envisioned by QuAMax assumes a centralized RAN architecture where a QPU, co-located with centralized RAN computational resources in a data center, is connected to the APs via high-speed fiber or millimeter-wave links” note: picking the smaller data amount maps to how Kim has two different ways to write the same detection program as a QUBO. It works out what each one costs. The first one, if expanded, produces terms multiplying three and four variable together, and an annealer can only handle two at a time, so you would have to add extra variable to break those products down. This is what requiring quadratization with additional variables means. The second way avoids the problem completely, it maps variables to symbols in a straight line, so the expansion stays quadratic and no extra variables are needed. Kim then chooses, instead, we retain... the QuAMax transform at the receiver. More variables means more data, so QuAMax is rejecting the costlier representation in favor of the cheaper one. QuAMax sends the coefficients of the formulation it kept. It describes them being passed to the annealer, which loads them onto the chip.)
It would be obvious to one of ordinary skill in the art before the effective filing date of the
claimed invention to combine the teaching of Ueda and Kim because it will allow for a reduction in the programming and preprocessing overhead that Kim identifies in section 5.2 and 7 as dominating total computation time by several orders of magnitude.
Regarding claim 6,
The combination of Ueda and Kim teaches,
determine whether or not a matrix representing the QUBO model satisfies a criterion for determining whether to execute a compression process on th; (Ueda, page 3, section 3.1, “Since is often a sparse matrix 0 with many elements, simple enumeration methods are inefficient. Therefore… a method is used to represent the non-elements… as a sequence of three terms… Note that this representation method focusing on non-elements increases the amount of description when there are few 0s, due to the explicit display of information in the index part.” and section 3.3, “when the original amount of data is small, the amount of description actually increases” note: Ueda states that the coefficient matrix is often sparse and that plan enumeration is inefficient for it, and states that the method instead records the non-zero elements as three-term sequences. Ueda states that this method increases the amount of description where there are few zeros, because index information must then be written explicitly. Ueda states the same failure where the original data amount is mall. Ueda therefore states a condition determining whether the compression is worth performing, the matrix must be sparse enough, and the input large enough, that the compressed form is in fact smaller. Ueda presents compression as conditional, not automatic.)
and convert, if the matrix satisfies the criterion, converts the matrix to information represented in a prescribed compression format (Ueda, page 4, section 3.2, “Compressed Row Storage (CRS) is a known method for representing sickle matrices… CRS aims to reduce the amount of code in the index section by first sorting up to the (i, j) order, and then separately storing information about which data point is related to each bag” section 3.3, “In this case, by creating a separate value table and representing it with an index to it, the amount of data can be reduced compared to representing the value itself. Furthermore, since the index increases with the type number, the number of repetitions can be listed alongside it to represent multiple values at once… The data size of the proposed representation is (beginning, count, increment, index, flag), with each being (16 bits, 8 bits, 8 bits, 16 bits, 1 bit)”, note: Ueda discloses two defined layouts. The first is Compressed Row storage, which Ueda identifies by name as a known method. The second one Ueda states that a separate value table is created and represented by an index into it, and that a repetition count is listed alongside the index so that multiple values are represented at once.)
Claim 7 is a system claim, An information processing system comprising: an information processing device; and an annealing engine, wherein the information processing device comprises: at least one memory configured to store instructions, and at least one processor configured to execute the instructions to: (Kim, page 3, Figure 1, “A D-Wave 2000Q (DW2Q) machine at NASA Ames Research Center, which hosts a Whistler processor manufactured with 2,048 qubits and 5,019 qubit-coupling parameters” and page 12, section 7, “a QPU, co-located with centralized RAN computational resources in a data center, is connected to the APs via high-speed fiber or millimeter-wave links.”), that corresponds to claim 1. Otherwise, they are not patentably distinguishable. Therefore, claim 7 is rejected for the same reasons as claim 1.
Claim 8 is a method claim that corresponds to claim 1. Otherwise, they are not patentably distinguishable. Therefore, claim 8 is rejected for the same reasons as claim 1.
Claim(s) 2, 3, 4, and 5 is/are rejected under 35 U.S.C. 103 as being unpatentable over Ueda in
view Kim and in further view of Tanahashi and Hauke.
Regarding claim 2,
The combination of Ueda and Kim does not teach,
extract, from the program, a Hamiltonian among processes to be performed in the annealing;
convert the extracted Hamiltonian to a Hamiltonian with a lower data amount by mathematical formula manipulation;
and convert a process represented by the converted Hamiltonian to a program.
Tanahashi teaches,
extract, from the program, a Hamiltonian among processes to be performed in the annealing; (Tanahashi, page 9, section 5.2, “We can tell the compiler which terms in the Hamiltonian represent equality=inequality constraints using the Constraint class in PyQUBO. By just using Constraint, we can extract the information about unsatisfied constraints in the obtained results. In the example for the graph partitioning problem (Table III), the Hamiltonian for the problem is contained in a Constraint object (line 17).” and page 8, section 5, “The Hamiltonian in PyQUBO is internally represented as a tree. For example, the Hamiltonian for the number partition ing problem is represented as a tree shown in the left panel of Fig. 3. The compilation process of PyQUBO is shown in the right panel of Fig. 3. Firstly, the Hamiltonian is converted to a higher-order polynomial by folding the tree. Then, a higher order polynomial is reduced to a second-order polynomial by introducing auxiliary variables. Finally, the QUBO matrix is created from the coefficients of the second-order polynomial” note: Tanahashi states that the Hamiltonian is contained in a constraint object at line 17 of the program shown in Table 3, and that the compiler is told which of its terms represent constraints. Tanahashi states that the compiler then takes that Hamiltonian, folds it into a polynomial, reduces it, and creates the QUBO matrix from the result, the matrix the Ising machine executes. The claim’s extractions of a Hamiltonian from the program reads on the compiler taking up the Hamiltonian identified inside the program and carrying it forward into the QUBO the annealer runs.)
and convert a process represented by the converted Hamiltonian to a program. (Tanahashi, page 7, section 5, “Practically, we need to write a program to prepare the QUBO matrix corresponding to the combinatorial optimization problem. To obtain the QUBO matrix, we rewrite the Hamiltonian such that the linear and quadratic terms of the spin variables or 0–1 binary variables are separate… To write a program for preparing the QUBO, we need to manually expand the Hamiltonian as
PNG
media_image1.png
40
152
media_image1.png
Greyscale
Using the above equation and dimod developed by D-Wave Systems,40) we can write a code to produce the QUBO in Python(TableI).” and page 8, “Firstly, we define the array of spin variables (line 6) and the Hamiltonian of the problem (line 9). Then, we compile the Hamiltonian to get the model (line 12). Finally, the QUBO is generated by calling the to_qubo() method of the model (line 15)” note: Tanahashi states the sequence the claim recites, in order and in the reference’s own words. First, the Hamiltonian is rewritten and manually expanded. Then a program is written from the rewritten form and then it prints that code in the PyQUBO version. The claim’s converted Hamiltonian read on Tanahashi’s rewritten and expanded Hamiltonian. The claim’s conversion of the process it represents to a program reads on Tanahashi’s statement that a code is written from the equation to produce the QUBO.”
It would be obvious to one of ordinary skill in the art before the effective filing date of the
claimed invention to combine the teaching of Ueda, Kim, and Tanahashi because it would help allow avoiding the software bugs that Tanahashi identifies in section 5 since expanding the Hamiltonian by hand is susceptible to software bugs from miscalculation and gets worse as constraints multiple.
Tanahashi does not teach,
convert the extracted Hamiltonian to a Hamiltonian with a lower data amount by mathematical formula manipulation;
Hauke teaches,
convert the extracted Hamiltonian to a Hamiltonian with a lower data amount by mathematical formula manipulation; (Hauke, page 5, “If the problem of interest has a cost function of high-order interactions (k-local with k ≥3), one should reduce it to QUBO format by using ancillary variables to implement it on a real device. For example, a 3-local expression x1x2x3 is reduced to x1x4 if we define x4 = x2x3… While this technique has the advantage that any problem can in principle be studied on a currently-available device, it usually leads to a large overhead in the number of variables. Therefore, effort should further be made in studying combinatorial problems in their native HOBO form. We concentrate on QUBO in this article” note: Hauke describes one problem written two ways. In the original, a term can multiple three or more variables together. In the reworked version, those long products have been broken apart by inventing new variables. Getting between the two is ordinary algebra swap in a new name for a product then add a term that forces the new name to equal what it stans form is the claims formula manipulation.
It would be obvious to one of ordinary skill in the art before the effective filing date of the
claimed invention to combine the teaching of Ueda, Kim, Tanahashi, and Hauke because it would allow there to fit a larger problem within the machine’s fixed variable budget, since Hauke states in section 6 that approximately 30 logical spin variables can be embedded in the 2000 variables of the D-Wave 2000Q and that this overhead severely limits what can be studied.
Regarding claim 3,
The combination of Ueda, Kim, Tanahashi, and Hauke teaches,
convert the process represented by the Hamiltonian to the program by using a condition that a square of a quantum bit is equal to said quantum bit. (Kim, page 4, section 3.2.1, “When transform T is linear the expansion of the norm in Eq. 5 yields a quadratic polynomial objective function, since q2 i = qi for any 0 or 1-valued qi.” And page 14, “Using q2 i =qi, minimization of this objective function becomes the QUBO form (Eq.3):” note: the claim’s condition is that squaring a bit gives back the same bit. That holds for 0 and 1 and nothing else. Kim states it in exactly those terms and says applying it is what turns the multiplied out expression into the form the machine accepts. Kim says this twice, once as the general rule, and the other inside a fully worked example.)
Regarding claim 4,
The combination of Ueda, Kim, Tanahashi, and Hauke teaches,
convert, in a case in which a process for computing the Hamiltonian is described by an iterative process in the program, the iterative process to a function representing a process equivalent to said iterative process. (Tanahashi, page 7, section 5, “… To write a program for preparing the QUBO, we need to manually expand the Hamiltonian as
PNG
media_image1.png
40
152
media_image1.png
Greyscale
Using the above equation and dimod developed by D-Wave Systems,40) we can write a code to produce the QUBO in Python(TableI)”, page 8, Table 1 and 2, “
PNG
media_image2.png
392
622
media_image2.png
Greyscale
” and page 8, section 5, “we compile the Hamiltonian to get the model (line 12). Finally, the QUBO is generated by calling the to_qubo() method of the model (line 15). The code becomes much straightforward and readable than the conventional one in Table I,” note: Table 1 builds the Hamiltonian’s coefficients by walking through every pair of variables, one pair at a time. That is a loop that maps to the claim’s iterative process. Table 2 does the same job with the walk gone, the coefficients now come from two calls, compile and to_qubo. Tanahashi presents table 2 replacing table 1.)
Regarding claim 5,
The combination of Ueda, Kim, Tanahashi, and Hauke teaches,
convert, in a case in which the Hamiltonian in the program includes second spin introduced such that a product of three or more spins becomes a product of two or fewer spins, the program to a second program not including the second spin (Hauke, page 5, “current experimental devices can only handle 2-local interactions… a 3-local expression x1x2x3 is reduced to x1x4 if we define x4 = x2x3. The latter condition can be imposed by an additional term in the cost function 3x4 +x2x3 −2x2x4 −2x3x4… it usually leads to a large overhead in the number of variables. Therefore, effort should further be made in studying combinatorial problems in their native HOBO form.” Note: The machine can only handle two variables multiplied together at a time, but problems often need three or more. The standard fix is to invent a new variable that stands for a pair. Hauke defines x4 to mean x2 times x3, so x1x2x3 becomes x1x4, with an extra term added to force x4 to keep that meaning. Hauke’s x4 is the claims second spin. Hauke’s says keeping that invented variable costs you a large overhead in the number of variables and points the reader back to the original form, which does not have it. That is the claim’s second program.)
Conclusion
Any inquiry concerning this communication or earlier communications from the examiner should be directed to UYEN-NHU PHAM TRAN whose telephone number is (571)272-1559. The examiner can normally be reached Monday - Friday 7:30-5.
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, Miranda Huang can be reached at (571) 270-7092. 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.
/U.P.T./Examiner, Art Unit 2124
/MIRANDA M HUANG/Supervisory Patent Examiner, Art Unit 2124
Prosecution Insights