Newbie Project: Calculate a Mersenne Prime with Quantum Computing

Question

I am new to the quantum world and wondering the bounds of which the technology is at the current state of the art: specifically in computing prime numbers.

I would like to, if possible, create a project that seeks to find Mersenne prime numbers (see here and here for more info).

I know there have been an algorithm(s) proposed for finding primes, but are there any actual languages I can make use of at the current state of the art? I have access to a QPU/Lattices using the pyquil language but haven't seen anything in the documentation that does this (at least in English I understand).

Answer 1

It's likely that this algorithm hasn't yet been implemented in QISKit / Q# / pyquil etc. It's also important to note that you would not be discovering new Mersenne primes with a quantum computer - the paper referenced says:

We propose a quantum circuit that creates a pure state corresponding to the quantum superposition of all prime numbers less than $2^n$, where $n$ is the number of qubits of the register.

Even with new quantum computers, this might only amount to $ 2^{73} $, at best. And, there's no guarantee that these quantum computers will have the required coherence times.

This doesn't mean that it would be a waste to implement this algorithm - any contribution to a quantum programming language (QISKit / Q# / pyquil) is welcomed! But this algorithm won't be beating classical computers anytime soon.