Period finding for Quantum Computers

Question

Shor's algorithm shows how a quantum computer (with sufficiently many qubits) can solve the factorization problem efficiently. Also the discrete logarithm problem can be solved efficiently with such a quantum computer.

Both boil down into finding the period of a certain function.

Can quantum computer find the period of any given function efficiently? Are there any requirements towards the function?

Closely related, the discussed post-quantum schemes (e.g. the ones submitted to NIST) do not provide a function whose period could be exploited to break the scheme?

Answer 1

There are a few limitations on the function that you may or may not consider obvious.

The image of the function $f$ has to be a finite set. The function $f$ has to be computable and the efficiency depends on how well $f$ can be implemented as a quantum circuit. Arguably, you also need some sort of bound on the period so that you know how big the quantum Fourier transform needs to be (alternatively you could keep running the algorithm doubling the size of the QFT until it is successful).

A fuller generalisation of Shor's algorithm is the hidden subgroup problem for Abelian groups, where the cyclic group structure of iterative evaluation is generalised to the action of a general Abelian group. All post-quantum algorithms should be designed so that there is no instance of this problem that helps to crack the cryptosystem. "Noisy" algorithms seem to be a good way to avoid hidden abelian subgroup structure.

It's worth noting that the hardness of short/close vector problems in lattices can be attacked if we can efficiently solve the hidden dihedral subgroup problem (though we don't know of a polynomial time quantum algorithm for solving this).

Answer 2

Can quantum computer find the period of any given function efficiently? Are there any requirements towards the function?

Well, the function has to be periodic; that is, we have, for some $c > 0$, $f(x) = f(x+c)$, for all $x$ [1].

For both factoring and discrete log, we have such a function; and we know how finding the period of that function will give us the answer.

However, postquantum algorithms, we don't have such a way. For code-based schemes, no periodicity is apparent. For lattice-based schemes, there is (periodicity is inherent in the idea of a lattice), however we don't know how to convert finding such a periodicity into (say) an answer to the shortest vector problem.

---

[1]: Actually, I believe Shor's algorithm will work even if the above relation holds for most $x$; however for the functions of interest, true periodicity holds...

Answer 3

With a register of qbits and a function implemented on a quantum computer, one would measure the function output for the usual "mixed" input. Measuring would result in a state fixing some value from the function range while keeping all proper inputs in superposition. This works for RSA and whatever you can implement on your computer. Use FFT to deduce your period from that superposition.