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.
It is likely that the patent eligibility this invention would be challenged. Specifically, it would likely be found, at least initially, to be abstract for being directed to a mathematical method for solving a number‑theoretic problem rather than to a technological improvement to a machine. The algorithmic components of Shor’s algorithm comprise a sequence of mathematical operations, such as period finding via quantum phase estimation and the inverse quantum Fourier transform. Carrying out these mathematical operations on a quantum computer likely does not confer patent eligibility in the absence of specific improvements to the operation of the quantum computer itself. Arguably, the only improvement of the algorithm is to the mathematical processing – i.e., more efficiently factoring a number using a quantum computer. A critical PTO examiner would likely characterize the invention as using conventional and known quantum computing processes, such as superposition, controlled unitary gates and the quantum Fourier transform, to carry out an improved mathematical method. Such a PTO examiner would likely also emphasize the risk of whole scale preemption of the use of foundational mathematical principles that might arise from the patenting of such an invention. Thus, there is a good chance that this invention would ultimately be found to be ineligible under current law.
Interestingly, the PTO, in an example it provided in a guidance document, stated that that an invention directed to RSA-encryption (which could be characterized as being a functional complement of Shor’s algorithm) is patent eligible.[i] This example was directed to a method for establishing cryptographic communications between a first computer terminal and a second computer terminal, and the invention carried out steps including (i) receiving a plaintext word signal; (ii) transforming the plaintext word signal into message blocks; (iii) encoding each message block using a mathematical process; and (iv) transmitting the resultant ciphertext to the second computer terminal over a communications channel. The PTO in its guidance initially indicated that the invention was abstract. However, it found that the inclusion of steps like receiving the plaintext word signal at the first computer terminal, transforming the plaintext word signal to message block word signals, and transmitting the encoded ciphertext word signal to the second computer terminal over a communication channel, integrated an otherwise abstract invention into a practical application that is patentable. In particular, it found that “the combination of additional elements use the mathematical formulas and calculations in a specific manner that sufficiently limits the use of the mathematical concepts to the practical application of transmitting the ciphertext word signal to a computer terminal over a communication channel.”[ii]
Given the PTO’s guidance, one could argue that the Shor’s algorithm invention set forth above improves the recited decryption computer by making it more efficient, e.g., compared to a decryption computer running a classical algorithm in the absence of the relevant RSA decryption key. Nevertheless, under the current Mayo/Alice framework, it will be an uphill battle to convince the examiner or the judicial decision maker that the invention is directed to anything other than essentially an ineligible improved mathematical method for factoring numbers.
Conclusions
Quantum computing appears to be on the threshold of an explosive innovative stage that likely will yield result in usefully operational quantum computers. Patent protection of innovations in the hardware of these quantum computers as well as the algorithms running on them will be critical in ensuring robust growth and development of the industry. However, the uncertain state of patent eligibility law in the US is a barrier to protecting many of these inventions. There is patent reform legislation pending in Congress that would reform patent eligibility law in response to the ongoing unhappiness with the current state of the law.[iii] But given the current polarization and paralysis, it is not clear when Congress might act to reform patent eligibility law and whether it might do so in a way that is helpful to the patenting of quantum computing inventions. In the meantime, IP counsel and personnel at quantum computing companies during the patenting process should carefully consider both the evolving patent eligibility case law and aspects in their inventions that may help establish patent eligibility.
[i] U.S. Patent & Trademark Office, Subject Matter Eligibility Examples: Abstract Ideas, Example 41 (Jan. 7, 2019), available at https://www.uspto.gov/sites/default/files/documents/101_examples_37to42_20190107.pdf.
[ii] Id.
[iii] Patent Eligibility Restoration Act of 2025, S. 1546, 119th Cong. (2025) (introduced May 1, 2025; pending before the Senate Judiciary Committee).
Sinan Utku is a Special Counsel, Covington and Burling LLP; Instructor, Bilkent University Law School. Nothing in this article should be construed as reflecting the official views, opinions, or positions of any organisation or institution with which the author is affiliated. The author writes in a personal capacity only.