** This post assumes you have a sound understanding of Quantum Mechanics, more precisely eigenstates, superpositions and entanglements
Shor’s algorithm allows us to find a factor of any composite number in for any random , which is important in this scope to understand, as cryptography’s security baseline is founded on the fact that factoring cannot happen in polynomial time – I have talked on this subject in my post Yes Diffie-Hellman is secure, quoting myself
Because the discrete logarithm is not NP-complete, it is not possible to compute our in polynomial time and therefore generating a big prime number to be used in generating a cryptographic key renders exhaustive search attack completely useless.
- Ali Abbas
Since Shor’s algorithm runs in polynomial time to the length , it solves the discrete logarithm problem and hence breaks the conjecture on which public key cryptography such as RSA are based upon.
Quantum Fourier Transform
QFT is simply a Discrete Fourier transformation applied to a quantum amplitude using a unitary operator, meaning, there exists such that – in other words, assuming a basis state, there exists a vector which is a superposition of all computational basis, defining the orthonormal basis states – it is unitary because the amplitude of the vector never changes as part of the transform.
For example, taking a set of complex numbers, , the orthonormal basis state acted upon is:
defined by .
This means that the Fourier transform of an amplitude is a mapping of an arbitary state to
since per the Discrete Fourier equation, QFT can then be modelled as follow
Having said that, and not wanting of course to go into a full lecture on QFT – what is most important to understand here is that the speed at which we can apply QFT – by properly aligning the Qubits in a proper Quantum circuit, QFT is computed in order of gates (assuming of course that all factors of N are ) – an equivalent amplitude of would require simple gates.
To find the period of a random such as and , we create 2 entangled registers (input and output) of size , both initialized to . We then compute our periodic function f(x) to each number (remember, register 1 is loaded with an equally weighted superposition of integers 0 to N-1) in our input register and store the value in the second register – due to the superposition state and quantum computation parallelism, this operation is done in one step. Once the quantum computation is done, we observe the second register for some random value , such that register 1 is collapsed into an equal superposition of each values ranging from to for each value; In other words, we have a set values of possible such as , which means we observe a lower integer , such as . Our superposition in register 1 being , we apply a Discrete Fourier Transform (see earlier) on the superposition, this will generate an amplitude of integers (spectrum) which are multiples of ; Since we no longer have an equal superposition of states and our superposition in register 1 was periodic in nature, we can observe a state, let’s call it , which has a high probability of being a multiple of . Having and , we can easily compute and verify whether . If our verification works, we have found our periodic value and can resume to calculate . If not, then we pretty much repeat the process with a random value .
Of course, Shor’s algorithm can be more elaborated into steps and in soft and hard cases whether divides or not and if you have followed the core logic of the algorithm which we had quickly undergo, you can only come to realize that Shor’s algorithm is highly probabilistic in nature due to the nature of DFT, hence the more Shor is run, the more it becomes accurate. Quantum computing parallelism provides a significant gains since all states of all values of are computed in one step. Hence the problem of solving the discrete logarithm problem is in finding the period , which in case of Shor’s is shown to be trivial and faster than classical computing using a Discrete Fourier transform.