Shor’s Algorithm#

In the realm of quantum computing, where classical limitations are challenged and new horizons are explored, Shor’s Algorithm stands as a testament to the transformative potential of quantum mechanics in the field of cryptography. Developed by mathematician Peter Shor in 1994, this groundbreaking algorithm has the power to revolutionize the world of cryptography by efficiently factoring large numbers—once considered an insurmountable task for classical computers.

Qrisp provides a dead simple interface to integer factorization using your own backend. For details how this algorithm is implemented, please check the Shor’s algorithm tutorial.

shors_alg(N: int, inpl_adder: Callable | None = None, mes_kwargs: dict | None = None) → int[source]#

Performs Shor’s factorization algorithm on a given integer N.

The adder used for factorization can be customized. To learn more about this feature, please read QuantumModulus

Parameters:

Ninteger: The integer to be factored.
inpl_addercallable, optional: A function that performs in-place addition. The default is None.
mes_kwargsdict, optional: A dictionary of keyword arguments for get_measurement. This especially allows you to specify an execution backend. The default is {}.

Returns:

resinteger: A factor of N.

Examples

We factor 65:

>>> from qrisp.shor import shors_alg
>>> shors_alg(65)
5

For resource estimation and for programs in Jasp mode, the quantum part of order finding is also available with a semiclassical phase estimation, which needs a single control qubit instead of a phase register.

semiclassical_order_finding(a: int, N: int, precision: int | None = None, inpl_adder: Callable | None = None) → BigInteger[source]#

Run the quantum part of order finding with a semiclassical phase estimation, and return its outcome.

This is the quantum subroutine of Shor’s algorithm: the phase estimation of the multiplication by \(a\) modulo \(N\) on a QuantumModulus initialized to 1. Its outcome \(y\) is close to \(s \cdot 2^t / r\) for a random \(s\), where \(r\) is the order of \(a\) modulo \(N\) and \(t\) is the precision, so that \(r\) can be recovered classically, for example with continued fractions.

Instead of a \(t\)-qubit phase register followed by the inverse quantum Fourier transform, the phase estimation uses the semiclassical Fourier transform of Griffiths and Niu (1996), with one control qubit at a time following Mosca and Ekert (1999). Step \(j\) applies the multiplication by \(a^{2^{t-1-j}} \bmod N\) controlled on a fresh qubit, rotates the qubit by the phase of the bits measured before, measures bit \(j\) of \(y\), and resets the qubit before releasing it. The outcome has the same distribution as with the full phase register. The circuit needs \(t - 1\) fewer qubits, and \(t\) single-qubit rotations replace the \(t (t - 1) / 2\) controlled phase gates and \(\lfloor t / 2 \rfloor\) swaps of the inverse quantum Fourier transform. It requires mid-circuit measurements and rotations that depend on their outcomes.

The classical multipliers \(a^{2^k} \bmod N\) and their inverses modulo \(N\), which the in-place multiplications need, are computed exactly with Python integers when the function is called, so a and N must be integers and cannot be traced.

Note

This function can only be called in Jasp mode, for example within jaspify, or in the resource estimators count_ops and num_qubits.

Parameters:

aint: The number whose order is found, coprime to N.
Nint: The modulus, an odd integer larger than 2.
precisionint, optional: The number \(t\) of bits of the outcome. The default is \(2n\), where \(n = \lceil \log_2 N \rceil\) is the number of bits of \(N\).
inpl_adderCallable, optional: The in-place adder of the modular multiplication, see QuantumModulus. The default is the gidney_adder.

Returns:

BigInteger: The outcome \(y\), with \(\lceil t / 32 \rceil\) limbs. All qubits are reset and released before returning, so that repeated calls do not keep them allocated and later allocations can reuse them.

Raises:

TypeError: If a, N or precision is not an integer.
ValueError: If N is even or smaller than 3, if a is not coprime to N, or if precision is smaller than 1.
RuntimeError: If the function is called outside of Jasp mode.

Examples

The order of 7 modulo 15 is \(r = 4\), and \(2^t\) with the default precision \(t = 8\) is a multiple of \(r\). The outcome is therefore one of the multiples \(s \cdot 2^8 / 4 = 64 s\), each with probability \(1/4\). Calling the returned BigInteger gives its value:

>>> from qrisp.algorithms.shor import semiclassical_order_finding
>>> from qrisp.jasp import jaspify
>>> def order_finding():
...     return semiclassical_order_finding(7, 15)
>>> outcome = jaspify(order_finding)()
>>> print(outcome() % 64)
0

The resource estimators count the same circuit without simulating it. With the default adder, the circuit needs \(3n + 2 \lceil \log_2 n \rceil + 2\) qubits, 18 for \(n = 4\). It applies one rotation per bit of the outcome, 8 for \(t = 8\):

>>> from qrisp.jasp import count_ops, num_qubits
>>> print(num_qubits(meas_behavior="1")(order_finding)()["peak_allocations"])
18
>>> print(count_ops(meas_behavior="1")(order_finding)()["rz"])
8

Cryptography tools#

These tools can be utilized to spy on your enemies.

`rsa_encrypt`(e, N, message_int)	Encrypts an integer using a public key pair \((e,N)\).
`rsa_decrypt`(e, N, cipher_int[, backend])	Decrypts an integer using factorization powered by Shor's algorithm.
`rsa_encrypt_string`(e, N, message)	Encrypts an arbitrary Python string using RSA.
`rsa_decrypt_string`(e, N, ciphertext[, backend])	Decrypts a bitstring into a human readable string.