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 Claims
Claims 1-7 as presented in the preliminary amendment are pending and are examined herein.
Claims 2-4 and 6 are rejected under 35 USC 112(b).
Claims 1-7 are rejected under 35 USC 101 as being directed to an abstract idea without significantly more.
Claims 1-2 and 4-7 are rejected under 35 USC 103.
Information Disclosure Statement
The listing of references in the specification is not a proper information disclosure statement. 37 CFR 1.98(b) requires a list of all patents, publications, or other information submitted for consideration by the Office, and MPEP § 609.04(a) states, "the list may not be incorporated into the specification but must be submitted in a separate paper." Therefore, unless the references have been cited by the examiner on form PTO-892, they have not been considered.
Claim Rejections - 35 USC § 112(b)
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 2-4 and 6 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.
Regarding claims 2-3, portions of the formulas in these claims are illegible. For the purposes of examination, the formulas are being interpreted as being the same as those in the originally filed claims.
Regarding claim 3, the claim defines the symbol T, but this symbol is not used in any of the positively recited method steps. It is unclear what limiting effect, if any, the definition is intended to have on the scope of the claim. For the purposes of examination, the claim is being interpreted as being dependent on claim 2.
Regarding claim 3, the formula uses the symbol X which is not defined by the claim. For the purposes of examination, X is being interpreted as a constant which satisfies the condition specified on page 13, lines 24-25 of the specification.
Regarding claim 4, the claim recites the symbol T, but does not define this symbol. A person of ordinary skill in the art would understand that i represents the imaginary unit, that I represents the identity matrix having the dimension corresponding to the dimension of TT+, and that the dagger symbol (shown in this correspondence as + for typographical reasons) represents the conjugate transpose of the operator T. For the purposes of examination, T is being interpreted as being a projection onto a vector space as in claim 2.
Regarding claim 6, the claim recites W and T, but does not define these symbols. Note comments regarding the symbols which would be understood by a person of ordinary skill in the art in claim 4. For the purposes of examination, W is being interpreted as the quantum walk operator and T is being interpreted as being a projection onto a vector space.
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-7 are rejected under 35 U.S.C. 101 because the claimed invention is directed to an abstract idea without significantly more.
Step 1 Analysis
Each of the claims fall within one of the four statutory categories (i.e. process, machine, manufacture, or composition of matter).
Step 2 Analysis
Claim 1 includes the following recitation of an abstract idea:
A method of solving matrix equations (This is a recitation of a mathematical concept.)
...(ii) expressing Ib) as a superposition of eigenvectors of the system matrix A; (This is a recitation of a mathematical concept.)
(iii) translating Ib) to a superposition of eigenvectors of a unitary comprising a quantum walk operator defined by reflections about a linear span defined from A; (This is a recitation of a mathematical concept.)
(iv) applying quantum phase estimation using said unitary to the superposition of eigenvectors; (This is a recitation of a mathematical concept.)
(v) applying the inverse of each eigenvalue of system matrix A to its corresponding eigenvector in the translated superposition; (This is a recitation of a mathematical concept.)
(vi) uncomputing by applying inverse phase estimation and eigenvector translation; and(This is a recitation of a mathematical concept.)
(vii) extracting the solution Ix) from a result of the previous steps. (This is a recitation of a mathematical concept.)
Claim 1 recites the following additional elements which, considered individually and as an ordered combination, do not integrate the abstract idea into a practical application or amount to significantly more than the abstract idea:
using a quantum computing system, the method comprising: (This is a high level recitation of generic computer components for performing the abstract idea. This does not integrate the abstract idea into a practical application or amount to significantly more than the abstract idea. See MPEP 2106.05(f). Note in particular that the broadest reasonable interpretation of “quantum computing system” in view of the specification appears to encompass a classical computer performing simulations as described in the as-filed specification at page 30, lines 6-19.)
(i) obtaining a matrix equation Alx)=|b) where A is an N x N system matrix and Ix) and lb) are N -dimensional vectors; (This is insignificant extra-solution activity. See MPEP 2106.05(g). Moreover, sending or receiving data is well-understood, routine, conventional as evidenced by the court cases cited at MPEP 2106.05(d), example i. Receiving or transmitting data.)
Claim 1 does not reflect an improvement to computer technology or any other technology.
Claim 2 recites at least the abstract idea identified above in the claim upon which it depends, and further recites
the quantum walk operator containing a reflection operator defined as 2TT† - I, where application of T† and T performs projection onto a vector space. (This is a recitation of a mathematical concept.)
Claim 2 does not recite further additional elements which might integrate the abstract idea into a practical application or amount to significantly more than the abstract idea.
Claim 2 does not reflect an improvement to computer technology or any other technology.
Claim 3 recites at least the abstract idea identified above in the claim upon which it depends, and further recites the following mathematical concept
PNG
media_image1.png
162
464
media_image1.png
Greyscale
Claim 3 does not recite further additional elements which might integrate the abstract idea into a practical application or amount to significantly more than the abstract idea.
Claim 3 does not reflect an improvement to computer technology or any other technology.
Claim 4 recites at least the abstract idea identified above in the claim upon which it depends, and further recites
defining the quantum walk operator by the expression W = iS(2TT† - I), where S is a register swap operation (This is a recitation of a mathematical concept.)
Claim 4 does not recite further additional elements which might integrate the abstract idea into a practical application or amount to significantly more than the abstract idea.
Claim 4 does not reflect an improvement to computer technology or any other technology.
Claim 5 recites at least the abstract idea identified above in the claim upon which it depends, and further recites
subsequent to quantum phase estimation, extracting eigenvalues λj and applying ancilla rotation.
Claim 5 does not recite further additional elements which might integrate the abstract idea into a practical application or amount to significantly more than the abstract idea.
Claim 5 does not reflect an improvement to computer technology or any other technology.
Claim 6 recites at least the abstract idea identified above in the claim upon which it depends, and further recites
performing initial translation of lb) to a superposition of eigenvectors of W by applying T, and performing uncomputation by applying T† . (This is a recitation of a mathematical concept.)
Claim 6 does not recite further additional elements which might integrate the abstract idea into a practical application or amount to significantly more than the abstract idea.
Claim 6 does not reflect an improvement to computer technology or any other technology.
Claim 7 recites at least the abstract idea identified above in the claim upon which it depends, and further recites
preventing negative elements from appearing on the diagonal of system matrix A by adding a constant multiple of the identity matrix. (This is a recitation of a mathematical concept.)
Claim 7 does not recite further additional elements which might integrate the abstract idea into a practical application or amount to significantly more than the abstract idea.
Claim 7 does not reflect an improvement to computer technology or any other technology.
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 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.
This application currently names joint inventors. In considering patentability of the claims the examiner presumes that the subject matter of the various claims was commonly owned as of the effective filing date of the claimed invention(s) absent any evidence to the contrary. Applicant is advised of the obligation under 37 CFR 1.56 to point out the inventor and effective filing dates of each claim that was not commonly owned as of the effective filing date of the later invention in order for the examiner to consider the applicability of 35 U.S.C. 102(b)(2)(C) for any potential 35 U.S.C. 102(a)(2) prior art against the later invention.
Claims 1-2 and 4-6 are rejected under 35 U.S.C. 103 as being unpatentable over Dervovic (Quantum linear systems algorithms: a primer) in view of Childs (On the Relationship Between Continuous- and Discrete-Time Quantum Walk).
Regarding claim 1, Dervovic teaches
A method of solving matrix equations using a quantum computing system, the method comprising: (Dervovic, Abstract, section 3 describes the HHL algorithm, which is a quantum algorithm for solving a linear system.)
(i) obtaining a matrix equation Alx)=|b) where A is an N x N system matrix and Ix) and lb) are N -dimensional vectors; (Dervovic, page 28, first paragraph of section 3.1)
(ii) expressing Ib) as a superposition of eigenvectors of the system matrix A; (iii) translating Ib) to a superposition of eigenvectors of a unitary comprising a quantum walk operator defined by reflections (Dervovic, page 29, last paragraph going on to page 30 considers the case in which |b) is represented as a linear combination of the eigenvectors |uj) of the matrix A. See also second paragraph of section 3.2.1 for the eigen representation of A. Note that the representation of |b) as a superposition of eigenvectors of A is the same as its representation as a superposition of eigenvectors of exp(iAt) because they have the same eigenvectors/eigenstates. Dervovic, section 3.2.1, equation (69) applies the quantum unitary operator exp(iAt) to an eigenvector |uj). Page 29, last paragraph going on to page 30 indicates that the operations are extended by linearity to the full state |b). Page 46, second paragraph describes a modification to the HHL algorithm in which the function (i.e., the unitary exp(iAt) as is clear from the context of the previous theorem) is approximated using Chebyshev polynomials which can be implemented using random walks.)
...(iv) applying quantum phase estimation using said unitary to the superposition of eigenvectors; (Dervovic, page 29, equation (69) and corresponding exposition.)
(v) applying the inverse of each eigenvalue of system matrix A to its corresponding eigenvector in the translated superposition; (Dervovic, pages 29-30, equation (70) and corresponding exposition. See also (72) where the result of applying this procedure to the full linear combination of eigenstates, rather than just the single eigenstate |uj), is shown.)
(vi) uncomputing by applying inverse phase estimation and eigenvector translation; and (Dervovic, page 30, equation (73) and corresponding exposition)
(vii) extracting the solution Ix) from a result of the previous steps. (Dervovic, page 30, paragraph following equation (73))
Dervovic does not appear to explicitly teach
a unitary comprising a quantum walk operator defined by reflections about a linear span defined from A;
However, Childs—directed to analogous art--teaches
a unitary comprising a quantum walk operator defined by reflections about a linear span defined from A; (Childs, page 584, last paragraph going onto page 585 describes defining the quantum walk operator based on reflections about the linear span {|ψj)} where |ψj) is defined based on the hermition matrix H as shown in equation (4).)
It would have been obvious to a person of ordinary skill in the art before the effective filing date of the claimed invention to have modified Dervovic by Childs because Dervovic writes on page 46: “A similar approach is possible using a decomposition of the function via Chebyshev polynomials [CKS17]. The benefit here is that the Chebyshev polynomials can be implemented via quantum walks, which was demonstrated by Childs [Chi10]. This leads to a slightly more efficient implementation of the operators, but requires explicit access to the entries of A.”
Regarding claim 2, the rejection of claim 1 is incorporated herein. Furthermore, Childs teaches
comprising the quantum walk operator containing a reflection operator defined as 2TT† - I, where application of T† and T performs projection onto a vector space. (Childs, page 585, equation (7) and corresponding exposition).
It would have been obvious to a person of ordinary skill in the art before the effective filing date of the claimed invention to have combined these references in this way for the same reasons given above with respect to claim 1.
Regarding claim 4, the rejection of claim 1 is incorporated herein. Furthermore, Childs teaches
further comprising defining the quantum walk operator by the expression W = iS(2TT† - I), where S is a register swap operation (Childs, page 585, equation (7) and page 584, last paragraph)
It would have been obvious to a person of ordinary skill in the art before the effective filing date of the claimed invention to have combined these references in this way for the same reasons given above with respect to claim 1.
Regarding claim 5, the rejection of claim 1 is incorporated herein. Furthermore, Dervovic teaches
subsequent to quantum phase estimation, extracting eigenvalues λj and applying ancilla rotation. (Page 30, Figure 5 and caption. See in particular sub-circuit b and accompanying description in the caption.)
Regarding claim 6, the rejection of claim 1 is incorporated herein. Furthermore, Dervovic teaches
initial translation of lb) to a superposition of eigenvectors of W by applying T, and performing uncomputation by applying T† . (Dervovic, page 30, figure 5, sub-circuit (a) shows applying U to the input register |b). The caption shows that this results in a superposition of eigenvectors of the unitary matrix U. This is uncomputed using U+ in the uncompute step (c). Note that in the combination with Childs described with respect to claim 1, the quantum walk operator taught by Childs would be used so that the superposition of eigenvectors of the unitary U would be a superposition of eigenvectors of the quantum walk operator.)
It would have been obvious to a person of ordinary skill in the art before the effective filing date of the claimed invention to have combined these references in this way for the same reasons given above with respect to claim 1.
Claim 7 is rejected under 35 U.S.C. 103 as being unpatentable over Dervovic (Quantum linear systems algorithms: a primer) in view of Childs (On the Relationship Between Continuous- and Discrete-Time Quantum Walk), further in view of Li (US 2024/0354360 A1).
Regarding claim 7, the rejection of claim 1 is incorporated herein. The combination of Dervovic and Childs does not appear to explicitly teach
further comprising preventing negative elements from appearing on the diagonal of system matrix A by adding a constant multiple of the identity matrix.
However, Li—directed to analogous art--teaches
further comprising preventing negative elements from appearing on the diagonal of system matrix A by adding a constant multiple of the identity matrix. (Li, [0087] describes preprocessing the linear system by applying a polynomial p to the matrix A. The genus of polynomial includes species which include constant terms and consequently, the preprocessing would result in adding a constant multiple of the identity matrix. This would in the ordinary course of operation be expected to at times achieve the statement of intended result of preventing negative elements from appearing on the diagonal of the matrix.)
It would have been obvious to a person of ordinary skill in the art before the effective filing date of the claimed invention to have modified Dervovic and Childs by Li because these techniques “can reduce the time, complexity and computation amount in solving linear problems and speed up solution of the quantum linear algorithm, while reducing occupation of hardware resources” (Li, [0087]).
Allowable Subject Matter
Claim 3 is not rejected under 35 USC 103.
Regarding claim 3, Dervovic in view of Childs does not appear to explicitly teach
PNG
media_image1.png
162
464
media_image1.png
Greyscale
Li (US 2024/0354360 A1) is believed to be the most pertinent prior art to this limitation. Li, [0189-0191] describes defining a quantum walk operator T to be used to solve a linear system using a Chebyshev polynomial approximation. The equations for T and |ψj) define a similar operator to the claimed operator T, though the notation differs somewhat. Note in particular that |k) and |k+N) could be written as |0)|k) and |1)|k) since these are binary representations and the order (e.g., |0)|k) versus |k)|0)) is a matter of notation. Note also that |ψj) includes the |j) term (corresponding to |j,0) in the claimed formula for T). However, Li does not teach the definition of T including the failure states as required by the claim and includes only half the number of terms in the claimed definition. Consequently, the definition of T taught by Li cannot be mapped to the claimed formula.
Note that the indication of allowable subject matter is dependent on the interpretation under 35 USC 112(b). If claim 3 were rolled up directly into claim 1 without further amendment, it would not appear to further limit the claim as it defines a symbol not actually used. Any amendment other than rolling up claims 3 and 2 into claim 1 would require further consideration to determine patentability over the prior art. Note also that the claims are rejected under 35 USC 101.
Conclusion
Harrow (Quantum Algorithm for Linear Systems of Equations) – provides the original presentation of the HHL algorithm upon which the other prior art is based.
Any inquiry concerning this communication or earlier communications from the examiner should be directed to Markus A Vasquez whose telephone number is (303)297-4432. The examiner can normally be reached Monday to Friday 9AM to 4PM PT.
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 Zhen can be reached on (571) 272-3768. 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.
/MARKUS A. VASQUEZ/ Primary Examiner, Art Unit 2121
Prosecution Insights