Shor

class Shor(N=15, a=2, quantum_instance=None)[source]

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.

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\) .

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

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

Parameters

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

  • a (int) – A random integer that satisfies a < N and gcd(a, N) = 1, has a min. value of 2.

  • quantum_instance (Union[QuantumInstance, BaseBackend, None]) –

    Quantum Instance or Backend

    Raises:

    ValueError: Invalid input

Attributes

Shor.backend

Returns backend.

Shor.quantum_instance

Returns quantum instance.

Shor.random

Return a numpy random.

Methods

Shor.construct_circuit([measurement])

Construct circuit.

Shor.run([quantum_instance])

Execute the algorithm with selected backend.

Shor.set_backend(backend, **kwargs)

Sets backend with configuration.