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 .
Status of the Claims
Claims 1-17 are pending for examination.
Claims 1, 13 and 17 are independent Claims.
Claims 1-3 and 5-17 are rejected under 35 U.S.C. §103.
Claim 2 is rejected under 35 U.S.C. §112(b).
Claim Objections
Claim 4 is objected to as being dependent upon a rejected base claim, but would be allowable if rewritten in independent form including all of the limitations of the base claim and any intervening claims.
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 2 recites the limitation "the one or more tensor networks have a same graph representation as each other" in the Claim. When there is only one tensor network, “a same graph representation as each other” is indefinite.
Claim Rejections - 35 USC § 103
The following is a quotation of 35 U.S.C. 103 which forms the basis for all obviousness rejections set forth in this Office action:
A patent for a claimed invention may not be obtained, notwithstanding that the claimed invention is not identically disclosed as set forth in section 102, if the differences between the claimed invention and the prior art are such that the claimed invention as a whole would have been obvious before the effective filing date of the claimed invention to a person having ordinary skill in the art to which the claimed invention pertains. Patentability shall not be negated by the manner in which the invention was made.
Claim(s) 1-2, 5-6, 10-14 and 17 is/are rejected under 35 U.S.C. 103 as being unpatentable over Huang et al. (U.S. 2021/0334313 hereinafter Huang) in view of Huang et al. (U.S. 2021/0209270 hereinafter Huang2).
As Claim 1, Huang teaches a non-transitory memory storing instructions and a processor for a quantum simulator, wherein when the processor executes the instructions, the processor is configured to:
perform a local search algorithm to determine a plurality of contraction expressions (Huang (¶0071 line 1-4, fig. 7 item 712), “the computing host may determine a reconstructed sub-graph as an optimal contraction performance as a local optimal sub-graph. The local optimal sub-graph may have a least computation complexity”), wherein each contraction expression is suitable to contract a respective tensor network of one or more tensor networks into a determined contracted tensor network (Huang (¶0061, fig. 6 item 606, fig. 7 item 706), “the computing host may reconstruct the sub-graph. The computing host may discover different combinations of leaf nodes that are contractable to generate a new sub-graph.”, Huang (¶0072, fig. 2 item 714), “the computing host may replace the sub-graph with the local optimal sub-graph”);
determine, for each contraction expression, a contraction cost for contracting the respective tensor network into the determined contracted tensor network based on a cost function (Huang (¶0062, fig. 6 item 608), “contraction performance may be evaluated in terms of computation cost.”);
select the contraction expression with the lowest contraction cost (Huang (¶0064, fig. 6 item 612), “When the contraction performance of the reconstructed sub-graph satisfies a preset criteria, at block 612, the computing host may replace the sub-graph with the reconstructed
sub-graph.”); and
contract each tensor network of the one or more tensor networks into the determined contracted tensor network based on the selected contraction expression (Huang (¶0064, fig. 6 item 612), “When the contraction performance of the reconstructed sub-graph satisfies a preset criteria, at block 612, the computing host may replace the sub-graph with the reconstructed
sub-graph.”);
Huang may not explicitly disclose:
wherein the cost function is based on at least one of:
a first parameter indicating an amount of memory required for contracting the respective tensor network into the determined contracted tensor network;
a second parameter indicating a computational complexity required for contracting the respective tensor network into the determined contracted tensor network; and
a third parameter indicating a number of read-write operations required for contracting the respective tensor network into the determined contracted tensor network.
Huang2 teaches:
wherein the cost function (Huang2 (¶0056, ¶0062), “maximum value of the sum of the sizes of the tensors in the tensor network. Depending on the scenarios, the time and space consumptions can be merged into a single quantity which serves as a resource estimator for the contraction”) is based on at least on of:
a first parameter indicating an amount of memory required for contracting the respective tensor network into the determined contracted tensor network (Huang2 (¶0056, ¶0062), “maximum value of the sum of the sizes of the tensors in the tensor network. Depending on the scenarios, the time and space (an amount of memory) consumptions can be merged into a single quantity which serves as a resource estimator for the contraction”);
a second parameter indicating a computational complexity required for contracting the respective tensor network into the determined contracted tensor network (Huang2 (¶0056, ¶0062), “maximum value of the sum of the sizes of the tensors in the tensor network. Depending on the scenarios, the time and space (computational complexity) consumptions can be merged into a single quantity which serves as a resource estimator for the contraction”); and
a third parameter indicating a number of read-write operations required for contracting the respective tensor network into the determined contracted tensor network (Huang2 (¶0051 line 3-4), “additional space of dimension (a) x dimension (c) x dimension(d) is needed”; Huang2 (¶0052 line 4-7), “The estimation of the cost of the matrix manipulation (read-write operations) can depend on the shape of the intermediate tensors rather than the actual values”).
Huang teaches a system/method for searching the optimized contraction operation based on consumption cost. Huang2 discloses parameters for optimizing contraction operation in quantum simulation. It would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to modify consumption cost of Huang instead be parameters taught by Huang2, with a reasonable expectation of success. The motivation would be to “provide methods and systems that use sub-networks to make estimations on computational costs on contraction orders.” (Huang2 (¶0062 line 1-3))
As Claim 2, besides Claim 1, Huang in view of Huang2 teaches wherein the one or more tensor networks have a same graph representation as each other (Huang (¶0059, fig. 6 item 602), “computing host may obtain a contraction tree associated with a tensor network, wherein a plurality of vertices and edges of the contraction tree correspond to a set of tensor nodes and indices of the tensor network, respectively.”).
As Claim 5, besides Claim 1, Huang in view of Huang2 teaches wherein performing the local search algorithm to determine the plurality of contraction expressions comprises applying a plurality of local transformations, the plurality of local transformations including at least one of the following local transformations from a first contraction expression to a second contraction expression: from (a*b)*c to (c*b)*a; from (a*b)*c to (a*c)*b; from a*(b*c) to b*(a*c); from a*(b*c) to c*(b*a); wherein a, b, and c are tensors of the respective tensor network and, * denotes a convolution operation (Huang2 (¶0052 line 1-4), “merging tensors can involve matrix multiplication. In resource estimation, instead of performing the actual matrix multiplication right away, the cost of the matrix multiplication can be estimated first”).
As Claim 6, besides Claim 1, Huang in view of Huang2 teaches wherein the local search algorithm comprises one of a hill climbing algorithm or a simulated annealing algorithm (Huang2 (¶0050), “As an example, an edge b can be merged and summed over. As a result, a tensor network 502 is generated with a new tensor F replacing tensors connected by edge b”).
As Claim 10, besides Claim 1, Huang in view of Huang2 teaches wherein at least one of:
each contraction expression comprises at least one convolution of two tensors of the respective tensor network of the one or more tensor networks (Huang2 (¶0052 line 1-4), “merging tensors can involve matrix multiplication. In resource estimation, instead of performing the actual matrix multiplication right away, the cost of the matrix multiplication can be estimated first”) and
determining a contraction cost of a contraction expression comprises performing at least one convolution of two tensors of the respective tensor network of the one or more tensor networks (Huang (¶0064, fig. 6 item 612), “When the contraction performance of the reconstructed sub-graph satisfies a preset criterion, at block 612, the computing host may replace the sub-graph with the reconstructed sub-graph.”).
As Claim 11, besides Claim 12, Huang in view of Huang2 teaches configured to save a convolution result of determining a convolution of two tensors of the respective tensor network in a cache (Huang2 (¶0054 last 5 lines), “The chosen edge and its neighbors in the tensor network can then be replaced by the new intermediate tensor. In some embodiments, the above iterative step can be repeated until the contraction order is empty.”).
As Claim 12, besides Claim 12, Huang in view of Huang2 teaches configured to reuse a convolution result, which was saved while contracting a first tensor network, when contracting a second tensor network (Huang2 (¶0054 last 5 lines), “The chosen edge and its neighbors in the tensor network can then be replaced by the new intermediate tensor. In some embodiments, the above iterative step can be repeated until the contraction order is empty.”).
As Claim 13, the Claim is rejected for the same reasons as Claim 1.
As Claim 14, besides Claim 13, Huang in view of Huang2 teaches configured to simulate a quantum circuit, wherein simulating the quantum circuit comprises contracting one or more tensor networks into the determined contracted tensor network (Huang2 (¶0054 last 5 lines), “The chosen edge and its neighbors in the tensor network can then be replaced by the new intermediate tensor. In some embodiments, the above iterative step can be repeated until the contraction order is empty.”).
As Claim 17, the Claim is rejected for the same reasons as Claim 1.
Claim(s) 3 is/are rejected under 35 U.S.C. 103 as being unpatentable over Huang in view of Huang2 in further view of Wu et al. (U.S. 2022/0350863 hereinafter Wu).
As Claim 3, besides Claim 1, Huang in view of Huang2 may not explicitly disclose:
wherein the cost function is based on an arithmetic intensity, which is defined by a ratio of the second parameter and the third parameter.
Wu teaches:
wherein the cost function is based on an arithmetic intensity, which is defined by a ratio of the second parameter and the third parameter (Wu (¶0058 line 6-9), “the logic 170 may determine a ratio of floating-point instructions to memory read instructions and control a dimension size (e.g., M) of a matrix kernel based at least in part on the ratio”).
Huang in view of Huang2 discloses parameters for optimizing tensor (neural) network contraction operation in quantum simulation. The parameters include space or memory consumption. Wu discloses system/method to enhance memory access and improve deep learning result. It would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to modify consumption cost of Huang in view of Huang2 instead be ratio number taught by Wu, with a reasonable expectation of success. The motivation would be to “performance-enhance at least to the extent that the logic 170 ensures that an acceptable FP AIR is maintained despite the potential side-effects of controlling the dimension size of the maintenance kernel. Fewer cache conflicts may translate into less latency and improved deep learning results (e.g., shorter training times).” (Wu (¶0058 last 6 lines)).
Claim(s) 7-9 is/are rejected under 35 U.S.C. 103 as being unpatentable over Huang in view of Huang2 in further view of Fang (“A Parallel Tensor Network Contraction Algorithm and Its Application in Quantum Computation” hereinafter Fang).
As Claim 7, besides Claim 1, Huang in view of Huang2 teaches:
the respective tensor network has a graph representation comprising a vertex for each tensor of the respective tensor network and at least one edge for each tensor leg of each tensor (Huang2 (¶0050), “As an example, an edge b can be merged and summed over. As a result, a tensor network 502 is generated with a new tensor F replacing tensors connected by edge b”)
Huang in view of Huang2 may not explicitly disclose:
and the processor is further configured to perform a slicing operation during the local search algorithm by fixing a set of tensor legs in the respective tensor network.
Fang teaches:
, and the processor is further configured to perform a slicing operation during the local search algorithm by fixing a set of tensor legs in the respective tensor network (Fang (1.2.1 A Parallel tensor network contraction algorithm, second paragraph), “slicing the tensor network, i.e. splitting it into multiple simpler tensor networks that sum to the original tensor network. By slicing k edges, the original tensor network will be split into 2^k tensor networks with identical structure, each with lower space and time requirements to contract than the original.”).
Huang in view of Huang2 discloses parameters for optimizing tensor (neural) network contraction operation in quantum simulation. The parameters include space or memory consumption. Wu discloses system/method to apply slicing for parallel contraction of tensor network. It would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to modify consumption cost of Huang in view of Huang2 instead be slicing taught by Wu, with a reasonable expectation of success. The motivation would be to “show that this procedure indeed finds good contraction schemes in practice, and thus give evidence that efficient parallel tensor network contraction is indeed possible under this framework” (Fang (1.2.1 Parallel tensor network contraction algorithm, last paragraph)).
As Claim 8, besides Claim 7, Huang in view of Huang2 in further view of Fang teaches configured to update the fixed set of tensor legs after a determined number of steps of performing the local search algorithm by at least one of removing a random tensor leg from the fixed set and adding a tensor leg resulting in the largest reduction of the first parameter to the fixed set (Huang (¶0064, fig. 6 item 612), “When the contraction performance of the reconstructed sub-graph satisfies a preset criteria, at block 612, the computing host may replace the sub-graph with the reconstructed sub-graph.”)
As Claim 9, besides Claim 1, Huang in view of Huang2 may not explicitly disclose further configured to select the same contraction expression with the lowest contraction cost for contracting in parallel each of multiple tensor networks having the same graph representation into the determined contracted tensor network.
Fang teaches:
further configured to select the same contraction expression with the lowest contraction cost for contracting in parallel each of multiple tensor networks having the same graph representation into the determined contracted tensor network (Fang (1.2.2 Parallel tensor network contraction algorithm, second paragraph), “is to find a feasible contraction scheme (i.e. one with a space cost low enough to fit in the available memory) with as low a time cost as possible”).
Huang in view of Huang2 discloses parameters for optimizing tensor (neural) network contraction operation in quantum simulation. The parameters include space or memory consumption. Wu discloses system/method to apply slicing for parallel contraction of tensor network. It would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to modify consumption cost of Huang in view of Huang2 instead be slicing taught by Wu, with a reasonable expectation of success. The motivation would be to “show that this procedure indeed finds good contraction schemes in practice, and thus give evidence that efficient parallel tensor network contraction is indeed possible under this framework” (Fang (1.2.1 Parallel tensor network contraction algorithm, last paragraph)).
Claim(s) 15-16 is/are rejected under 35 U.S.C. 103 as being unpatentable over Huang in view of Huang2 in further view of Villalonga (“A flexible high-performance simulator for verifying and Benchmarking quantum circuits implemented on real hardware” hereinafter Villalonga).
As Claim 15, besides Claim 13, Huang in view of Huang2 may not explicitly disclose:
configured to perform a verification of a quantum circuit by finding an amplitude of each of multiple samples produced by the quantum circuit.
Villalonga teaches:
configured to perform a verification of a quantum circuit by finding an amplitude of each of multiple samples produced by the quantum circuit (Villalonga (Results, second paragraph, last 7 lines), “Figure 2 reports the distribution of the runtimes for a single instance of each of the six simulations [Run 1–6] for both Pleiades and Electra”).
Huang in view of Huang2 discloses parameters for optimizing tensor (neural) network contraction operation in quantum simulation. Villalonga teaches a system/method for verification and benchmarking by simulating quantum system. It would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to modify consumption cost of Huang in view of Huang2 instead be benchmarking system taught by Villalonga, with a reasonable expectation of success. The motivation would be to provide “our tensor network-based simulator relies on four different points of strength as follows:” Robustness, Strength, Flexibility and Scalability (Villalonga (page 2, second column, line 1-2)).
As Claim 16, besides Claim 13, Huang in view of Huang2 may not explicitly disclose:
configured to determine a linear cross-entropy benchmarking of a bit string including a plurality of samples produced by a quantum circuit.
Villalonga teaches:
configured to determine a linear cross-entropy benchmarking of a bit string including a plurality of samples produced by a quantum circuit (Villalonga (Results, second paragraph, line 7-8), “the peak for the LINear equations software PACKage (LINPACK) benchmark is 23 PFLOPS (single precision, projected), which is only 15% larger than the peak we obtained with our simulator”).
Huang in view of Huang2 discloses parameters for optimizing tensor (neural) network contraction operation in quantum simulation. Villalonga teaches a system/method for verification and benchmarking by simulating quantum system. It would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to modify consumption cost of Huang in view of Huang2 instead be benchmarking system taught by Villalonga, with a reasonable expectation of success. The motivation would be to provide “our tensor network-based simulator relies on four different points of strength as follows:” Robustness, Strength, Flexibility and Scalability (Villalonga (page 2, second column, line 1-2)).
Response to Arguments
Objections to the Claims:
Applicant amended Claims 1 and 13; therefore, the claims are no longer objected.
Rejections under 35 U.S.C. §112(b):
Applicant amended Claims 2 and 4; 35 U.S.C. §112(b) rejections on Claims 4 are respectfully withdrawn. Claim 2 is rejected under new 35 U.S.C. §112(b) rejection(s).
Rejections under 35 U.S.C. §103:
As Claim 1, Applicant argue that Huang2 does not disclose “a cost function that separately tracks read-write operations apart from computational complexity” (first paragraph of page 9 in the remarks).
PNG
media_image1.png
118
606
media_image1.png
Greyscale
Applicant’s argument(s) are fully considered but are not persuasive. The Claim recites “the cost function is based on at least one of:”. Therefore, “a cost function that separately tracks read-write operations apart form computational complexity” is not claimed at least in Claims 1, 13 and 17. Further clarifying the Claims with these limitation(s) might advance the prosecution.
Conclusion
The prior art made of record and not relied upon is considered pertinent to applicant's disclosure. Samuel Webb Williams (“Auto-tuning Performance on Multicore Computers”, http://www.eecs.berkeley.edu/Pubs/TechRpts/2008/EECS-2008-164.html), discloses a relationship between memory, read/write operation per second and arithmetic intensity.
THIS ACTION IS MADE FINAL. Applicant is reminded of the extension of time policy as set forth in 37 CFR 1.136(a).
A shortened statutory period for reply to this final action is set to expire THREE MONTHS from the mailing date of this action. In the event a first reply is filed within TWO MONTHS of the mailing date of this final action and the advisory action is not mailed until after the end of the THREE-MONTH shortened statutory period, then the shortened statutory period will expire on the date the advisory action is mailed, and any nonprovisional extension fee (37 CFR 1.17(a)) pursuant to 37 CFR 1.136(a) will be calculated from the mailing date of the advisory action. In no event, however, will the statutory period for reply expire later than SIX MONTHS from the mailing date of this final action.
Any inquiry concerning this communication or earlier communications from the examiner should be directed to NHAT HUY T NGUYEN whose telephone number is (571)270-7333. The examiner can normally be reached M-F: 12:00-8:00 EST.
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, Viker Lamardo can be reached at 571-270-5871. 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.
/NHAT HUY T NGUYEN/ Primary Examiner, Art Unit 2147
Prosecution Insights