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 .
Information Disclosure Statement
The information disclosure statement (IDS) submitted on 01/31/2024 and 04/02/2024 are in compliance with the provisions of 37 CFR 1.97. Accordingly, the information disclosure statement is being considered by the examiner.
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.
Claims 1-20 are rejected under 35 U.S.C. 112(b) or 35 U.S.C. 112 (pre-AIA ), second paragraph, as being indefinite for failing to particularly point out and distinctly claim the subject matter which the inventor or a joint inventor (or for applications subject to pre-AIA 35 U.S.C. 112, the applicant), regards as the invention.
Claims 1 and 19 recite the variable ‘u’ in “Gu = h” however, ‘u’ is undefined. For examination purposes, Examiner interprets ‘u’ as the solution to the linear system in accordance with page 82 of the Applicant’s specification. Claims 2-18 and 20 are dependent claims that do not cure the deficiencies and are rejected for similar reasons.
Claim Rejections - 35 USC § 101
35 U.S.C. 101 reads as follows:
Whoever invents or discovers any new and useful process, machine, manufacture, or composition of matter, or any new and useful improvement thereof, may obtain a patent therefor, subject to the conditions and requirements of this title.
Claims 1-20 are rejected under 35 U.S.C. 101 because the claimed invention is directed to an abstract idea without significantly more.
Step 1
According to the first part of the analysis, in the instant case, claims 1-18 are directed to a method and claims 19-20 are directed to a non-transitory computer-readable storage medium. Thus, each of the claims falls within one of the four statutory categories (i.e. process, machine, manufacture, or composition of matter).
Claim 1 recites:
Step 2A, Prong 1
“(b) defining a Newton system for the SOCP instance by constructing matrix G and vector h, where matrix G and vector h describe constrains for a linear system Gu = h based on the SOCP instance” (This step is directed to a mathematical concept. See MPEP § 2106.04(a)(2), subsection I.)
“(c) preconditioning matrix G and vector h via row normalization to reduce a condition number of matrix G” (This step is directed to a mathematical concept. See MPEP § 2106.04(a)(2), subsection I.)
“(d) iteratively determining u until a predetermined iteration condition is met, the iterations comprising: causing the quantum computing system to apply matrix G and vector h to a quantum linear system solver (QLSS) to generate a quantum state” (This step is directed to a mathematical concept. See MPEP § 2106.04(a)(2), subsection I.)
“causing the quantum computing system to perform quantum state tomography on the quantum state” (This step is directed to a mathematical concept. See MPEP § 2106.04(a)(2), subsection I.)
“updating a value of u based on a current value of u and the output of the quantum state tomography” (This step is directed to a mathematical concept. See MPEP § 2106.04(a)(2), subsection I.)
“(e) determining a solution to the SOCP instance based on the updated value of u” (This step is directed to a mathematical concept. See MPEP § 2106.04(a)(2), subsection I.)
Step 2A, Prong 2
“(a) receiving the SOCP instance” (insignificant extra-solution activity)
This judicial exception is not integrated into a practical application.
Step 2B
“(a) receiving the SOCP instance” (This step appears to be directed to transmitting or receiving information, which is well-understood, routine, and conventional. i. Receiving or transmitting data over a network, e.g., using the Internet to gather data, Symantec, 838 F.3d at 1321, 120 USPQ2d at 1362 (utilizing an intermediary computer to forward information); See MPEP 2106.05 (d) (II).)
The claim does not include additional elements that are sufficient to amount to significantly more than the judicial exception.
Claim 2 recites:
Step 2A, Prong 1
“wherein preconditioning matrix G and vector h comprises: determining a diagonal matrix D where at least one entry Dit is equal to the norm of row i of matrix G” (This step is directed to a mathematical concept. See MPEP § 2106.04(a)(2), subsection I.)
Step 2A, Prong 2 & 2B
The claim does not recite any additional elements.
Claim 3 recites:
Step 2A, Prong 1
“redefining matrix G and vector h according to: G = D-'G and h= D-'h” (This step is directed to a mathematical concept. See MPEP § 2106.04(a)(2), subsection I.)
Step 2A, Prong 2 & 2B
The claim does not recite any additional elements.
Claim 4 recites:
Step 2A, Prong 1
“wherein D-'G has a condition number less that the condition number of previous matrix G” (This step is directed to a mathematical concept. See MPEP § 2106.04(a)(2), subsection I.)
Step 2A, Prong 2 & 2B
The claim does not recite any additional elements.
Claim 5 recites:
Step 2A, Prong 1
“wherein the output of the quantum state tomography is a unit vector v' indicating an iteration direction for u” (This step is directed to a mathematical concept. See MPEP § 2106.04(a)(2), subsection I.)
Step 2A, Prong 2 & 2B
The claim does not recite any additional elements.
Claim 6 recites:
Step 2A, Prong 1
“The method of claim 5, wherein the unit vector v' is characterized by ||V – v|| ≤ { with probability equal to or greater than a predetermined probability threshold, where v ocG-'h and is a tomography precision parameter.” (This step is directed to a mathematical concept. See MPEP § 2106.04(a)(2), subsection I.)
Step 2A, Prong 2 & 2B
The claim does not recite any additional elements.
Claim 7 recites:
Step 2A, Prong 1
“determining a step length o 0 based on the unit vector v and adding the current value of u to the product of: (1) the step length o and (2) the unit vector v” (This step is directed to a mathematical concept. See MPEP § 2106.04(a)(2), subsection I.)
Step 2A, Prong 2 & 2B
The claim does not recite any additional elements.
Claim 8 recites:
Step 2A, Prong 1
“
PNG
media_image1.png
69
315
media_image1.png
Greyscale
where Ax, As, Ax, and Ar are components of the unit vector v'; x, s, x, and r are components of current u;p(x, r, s, x) is a duality gap; a is the step length; and r is the number of second-order cone constraints of the SOCP instance.” (This step is directed to a mathematical concept. See MPEP § 2106.04(a)(2), subsection I.)
Step 2A, Prong 2 & 2B
The claim does not recite any additional elements.
Claim 9 recites:
Step 2A, Prong 1
“wherein the step length o is determined such that a duality gap p of the updated value of u is a factor of o smaller than the current value of u within a second order deviation in the step length o.” (This step is directed to a mathematical concept. See MPEP § 2106.04(a)(2), subsection I.)
Step 2A, Prong 2 & 2B
The claim does not recite any additional elements.
Claim 10 recites:
Step 2A, Prong 1
“wherein the duality gap u describes a difference between the current value of u and an exact solution to the linear system Gu = h” (This step is directed to a mathematical concept. See MPEP § 2106.04(a)(2), subsection I.)
Step 2A, Prong 2 & 2B
The claim does not recite any additional elements.
Claim 11 recites:
Step 2A, Prong 1
“wherein the quantum state tomography is performed according to a tomography precision parameter { that decreases with each new iteration” (This step is directed to a mathematical concept. See MPEP § 2106.04(a)(2), subsection I.)
Step 2A, Prong 2 & 2B
The claim does not recite any additional elements.
Claim 12 recites:
Step 2A, Prong 1
“wherein the tomography precision parameter { decreases by (/2 with each new iteration” (This step is directed to a mathematical concept. See MPEP § 2106.04(a)(2), subsection I.)
Step 2A, Prong 2 & 2B
The claim does not recite any additional elements.
Claim 13 recites:
Step 2A, Prong 1
“wherein causing the quantum computing system to apply matrix G and vector h to the QLSS to generate the quantum state comprises k > 0 applications of the QLSS and k controlled-applications of the QLSS to generate the quantum state” (This step is directed to a mathematical concept. See MPEP § 2106.04(a)(2), subsection I.)
Step 2A, Prong 2 & 2B
The claim does not recite any additional elements.
Claim 14 recites:
Step 2A, Prong 1
“repeating steps (b)-(d) and iteratively updating a duality gap u based on the output of the quantum state tomography until the duality gap u is less than the target precision s, where the duality gap u describes a difference between the current value of u and an exact solution to the linear system Gu = h” (This step is directed to a mathematical concept. See MPEP § 2106.04(a)(2), subsection I.)
Step 2A, Prong 2
“receiving a target precision s for the solution to the SOCP instance” (insignificant extra-solution activity)
This judicial exception is not integrated into a practical application.
Step 2B
“receiving a target precision s for the solution to the SOCP instance” (This step appears to be directed to transmitting or receiving information, which is well-understood, routine, and conventional. i. Receiving or transmitting data over a network, e.g., using the Internet to gather data, Symantec, 838 F.3d at 1321, 120 USPQ2d at 1362 (utilizing an intermediary computer to forward information); See MPEP 2106.05 (d) (II).)
The claim does not include additional elements that are sufficient to amount to significantly more than the judicial exception.
Claim 15 recites:
Step 2A, Prong 1
“wherein matrix G and vector h are constructed further based on the updated value of u” (This step is directed to a mathematical concept. See MPEP § 2106.04(a)(2), subsection I.)
Step 2A, Prong 2 & 2B
The claim does not recite any additional elements.
Claim 16 recites:
Step 2A, Prong 1
Claim 16 recites at least the abstract idea identified above in claim 1.
Step 2A, Prong 2
“wherein causing the quantum computing system to apply matrix G and vector h to the QLSS comprises causing the quantum computing system to execute a quantum circuit” (Mere instructions to apply the exception using a generic computer component. See 2106.05(f).)
This judicial exception is not integrated into a practical application.
Step 2B
“wherein causing the quantum computing system to apply matrix G and vector h to the QLSS comprises causing the quantum computing system to execute a quantum circuit” (Mere instructions to apply the exception using a generic computer component. See 2106.05(f).)
The claim does not include additional elements that are sufficient to amount to significantly more than the judicial exception.
Claim 17 recites:
Step 2A, Prong 1
“wherein the QLSS operates on a block encoded version of matrix G and a state-prepared version of vector h” (This step is directed to a mathematical concept. See MPEP § 2106.04(a)(2), subsection I.)
Step 2A, Prong 2 & 2B
The claim does not recite any additional elements.
Claim 18 recites:
Step 2A, Prong 1
“causing matrix G to be block encoded onto the quantum computing system and the vector h to be state encoded onto the quantum computing system” (This step is directed to a mathematical concept. See MPEP § 2106.04(a)(2), subsection I.)
Step 2A, Prong 2 & 2B
The claim does not recite any additional elements.
Claim 19 recites:
See rejection of claim 1. Same rationale applies.
Step 2A, Prong 2 & 2B
The claim recites additional elements (“A non-transitory computer-readable storage medium storing code”). (Mere instructions to apply the exception using a generic computer component. See 2106.05(f).)
This judicial exception is not integrated into a practical application.
The claim does not include additional elements that are sufficient to amount to significantly more than the judicial exception.
Claim 20 recites:
See rejection of claim 2. Same rationale applies.
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-2, 5, 11, 13-20 are rejected under 35 U.S.C. 103 as being unpatentable over Kerenidis et al. (“A quantum interior-point method for second-order cone programming”) in view of Augustino et al. (“An inexact-feasible quantum interior point method for second-order cone optimization”).
Regarding Claim 1,
Augustino (“An Inexact-Feasible Quantum Interior Point Method for Second-order Cone Optimization”) teaches a quantum interior point method (QIPM) for solving a second-order cone program (SOCP) instance using a quantum computing system, the method comprising:
(a) receiving the SOCP instance (pg. 1; “If all cones Ki are of the same type, the optimization problem is a linear program (LP), second order cone program (SOCP), and semidefinite program (SDP), respectively.”);
(b) defining a Newton system for the SOCP instance by constructing matrix G and vector h, where matrix G and vector h describe constrains for a linear system Gu = h based on the SOCP instance (pg. 5, section 2.2; “Instead, given a matrix A and a vector b, we construct the quantum state A−1b (using the notation from (2))… Instead, given a matrix A and a vector b, we construct the quantum state A−1b (using the notation from (2)).” pg. 8; “More precisely, in each step we apply to our current iterate (x,y,s) one round of Newton’s method for solving the system (10) with ν = σµ.”);
(d) iteratively determining u until a predetermined iteration condition is met (pg. 9, algorithm 2;), the iterations comprising:
causing the quantum computing system to apply matrix G and vector h to a quantum linear system solver (QLSS) to generate a quantum state (pg. 9, algorithm 2;);
causing the quantum computing system to perform quantum state tomography on the quantum state (pg. 9, algorithm 2;); and
updating a value of u based on a current value of u and the output of the quantum state tomography (pg. 9, algorithm 2;); and
(e) determining a solution to the SOCP instance based on the updated value of u (pg. 9, algorithm 2;).
Kerenidis does not explicitly disclose
(c) preconditioning matrix G and vector h via row normalization to reduce a condition number of matrix G;
However, Augustino (“An Inexact-Feasible Quantum Interior Point Method for Second-order Cone Optimization”) teaches
(c) preconditioning matrix G and vector h via row normalization to reduce a condition number of matrix G (pg. 3, section 2.1; “A block encoding U of A is a unitary such that:
PNG
media_image2.png
73
190
media_image2.png
Greyscale
where α is a normalization factor.” Pg. 4; “Thus, U† RUL is a block encoding of A with normalization factor ∥A∥F.”);
Kerenidis and Augustino are analogous because they are directed to quantum interior point method second-order cone optimization.
It would have been obvious to one of ordinary skill in the art before the effective filing date to modify the quantum interior point method of Kerenidis with the normalization of Augustino.
Doing so would allow for pre-processing to create certain data structures that can be stored in quantum-accessible storage, i.e.,QRAM (Augustino pg. 4).
Regarding Claim 2,
Kerenidis and Augustino teach the method of claim 1. Kerenidis further teaches wherein preconditioning matrix G and vector h comprises: determining a diagonal matrix D where at least one entry Dit is equal to the norm of row i of matrix G (pg. 5, section 2.1; “2. The matrix representations Arw(x) and Qx are the block-diagonal matrices containing the representations of the blocks:”).
Regarding Claim 5,
Kerenidis and Augustino teach the method of claim 1. Kerenidis further teaches wherein the output of the quantum state tomography is a unit vector v' indicating an iteration direction for u (pg. 9, algorithm 2; “Perform vector state tomography with UN (Theorem 3) and use the norm es timate from (b) to obtain the classical estimate (∆x;∆y;∆s) such that with probability 1 − 1/poly(n),”).
Regarding Claim 11,
Kerenidis and Augustino teach the method of claim 1. Kerenidis further teaches wherein the quantum state tomography is performed according to a tomography precision parameter { that decreases with each new iteration (pg. 16, section 4.3; “If the tomography precision for iteration i is chosen to be at least (i.e. smaller than)
PNG
media_image3.png
61
337
media_image3.png
Greyscale
, then the premises of Theorem 4 are satisfied.”).
Regarding Claim 13,
Kerenidis and Augustino teach the method of claim 1. Kerenidis further teaches wherein causing the quantum computing system to apply matrix G and vector h to the QLSS to generate the quantum state comprises k > 0 applications of the QLSS and k controlled-applications of the QLSS to generate the quantum state (pg. 8-9, section 4; “In a way, it is similar to the SDP solver from [16] since we apply a quantum linear system solver to get the solutions of the Newton system (11) as quantum states and then perform tomography to recover the solutions. However, it differs from the SDP solver as the construction of block encodings for the Newton matrix for the SOCP case is much simpler than that for the general SDP case.” Algorithm 2.).
Regarding Claim 14,
Kerenidis and Augustino teach the method of claim 1. Kerenidis further teaches further comprising: receiving a target precision s for the solution to the SOCP instance (pg. 9, algorithm 2;); and repeating steps (b)-(d) and iteratively updating a duality gap u based on the output of the quantum state tomography until the duality gap u is less than the target precision s, where the duality gap u describes a difference between the current value of u and an exact solution to the linear system Gu = h (pg. 7; “The difference between these two values is called the duality gap, it is denoted by µ, and usually normalized by a factor of 1 r:
PNG
media_image4.png
72
496
media_image4.png
Greyscale
”).
Regarding Claim 15,
Kerenidis and Augustino teach the method of claim 14. Kerenidis further teaches wherein matrix G and vector h are constructed further based on the updated value of u (pg. 9, algorithm 2;).
Regarding Claim 16,
Kerenidis and Augustino teach the method of claim 1. Kerenidis further teaches wherein causing the quantum computing system to apply matrix G and vector h to the QLSS comprises causing the quantum computing system to execute a quantum circuit (pg. 5; “Furthermore, U needs to be implemented efficiently, i.e. using an ℓ-qubit quantum circuit of depth (poly)logarithmic in n. Such a circuit would allow us to efficiently create states |Ai corresponding to columns of A.”).
Regarding Claim 17,
Kerenidis and Augustino teach the method of claim 1. Kerenidis further teaches wherein the QLSS operates on a block encoded version of matrix G and a state-prepared version of vector h (pg. 5;
PNG
media_image5.png
95
907
media_image5.png
Greyscale
).
Regarding Claim 18,
Kerenidis and Augustino teach the method of claim 17. Kerenidis further teaches further comprising: causing matrix G to be block encoded onto the quantum computing system and the vector h to be state encoded onto the quantum computing system (pg. 6; “Theorem 2. (Quantum linear algebra with block encodings) [7, 10] Let A ∈ Rn×n be a matrix with non-zero eigenvalues in the interval [−1,−1/κ] ∪ [1/κ,1], and let ϵ > 0. Given an imple mentation of an (ζ,O(logn)) block encoding for A in time TU and a procedure for preparing state |b in time Tb,”).
Regarding Claim 19,
Claim 19 is the computer-readable storage medium corresponding to the method of claim 1. Claim 19 is substantially similar to claim 1 and is rejected on the same grounds.
Regarding Claim 20,
Claim 20 is the computer-readable storage medium corresponding to the method of claim 2. Claim 20 is substantially similar to claim 2 and is rejected on the same grounds.
Conclusion
Any inquiry concerning this communication or earlier communications from the examiner should be directed to HENRY K NGUYEN whose telephone number is (571)272-0217. The examiner can normally be reached Mon - Fri 7:00am-4:30pm.
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, Li B Zhen can be reached at 5712723768. 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.
/HENRY NGUYEN/Examiner, Art Unit 2121
Prosecution Insights