Patent Description:
Classical computers have memories made up of bits, where each bit can represent either a zero or a one. Quantum computers maintain sequences of quantum bits, called qubits, where each quantum bit can represent a zero, one or any quantum superposition of zeros and ones. Quantum computers operate by setting qubits in an initial state and controlling the qubits, e.g., according to a sequence of quantum logic gates.

"<NPL>) discloses that it is possible to reduce the number of quantum modular multiplications necessary for Shor's algorithm by a factor of w, at a cost of adding temporary storage space and associated machinery for a table of 2w entries, and performing 2w times as many classical modular multiplications. The storage space may be a quantum-addressable classical memory, or pure quantum memory. With classical computation as much as <NUM> times as fast as quantum computation, values of w from <NUM> to <NUM> seem attractive; physically feasible values depend on the implementation of the memory.

This specification describes techniques for accelerating quantum computations using windowed quantum arithmetic.

In classical computing, operation counts can be reduced by merging operations together using lookup tables. For example, fast software implementations of cyclic redundancy check parity check codes process multiple bits at a time using precomputed tables. These techniques are known as "windowing.

This specification describes windowing in quantum computing. In particular, techniques for reducing operation counts in quantum computing by merging multiple controlled operations into a single operation acting on a value produced by a QROM (quantum read only memory) lookup (referred to herein as a "table lookup") are described.

A table lookup is an operation that retrieves data from a classical table addressed by a quantum register. It performs the operation <MAT> where T represents a classically precomputed table with L entries. <FIG> is a quantum circuit diagram of an example quantum circuit <NUM> for performing a table lookup with a Toffoli count of L - <NUM> (independent of the number of bits in each entry. ) In <FIG>, the perpendicular lines merging from and merging into other lines to form corners, e.g., merging lines <NUM>, are AND computations and uncomputations, respectively, and are equivalent to Toffoli gates. If the control qubit <NUM> is set and the address register <NUM> contains the binary value a, the example quantum circuit <NUM> xors the a-th bit string from a precomputed lookup table T into W output qubits. In the example quantum circuit <NUM>, L = <NUM> and W = <NUM>. The question marks beside the CNOT targets indicate that the target should be omitted or included depending on a corresponding bit in T. Using known techniques (e.g., techniques different to those described in this specification), it is possible to compute a table lookup in O(WL/k + k) Toffolis, where W represents the output size of the lookup and k represents a freely chosen parameter.

<FIG> depicts a quantum computation system <NUM>. The system <NUM> is implemented as quantum and classical computer programs on one or more quantum computing devices and classical computers in one or more locations, in which the systems, components, and techniques described below can be implemented.

The system <NUM> includes a quantum computing device <NUM> in data communication with one or more classical processors <NUM>. For convenience, the quantum computing device <NUM> and classical processors <NUM> are illustrated as separate entities, however in some implementations the classical processors <NUM> may be included in the quantum computing device <NUM>.

The quantum computing device <NUM> includes components for performing quantum computation. For example, the quantum computing device <NUM> includes quantum circuitry <NUM> and control devices <NUM>.

The quantum circuitry <NUM> includes components for performing quantum computations, e.g., components for implementing the various quantum circuits and operations described in this specification. The quantum circuitry includes a quantum system that includes one or more qubits <NUM>. The qubits <NUM> are physical qubits that may be used to perform algorithmic operations or quantum computations. The specific realization of the one or more qubits and their interactions may depend on a variety of factors including the type of quantum computations that the quantum computing device <NUM> is performing. For example, the qubits may include qubits that are realized via atomic, molecular or solid-state quantum systems. In other examples the qubits may include, but are not limited to, superconducting qubits, e.g., Gmon or Xmon qubits, or semi-conducting qubits. Further examples of realizations of multi-level quantum subsystems include fluxmon qubits, silicon quantum dots or phosphorus impurity qubits. In some cases the quantum circuitry may further include one or more resonators attached to one or more superconducting qubits. In other cases ion traps, photonic devices or superconducting cavities (with which states may be prepared without requiring qubits) may be used.

In this specification, the term "quantum circuit" is used to refer to a sequence of quantum logic operations that can be applied to a qubit register to perform a respective computation. Quantum circuits comprising different quantum logic operations, e.g., single qubit gates, multi-qubit gates, etc., may be constructed using the quantum circuitry <NUM>. Constructed quantum circuits can be operated/implemented using the control devices <NUM>.

The type of control devices <NUM> included in the quantum system depend on the type of qubits included in the quantum computing device. For example, in some cases the multiple qubits can be frequency tunable. That is, each qubit may have associated operating frequencies that can be adjusted using one or more control devices. Example operating frequencies include qubit idling frequencies, qubit interaction frequencies, and qubit readout frequencies. Different frequencies correspond to different operations that the qubit can perform. For example, setting the operating frequency to a corresponding idling frequency may put the qubit into a state where it does not strongly interact with other qubits, and where it may be used to perform single-qubit operations/gates. In these examples the control devices <NUM> may include devices that control the frequencies of qubits included in the quantum circuitry <NUM>, an excitation pulse generator and control lines that couple the qubits to the excitation pulse generator. The control devices may then cause the frequency of each qubit to be adjusted towards or away from a quantum gate frequency of an excitation pulse on a corresponding control driveline.

The control devices <NUM> may further include measurement devices, e.g., readout resonators. Measurement results obtained via measurement devices may be provided to the classical processors <NUM> for processing and analyzing. Measurement devices perform physical measurements on properties of the qubits, either directly or indirectly, from which the state(s) of the qubits can be inferred.

<FIG> is a flow diagram of a process <NUM> for performing a product addition operation on a target quantum register of qubits and a source quantum register of qubits. For convenience, the process <NUM> will be described as being performed by a system of one or more classical and quantum computing devices located in one or more locations. For example, a quantum computation system, e.g., the system <NUM> of <FIG>, appropriately programmed in accordance with this specification, can perform the process <NUM>.

The product addition operation performed by example process <NUM> can be given by x = x + ky (or equivalently 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, and k represents a (classical) constant scalar value for the product addition operation. The first value and second value are quantum integers. In this specification, a quantum integer refers to a classical integer or a superposition of classical integers stored by a quantum register, e.g., as a sequence of qubits using <NUM> complement little endian format.

The system determines multiple entries of a lookup table (step <NUM>). For each index in a first set of indices, where the first set of indices includes index values between zero and a maximum index value that is a function of a predetermined window size, the system multiplies the index value by a scalar for the product addition operation. The maximum index value that is a function of the predetermined window size is equal to <NUM> to the power of the predetermined window size.

In some implementations the system can determine the entries of the lookup table using classical computation, e.g., classically performed multiplications. The lookup table defined by the determined entries can then be stored in classical memory of the system.

For each index in a second set of indices, the system determines multiple address values (step <NUM>) and adjusts values of the target quantum register based on the determined multiple entries of the lookup table and the determined multiple address values (step <NUM>). The second set of indices includes index values between zero and a maximum index value that is a function of the source quantum register and where the index values are stepped by the predetermined window size. The maximum index value that is a function of the source quantum register can be equal to the length of the source quantum register.

To determine the multiple address values, the system extracts source quantum 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. The system sets the multiple address values equal to respective extracted source quantum register values. Extracting the source quantum register values is a quantum computation performed by quantum computing devices based on quantum unitary operations/quantum gates (excluding measurements).

To adjust values of the target quantum register based on the determined multiple entries of the lookup table and the determined multiple address values, the system identifies table entries (determined at step <NUM>) that correspond to the address values (determined at step <NUM>). In some implementations the system may store the identified table entries in a temporary quantum register. The system uses the identified table entries to adjust a subset of entries of the target quantum register. The subset of entries correspond to entries including and after the current index from the second set of indices. To adjust the subset of entries of the target quantum register, the system adds the identified table entries into the target quantum register. For example, the system can perform a quantum addition computation using quantum computing devices, e.g., by applying a quantum addition circuit to the target quantum register and the temporary quantum register. The quantum addition circuit may include a sequence of quantum logic gates that implement an addition operation.

The windowed implementation of product addition described by example process <NUM> has an asymptotic Toffoli count of <MAT> where w represents the predetermined window size. The predetermined window size equals log<NUM> n, where n represents a number of logical qubits in the target quantum register. In these implementations the table lookup is as expensive as the addition, achieves a Toffoli count of O(n<NUM>/lg n).

<FIG> shows a snippet <NUM> of executable python <NUM> code for performing a product addition operation on a target quantum register of qubits and a source quantum register of qubits. In the code snippets described in this specification, quantum operations are specified in the same way as classical operations. The code interpreter must then decompose high level quantum arithmetic into corresponding low level quantum operations. For example, when a, b are variables holding quantum integers, the statement a+= b applies a quantum addition circuit to a and b. If b is a classical integer, then b is treated as a temporary expression (an rvalue) that must be loaded into a quantum register so that a quantum addition circuit using the classical integer can be applied. There are other kinds of rvalues that can be temporarily loaded into a register in order to add them into a target. Indexing a lookup table with a quantum integer produces a lookup rvalue and so the statement a += T[b] results in the following three actions: compute a table lookup with classical data T and quantum address b into a temporary register, then add the temporary register into a, then uncompute the table lookup.

Section <NUM> of the snippet <NUM> defines the product addition operation "plus _equal_product", where "target" represents the target quantum register, "Quint" represents a quantum integer, "k" represents the constant scalar value for the product addition operation, "int" represents a classical integer, "y" represents the source quantum register, "window" represents the predetermined window size.

Section <NUM> of the snippet <NUM> corresponds to step <NUM> of example process <NUM>. For each index i in a first set of indices that ranges from zero to <NUM>window, a respective table entry value i * k is computed. Section <NUM> of the snippet <NUM> corresponds to step <NUM> of example process <NUM>. For each index i in a second set of indices that ranges from <NUM> to the length of the source quantum register len(y) stepped by the window size, values within a corresponding segment of the target register are adjusted based on values in a corresponding set of the computed table entries, where the size of the set equals the predetermined window size.

<FIG> is a flow diagram of an example process <NUM> for multiplying values of a target quantum register of qubits by an odd integer. For convenience, the process <NUM> will be described as being performed by a system of one or more classical and quantum computing devices located in one or more locations. For example, a quantum computation system, e.g., the system <NUM> of <FIG>, appropriately programmed in accordance with this specification, can perform the process <NUM>.

The multiplication operation performed by example process <NUM> can be given by x *= k, where x represents a variable storing a first value in the target quantum register and k represents an odd integer. The first value is a quantum integer, as defined above with reference to example process <NUM>.

The system determines multiple entries of a lookup table (step <NUM>). For each index in a first set of indices, where the first set of indices includes index values between zero and a maximum table index that is a function of a predetermined window size, the system determines a product of the index in the first set of indices and the odd integer. The maximum table index that is a function of the predetermined window size is equal to <NUM> to the power of the predetermined window size.

For each index in a second set of indices, the system extracts multiple values of the target quantum register (step <NUM>) and adjusts 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 (step <NUM>). The second set of indices includes index values from a maximum index value that is a function of the target quantum register to zero, where the index values are stepped by a predetermined window size. The maximum index value that is a function of the target quantum register can equal to the length of the target quantum register.

To extract multiple values of the target quantum register, the system extracts values between the index in the second set of indices to the index in the second set of indices plus the predetermined window size. Extracting the target quantum register values is a quantum computation performed by quantum computing devices.

To adjust values of the target quantum register based on the determined multiple entries of the lookup table and the extracted multiple address values, the system identifies table entries (determined at step <NUM>) that correspond to the address values (determined at step <NUM>). In some implementations the system may store the identified table entries in a temporary quantum register. The system uses the identified table entries to adjust a subset of entries of the target quantum register. The subset of entries correspond to entries including and after the current index from the second set of indices plus the window size. To adjust the subset of entries of the target quantum register, the system adds the identified table entries into the target quantum register. For example, the system can perform a quantum addition computation using quantum computing devices, e.g., by applying a quantum addition circuit to the target quantum register and the temporary quantum register. The quantum addition circuit may include a sequence of quantum logic gates that implement an addition operation.

The windowed multiplication described by example process <NUM> has Toffoli count of <MAT> where w represents the predetermined window size. The predetermined window size equals log<NUM> n, where n represents a number of logical qubits in the target quantum register. In these implementations the Toffoli count is O(n<NUM>/lg n).

<FIG> shows a snippet <NUM> of executable python <NUM> code for multiplying values of a target quantum register of qubits by an odd integer.

Section <NUM> of the snippet <NUM> defines the multiplication operation. As in snippet <NUM>, "target" represents the target quantum register, "Quint" represents a quantum integer, " k" represents a constant scalar value for the multiplication operation, "int" represents a classical integer, and "window" represents the predetermined window size.

Section <NUM> of the snippet <NUM> defines an optional routine for normalizing the scalar value k. Section <NUM> of the snippet <NUM> corresponds to step <NUM> of example process <NUM>. Section <NUM> of the snippet <NUM> corresponds to steps <NUM> and <NUM> of example process <NUM>. Section <NUM> of the snippet <NUM> defines a routine for fixing up the window, e.g., to complete the multiplication operation for all target register entries previously not operated on during section <NUM>.

<FIG> is a flow diagram of an example process <NUM> for performing a modular product addition operation using a target quantum register of qubits and a source quantum register of qubits. For convenience, the process <NUM> will be described as being performed by a system of one or more classical and quantum computing devices located in one or more locations. For example, a quantum computation system, e.g., the system <NUM> of <FIG>, appropriately programmed in accordance with this specification, can perform the process <NUM>.

The modular product addition operation performed by example process <NUM> can be given by x+= ky (mod N), 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 modular product addition operation, and N represent a classical constant modulo for the modular product addition operation. In some implementations values of x, y and k are positive and less than N. As described above with reference to <FIG>, the first value and the second value can be quantum integers.

For each index in a first set of indices, the system determines multiple address values (step <NUM>) and determines multiple table entries (step <NUM>). The first set of indices includes index values between zero and a maximum index value that is a function of the source quantum register, where the index values are stepped by a predetermined window size. The maximum index value that is a function of the source quantum register can be equal to the length of the source quantum register.

To determine the multiple address values, the system extracts source quantum 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. The system sets the multiple address values as equal to respective extracted source quantum register values. Extracting the source quantum register values is a quantum computation performed by quantum computing devices.

To determine the multiple table entries, the system determines, for each index in a second set of indices, a table entry given by a product of i) a scalar in the product addition operation, ii) <NUM> to the power of the index in the first set of indices, and iii) the index in the second set of indices, then applies a modulus operation corresponding to the modular product addition operation to the determined table entry. The second set of indices includes index values between zero and a maximum table index that is a function of the predetermined window size, e.g., <NUM> to the power of the predetermined window size. In some implementations the system can determine the entries of the table using classical computation, e.g., classically performed multiplications. The table defined by the determined entries can then be stored in classical memory of the system.

The system then adjusts values of the target quantum register based on the determined multiple table entries and the determined multiple address values (step <NUM>), e.g., using table entries corresponding to the determined address values. In some implementations the system may store the table entries corresponding to the determined address values in a temporary quantum register. The system uses the table entries to adjust entries of the target quantum register. To adjust the entries of the target quantum register, the system adds the determined table entries into the target quantum register. For example, the system can perform a quantum addition computation using quantum computing devices, e.g., by applying a quantum addition circuit to the target quantum register and the temporary quantum register. The quantum addition circuit may include a sequence of quantum logic gates that implement an addition operation.

The windowed modular product addition described by example process <NUM> has Toffoli count of <MAT> where w represents the predetermined window size. In some implementations the predetermined window size can equal ln n, where n represents a number of logical qubits in the target quantum register. In these implementations the Toffoli count is O(n<NUM>/lg n).

A series of modular product additions can be performed to perform a modular multiplication operation x *= k (mod N) where k has a multiplicative inverse modulo N and both are classical constants.

<FIG> shows a snippet <NUM> of executable python <NUM> code for performing a modular product addition operation. Section <NUM> of the snippet <NUM> defines the modular product addition operation "plus_equal_product_mod", where "target" represents the target quantum register, "Quint" represents a quantum integer, "QuintMod" represents a quantum integer associated with a modulus, " k" represents the constant scalar value for the modular product addition operation, "int" represents a classical integer, "y" represents the source quantum register, and "window" represents the predetermined window size.

Section <NUM> of the snippet <NUM> corresponds to step <NUM> of example process <NUM>. Section <NUM> of snippet <NUM> corresponds to step <NUM> of example process <NUM>. Section <NUM> of snippet <NUM> corresponds to step <NUM> of example process <NUM>.

<FIG> is a flow diagram of an example process <NUM> for performing a modular exponentiation operation using a target quantum register of qubits and a source quantum register of qubits. For convenience, the process <NUM> will be described as being performed by a system of one or more classical and quantum computing devices located in one or more locations. For example, a quantum computation system, e.g., the system <NUM> of <FIG>, appropriately programmed in accordance with this specification, can perform the process <NUM>.

The modular exponentiation operation performed by example process <NUM> can be given by x *= ke (mod N), where x represents a variable storing a first value in the target quantum register, e represents a corresponding variable storing a second value in the source quantum register, k represents a classical constant scalar value for the modular exponentiation operation, and N represent a classical constant modulo for the modular exponentiation operation. The first value can be a classical integer or a superposition of classical integers. The second value can be a classical integer or a superposition of classical integers.

For each index in a first set of indices, where the first set of indices includes index values between zero and a first maximum index value that is a function of the source quantum register, e.g., equal to the length of the source quantum register, and where the index values are stepped by a first predetermined window size, the system performs steps <NUM>-<NUM>.

The system determines a first number of address values by extracting source quantum 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 first predetermined window size (step <NUM>). Extracting the source quantum register values is a quantum computation performed by quantum computing devices.

For each index in a second set of indices, where the second set of indices includes index values between zero and a second maximum index value that is a function of the target register, e.g., equal to the length of the target quantum register, and where the index values are stepped by a second predetermined window size, the system performs steps <NUM>, <NUM>, <NUM>.

The system determines a second number of address values by extracting target 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 second predetermined window size (step <NUM>). Extracting the target quantum register values is a quantum computation performed by quantum computing devices.

For each index in a third set of indices, where the third set of indices includes index values between <NUM> and a third maximum value that is based on the first predetermined window size, e.g., k<NUM>i+w<NUM> where k represents a scalar for the modular exponentiation operation, i represents the index in the first set of indices, and w<NUM> represents the first predetermined window size, the system performs step <NUM>.

For each index in a fourth set of indices, where the fourth set of indices includes index values between <NUM> and a fourth maximum value that is a function of the target quantum register and the second predetermined window size, e.g., <NUM> to the power of the second window size, the system determines 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) <NUM> to the power of the index in the second set of indices, and applying a modulus operation (step <NUM>). In some implementations the system can determine entries of the table using classical computation, e.g., classically performed multiplications. The table defined by the determined entries can then be stored in classical memory of the system.

The system adjusts a modular addition register of qubits using table entries corresponding to the first number of address values and the second number of address values (step <NUM>). For example, the system can perform a quantum addition computation using quantum computing devices, e.g., by applying a quantum addition circuit to the modular addition register and a temporary quantum register storing table entries corresponding to the first number of address values and the second number of address values. The quantum addition circuit may include a sequence of quantum logic gates that implement an addition operation.

For each index in a fifth set of indices, where the fifth set of indices includes index values between zero and a fifth maximum index value that is a function of the target register, e.g., equal to the length of the target quantum register, and where the index values are stepped by the second predetermined window size, the system performs steps <NUM>-<NUM>.

The system determines a third number of address values by extracting values of the adjusted modular addition register corresponding to indices between i) the index in the fifth set of indices, and ii) the index in the fifth set of indices plus the second predetermined window size (step <NUM>). Extracting the values is a quantum computation performed by quantum computing devices.

For each index in a sixth set of indices, where the sixth set of indices includes index values between <NUM> and a sixth value that is based on the second predetermined window size, the system performs step <NUM>.

For each index in a seventh set of indices, where the seventh set of indices includes index values between <NUM> and a seventh maximum value that is a function of the modular addition register and the second predetermined window size, e.g., equal to <NUM> to the power of the second window size, the system determines a table entry by multiplying i) the index in the sixth set of indices, ii) the index in the seventh set of indices, and iii) <NUM> to the power of the index in the fifth set of indices, and applying a modulus operation (step <NUM>).

The system adjusts (e.g., through subtraction) the target quantum register using table entries corresponding to the first number of address values and the third number of address values (step <NUM>).

The windowed modular exponentiation described by example process <NUM> has Toffoli count of <MAT> where ne represents the number of exponent qubits, n represents the register size, we represents the exponent windowing size (the first predetermined window size), and wm represents the multiplication windowing (the second predetermined window size). In some implementations the first predetermined window size and the second window size can be equal. For example, the first predetermined window size and second predetermined window size can both be equal to ln n /<NUM>, where n represents a number of logical qubits in the target quantum register. These window sizes produce a Toffoli count of <MAT> which saves two log factors over known, alternative algorithms.

<FIG> shows a snippet <NUM> of executable python <NUM> code for performing a modular exponentiation operation. Section <NUM> of the snippet <NUM> defines the modular exponentiation operation "times_equal_exp_mod", where "target" represents the target quantum register, "Quint" represents a quantum integer, "QuintMod" represents a quantum integer associated with a modulus, " k" represents the constant scalar value for the modular exponentiation operation, "int" represents a classical integer, "e" represents the source quantum register, "e_window" represents the first predetermined window size and "m_window" represents the second predetermined window size.

Section <NUM> of the snippet <NUM> corresponds to the first set of indices. Section <NUM> corresponds to step <NUM> of example process <NUM>. Section <NUM> corresponds to the second set of indices. Section <NUM> corresponds to step <NUM> of example process <NUM>. Section <NUM> corresponds to the third, fourth sets of indices and step <NUM> of example process <NUM>. Section <NUM> corresponds to step <NUM> of example process <NUM>.

Section <NUM> of the snippet <NUM> corresponds to the fifth set of indices. Section <NUM> corresponds to step <NUM> of example process <NUM>. Section <NUM> corresponds to the sixth, seventh set of indices and step <NUM> of example process <NUM>. Section <NUM> corresponds to step <NUM> of example process <NUM>. Sections <NUM> and <NUM> are optional routines for a relabeling swap and Xoring a swap result into a correct register.

Implementations of the digital and/or quantum subject matter and the digital functional operations and quantum operations described in this specification and appendix can be implemented in digital electronic circuitry, suitable quantum circuitry or, more generally, quantum computational systems, in tangibly-embodied digital and/or quantum computer software or firmware, in digital and/or quantum computer hardware, including the structures disclosed in this specification and their structural equivalents, or in combinations of one or more of them. Quantum computation systems in general and quantum computers specifically may be realized or based on different quantum computational models and architectures. For example, the quantum computation system may be based on or described by models such as the quantum circuit model, one-way quantum computation, adiabatic quantum computation, holonomic quantum computation, analog quantum computation, digital quantum computation, or topological quantum computation.

Implementations of the digital and/or quantum subject matter described in this specification can be implemented as one or more digital and/or quantum computer programs, i.e., one or more modules of digital and/or quantum computer program instructions encoded on a tangible non-transitory storage medium for execution by, or to control the operation of, data processing apparatus. The digital and/or quantum computer storage medium can be a machine-readable storage device, a machine-readable storage substrate, a random or serial access memory device, one or more qubits, or a combination of one or more of them. Alternatively or in addition, the program instructions can be encoded on an artificially-generated propagated signal that is capable of encoding digital and/or quantum information, e.g., a machine-generated electrical, optical, or electromagnetic signal, that is generated to encode digital and/or quantum information for transmission to suitable receiver apparatus for execution by a data processing apparatus.

The term "data processing apparatus" refers to digital and/or quantum data processing hardware and encompasses all kinds of apparatus, devices, and machines for processing digital and/or quantum data, including by way of example a programmable digital processor, a programmable quantum processor, a digital computer, a quantum computer, multiple digital and quantum processors or computers, and combinations thereof. The apparatus can also be, or further include, special purpose logic circuitry, e.g., an FPGA (field programmable gate array), an ASIC (application-specific integrated circuit), or a quantum simulator, i.e., a quantum data processing apparatus that is designed to simulate or produce information about a specific quantum system. In particular, a quantum simulator is a special purpose quantum computer that does not have the capability to perform universal quantum computation. The apparatus can optionally include, in addition to hardware, code that creates an execution environment for digital and/or quantum computer programs, e.g., code that constitutes processor firmware, a protocol stack, a database management system, an operating system, or a combination of one or more of them.

A digital and/or quantum computer program may, but need not, correspond to a file in a file system. A digital and/or quantum computer program can be deployed to be executed on one digital or one quantum computer or on multiple digital and/or quantum computers that are located at one site or distributed across multiple sites and interconnected by a digital and/or quantum data communication network. A quantum data communication network is understood to be a network that may transmit quantum data using quantum systems, e.g. qubits. Generally, a digital data communication network cannot transmit quantum data, however a quantum data communication network may transmit both quantum data and digital data.

The processes and logic flows described in this specification can be performed by one or more programmable digital and/or quantum computers, operating with one or more digital and/or quantum processors, as appropriate, executing one or more digital and/or quantum computer programs to perform functions by operating on input digital and quantum data and generating output. The processes and logic flows can also be performed by, and apparatus can also be implemented as, special purpose logic circuitry, e.g., an FPGA or an ASIC, or a quantum simulator, or by a combination of special purpose logic circuitry or quantum simulators and one or more programmed digital and/or quantum computers.

For a system of one or more digital and/or quantum computers to be "configured to" perform particular operations or actions means that the system has installed on it software, firmware, hardware, or a combination of them that in operation cause the system to perform the operations or actions. For one or more digital and/or quantum computer programs to be configured to perform particular operations or actions means that the one or more programs include instructions that, when executed by digital and/or quantum data processing apparatus, cause the apparatus to perform the operations or actions. A quantum computer may receive instructions from a digital computer that, when executed by the quantum computing apparatus, cause the apparatus to perform the operations or actions.

Digital and/or quantum computers suitable for the execution of a digital and/or quantum computer program can be based on general or special purpose digital and/or quantum processors or both, or any other kind of central digital and/or quantum processing unit. Generally, a central digital and/or quantum processing unit will receive instructions and digital and/or quantum data from a read-only memory, a random access memory, or quantum systems suitable for transmitting quantum data, e.g. photons, or combinations thereof.

The essential elements of a digital and/or quantum computer are a central processing unit for performing or executing instructions and one or more memory devices for storing instructions and digital and/or quantum data. The central processing unit and the memory can be supplemented by, or incorporated in, special purpose logic circuitry or quantum simulators. Generally, a digital and/or quantum computer will also include, or be operatively coupled to receive digital and/or quantum data from or transfer digital and/or quantum data to, or both, one or more mass storage devices for storing digital and/or quantum data, e.g., magnetic, magneto-optical disks, optical disks, or quantum systems suitable for storing quantum information. However, a digital and/or quantum computer need not have such devices.

Digital and/or quantum computer-readable media suitable for storing digital and/or quantum computer program instructions and digital and/or quantum data include all forms of non-volatile digital and/or quantum memory, media and memory devices, including by way of example semiconductor memory devices, e.g., EPROM, EEPROM, and flash memory devices; magnetic disks, e.g., internal hard disks or removable disks; magneto-optical disks; CD-ROM and DVD-ROM disks; and quantum systems, e.g., trapped atoms or electrons. It is understood that quantum memories are devices that can store quantum data for a long time with high fidelity and efficiency, e.g., light-matter interfaces where light is used for transmission and matter for storing and preserving the quantum features of quantum data such as superposition or quantum coherence.

Claim 1:
A method performed by a quantum computing system (<NUM>) comprising quantum computing hardware (<NUM>) in communication with one or more classical processors (<NUM>) for performing a product addition operation on a target quantum register of qubits of the quantum hardware and a source quantum register of qubits of the quantum hardware, the method comprising:
determining (<NUM>), by the one or more classical processors, multiple entries of a lookup table, comprising, for each index in a first set of indices corresponding to indices of the lookup table, wherein the first set of indices comprises index values between zero and a maximum index value equal to two to the power of a predetermined window size, multiplying the index value by a scalar for the product addition operation, wherein the predetermined window size is an integer being log<NUM> n, where n represents a number of logical qubits in the target quantum register;
writing, by the one or more classical processors, each of the multiple entries of the lookup table to a lookup table at the respective index value of the entry in the lookup table; and
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 equal to the length of the source quantum register, wherein the index values are stepped by the predetermined window size:
determining (<NUM>), using the quantum computing hardware, 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 setting the multiple address values equal to respective extracted source quantum register values; and
adjusting (<NUM>), using the quantum computing hardware, values of the target quantum register based on the determined multiple entries of the lookup table and the determined multiple address values, the adjusting comprising:
computing a table lookup into a temporary quantum register using the determined multiple entries of the lookup table and the determined multiple address values;
adding the temporary quantum register into the target quantum register; and
uncomputing the table lookup.