Patent US10430162

Quantum resource estimates for computing elliptic curve discrete logarithms
[+] Show Details

US10430162

1. A computer-implemented method, comprising: (6) (3)

inputting a prime number;

generating reversible circuit designs for performing a modular arithmetic operation on the prime number, the modular arithmetic operation being one of addition, subtraction, multiplication, or division; and

storing the reversible circuit designs as quantum-computer executable instructions.

2. The method of claim 1, further comprising configuring a quantum computer to implement the reversible circuits described by the reversible circuit designs using the quantum-computer executable instructions. (0)

3. The method of claim 1, wherein the data on which the modular arithmetic operation acts is encoded using Montgomery encoding for the underlying prime number. (0)

4. The method of claim 1, wherein the modular arithmetic operation performed is addition, and wherein the addition operation is implemented using a quantum circuit design for integer addition, followed by a reversible circuit that tests for overflows and reduces an output modulo by the prime number if necessary. (0)

5. The method of claim 1, wherein the modular arithmetic operation performed is subtraction, and wherein the subtraction operation is implemented using a quantum circuit design for integer addition, followed by a reversible circuit that tests for overflows and reduces an output modulo by the prime number if necessary. (0)

6. The method of claim 1, wherein the modular arithmetic operation performed is multiplication, and wherein the multiplication operation is implemented iteratively by conditionally updating an accumulator by a shifted version of the prime number and a prime modulus followed by a qubit permutation that realizes a division by 2. (0)

7. The method of claim 1, wherein the modular arithmetic operation performed is division, and wherein the division relies on a reversible computation of a Montgomery inverse by an iterative process that is executed by a specified number of steps and that involves a reduction sub-process and a counting sub-process. (1) (0)

9. A quantum computing device configured to implement a sequence of reversible circuits that in combination, perform a modular arithmetic operation on a prime number, the modular arithmetic operation being one of addition, subtraction, multiplication, or division. (4) (0)

10. The quantum computing device of claim 9, wherein the modular arithmetic operation performed is addition, and wherein the addition operation is implemented using a quantum circuit for integer addition, followed by a reversible circuit that tests for overflows and reduces an output modulo by the prime number if necessary. (0)

11. The quantum computing device of claim 9, wherein the modular arithmetic operation performed is subtraction, and wherein the subtraction operation is implemented using a quantum circuit for integer addition, followed by a reversible circuit that tests for overflows and reduces an output modulo by the prime number if necessary. (0)

12. The quantum computing device of claim 9, wherein the modular arithmetic operation performed is multiplication, and wherein the multiplication operation is implemented iteratively by conditionally updating an accumulator by a shifted version of the prime number and a prime modulus followed by a qubit permutation that realizes a division by 2. (0)

13. The quantum computing device of claim 9, wherein the modular arithmetic operation performed is division, and wherein the division relies on a reversible computation of a Montgomery inverse by an iterative process that is executed by a specified number of steps and that involves a reduction sub-process and a counting sub-process. (1) (0)

View Abstract and Specification Size

PDF with Images and Document Face >

Full Text Publication >

Patent US10430162

Quantum resource estimates for computing elliptic curve discrete logarithms

Patent Matrix® Search