qit.examples.find_order

qit.examples.find_order(a, N, epsilon=0.25)

Quantum order-finding subroutine.

Finds the period of the function f(x) = a^x mod N.

Parameters

  • a (int) – base

  • N (int) – modulus

  • epsilon (float) – maximum allowed failure probability for the subroutine

N and epsilon together determine the number of qubits, m required to perform the modular arthmetic, and t to serve as the index in the phase estimation.

Returns

(r, s) where r/s approximates period / 2**t.

Return type

int, int

Uses phase_estimation.

See [3], [4] chapter 5.3.