Quantum state preparation

Quantum state preparation constructs a circuit $B$ that maps a simple reference state to a desired state, $B|0^n⟩=|\psi ⟩$. Efficient amplitude encoding requires structure or suitable oracle access to avoid reading exponentially many arbitrary amplitudes.

For a semiprime $N=pq$ with distinct known primes, this quantum state is uniform over the reduced residue classes. With $n$ binary digits in $N$, its fraction among all $2^n$ computational labels is $a=(p-1)(q-1)/2^n\ge 1/4$. An ancilla qubit whose one probability is $1/(4a)$ dilutes the joint good probability to exactly $1/4$. A reversible range-and-greatest common divisor predicate marks the good labels with ancilla qubit one, and a single exact amplitude amplification iteration produces $|{\xi }_N⟩|1⟩$. Known prime factors provide the cardinality; the membership test itself needs only $N$. Polynomial gate complexity presumes ideal one-qubit rotations at the specified amplitudes.

In an $N$-dimensional computational basis, the uniform superposition state isMeasurement in that basis gives the uniform distribution on a finite set. For $N=2^n$, Hadamard gates prepare it from $|0^n⟩$. Its reflection $2|s_N⟩⟨s_N|-I$ is a Grover diffusion operator.

Hierarchical probability-distribution state preparation recursively bisects a classical probability distribution. At each level, a controlled rotation splits every parent interval's amplitude between its two children according to their conditional probabilities.