Prime States: Cost and Memory Limits for a New Quantum Design

In the paper's words

A recurring proposal in quantum-architecture design is to treat the prime numbers not as parameters of an algorithm but as the fundamental addressable units of a register: a "Prime state" that superposes all primes below 2^n. The specific gap this paper addresses is quantitative: no compact derivation exists that a system architect can use to compare the preparation cost, entanglement content, and classical emulability of such a prime-basis register against a standard computational-basis register. Using the Prime-state construction of Latorre and Sierra, in which a Grover oracle implementing the Miller-Rabin test prepares |P_n⟩ = π(2^n)^-1/2∑_p<2^n|p⟩, we derive: (i) the prime-state population π(2^n) ≈ 2^n/(nln 2), giving 75 640 for n=20 under the PNT approximation; (ii) a Grover preparation cost of (π/4)√nln 2 oracle calls, i.e. $5.23$ calls at n=64, against 2⁶4 classical candidates; (iii) an entanglement entropy ceiling of log₂ π(2^n) bits across any bipartition, $16.21$ bits at n=20; and (iv) a coprimality-derived collision floor of 6/π² ≈ 0.6079 for random register pairs.

The abstract, verbatim, and its opening sentence is the claim. Every line below is quoted from the text.

Numbers it reports

1. Using the Prime-state construction of Latorre and Sierra, in which a Grover oracle implementing the Miller-Rabin test prepares $|\mathbb{P}_n\rangle = \pi(2^n)^{-1/2}\sum_{p\lt 2^n}|p\rangle$, we derive: (i) the prime-state population $\pi(2^n) \approx 2^n/(n\ln 2)$, giving $75\,640$ for $n=20$ under the PNT approximation; (ii) a Grover preparation cost of $(\pi/4)\sqrt{n\ln 2}$ oracle calls, i.e. $5.23$ calls at $n=64$, against $2^{64}$ classical candidates; (iii) an entanglement entropy ceiling of $\log_2 \pi(2^n)$ bits across any bipartition, $16.21$ bits at $n=20$; and (iv) a coprimality-derived collision floor of $6/\pi^2 \approx 0.6079$ for random register pairs.

   from Abstract

2. Its method is derivation from stated inputs, in the cost-accounting discipline exemplified by contract-style verification of quantum simulators, where every number is either computed with shown arithmetic or labeled a projection with stated assumptions [10].

   from 1. Introduction

3. A derivation of the Grover preparation cost $(\pi/4)\sqrt{n\ln 2}$ oracle calls and its comparison with the classical candidate scan, giving a cost ratio exponential in $n$ (Section 4.2).

   from 1. Introduction

4. An entanglement entropy ceiling $\log_2 \pi(2^n)$ bits valid for any bipartition of the register, with numeric values (Section 4.3).

   from 1. Introduction

5. A coprimality collision floor $6/\pi^2 \approx 0.6079$ for pairs of independent register values, derived from the Euler product (Section 4.4).

   from 1. Introduction

6. The entropy and cost bounds derived here also bear, at the level of representation choice, on problems outside quantum architecture: any field that must choose between a microscopic and a coarse-grained description of a structured discrete system faces the same trade-off between fidelity and computational cost that the prime state versus computational-basis comparison exhibits, a trade-off formalized as predictive efficiency in [12].

   from 1. Introduction

How it is done

1. A recurring proposal in quantum-architecture design is to treat the prime numbers not as parameters of an algorithm but as the fundamental addressable units of a register: a "Prime state" that superposes all primes below $2^n$.

   from Abstract

2. This is the practical stake of the "Prime state" proposal: a quantum superposition of all primes below $2^n$, preparable by Grover's algorithm with a Miller-Rabin oracle, whose entanglement measures encode number-theoretic counting functions [3].

   from 1. Introduction

3. It proposes building the state with Grover's algorithm whose oracle is a quantum implementation of the classical Miller-Rabin primality test, generalizes the construction to a Twin Prime state by adding $2$ to each prime and re-applying the primality circuit so that measuring the ancilla yields the probability of finding a twin, and shows that the Prime state verifies Goldbach's conjecture and that the combination of the primality circuit with the Quantum Fourier Transform counts primes within an error smaller than the fluctuations allowed by the Riemann hypothesis [3].

   from 2. Background and Related Work

4. This is an analytical paper.

   from 3. Methods

What would falsify it

1. A discussion of which observations would falsify these bounds, and of the opposing ontological position that primes are spectral artifacts of a continuous substrate rather than fundamental discrete entities [11] (Sections 6 and 2).

   from 1. Introduction

2. The totient result of [8] is the constructive counterexample: a bias that numerics suggested at $98\%$ to $2\%$ on twin primes is provably exactly $50\%$–$50\%$ once only $p$ is assumed prime, so structural balance in the prime basis can be proved where numerics mislead.

   from 6. Discussion

3. The main results would be falsified as follows.

   from 6. Discussion

Where the claim stops

1. What the bound does not establish is saturation.

   from 6. Discussion

2. The same asymmetry applies to the preparation cost: $G(n) \approx (\pi/4)\sqrt{n \ln 2}$ counts oracle calls in the ideal Grover regime with a unit-cost Miller-Rabin oracle, and the projected gate count of $8.77 \times 10^7$ at $n = 64$ rests on the assumed $k = 64$ rounds and schoolbook exponentiation; a circuit-level implementation with ancilla overhead, uncomputation, and error correction would raise it by factors this paper does not estimate.

   from 6. Discussion

3. The totient result of [8] is the constructive counterexample: a bias that numerics suggested at $98\%$ to $2\%$ on twin primes is provably exactly $50\%$–$50\%$ once only $p$ is assumed prime, so structural balance in the prime basis can be proved where numerics mislead.

   from 6. Discussion

Where to read

1. Abstract214 words · 1 min
2. 1. Introduction917 words · 4 min
3. 2. Background and Related Work1,106 words · 5 min
4. 3. Methods338 words · 1 min
5. 4. Analysis1,563 words · 7 min
6. 5. Results257 words · 1 min
7. 6. Discussion894 words · 4 min
8. 7. Practical Implications and Engineering Pathways753 words · 3 min
9. 8. Conclusion260 words · 1 min
10. Provenance and AI Involvement240 words · 1 min