DETAILED ACTION
This action is in response to the original filing on July 17, 2023. Claims 1-9 are pending and have been considered below. Claims 1, 8, and 9 are independent claims.
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
Acknowledgment is made of applicant’s claim for foreign priority under 35 U.S.C. 119 (a)-(d). The certified copy has been filed in parent Application No. PCT/JP2021/042759, filed on November 22, 2021.
Claim Objections
Claim 1 is objected to because of the following informalities: “A random number generator comprising: at least one memory…” should read “A random number generator system comprising: at least one memory…” Appropriate correction is required.
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 3 recites the limitation “a value included in the new subinterval assigned to the binary variable whose value, which has been obtained…” It is unclear which “binary variable” is being referred to. For example, it could refer to one of the “n binary variables” of “a new Ising model” in claim 3 or one of the “n binary variables” of “an Ising model” in claim 1. For examination purposes, “the binary variable” will interpreted to mean “a binary variable of the n binary variables which are an execution result of quantum annealing for the new Ising model.”
Claim 5 recites the limitation "the same quantum annealing machine" in page 6, line 1. There is insufficient antecedent basis for this limitation in the claim. For examination purposes, this limitation will be interpreted to mean “a same quantum annealing machine.” Additionally, there is insufficient basis for the limitation “the binary variables in the s Ising models.” For examination purposes, “the binary variables in the s Ising models” will be interpreted to mean “binary variables in the s Ising models.”
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-9 are rejected under 35 U.S.C. 101 because the claimed invention is directed to an abstract idea without significantly more.
Regarding claim 1:
Step 1 – Claim 1 is directed to a system: A random number generator comprising: at least one memory… and at least one processor…
Step 2A, Prong 1 – A judicial exception is recited in this claim as it recites a mathematical concept (see MPEP 2106.04(a)(2)(I)):
generate, based on the probability distribution, an Ising model using n binary variables (n is an integer equal to or greater than 2) each of which is assigned to a respective one of n subintervals obtained by dividing a numerical range of random numbers… to generate an Ising model requires initializing the states of its “n binary variables,” defining the Hamiltonian of the initial set of spins for the Ising model, and dividing “a numerical range” into “subintervals,” which are mathematical concepts.
acquire values of the n binary variables, the values being an execution result of quantum annealing for the Ising model… to acquire values as an execution result of quantum annealing requires computing an optimal arrangement of the n binary variables of the Ising model, which is a mathematical concept.
Step 2A, Prong 2 – The following limitations are additional elements that fail to integrate the judicial exception into a practical application:
at least one memory storing instructions; and at least one processor configured to execute the instructions stored in the memory to… a memory and processor(s) of a computing system used as mere tools to apply an exception is a generic element for performing or applying the abstract idea using a generic computing environment (see MPEP 2106.05(f)).
receive an input for designating a probability distribution of random numbers… to receive an input is data gathering (see MPEP 2106.05(g)).
output, as a random number, a value included in the subinterval assigned to the binary variable whose value, which has been obtained as the execution result, is equal to a predetermined value… to output a value within a numerical range is data outputting (see MPEP 2106.05(g)).
Step 2B – These elements are recited at such a high level of generality that they fail to integrate the abstract idea into a practical application, since they provide nothing more than mere instructions to implement an abstract idea on a generic computer (MPEP 2106.05(f)) or only amount to data gathering and outputting (MPEP 2106.05(g)) without significantly more. These limitations, taken either alone or in combination, fail to provide an inventive concept. Thus, the claim is not patent eligible.
Claims 2-7 recite limitations which further narrow the abstract idea of claim 1 by specifying more details of the mathematical concepts that occur:
Regarding claim 2, specifying wherein the Ising model is a model expressed by using a first function of the binary variables and a second function of the binary variables, the first function is expressed by a sum total of products of a value of a function and values of the binary variables, the function being such a function that its value becomes smaller as a value of the probability distribution in the subinterval to which the binary variable is assigned becomes larger, and the second function is a function that has a minimum value when a value of one of the n binary variables is equal to the predetermined value in this manner does not overcome the rejection of claim 1 as modifying “the Ising model” does not make “generating… an Ising model” to not be a mental process.
Regarding claim 3, this claim further limits the abstract idea of claim 1 to be based on mathematical concepts: further generate, based on the probability distribution, a new Ising model using n binary variables each of which is assigned to a respective one of n new subintervals that are obtained by further dividing the subinterval assigned to the binary variable whose value, which has been obtained as the execution result, is equal to the predetermined value and further acquire values of the n binary variables which are an execution result of quantum annealing for the new Ising model are mathematical concepts, as explained in claim 1 above (see reasoning for “generate… an Ising model” and “acquire values,” respectively). Furthermore, wherein the processor is further configured to execute the instructions to… is still using a processor as a mere tool to apply an exception using a generic computing environment (see MPEP 2106.05(f)). Furthermore, output, as a random number, a value included in the new subinterval assigned to the binary variable whose value, which has been obtained as the execution result of quantum annealing for the new Ising model, is equal to the predetermined value is still data outputting (see MPEP 2106.05(g)).
Regarding claim 4, this claim further limits the abstract idea of claim 1 to be based on a mathematical concept: wherein a plurality of random numbers are output by acquiring execution results of quantum annealing processes that have been performed for the same Ising model a plurality of times… to acquire execution results for quantum annealing processes that have been performed a plurality of times is a mathematical concept, as explained in claim 1 above (see reasoning for “acquire values”).
Regarding claim 5, this claim further limits the abstract idea of claim 1 to be based on mathematical concepts: generate s Ising models (s is an integer equal to or greater than 2) and associate t binary variables (t is an integer equal to or greater than 4), which constitute a set of the binary variables in the s Ising models, with t qubits, respectively, of the same quantum annealing machine, and thereby acquires values of the t binary variables, which are execution results of quantum annealing processes for the s Ising models… to generate Ising models and acquire values of binary variables as execution results of quantum annealing are mathematical concepts, as explained in claim 1 above (see reasoning for “generate… an Ising model” and “acquire values,” respectively). To associate binary variables with qubits is to map a classical binary variable (0 or 1) to a qubit (spin up or down/+1 or -1), which is a mathematical concept.
Regarding claim 6, this claim further limits the abstract idea of claim 1 to be based on mathematical concepts: generate a pseudo-random number within the subinterval assigned to the binary variable whose value, which has been obtained as the execution result, is equal to the predetermined threshold… to generate a pseudo-random number within a subinterval requires mathematical calculations and formulas to generate numbers within a specific fixed range. Furthermore, wherein the processor is further configured to execute the instructions to… is still using a processor as a mere tool to apply an exception using a generic computing environment (see MPEP 2106.05(f)). Furthermore, output the pseudo-random number within the subinterval selected according to the execution result… is still data outputting (see MPEP 2106.05(g)).
Regarding claim 7, describing wherein the processor is further configured to execute the instructions to receive an input for designating the subinterval is still data gathering (see MPEP 2106.05(g)).
Claims 8-9 are a method and computer-readable medium, respectively, that parallel the system of claim 1. Claims 8-9 are rejected under substantially the same rationale as claim 1.
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 1, 4, and 7-9 are rejected under 35 U.S.C. 103 as being unpatentable over Minematsu et al. (US 20200150928 A1, hereinafter Minematsu) in view of Okada et al. (US 20210286593 A1, hereinafter Okada) and further in view of Okada et al. (“Efficient partition of integer optimization problems with one-hot encoding,” 2019, hereinafter Okada (2019)).
Regarding claim 1:
Minematsu teaches a random number generator (Abstract: “Provided are a random number generation device”) comprising: at least one memory storing instructions (¶141 “the present invention can also be made using a computer-readable, non-transitory recording medium storing the random number generation program”).
Regarding the limitation and at least one processor configured to execute the instructions stored in the memory to: receive an input for designating a probability distribution of random numbers, Minematsu teaches and at least one processor configured to execute the instructions stored in the memory (Fig. 9 – 21, ¶140 “The CPU 21 sequentially executes the processing described in each example embodiment of the present invention”) to… designate a probability distribution of random numbers (Fig. 4 – 401, ¶33 “FIG. 4 is a diagram conceptually illustrating one example of the probability distribution 401. The horizontal axis indicates a numeric value representing a value of a random variable (“X” in FIG. 4), and represents that a value is larger to the right side. The vertical axis represents a probability (“Y” in FIG. 4), and represents that a probability is higher to the upper side,” ¶34 “The probability distribution 401 may be a mathematically defined probability distribution such as a discrete Gaussian distribution, or may be a probability distribution approximated depending on the desired precision,” Fig. 6 – 205, Fig. 7 – S201, ¶93 “The second random number generation unit 205 selects a given number of probabilities that follow a predetermined probability distribution (exemplified in FIG. 4) (Step S201)… The probability is represented with desired precision (or a desired number of digits)”). However, Minematsu fails to teach to: receive an input for designating a probability distribution…
Okada, in the same field of endeavor, teaches to receive an input for designating a probability distribution (¶36 “The present invention is to generate a random number r… according to an arbitrary D-dimensional probability distribution function f,” ¶40 “The random number generation apparatus outputs a D-dimensional random number r… with the basic distribution function f… as input”).
Minematsu and Okada are analogous art to the present invention as both are in the same field of endeavor of random number generation. Therefore, it would have been obvious to one of ordinary skill in the art, before the effective filing date of the claimed invention, to combine the input of Okada with the probability distribution of Minematsu. The motivation to do so is “to generate random numbers not only from a multidimensional probability distribution such that a probability in an impossible area is zero but from an arbitrary probability distribution” (Okada, ¶48).
Regarding the limitation generate, based on the probability distribution, an Ising model using n binary variables (n is an integer equal to or greater than 2) each of which is assigned to a respective one of n subintervals obtained by dividing a numerical range of random numbers, Minematsu teaches the probability distribution (Fig. 4 – 401, ¶34) and subintervals obtained by dividing a numerical range of random numbers (¶31 “numeric values included in the bin range represent the random numbers included in each of the bin ranges,” Fig. 4 – 401, ¶35 “bin ranges are generated by dividing, into a plurality of ranges, a numeric extent included in the probability distribution approximated as described above. For example, FIG. 4 exemplifies six bin ranges consisting of the first bin range… to the sixth bin range,” Figure 4 depicts “bin ranges” x1 to x6 or subintervals of a numerical range of random numbers). However, Minematsu fails to teach generate, based on the probability distribution, an Ising model using n binary variables (n is an integer equal to or greater than 2) each of which is assigned to a respective one of n subintervals obtained by dividing a numerical range of random numbers.
Okada (2019), in the same field of endeavor, teaches generate, based on an integer combinatorial problem, an Ising model (Page 1, ¶1 “the cost function of a combinatorial optimization problem can be mapped to the Hamiltonian of a classical Ising model”) using n binary variables (n is an integer equal to or greater than 2) each of which is assigned to a respective one of n components (Page 2, ¶1 “A cost function that can be handled by the D-Wave quantum annealer is as follows:
PNG
media_image1.png
63
991
media_image1.png
Greyscale
¶3 “the quantum annealer requires that the cost function is represented in the form of a quadratic unconstrained binary optimization problem (QUBO) or Ising model… the binarization of the integer variables is achieved using one-hot encoding. For example, the following integer optimization problem with N integer variables {Si}i=1,2,…,N:
PNG
media_image2.png
85
1005
media_image2.png
Greyscale
Where Si ∈ (1, 2, …, Q), Q is the number of components, Jj,i+1 is an interaction between Si and Si+1, and δ denotes the Kronecker delta function, is rewritten as
PNG
media_image3.png
94
998
media_image3.png
Greyscale
by one-hot encoding. Here, xi(q) ∈ (0, 1) is a binary variable that is assigned to the component q of Si… Subsequently, a penalty term is introduced to obtain the following unconstrained form:
PNG
media_image4.png
74
993
media_image4.png
Greyscale
where the second term depicts the penalty term introduced to extract feasible solutions that satisfy the constraint… which we call ‘one-hot constraint’,” wherein Equation (7) depicts “a cost function” that is “represented in the form of… [an] Ising model” which is generated using n binary variables or “xi(q)” each of which is assigned to a respective one of n “component q,” Page 4, “Assessing performance” Section, ¶1 “Q is set to 4, Si ∈ (1,2,3,4)”).
Okada (2019) further teaches acquire values of the n binary values, the values being an execution result of quantum annealing for the Ising model (Abstract: “The current version of the D-Wave quantum annealer can solve unconstrained binary optimization problems with a limited number of binary variables… To solve these problems with the quantum annealer, the integer variables are generally binarized with one-hot encoding, and the binarized problem is partitioned into small subproblems… partitioning methods that extract subproblems with as many feasible solutions as possible are required,” Page 2, ¶3 “the quantum annealer requires that the cost function is represented in the form of a quadratic unconstrained binary optimization problem (QUBO) or Ising model,” Page 3, Fig. 1, Caption: “Problem graph of Eq. (7). Vertices and edges represent binary variables xi(q) and interactions between them… Q binary variables {xi(q)}q=1,2…,Q are assigned to each Si and the total number of binary variables is NQ. Although there exist 2NQ configurations of the binary variables, only QN configurations satisfy the one-hot constraint” and ¶1 “the entire search space of the binarized optimization problem [Eq. (7)] is dominated by unfeasible solutions… to efficiently solve large optimization problems under the one-hot constraint using the quantum annealer, partitioning methods are required to extract subproblems with as many feasible solutions as possible,” Page 4, Fig. 2 and ¶2 “a subproblem of the binary subproblem is embedded into the D-Wave quantum annealer,” Page 6, ¶1 “After optimizing the embedded subproblem using the D-Wave quantum annealer, the variables in the subproblem are replaced to the best solution among the 1,000 solutions obtained using the quantum annealer”).
Regarding the limitation and output, as a random number, a value included in the subinterval assigned to the binary variable whose value, which has been obtained as the execution result, is equal to a predetermined value, Minematsu teaches and output, as a random number, a value included in the subinterval (Fig. 1 – 101, Fig. 2, ¶66 “The random number generation device 101 may specify a bin range for each random number by executing the processing illustrated in FIG. 2 a given number of times, and may output information representing the specified bin ranges. Executing the processing illustrated in FIG. 2 a given number of times enables generation of random numbers that follow a cumulative frequency”). However, Minematsu fails to teach a value included in the subinterval assigned to the binary variable whose value, which has been obtained as the execution result, is equal to a predetermined value.
Okada (2019) teaches a value included in a component assigned to the binary variable (Page 2, ¶3 “xi(q) ∈ (0, 1) is a binary variable that is assigned to the component q of Si,” Page 4, “Assessing Performance” Section, ¶1 “Q is set to 4, Si ∈ (1, 2, 3, 4)”) whose value, which has been obtained as the execution result (Page 6, ¶1 “After optimizing the embedded subproblem using the D-Wave quantum annealer, the variables in the subproblem are replaced to the best solution among the 1,000 solutions obtained using the quantum annealer”), is equal to a predetermined value (Page 2, ¶3 “xi(q) = 1 indicates that the component q is selected for Si, and feasible solutions are constrained to configurations in which exactly one component is selected for each Si”).
Minematsu, Okada, and Okada (2019) are analogous to the claimed invention as all are in the same field of endeavor of data processing. Therefore, it would have been obvious for one of ordinary skill in the art, before the effective filing date of the claimed invention, to combine the quantum annealing and Ising model using binary variables of Okada (2019) and the input-designated probability distribution of Okada with the random number generation system of Minematsu. The motivation to do so is “to generate random numbers not only from a multidimensional probability distribution such that a probability in an impossible area is zero but from an arbitrary probability distribution” (Okada, ¶48) and to accelerate the computation of practical problems through quantum annealing (Okada (2019), Page 1, ¶1 “D-Wave Systems Inc. developed a commercial [Quantum annealing] machine based on superconducting flux qubits. Experimental studies using QA machines have been performed to compare the performance of QA with that of [Simulated annealing] and to demonstrate the applicability of QA machines to practical problems,” Page 2, ¶2 “large problems are partitioned into subproblems that can be handled by the quantum annealer… employing the quantum annealer is considered to be advantageous if it can solve subproblems with many closed loops more efficiently than classical algorithms”).
Regarding claim 4, Minematsu in view of Okada and further in view of Okada (2019) teaches the random number generator according to claim 1 (and thus the rejection of claim 1 is incorporated).
Regarding the limitation wherein a plurality of random numbers are output by acquiring execution results of quantum annealing processes that have been performed for the same Ising model a plurality of times, Minematsu teaches wherein a plurality of random numbers are output by acquiring execution results of a process a plurality of times (Fig. 2, ¶66 “Executing the processing illustrated in FIG. 2 a given number of times enables generation of random numbers that follow a cumulative frequency (i.e., a distribution concerning second random numbers) in the frequency information”). However, Minematsu fails to teach execution results of quantum annealing processes that have been performed for the same Ising model a plurality of times.
Okada (2019) teaches results of quantum annealing processes that have been performed for the same Ising model a plurality of times (Page 6, ¶¶1-2 “After optimizing the embedded subproblem using the D-Wave quantum annealer, the variables in the subproblem are replaced to the best solution among the 1,000 solutions obtained using the quantum annealer… We complete refining the current solution when all local energies are minimized. Finally, the best solution obtained in the procedure is updated. These processes are iterated, and we compare the solution accuracy… The average, maximum, and minimum energies for 16 trials are plotted, and the same 16 initial states are used for each partitioning method”).
Minematsu and Okada (2019) are analogous to the claimed invention as both are in the same field of endeavor of data processing. Therefore, it would have been obvious for one of ordinary skill in the art, before the effective filing date of the claimed invention, to combine the quantum annealing process of Okada (2019) with the random number generation of Minematsu. The motivation to do so is to accelerate the computation of practical problems through quantum annealing (Okada (2019), Page 1, ¶1 “D-Wave Systems Inc. developed a commercial [Quantum annealing] machine based on superconducting flux qubits. Experimental studies using QA machines have been performed to compare the performance of QA with that of [Simulated annealing] and to demonstrate the applicability of QA machines to practical problems,” Page 2, ¶2 “large problems are partitioned into subproblems that can be handled by the quantum annealer… employing the quantum annealer is considered to be advantageous if it can solve subproblems with many closed loops more efficiently than classical algorithms”).
Regarding claim 7, Minematsu in view of Okada and further in view of Okada (2019) teaches the random number generator according to claim 1 (and thus the rejection of claim 1 is incorporated).
Regarding the limitation wherein the processor is further configured to execute the instructions to receive an input for designating the subinterval, Minematsu teaches the subinterval (Fig. 3, ¶50 “A frequency concerning the cumulative frequency in the frequency information exemplified in FIG. 3 represents the number (frequency) of random numbers included in each bin range when the bin range for a random number (or a numeric value) generated with desired precision is specified with the desired precision”). However, Minematsu fails to teach wherein the processor is further configured to execute the instructions to receive an input for designating the subinterval.
Okada teaches wherein the processor is further configured to execute the instructions to receive an input for designating a hole (¶¶34-35 “An impossible area of a random variable is called “a hole”, and the area of the hole is given as a parameter… A hole [h]… is a hypercube in D-dimensional space, and each hi indicates a range… for a random variable,” ¶40 “The random number generation apparatus outputs a D-dimensional random number r… with the basic distribution function f and the hole [h] as input”).
Minematsu and Okada are analogous art to the claimed invention as both are in the same field of endeavor of random number generation. Therefore, it would have been obvious to one of ordinary skill in the art, before the effective filing date of the claimed invention, to combine the subinterval of Minematsu with the input of Okada. The motivation to do so is “to generate random numbers not only from a multidimensional probability distribution such that a probability in an impossible area is zero but from an arbitrary probability distribution” (Okada, ¶48).
Claims 8-9 are a method and computer-readable medium, respectively, that parallel the system of claim 1. Claims 8-9 are rejected under substantially the same rationale as claim 1.
Claim 2 is rejected under 35 U.S.C. 103 as being unpatentable over Minematsu in view of Okada and further in view of Okada (2019), and further in view of Passos et al. (“κ-Entropy Based Restricted Boltzmann Machines,” 2019, hereinafter Passos).
Regarding claim 2, Minematsu in view of Okada and further in view of Okada (2019) teaches the random number generator according to claim 1 (and thus the rejection of claim 1 is incorporated).
Okada (2019) further teaches wherein the Ising model is a model expressed by using a first function of the binary variables and a second function of the binary variables (Page 2, ¶1 “A cost function that can be handled by the D-Wave quantum annealer is as follows,” Equation (4), ¶3 “the quantum annealer requires that the cost function is represented in the form of a… Ising model,” and Equation (7) depicts a model expressed by using a first function of the binary variables or xi(q) and xi+1(q) and a second function of the binary variables or xi(q)).
Regarding the limitation the first function is expressed by a sum total of products of a value of a function and values of the binary variables, the function being such a function that its value becomes smaller as a value of the probability distribution in the subinterval to which the binary variable is assigned becomes larger, Minematsu teaches the probability distribution in the subinterval (Fig. 4 – 401, ¶35 “bin ranges are generated by dividing, into a plurality of ranges, a numeric extent included in the probability distribution… FIG. 4 exemplifies six bin ranges,” wherein x1 to x6 in Figure 4 depict the probability distribution in the subinterval or “bin ranges”). However, Minematsu fails to teach the first function is expressed by a sum total of products of a value of a function and values of the binary variables, the function being such a function that its value becomes smaller as a value of the probability distribution in the subinterval to which the binary variable is assigned becomes larger.
Okada (2019) teaches the first function is expressed by a sum total of products of a value of a function and values of the binary variables (Page 2, ¶3 “Ji,i+1 is an interaction between Si and Si+1… xi(q)… is a binary variable,” Equation (7) depicts the first function:
PNG
media_image5.png
60
173
media_image5.png
Greyscale
wherein “Ji,i+1” encompasses a value of a function and “xi(q)xi+1(q)” encompasses values of the binary variables) and a value of the component to which the binary variable is assigned (Page 2, ¶3 “xi(q)… is a binary variable that is assigned to the component q,” Page 4, “Assessing performance” Section, ¶1 “Q is set to 4, Si ∈ (1, 2, 3, 4)”). However, Okada (2019) fails to teach the first function is expressed by a sum total of products of a value of a function and values of the binary variables, the function being such a function that its value becomes smaller as a value of the probability distribution in the subinterval to which the binary variable is assigned becomes larger.
Passos, which is reasonably pertinent to the claimed invention, teaches the function being such a function that its value becomes smaller as a probability becomes larger (Page 2, Col. 2, Section B, ¶2 “pi is the probability to find the system in the ith state given a set of k discrete states,” Page 3, Col. 1, ¶3 “Kaniadakis… introduced the so-called κ-entropy, which can be written as follows:
PNG
media_image6.png
67
364
media_image6.png
Greyscale
where κ is a deformation parameter and lnk(x) is the deformed logarithm expressed as follows:
PNG
media_image7.png
53
356
media_image7.png
Greyscale
Page 4, Col. 1, ¶2 “Regarding the κ parameter, which controls the slope of the Kaniadakis function, it was considered a set of values within the range κ ∈ {0.0 … 10.0},” wherein the function or the negative term “pilnk(pi)” as depicted in Equation (8) is such a function that its value becomes smaller or more negative as probability “pi” becomes larger regardless of the range of values of “the κ parameter”).
Okada (2019) further teaches the second function is a function that has a minimum value when a value of one of the n binary variables is equal to the predetermined value (Page 2, ¶3 “xi(q) = 1 indicates that the component q is selected for Si, and feasible solutions are constrained to configurations in which exactly one component is selected for each Si…
PNG
media_image8.png
84
176
media_image8.png
Greyscale
the second term depicts the penalty term introduced to extract feasible solutions that satisfy the constraint
PNG
media_image9.png
39
110
media_image9.png
Greyscale
which we call ‘one-hot constraint,’” wherein the “second term” depicted in Equation (7) encompasses the second function is a function that has a minimum value or 0 when a value of one of the n binary variables or xi(q) is equal to the predetermined value or 1).
Minematsu, Okada (2019), and Passos are analogous art to the claimed invention as all are in the same field of endeavor of data processing. Therefore, it would have been obvious for one of ordinary skill in the art, before the effective filing date of the claimed invention, to combine the Ising model expression of Okada (2019) and the entropy function of Passos with the probability distribution in the subinterval of Minematsu. The motivation to do so is to accelerate the computation of practical problems through quantum annealing (Okada (2019), Page 1, ¶1 “D-Wave Systems Inc. developed a commercial [Quantum annealing] machine based on superconducting flux qubits. Experimental studies using QA machines have been performed to compare the performance of QA with that of [Simulated annealing] and to demonstrate the applicability of QA machines to practical problems,” Page 2, ¶2 “large problems are partitioned into subproblems that can be handled by the quantum annealer… employing the quantum annealer is considered to be advantageous if it can solve subproblems with many closed loops more efficiently than classical algorithms”) and to better model systems of interacting parts (Passos, Page 3, Col. 1, ¶1 “Although the [Shannon-Boltzmann-Gibbs] entropy is arguably a valuable tool, it fails to describe systems composed of strong correlated or interacting parts… the SBG entropy does not completely model the system,” ¶6 “The generalization of SBG entropy introduced by Kaniadakis allowed us to better describe thermodynamic systems”).
Claim 3 is rejected under 35 U.S.C. 103 as being unpatentable over Minematsu in view of Okada and further in view of Okada (2019), and further in view of Zlokapa et al et al. (“Quantum adiabatic machine learning with zooming, 2020, hereinafter Zlokapa), and further in view of Yarkoni et al. (“Semi-supervised time series classification method for quantum computing,” 2020, hereinafter Yarkoni).
Regarding claim 3, Minematsu in view of Okada and further in view of Okada (2019) teaches the random number generator according to claim 1 (and thus the rejection of claim 1 is incorporated).
Regarding the limitation wherein the processor is further configured to execute the instructions to: further generate, based on the probability distribution, a new Ising model using n binary variables each of which is assigned to a respective one of n new subintervals that are obtained by further dividing the subinterval assigned to the binary variable whose value, which has been obtained as the execution result, is equal to the predetermined value, Minematsu teaches the probability distribution (Fig. 4 – 401, ¶34) and the subinterval (¶31, Fig. 4 – 401 and x1 to x6, ¶35 as explained above with respect to claim 1). However, Minematsu fails to teach wherein the processor is further configured to execute the instructions to: further generate, based on the probability distribution, a new Ising model using n binary variables each of which is assigned to a respective one of n new subintervals that are obtained by further dividing the subinterval assigned to the binary variable whose value, which has been obtained as the execution result, is equal to the predetermined value.
Okada (2019) teaches the component assigned to the binary variable (Page 2, ¶3 “xi(q) ∈ (0, 1) is a binary variable that is assigned to the component q of Si,” Page 4, “Assessing Performance” Section, ¶1 “Q is set to 4, Si ∈ (1, 2, 3, 4)”) whose value, which has been obtained as the execution result (Page 6, ¶1 “After optimizing the embedded subproblem using the D-Wave quantum annealer, the variables in the subproblem are replaced to the best solution among the 1,000 solutions obtained using the quantum annealer”), is equal to the predetermined value (Page 2, ¶3 “xi(q) = 1 indicates that the component q is selected for Si, and feasible solutions are constrained to configurations in which exactly one component is selected for each Si”). However, Okada (2019) fails to teach wherein the processor is further configured to execute the instructions to: further generate, based on the probability distribution, a new Ising model using n binary variables each of which is assigned to a respective one of n new subintervals that are obtained by further dividing the subinterval…
Zlokapa, in the same field of endeavor, teaches wherein the processor is further configured to execute the instructions (Page 1, Col. 2, ¶2 “implement the proposed algorithm (QAML-Z) on the D-Wave quantum annealer”) to: further generate, based on an energy surface, a new Ising model using n binary variables (Page 2, Col. 1, ¶¶1-2 “Given spins si ∈ {0, 1} obtained by transforming up/down spins, let R(xT) be a strong classifier given by
PNG
media_image10.png
80
448
media_image10.png
Greyscale
i.e., an ensemble of the weak classifiers where each weak classifier is either turned on or off (weight 1 or 0)… in the original QAML algorithm, the following Ising model Hamiltonian is minimized after transforming the range si ∈ {-1, 1}, adding an additional λ regularization hyperparameter to penalize nonzero si
PNG
media_image11.png
121
634
media_image11.png
Greyscale
both Equations (1) and (6) depict N “spins si” or n binary variables, Col. 2, Section B, ¶1 “We denote the zooming variant of quantum annealing for machine learning as QAML-Z. Under this reformulation, the weights of the classifiers may be extended from the set {0, 1} to the continuous interval [-1, 1],” Fig. 1 and Caption “QAML-Z iteratively updates the weight µ (indicated by the red dot) of a weak classifier (index 0 in the diagram) in the strong classifier ensemble by performing a binary search over the energy surface using spin up/down outcomes,” ¶2 “Let each qubit have a mean µi(t) (starting at µi(0) = 0 for all i) and let the search breadth be σ(t) = bt where t = 0,t, …, T – 1 for T iterations and 0 < b < 1 is a free parameter. Each iteration, the Hamiltonian is centered around the previous mean and the search breadth is narrowed. Receiving spin up or spin down corresponds to shifting the new mean either right or left by a distance given by the search breadth. The weight given to each classifier is thus updated according to the old mean and consequent shift, resulting in a modified Hamiltonian,” Page 3, Col. 1, ¶1 “This new Hamiltonian may be iteratively optimized for t = 0, 1, . . , T – 1 to update µi(t+1) = µi(t) + siσ(t+1) resulting in the new strong classifier,” wherein a “new Hamiltonian” is implied to result in a new Ising model) and t new subintervals that are obtained by further dividing a previous subinterval (Page 3, Col. 2, ¶1 “we set the zoom parameter b = ½ to perform a binary search over the real numbers… QAML-Z was trained for only 8 iterations,” one of ordinary skill in the art would recognize that “to perform a binary search” would involve iteratively searching new subintervals that are obtained by further dividing a subinterval from the previous iteration in half). However, Zlokapa fails to teach a new Ising model using n binary variables each of which is assigned to a respective one of n new subintervals…
Yarkoni, in the same field of endeavor, teaches to generate a new Ising model using binary variables each of which is assigned to a respective one of n subsets (Page 1, Section 1, ¶1 “the problem is formulated as a quadratic unconstrained binary optimization (QUBO) problem, or its equivalent form of an Ising Hamiltonian,” Page 5, Section 3.2, ¶1 “Given the encoded strings and the common set of features V, we can now formulate the set cover problem as a QUBO… Consider the universe set U = {1, …, n} and a set of subsets Vi such that… Vi ⊆ U. Finding the smallest number of subsets Vi whose union is U is a well-known NP-hard optimization problem in the worst case. In order to map the set cover problem to a QUBO problem, we use the following binary variables:
PNG
media_image12.png
189
1128
media_image12.png
Greyscale
… We consider the full QUBO as a sum of two components:
PNG
media_image13.png
224
1121
media_image13.png
Greyscale
The complete QUBO is given by H = HA + HB,” Page 7, Algorithm 1 depicts a process to “FORMULATE THE QUBO PROBLEM” or generate a new Ising model for each “TS in test data”).
Zlokapa further teaches further acquire values of the n binary variables which are an execution result of quantum annealing for the new Ising model (Page 2, Col. 1, ¶1 “Given spins si ∈ {0,1} obtained by transforming up/down spins, let R(xT) be a strong classifier given by… an ensemble of the weak classifiers,” Col. 2, Section B, ¶1 “By iteratively performing quantum annealing, the binary weights on the weak classifiers can be made continuous, resulting in a stronger classifier. This is achieved by performing a search on the real numbers, effectively zooming in on a region of the energy surface each iteration… We denote the zooming variant of quantum annealing for machine learning as QAML-Z,” Fig. 1 and Caption “While QAML only performs one anneal, QAML-Z iteratively updates the weight µ… by performing a binary search,” ¶2 “The weight given to each classifier is thus updated according to the old mean and consensus shift, resulting in a modified Hamiltonian according to the substitution sici(xT) [Wingdings font/0xE0] σ(t)sici + µi(t)ci(xT). The full expression is:
PNG
media_image14.png
424
623
media_image14.png
Greyscale
Page 3, Col. 1, ¶¶1-2 “this new Hamiltonian may be iteratively optimized for t = 0, 1, . . . , T – 1 to update µi(t + 1) = µi(t) + siσ(t+1), resulting in the new strong classifier… Since the zooming algorithm increases the probability of overfitting, we propose a two-step randomization process to regularize the iterative process. After each iteration, for each qubit si that the energy worsens by the update… we apply the flip si [Wingdings font/0xE0] -si with monotonically decreasing probability pf(t)… all qubits are uniformly randomly flipped from si to -si with probability qf(t)… akin to a cluster-flip move in variants of simulated annealing,” ¶¶4-5 “With the augmented set of classifiers, the Hamiltonian is now given by:
PNG
media_image15.png
190
609
media_image15.png
Greyscale
where H(t) is iteratively optimized for t = 0, 1, . . . to update µil(t + 1) = µil(t) + silσ(t+1)… Quantum annealing yields a distribution of excited states, allowing the construction of a stronger classifier,” Col. 2, Section III, ¶1 “We evaluated the performance of the QAML-Z algorithm on the programmable D-Wave 2X quantum annealer… with 1098 physical qubits… The Ising model is generated from weak classifiers… the QAML-Z algorithm augments this set of weak classifiers,” wherein for each subsequent iteration of quantum annealing in “QAML-Z,” the n binary variables or “spins” from the previous iteration informs the updated weight “µi(t+1)” which further informs an implied updated Hamiltonian H(t+1) for the new Ising model, while spins “are uniformly randomly flipped” between each execution of the iterative quantum annealing or “QAML-Z” to further acquire values of the n binary variables).
Regarding the limitation and output, as a random number, a value included in the new subinterval assigned to the binary variable whose value, which has been obtained as the execution result of quantum annealing for the new Ising model, is equal to the predetermined value, Minematsu teaches and output, as a random number, a value included in a subinterval (Fig. 1 – 101, Fig. 2, ¶66 see claim 1 above). However, Minematsu fails to teach the new subinterval assigned to the binary variable whose value, which has been obtained as the execution result of quantum annealing for the new Ising model, is equal to the predetermined value.
Zlokapa teaches the new subinterval (Page 3, Col. 2, ¶1 “we set the zoom parameter b = ½ to perform a binary search over the real numbers… QAML-Z was trained for only 8 iterations” as explained above) and the binary variable whose value, which has been obtained as the execution result of quantum annealing for the new Ising model (Page 2, Col. 1, ¶1, Col. 2, Section B, ¶1-2, Fig. 1, and Caption, Page 3, Col. 1, ¶¶1-2 and ¶¶4-5, Col. 2, Section III, ¶1 as explained above; it is implicit that the final output after the last iteration of the execution result of quantum annealing for the new Ising model that is derived based on the last and narrowest new subinterval after t=8 iterations of “binary search” contains a final configuration of “spins” with the binary value). However, Zlokapa fails to teach the new subinterval assigned to the binary variable whose value, which has been obtained as the execution result of quantum annealing for the new Ising model, is equal to the predetermined value.
Yarkoni teaches a subset assigned to the binary variable (Page 5, Section 3.2, ¶1 “Finding the smallest number of subsets Vi whose union U… to map the set cover problem to a QUBO problem, we use the following binary variables: xi”) whose value is equal to the predetermined value (Page 5, Equation (2) depicts whether a binary variable is equal to the predetermined value 0 or 1 based on whether its corresponding set is included in a universal set).
Minematsu, Okada (2019), Zlokapa, and Yarkoni are analogous art to the claimed invention as all are in the same field of endeavor of data processing. Therefore it would have been obvious to one of ordinary skill in the art, before the effective filing date of the claimed invention, to combine the first iteration of Ising model generation and quantum annealing of Okada (2019), the further dividing of subintervals and quantum annealing of Zlokapa, and the second iteration of Ising model generation using binary variables of Yarkoni with the bin ranges of the probability distribution and random number generation system of Minematsu. The motivation to do so is to accelerate the computation of practical problems through quantum annealing (Okada (2019), Page 1, ¶1 “D-Wave Systems Inc. developed a commercial [Quantum annealing] machine based on superconducting flux qubits. Experimental studies using QA machines have been performed to compare the performance of QA with that of [Simulated annealing] and to demonstrate the applicability of QA machines to practical problems,” Page 2, ¶2 “large problems are partitioned into subproblems that can be handled by the quantum annealer… employing the quantum annealer is considered to be advantageous if it can solve subproblems with many closed loops more efficiently than classical algorithms”), to improve classical problem solving methods through quantum annealing (Zlokapa, Page 6, Col. 1, Section IV, ¶1 “improve the state-of-the-art quantum machine learning algorithm for quantum annealers”), and to use less data than classical techniques (Yarkoni, Abstract: “We present results indicating our method is competitive with current semi- and unsupervised classification techniques, but using less data than classical techniques”).
Claim 5 is rejected under 35 U.S.C. 103 as being unpatentable over Minematsu in view of Okada and further in view of dwave-system Documentation, Release 0.9.12 (2020, hereinafter D-Wave Documentation).
Regarding claim 5, Minematsu in view of Okada and further in view of Okada (2019) teaches the random number generator according to claim 1 (and thus the rejection of claim 1 is incorporated).
The combination of Minematsu, Okada, and Okada (2019) fails to teach wherein the processor is further configured to execute the instructions to: generate s Ising models (s is an integer equal to or greater than 2). However, D-Wave Documentation, in the same field of endeavor, teaches this limitation (Page 36, “TilingComposite” Section: “Composite to tile a small problem across a Chimera-structured sampler… The D-Wave 2000Q QPU supports a C16 Chimera graph… A problem that can be minor-embedded in a single unit cell, for example, can therefore be tiled across the unit cells of a D-Wave 2000Q as 16x16 duplicates. This enables sampling 256 solutions in a single call,” wherein a “QPU” encompasses the processor, Page 38, “Examples” Section: “This example submits a simple Ising problem of just two variables on a D-Wave system. Because the problem fits in a single Chimera unit cell, it is tiled across the solver’s entire Chimera graph, resulting in multiple samples,” Page 39, “TilingComposite.sample_ising(h, J, **parameters) – Sample from an Ising model using the implemented sample method,” wherein “the implemented sample method” encompasses execute the instructions to: generate s Ising models).
Regarding the limitation and associate t binary variables (t is an integer equal to or greater than 4), which constitute a set of the binary variables in the s Ising models, with t qubits, respectively, of the same quantum annealing machine, and thereby acquires values of the t binary variables, which are execution results of quantum annealing processes for the s Ising models, Okada (2019) teaches and associate t binary variables (t is an integer equal to or greater than 4), which constitute a set of the binary variables in the Ising model (Page 2, ¶3 “the following integer optimization problem with N integer variables {Si}i=1,2,…,N… where Si ∈ (1,2 …, Q), Q is the number of components,” Page 3, Fig. 1(a), ¶1 “Q binary variables {xi(q)}q=1,2,…,Q are assigned to each Si, and the total number of binary variables is NQ”), with t qubits, respectively, of the same quantum annealing machine (Page 2, ¶¶1-3 “A cost function that can be handled by the D-Wave quantum annealer… where the interactions between qubits are restricted to the Chimera graph… Although the Chimera graph for D-Wave 2000Q is (M,N,L) = (16,16,4), the number of operable qubits is less than Nq = 2MNL = 2048… Due to the limitation of the number of available qubits, we cannot solve large optimization problems directly using the D-Wave quantum annealer. In real settings, large problems are partitioned into subproblems that can be handled by the quantum annealer… the quantum annealer requires that the cost function is represented in the form of a quadratic unconstrained binary optimization problem (QUBO) or Ising model,” Page 10, “Multivalued Partition” Section, ¶2 “The average number of NS(Qembed) of embedded integer variables with Qembed components are shown in Table 2… The average number of binary variables embedded into the D-Wave quantum annealer is 225,” Page 11, Table 2 depicts N=14.5, 8, or 43.2 “integer variables” with Q=2, 3, or 4 “components,” meaning the resulting “binary variables” would be NQ = 29, 24, or 172.8, respectively, which are below the maximum number of “operable qubits” or 2048; one of ordinary skill in the art can infer that NQ or t qubits of the “D-Wave quantum annealer” or the same quantum annealing machine are used to associate t binary variables), and thereby acquires values of the t binary variables, which are execution results of quantum annealing processes for the Ising model (Page 2, ¶2 “The subproblems are iteratively optimized by the quantum annealer, and the optimization result is used to improve the current solution. A cluster of spins in the subproblem are simultaneously updated in this scheme,” Page 4, ¶2 “a larger number of binary variables can be embedded into the D-Wave quantum annealer,” Page 6, ¶1 “After optimizing the embedded subproblem using the D-Wave quantum annealer, the variables in the subproblem are replaced to the best solution among the 1,000 solutions obtained using the quantum annealer”). However, Okada (2019) fails to teach the s Ising models.
D-Wave Documentation teaches the s Ising models (Page 38, “Examples” Section: “This example submits a simple Ising problem… Because the problem fits in a single Chimera unit cell, it is tiled across the solver’s entire Chimera graph”).
Minematsu, Okada (2019), and D-Wave Documentation are analogous art to the present invention as all are in the same field of endeavor of data processing. Therefore, it would have been obvious to one of ordinary skill in the art, before the effective filing date of the claimed invention, to combine the generating of multiple Ising models of D-Wave Documentation and the process of Okada (2019) with the system of Minematsu. The motivation to do so is to be able to execute multiple Ising problems in parallel (D-Wave Documentation, Page 36, “TilingComposite” Section: “Enables parallel sampling for small problems (problems that are minor-embeddable in a small part of a D-Wave solver’s Chimera graph)”) while accelerating the computation of practical problems through quantum annealing (Okada (2019), Page 1, ¶1 “D-Wave Systems Inc. developed a commercial [Quantum annealing] machine based on superconducting flux qubits. Experimental studies using QA machines have been performed to compare the performance of QA with that of [Simulated annealing] and to demonstrate the applicability of QA machines to practical problems,” Page 2, ¶2 “large problems are partitioned into subproblems that can be handled by the quantum annealer… employing the quantum annealer is considered to be advantageous if it can solve subproblems with many closed loops more efficiently than classical algorithms”).
Claim 6 is rejected under 35 U.S.C. 103 as being unpatentable over Minematsu in view of Okada and further in view of Okada (2019), and further in view of Stark et al. (“Random Sampling: Practice Makes Imperfect,” 2018, hereinafter Stark).
Regarding claim 6, Minematsu in view of Okada and further in view of Okada (2019) teaches the random number generator according to claim 1 (and thus the rejection of claim 1 is incorporated).
Regarding the limitation wherein the processor is further configured to execute the instructions to: generate a pseudo-random number within the subinterval assigned to the binary variable whose value, which has been obtained as the execution result, is equal to the predetermined value, Minematsu teaches wherein the processor is further configured to execute the instructions to: generate a random number within the subinterval (Fig. 1 – 101, Fig. 2, ¶66, see claim 1 above). However, Minematsu fails to teach wherein the processor is further configured to execute the instructions to: generate a pseudo-random number within the subinterval assigned to the binary variable whose value, which has been obtained as the execution result, is equal to the predetermined value.
Okada (2019) teaches a component assigned to the binary variable (Page 2, ¶3 and Page 4, “Assessing Performance” Section, ¶1, see claim 1 above) whose value, which has been obtained as the execution result (Page 4, ¶2 and Page 6, ¶1, see claim 1 above), is equal to the predetermined value (Page 2, ¶3 see claim 1 above). However, Okada (2019) fails to teach generate a pseudo-random number within the subinterval…
Stark, in the same field of endeavor, teaches to generate a pseudo-random number within a subinterval (Page 8, Section 4.1, ¶5 “A more accurate way to generate random integers on {1, . . . , m} is to use pseudo-random bits directly… To generate a pseudo-random integer uniformly distributed on {1, . . . , m}, generate µ pseudo-random bits (for instance, by taking the most significant µ bits from the PRNG output) and interpret the bits as a binary integer. If the integer is larger than m-1, then discard it and draw another µ bits until the µ bits represent an integer less than or equal to m-1”).
Regarding the limitation and output the pseudo-random number within the subinterval selected according to the execution result, Minematsu teaches and output the random number within the subinterval selected according to a process (Fig. 1 – 101, Fig. 2, ¶66 “The random number generation device 101 may specify a bin range for each random number… Executing the processing illustrated in FIG. 2 a given number of times enables generation of random numbers that follow a cumulative frequency”). However, Minematsu fails to teach output the pseudo-random number within the subinterval according to the execution result.
Okada (2019) teaches the execution result (Page 4, ¶2 and Page 6, ¶1 “the best solution”). However, Okada (2019) fails to teach output the pseudo-random number within the subinterval…
Stark teaches to output the pseudo-random number (Page 8, Section 4.1, ¶5 “To generate a pseudo-random integer uniformly distributed on {1, . . . , m}… draw another µ bits until the µ bits represent an integer less than or equal to m-1. When that occurs, return that integer, plus 1”).
Minematsu, Okada (2019), and Stark are analogous art to the claimed invention as all are in the same field of endeavor of data processing. Therefore, it would have been obvious for one of ordinary skill in the art, before the effective filing date of the claimed invention, to combine the quantum annealing and Ising model using binary variables of Okada (2019) and pseudo-random number generation of Stark with the random number generation system of Minematsu. The motivation to do so is to accelerate the computation of practical problems through quantum annealing (Okada (2019), Page 1, ¶1 “D-Wave Systems Inc. developed a commercial [Quantum annealing] machine based on superconducting flux qubits. Experimental studies using QA machines have been performed to compare the performance of QA with that of [Simulated annealing] and to demonstrate the applicability of QA machines to practical problems,” Page 2, ¶2 “large problems are partitioned into subproblems that can be handled by the quantum annealer… employing the quantum annealer is considered to be advantageous if it can solve subproblems with many closed loops more efficiently than classical algorithms”) and to design a cryptographically secure random number generation system (Page 10, ¶2 “we suggest R and Python use crypto graphically secure PRNGs by default… We have developed a CS-PRNG prototype as a Python package, cryptorandom”).
Conclusion
Any inquiry concerning this communication or earlier communications from the examiner should be directed to WILLIAM M LEE whose telephone number is (571)272-4761. The examiner can normally be reached Mon-Fri. 8am-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, Cesar Paula can be reached at (571)272-4128. 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.
/WILLIAM MICHAEL LEE/
Examiner, Art Unit 2145
/CESAR B PAULA/Supervisory Patent Examiner, Art Unit 2145
