Quantum circuit optimization using windowed quantum arithmetic

1. A method for performing a product addition operation on a target quantum register of qubits and a source quantum register of qubits, the method comprising:

determining multiple entries of a lookup table, comprising, for each index in a first set of indices, wherein the first set of indices comprises index values between zero and a maximum index value that is a function of a predetermined window size, multiplying the index value by a scalar for the product addition operation;

for each index in a second set of indices, wherein the second set of indices comprises index values between zero and a maximum index value that is a function of the source quantum register, wherein the index values are stepped by the predetermined window size:

determining multiple address values, comprising extracting source register values corresponding to indices between i) the index in the second set of indices, and ii) the index in the second set of indices plus the predetermined window size; and

adjusting values of the target quantum register based on the determined multiple entries of the lookup table and the determined multiple address values.

2. The method of claim 1 , wherein the maximum index value that is a function of the predetermined window size is equal to 2 to the power of the predetermined window size.

3. The method of claim 1 , wherein the maximum index value that is a function of the source quantum register is equal to a length of the source register.

4. The method of claim 1 , wherein the predetermined window size comprises ln n, where n represents a number of logical qubits in the target quantum register.

5. The method of claim 1 , wherein adjusting values of the target quantum register based on the determined multiple entries of the lookup table and the determined multiple address values comprises adding the determined multiple entries into the target quantum register.

6. The method of claim 1 , wherein the product addition operation performs x+=ky, where x represents a variable storing a first value in the target quantum register, y represents a corresponding variable storing a second value in the source quantum register, k represents a classical constant scalar value for the product addition operation.

7. The method of claim 6 , wherein the target quantum register comprises a fixed width 2s complement register.

8. The method of claim 6 , wherein the first value comprises a classical integer or a superposition of classical integers.

9. The method of claim 6 , wherein the second value comprises a classical integer or a superposition of classical integers.

10. A method for performing a modular product addition operation using a target quantum register of qubits and a source quantum register of qubits, the method comprising:

for each index in a first set of indices, wherein the first set of indices comprises index values between zero and a maximum index value that is a function of the source quantum register, wherein the index values are stepped by a predetermined window size:

determining multiple address values, comprising extracting source register values corresponding to indices between i) the index in the first set of indices, and ii) the index in the first set of indices plus the predetermined window size;

determining multiple corresponding table entries, comprising, for each index in a second set of indices, wherein the second set of indices comprises index values between zero and a maximum table index that is a function of the predetermined window size:

determining a table entry comprising a product of i) a scalar in the product addition operation, ii) 2 to the power of the index in the first set of indices, and iii) the index in the second set of indices, and

applying a modulus operation to the determined table entry; and

adjusting values of the target quantum register based on the determined multiple table entries and the determined multiple address values.

11. The method of claim 10 , wherein the maximum index value that is a function of the source quantum register is equal to a length of the source quantum register.

12. The method of claim 10 , wherein the maximum table index that is a function of the predetermined window size is equal to 2 to the power of the predetermined window size.

13. The method of claim 10 , wherein the modular product addition operation performs x+=ky (mod N), where represents a variable storing a first value in the target quantum register, y represents a corresponding variable storing a second value in the source quantum register, k represents a classical constant scalar value for the modular product addition operation, and N represent a classical constant modulo for the modular product addition operation.

14. The method of claim 13 , wherein values of x, y and k are positive and less than N.

15. The method of claim 13 , wherein the first value comprises a classical integer or a superposition of classical integers.

16. The method of claim 13 , wherein the second value comprises a classical integer or a superposition of classical integers.

17. The method of claim 10 , wherein the predetermined window size comprises ln n, where n represents a number of logical qubits in the target quantum register.

18. The method of claim 10 , wherein adjusting values of the target quantum register based on the determined multiple table entries and the determined multiple address values comprises adding the determined multiple table entries into the target quantum register.

19. The method of claim 10 , further comprising performing a series of modular product addition operations to perform a modular multiplication operation.

20. A method for multiplying values of a target quantum register of qubits by an odd integer, the method comprising:

determining multiple lookup table entries, comprising, for each index in a first set of indices, wherein the first set of indices comprises index values between zero and a maximum table index that is a function of a predetermined window size:

determining a product of the index in the first set of indices and the odd integer;

for each index in a second set of indices, wherein the second set of indices comprises index values from a maximum index value that is a function of the target quantum register to zero, wherein the index values are stepped by a predetermined window size:

extracting multiple values of the target quantum register between the index in the second set of indices to the index in the second set of indices plus the predetermined window size; and

adjusting multiple values of the target quantum register based on the determined multiple lookup table entries and the extracted multiple values of the target quantum register, wherein the multiple values of the target quantum register comprise values between the index in the second set of indices plus the predetermined window size and an end of the target quantum register.

21. The method of claim 20 , wherein the maximum table index that is a function of the predetermined window size is equal to 2 to the power of the predetermined window size.

22. The method of claim 20 , wherein the maximum index value that is a function of the target quantum register is equal to a length of the target quantum register.

23. The method of claim 20 , wherein multiplying values of a target quantum register of qubits by an odd integer comprises performing x*=k, where x represents a variable storing a first value in the target quantum register and k represents the odd integer.

24. The method of claim 23 , wherein the first value comprises a classical integer or a superposition of classical integers.

25. The method of claim 20 , wherein the predetermined window size comprises ln n, where n represents a number of logical qubits in the target quantum register.

26. The method of claim 20 , wherein adjusting multiple values of the target quantum register based on the determined multiple lookup table entries and the extracted multiple values of the target quantum register comprises adding the determined multiple lookup table entries into the target quantum register.

27. An apparatus comprising:

one or more classical computing processors; and

quantum computing hardware in data communication with the one or more classical processors,

wherein the apparatus is configured to perform operations for performing a product addition operation on a target quantum register of qubits and a source quantum register of qubits, the operations comprising:

determining multiple entries of a lookup table, comprising, for each index in a first set of indices, wherein the first set of indices comprises index values between zero and a maximum index value that is a function of a predetermined window size, multiplying the index value by a scalar for the product addition operation;

for each index in a second set of indices, wherein the second set of indices comprises index values between zero and a maximum index value that is a function of the source quantum register, wherein the index values are stepped by the predetermined window size:

determining multiple address values, comprising extracting source register values corresponding to indices between i) the index in the second set of indices, and ii) the index in the second set of indices plus the predetermined window size; and

adjusting values of the target quantum register based on the determined multiple entries of the lookup table and the determined multiple address values.