Notice of Pre-AIA or AIA Status
1. The present application, filed on or after March 16, 2013, is being examined under the first inventor to file provisions of the AIA .
Claim Rejections - 35 USC § 112
2. 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.
3. Claims 3 and 13 are rejected under 35 U.S.C. 112(b) as being indefinite for failing to particularly point out and distinctly claim the subject matter which the inventor or a joint inventor regards as the invention.
Regarding the rejected claims mentioned just above, the claims recite, in part, some version of a limitation “wherein the conditioning circuit operates further on the one or more ancillas.” In rejecting the claims, the Examiner notes that the bolded term for “conditioning circuit” features improper antecedent basis, thereby rendering the claims vague and indefinite. Specifically, there is no prior mention to introduce a “conditioning circuit” in either claim 3 or 13, and that such a prior mention is also absent in claims 1 and 11 from which claims 3 and 13 depend.
Claim Rejections - 35 USC § 103
4. 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.
5. The factual inquiries for establishing a background for determining obviousness under 35 U.S.C. 103 are summarized as follows:
1. Determining the scope and contents of the prior art.
2. Ascertaining the differences between the prior art and the claims at issue.
3. Resolving the level of ordinary skill in the pertinent art.
4. Considering objective evidence present in the application indicating obviousness or nonobviousness.
6. Claims 1-6 and 11-16 are rejected under 35 U.S.C. 103 as being obvious over Applicants’ Admitted Prior Art (“AAPA”) in view of Non-Patent Literature “Lecture 22” (“Aaronson”).
Regarding claim 1, AAPA teaches A method comprising:
preparing, via a state preparation circuit, an n choose 1 state on n qubits ([0035] of Applicants’ published specification, discussing a prior art quantum circuit implementation of Grover’s algorithm to find a quantum solution for a function in a function domain of n and which may be applied to the problem of unstructured database search, e.g. for which the simple base case would be understood to be n choose 1, and where [0036] clarifies that for the function domain of n then n qubits are initialized and hence involved);
for each in a sequence of iterations, applying an oracle and diffuser circuit ... ([0036] further teaches the scheme or oracle calls and diffusion operations that are repeated (i.e., iterative)); and
applying a measurement to the n qubits ([0036] further clarifies that upon iterating, “A measurement of the qubits after this point yields the quantum solution with a probability that approaches 1 for large values of N.”).
AAPA does not teach the further limitations that:
the prepared state is actually an n choose k state on n qubits, and
the iterative applying of the oracle is with a microdiffuser circuit, wherein the microdiffuser circuit operates on a subset of n qubits of varying size over the sequence of iterations, and wherein for the jth iteration of the sequence of iterations, the microdiffuser circuit operates on a subset of n qubits of size mj.
Rather, the Examiner relies upon AARONSON to teach what AAPA otherwise lacks, see e.g., Aaronson:
Regarding preparation of a state for an n choose k state, Aaronson on the 9th and final page addresses “a different way to handle the case of multiple marked items”, e.g. as a modification of the more routine application of Grover’s algorithm to solve for unordered search (as discussed on the reference’s pages 1-2), where in this noted different way, Aaronson contemplates “supposed we have N items, k of which are marked”, which the Examiner equates with Applicants’ recitation for “n choose k state.”
Regarding the microdiffuser aspect, Aaronson, staying with the same discussion found on its 9th and final page, details that N/k items are chosen randomly to arrive at a subset for which Grover’s algorithm is applied, such that it would be understood that the oracle and diffuser aspects would be constrained to that subset, and hence the diffuser would be a “microdiffuser” directed to operation on just the subset of qubits, as Applicants have recited. The related discussion at the bottom of page 8 clarifies that as k increments with each iteration, then it reasons that N/k changes to assume a different fraction representing a different sample size of qubits (i.e., as recited: “a subset of n qubits of varying size over the sequence of iterations”).
Both AAPA and Aaronson relate to quantum circuits that can be implemented to apply Grover’s Algorithm to provide a quantum solution to a problem. Hence, they are similarly directed and therefore analogous. The Examiner understands Aaronson to use the same/similar features detailed in Applicants’ specification regarding the prior art, but for a slightly modified problem, e.g. where the assumption of marked items in a search is greater than 1. Hence, it would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to incorporate the AAPA framework and infrastructure elements to be configured for use in a revised manner to address the revised task, as Aaronson does.
Regarding claim 2, AAPA in view of Aaronson teaches the method of claim 1, as discussed above. The aforementioned references teach the additional limitation wherein the microdiffuser circuit operates on the subset of n qubits of size mj (discussed above in relation to claim 1) and further on one or more ancillas (Aaronson’s 4th page, near the bottom: “So in the Hadamard basis, if you think about it, what we want is to perform the diagonal matrix A on the right. This A is easy to implement as a quantum circuit, by using some ancilla qubits to check whether the input is all 0’s, inverting the phase if not ...”). The motivation for combining the references is as discussed above in relation to claim 1.
Regarding claim 3, AAPA in view of Aaronson teaches the method of claim 2, as discussed above. The aforementioned references teach the additional limitation wherein the conditioning circuit operates further on the one or more ancillas (see above per claim 2, Aaronson at the bottom of its 4th page). The motivation for combining the references is as discussed above in relation to claim 1.
Regarding claim 4, AAPA in view of Aaronson teaches the method of claim 1, as discussed above. The aforementioned references teach the additional limitation wherein the measurement of the n qubits generates a search result that resolves an n-bit word by determining k bits of the n-bit word that are ON and n-k bits of the n-bit word that are OFF (Aaronson’s pages 1-2 discussing the search task that is performed using the quantum solution as described, where the measurement reveals the marked item that is searched for and found, and further on its page 9, it discusses an extension of the framework to the n choose k version of the same problem, where k such bits are determined, and where the existence of an item is a 1 and otherwise a 0, as discussed on Aaronson’s 1st page with respect to its oracle function). The motivation for combining the references is as discussed above in relation to claim 1.
Regarding claim 5, AAPA in view of Aaronson teaches the method of claim 1, as discussed above. The aforementioned references teach the additional limitation further comprising: conditioning the n qubits based on a randomization (Aaronson’s 9th page, again addressing the n choose k problem: “... we pick N/k items uniformly at random, and then run Grover’s algorithm on that subset only ... If we don’t find a marked item, we can try again with a new random subset.”). The motivation for combining the references is as discussed above in relation to claim 1.
Regarding claim 6, AAPA in view of Aaronson teaches the method of claim 5, as discussed above. The aforementioned references teach the additional limitation wherein the randomization is one of:
a randomization of an ordering of the n qubits; or a randomization of a grouping of the n qubits (see above per claim 5, Aaronson’s 9th page where the random aspect relates to a selection of qubits, i.e., a random grouping). The motivation for combining the references is as discussed above in relation to claim 1.
Regarding claim 11, the claim includes the same or similar limitations as claim 1 discussed above, and is therefore rejected under the same rationale. The claim is directed to a quantum circuit featuring a state preparation circuit, an oracle, and a microdiffuser circuit, which the Examiner believes are disclosed in [0035]-[0036] of Applicants’ published specification where a prior art example is detailed.
Regarding claim 12, the claim includes the same or similar limitations as claim 2 discussed above, and is therefore rejected under the same rationale.
Regarding claim 13, the claim includes the same or similar limitations as claim 3 discussed above, and is therefore rejected under the same rationale.
Regarding claim 14, the claim includes the same or similar limitations as claim 4 discussed above, and is therefore rejected under the same rationale.
Regarding claim 15, the claim includes the same or similar limitations as claim 5 discussed above, and is therefore rejected under the same rationale.
Regarding claim 16, the claim includes the same or similar limitations as claim 6 discussed above, and is therefore rejected under the same rationale.
7. Claims 7-10 and 17-20 are rejected under 35 U.S.C. 103 as being unpatentable over AAPA in view of Aaronson and further in view of Non-Patent Literature “A divide-and-conquer algorithm for quantum state preparation” (“Araujo”).
Regarding claim 7, AAPA in view of Aaronson teach the method of claim 1, as discussed above. The Examiner reasons that AAPA and Aaronson, with their teachings of iterative application of Grover’s Algorithm to arrive at quantum solutions, necessarily requires/involves logic that is akin to counter logic to manage the iterative looping as taught, i.e., the further limitations wherein the state preparation circuit operates on n data qubits (data0 . . . datan−1) and k+1 counter qubits (ctr0 . . . ctrk), where n>1 and n≥k, and wherein the state preparation circuit includes:
an auxiliary quantum circuit, Ck n, that operates on the n data qubits (data0 . . . datan−1) and the k+1 counter qubits (ctr0 . . . ctrk).
However, the aforementioned references are silent as to the further limitation for an X gate applied to ctrk, as the reference does not go into that level of detail. Rather, the Examiner relies upon ARAUJO to teach what AAPA etc. otherwise lack, see e.g., Araujo’s comparable state preparation framework, as established on pages 1-3 discussing features for loading data in a divide and conquer approach that is comparable to Aaronson’s subset operation, and specifically see page 6’s discussion (under the heading “Orthonormal ancillary”) of CNOT gates (which the Examiner equates with the recited X gate).
Both AAPA and Aaronson relate to quantum circuits that can be implemented to apply Grover’s Algorithm to provide a quantum solution to a problem. Araujo is similarly directed and therefore analogous. It would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to incorporate algorithms and quantum gate logic and related features, as taught by Araujo in greater and more granular detail, to concretely implement the n choose k approach taught by Aaronson at a more high level, as the Examiner has discussed in relation to claim 1, with a reasonable expectation of success.
Regarding claim 8, AAPA in view of Aaronson and further in view of Araujo teach the method of claim 7, as discussed above. The aforementioned references teach the additional limitations wherein the auxiliary quantum circuit Ck n, is generated by: providing an auxiliary quantum circuit C1 1;
recursively constructing Ck n by:
for j=1 . . . k, applying an
RY(2arccos square root of (n-j)/n)
gate on data0 controlled on the jth of the k+1 counter qubits;
controlled on data0, decrement the counter register; and
apply Cmin(n−1,k) n−1 on qubits data0 . . . datan−1, and ctr0 . . . ctrmin(n−1,k).
See for example, Araujo’s Algorithms 2-3, beginning on its page 5.
The motivation for combining the references is as discussed above in relation to claim 7.
Regarding claim 9, AAPA in view of Aaronson teach the method of claim 1, as discussed above. The Examiner reasons that AAPA and Aaronson, with their teachings of iterative application of Grover’s Algorithm to arrive at quantum solutions, necessarily requires/involves logic that is akin to counter logic to manage the iterative looping as taught, i.e., the further limitations wherein the microdiffuser circuit is a microdiffuser circuit, Gk,m n, that operates on m data qubits and j1+1 ancillas, where n> m and j1=min(m,k), and wherein the microdiffuser circuit comprises:
a first auxiliary quantum circuit, (Cj1 m)† that operates on the m data qubits (data0 . . . datan−1) and the j1+1 ancillas.
However, the aforementioned references are silent as to the further limitations for a first plurality of X gates applied to the m data qubits after operation of the first auxiliary quantum circuit and a controlled Z gate applied to one of the m data qubits and controlled by m−1 remaining data qubits after operation of the first plurality of X gates, as the reference does not go into that level of detail. Rather, the Examiner relies upon ARAUJO to teach what AAPA etc. otherwise lack, see e.g., Araujo’s comparable state preparation framework, as established on pages 1-3 discussing features for loading data in a divide and conquer approach that is comparable to Aaronson’s subset operation, and specifically see page 6’s discussion (under the heading “Orthonormal ancillary”) of CNOT gates (which the Examiner equates with the recited X gate).
Both AAPA and Aaronson relate to quantum circuits that can be implemented to apply Grover’s Algorithm to provide a quantum solution to a problem. Araujo is similarly directed and therefore analogous. It would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to incorporate algorithms and quantum gate logic and related features, as taught by Araujo in greater and more granular detail, to concretely implement the n choose k approach taught by Aaronson at a more high level, as the Examiner has discussed in relation to claim 1, with a reasonable expectation of success.
Regarding claim 10, AAPA in view of Aaronson and further in view of Araujo teach the method of claim 9, as discussed above. The aforementioned references teach the additional limitations wherein the microdiffuser circuit, Gk,m n, further includes:
a second plurality of X gates applied to the m data qubits after operation of the controlled Z gate; and
a second auxiliary quantum circuit, (Cj1 m) that operates on the m data qubits (data0 . . . datan−1) after operation of the second plurality of X gates and the j1+1 ancillas after operation of the first auxiliary quantum circuit.
See for example, Araujo’s Algorithms 2-3, beginning on its page 5.
The motivation for combining the references is as discussed above in relation to claim 9.
Regarding claim 17, the claim includes the same or similar limitations as claim 7 discussed above, and is therefore rejected under the same rationale.
Regarding claim 18, the claim includes the same or similar limitations as claim 8 discussed above, and is therefore rejected under the same rationale.
Regarding claim 19, the claim includes the same or similar limitations as claim 9 discussed above, and is therefore rejected under the same rationale.
Regarding claim 20, the claim includes the same or similar limitations as claim 10 discussed above, and is therefore rejected under the same rationale.
Claim Objections
8. Claims 9 and 19 are objected to because of the following informalities: neither claim terminates properly with a period. Claim 9 ends with a semi-colon where a period should be. Claim 19 appears to end with a ‘1’ where a period should be. Appropriate correction is required.
Conclusion
9. The prior art made of record and not relied upon is considered pertinent to Applicants’ disclosure:
US 20060224547 A1- Ulyanov
US 20050167658 A1- Williams
US 20200272930 A1- Aspuru-Guzik
US 11895232 B1- Stapleton
US 20220414508 A1- Shyamsundar
US 20200394537 A1- Wang
US 20200272910 A1- Kapit
US 20220383180 A1- Castrillo
Non-Patent Literature “Variational learning of Grover’s quantum search algorithm” (“Morales”)
Non-Patent Literature “Subdivided Phase Oracle for NISQ Search Algorithms” (“Satoh”)
Non-Patent Literature “Automatic Generation of Grover Quantum Oracles for Arbitrary Data Structures” (“Seidel”)
Non-Patent Literature “Simple Algorithm for Partial Quantum Search” (“Korepin”)
Non-Patent Literature “Modification of the quantum grover algorithm by using the inversion method around the middle” (“Cherckesova”)
Non-Patent Literature “A Review on Quantum Search Algorithms” (“Giri”)
Non-Patent Literature “Implementing Grover’s Algorithm on the IBM Quantum Computers” (“Mandviwalla”)
Non-Patent Literature “Lecture 4: Grover's Algorithm” (“Wright”)
Non-Patent Literature “Grover’s Algorithm — Mathematics, Circuits, and Code: Quantum Algorithms Untangled” (“Biswas”)
Non-Patent Literature “Complete 3-Qubit Grover search on a programmable quantum computer” (“Figgatt”)
10. Any inquiry concerning this communication or earlier communications from the examiner should be directed to SHOURJO DASGUPTA whose telephone number is (571)272-7207. The examiner can normally be reached M-F 8am-5pm CST.
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, Tamara Kyle can be reached at 571 272 4241. 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.
/SHOURJO DASGUPTA/Primary Examiner, Art Unit 2144