| Abstract: |
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 ![custom character]() (n log n) and a depth in ![custom character]() (n). |
| Inventor: |
Roetteler, Martin (Woodinville, WA, US); Svore, Krysta (Seattle, WA, US); Haener, Thomas (Bellevue, WA, US) |
| Applicant: |
Microsoft Technology Licensing, LLC (Redmond, WA, US) |
| Face Assignee: |
Microsoft Technology Licensing, LLC (Redmond, WA, US) |
| Filed: |
2017-06-30 |
| Issued: |
2019-09-24 |
| Claims: |
15 |
|
US10423887
|
1. A method comprising implementing an integer incrementer on a quantum computer using a qubit in an unknown state, wherein the implementing comprises:
(1)
(2)
|
|
3. A method, comprising:
(4)
(1)
|
|
9. A quantum computing device comprising input qubits, output qubits, and scratch qubits,
(4)
(1)
|
|
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.
(1)
(0)
|
|
