Patenting Quantum Computing Innovations – Part 5: Shor’s Algorithm and Conclusions

By Sinan Utku

Example 4: Shor’s Algorithm

Shor’s algorithm efficiently factors large integers into their prime factors by reducing the problem to a period-finding task, which can be solved much more efficiently on a quantum computer than on a classical one. The algorithm involves preparing a quantum superposition of inputs and preparing a quantum gate to evaluate a modular exponentiation function. It then applies quantum phase estimation to extract the period of this function. This involves applying controlled powers of the quantum gate for modular exponentiation and then performing an inverse quantum Fourier transform to obtain information about the period. Once the period is determined, a classical algorithm uses it to relatively easily compute the prime factors of the integer. Because Shor’s algorithm is exponentially faster than the best known classical factoring algorithms, it poses a significant threat to widely used public-key cryptosystems such as RSA, which rely on the difficulty of factoring large integers.

A quantum computer decrypting RSA-encrypted communications without the benefit of a key might carry out Shor’s algorithm:

• prepare a first quantum register with eigenvalue qubits that are initialized to a computational basis state, and a second quantum register that are initialized by eigenvector qubits that correspond to the product number that is desired to be factored;
• apply a Hadamard gate to each of the eigenvalue qubits placing them in a superposition state;
• apply a series of powers of a unitary operation that is associated with a modular exponentiation transform to the second quantum register, where application of each power of the unitary operation is controlled by a corresponding eigenvalue qubit, and the eigenvalue qubits are modified through phase kick-back;
• perform an inverse quantum Fourier transform on the first quantum register to carry out quantum phase estimation and obtain an estimate of a phase corresponding to the base unitary operator U acting on the second quantum register;
• derive a period parameter from the phase estimate and determine prime factors corresponding to the product number using the derived period parameter; and
• decrypt the encrypted message using the determined prime factors, the relevant public key and the product number.