Oblivious carry runway registers for performing piecewise additions

Abstract

Methods and apparatus for piecewise addition into an accumulation register using one or more carry runway registers, where the accumulation register includes a first plurality of qubits with each qubit representing a respective bit of a first binary number and where each carry runway register includes multiple qubits representing a respective binary number. In one aspect, a method includes inserting the one or more carry runway registers into the accumulation register at respective predetermined qubit positions, respectively, of the accumulation register; initializing each qubit of each carry runway register in a plus state; applying one or more subtraction operations to the accumulation register, where each subtraction operation subtracts a state of a respective carry runway register from a corresponding portion of the accumulation register; and adding one or more input binary numbers into the accumulation register using piecewise addition.

What is claimed is: 
     
         1 . A method for determining a result of an addition of multiple input binary numbers, the method comprising:
 removing one or more carry runway registers from an accumulation register, wherein i) the accumulation register comprises a first plurality of qubits with each qubit of the first plurality of qubits representing a respective bit of a first binary number, ii) respective states of portions of the accumulation register encode the multiple input binary numbers, and iii) each carry runway register of the one or more carry runway registers comprises multiple qubits representing a respective binary number, the removing comprising:
 applying one or more addition operations to the accumulation register, wherein each addition operation of the one or more addition operations adds a state of a respective carry runway register to a portion of the accumulation register that begins at a qubit position where the respective carry runway register is inserted in the accumulation register and ends at a qubit position prior to a next inserted carry runway or a most significant bit of the first binary number; and 
   measuring qubits in the accumulation register to determine a result of the addition of the multiple input binary numbers.