The Prime state of n qubits, |ℙn⟩, is defined as the uniform superposition of all the computational-basis states corresponding to prime numbers smaller than 2n. This state encodes, quantum mechanically, arithmetic properties of the primes. We first …