qiskit.algorithms.Shor

class Shor(quantum_instance=None)

Shor’s factoring algorithm.

Shor’s Factoring algorithm is one of the most well-known quantum algorithms and finds the prime factors for input integer $N$ in polynomial time.

Adapted from https://github.com/ttlion/ShorAlgQiskit

See also https://arxiv.org/abs/quant-ph/0205095

Parameters

quantum_instance (Union[QuantumInstance, BaseBackend, Backend, None]) – Quantum Instance or Backend

__init__(quantum_instance=None)

Parameters

quantum_instance (Union[QuantumInstance, BaseBackend, Backend, None]) – Quantum Instance or Backend

Methods

__init__([quantum_instance])	type quantum_instance Union[QuantumInstance, BaseBackend, Backend, None]
construct_circuit(N[, a, measurement])	Construct circuit.
factor(N[, a])	Execute the algorithm.
modinv(a, m)	Returns the modular multiplicative inverse of a with respect to the modulus m.

Attributes

quantum_instance

Returns quantum instance.

construct_circuit(N, a=2, measurement=False)

Construct circuit.

Parameters

• N (int) – The integer to be factored, has a min. value of 3.

• a (int) – Any integer that satisfies 1 < a < N and gcd(a, N) = 1.

• measurement (bool) – Boolean flag to indicate if measurement should be included in the circuit.

Return type

QuantumCircuit

Returns

Quantum circuit.

Raises

ValueError – Invalid N

factor(N, a=2)

Execute the algorithm.

The input integer $N$ to be factored is expected to be odd and greater than 2. Even though this implementation is general, its capability will be limited by the capacity of the simulator/hardware. Another input integer $a$ can also be supplied, which needs to be a co-prime smaller than $N$ .

Parameters

• N (int) – The integer to be factored, has a min. value of 3.

• a (int) – Any integer that satisfies 1 < a < N and gcd(a, N) = 1.

Returns

results of the algorithm.

Return type

ShorResult

Raises

• ValueError – Invalid input

• AlgorithmError – If a quantum instance or backend has not been provided

static modinv(a, m)

Returns the modular multiplicative inverse of a with respect to the modulus m.

Return type

int

property quantum_instance

Returns quantum instance.

Return type

Optional[QuantumInstance]