Shor¶

Shor(quantum_instance=None)

Bases: object

The deprecated Shor’s factoring algorithm.

The Shor class is deprecated as of Qiskit Terra 0.22.0 and will be removed no sooner than 3 months after the release date. It is replaced by the tutorial at Shor (opens in a new tab)

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.

Parameters

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

Methods

construct_circuit

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

Construct quantum part of the algorithm.

Parameters

• N (int) – The odd 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.

factor

Shor.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 odd 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

modinv

static Shor.modinv(a, m)

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

Return type

int

Attributes

quantum_instance

Returns quantum instance.

Return type

Optional[QuantumInstance]