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.