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 in polynomial time.
Adapted from https://github.com/ttlion/ShorAlgQiskit
See also https://arxiv.org/abs/quant-ph/0205095
Parameters
quantum_instance (Union[Backend, BaseBackend, QuantumInstance, None]) – Quantum Instance or Backend
__init__
__init__(quantum_instance=None)
Parameters
quantum_instance (Union[Backend, BaseBackend, QuantumInstance, None]) – Quantum Instance or Backend
Methods
__init__([quantum_instance]) | type quantum_instanceUnion[Backend, BaseBackend, QuantumInstance, 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
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
factor(N, a=2)
Execute the algorithm.
The input integer 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 can also be supplied, which needs to be a co-prime smaller than .
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
Raises
- ValueError – Invalid input
- AlgorithmError – If a quantum instance or backend has not been provided
modinv
static modinv(a, m)
Returns the modular multiplicative inverse of a with respect to the modulus m.
Return type
int
quantum_instance
Returns quantum instance.
Return type
Optional[QuantumInstance]