Compilation, Memory Management, And Fault Localization With Ancillas In An Unknown State
Among the embodiments disclosed herein are quantum circuits (and associated compilation techniques) for performing Shor's quantum algorithm to factor n-bit integers. Example embodiments of the circuits use only 2n+2 qubits. In contrast to previous space-optimized implementations, embodiments of the disclosed technology feature a purely Toffoli-based modular multiplication circuit. Certain other example modular multiplication circuits disclosed herein are based on an (in-place) constant-adder that uses dirty ancilla qubits to achieve a size in (n log n) and a depth in (n).
Claim CLM-00001. 1. A method comprising implementing an integer incrementer on a quantum computer using a qubit in an unknown state, wherein the implementing comprises:
altering the qubit in the unknown state from an original unknown state to a modified state as part of the implementing the integer incrementer; and returning the qubit in the unknown state from its modified state to its original unknown state.
Claim CLM-00003. 3. A method, comprising:
implementing an operation in a quantum computing device using one or more qubits in an unknown state, wherein the implementing comprises:
altering the one or more qubits from respective original unknown states into respective modified states; andreturning the one or more qubits from their respective modified states to the to their respective original unknown states.
Claim CLM-00009. 9. A quantum computing device comprising input qubits, output qubits, and scratch qubits,
the quantum computing device further comprising a circuit for performing an arithmetic operation using one or more of the scratch qubits when the scratch qubits are in an unknown state by altering at least one of the scratch qubits in the unknown state from an original unknown state to a modified state, and returning the at least one of the scratch qubits in the unknown state from its modified state to the original unknown state.
Claim CLM-00014. 14. An ancilla management system for a quantum computer configured to allocate one or more ancilla qubits in an unknown state for use in a first operation that modifies the qubits in the unknown states into respective modified unknown states and, in a second operation, returns the qubits to their original unknown states, wherein the ancilla management system allocates the qubits in the unknown states only if the qubits in the unknown state can be returned to their original unknown state prior to modification by other operations.
