Quantum circuit optimization using windowed quantum arithmetic
AssigneeGoogle Inc.
InventorCraig Gidney
Life of this patent
Estimating the term…
Abstract
Methods, systems and apparatus for performing windowed quantum arithmetic. In one aspect, a method for performing a product addition operation includes: determining multiple entries of a lookup table, comprising, for each index in a first set of indices, multiplying the index value by a scalar for the product addition operation; for each index in a second set of indices, 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 a target quantum register based on the determined multiple entries of the lookup table and the determined multiple address values.
Claims22
A method for performing a modular exponentiation 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,
- determining a first plurality of address values, comprising extracting multiple source register values;
- for each index in a second set of indices,
- determining a second plurality of address values, comprising extracting multiple target register values;
- for each index in a third set of indices and for each index in a fourth set of indices,
- determining a table entry by multiplying i) the index in the third set of indices, ii) the index in the fourth set of indices, and iii) 2 to the power of the index in the second set of indices, and applying a modulus operation;
- adjusting a modular addition register using table entries corresponding to the first plurality of address values and the second plurality of address values;
- for each index in a fifth set of indices,
- determining a third plurality of address values, comprising extracting multiple values of the adjusted modular addition register;
- determining, for each index in a sixth set of indices, multiple table entries, the determining comprising, for each index in a seventh set of indices,
- determining a table entry that corresponds to the index in the seventh set of indices by multiplying i) the index in the sixth set of indices, ii) the index in the seventh set of indices, and iii) 2 to the power of the index in the fifth set of indices, and applying a modulus operation;
- and
- adjusting the target quantum register using table entries corresponding to the first plurality of address values and the third plurality of address values.
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 modular exponentiation operation using a target quantum register of qubits and a source quantum register of qubits, the operations comprising:
- for each index in a first set of indices,
- determining a first plurality of address values, comprising extracting multiple source register values;
- for each index in a second set of indices,
- determining a second plurality of address values, comprising extracting multiple target register values;
- for each index in a third set of indices and for each index in a fourth set of indices,
- determining a table entry by multiplying i) the index in the third set of indices, ii) the index in the fourth set of indices, and iii) 2 to the power of the index in the second set of indices, and applying a modulus operation;
- adjusting a modular addition register using table entries corresponding to the first plurality of address values and the second plurality of address values;
- for each index in a fifth set of indices,
- determining a third plurality of address values, comprising extracting multiple values of the adjusted modular addition register;
- determining, for each index in a sixth set of indices, multiple table entries, the determining comprising, for each index in a seventh set of indices,
- determining a table entry that corresponds to the index in the seventh set of indices by multiplying i) the index in the sixth set of indices, ii) the index in the seventh set of indices, and iii) 2 to the power of the index in the fifth set of indices, and applying a modulus operation;
- and
- adjusting the target quantum register using table entries corresponding to the first plurality of address values and the third plurality of address values.
Dependencies are inferred from the claim text.