  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. This Prime state can be built using Grover's
algorithm, whose oracle is a quantum implementation of the classical
Miller-Rabin primality test. The Prime state is highly entangled, and its
entanglement measures encode number theoretical functions such as the
distribution of twin primes or the Chebyshev bias. This algorithm can be
further combined with the quantum Fourier transform to yield an estimate of the
prime counting function, more efficiently than any classical algorithm and with
an error below the bound that allows for the verification of the Riemann
hypothesis. We also propose a Twin Prime state to measure the number of twin
primes and another state to test the Goldbach conjecture. Arithmetic properties
of prime numbers are then, in principle, amenable to experimental verifications
on quantum systems.
