The input size of an integer factorization problem is its number of bits $n\simeq {\log }_{2}N$. Trial division up to $\sqrt{N}$ is exponential in $n$; advanced classical algorithms do substantially better, but no general polynomial-time classical factoring algorithm is known. The heuristic general-purpose general number field sieve has subexponential rather than polynomial scaling, roughly $\exp (O(n^{1/3}(\log n{)}^{2/3}))$. This describes known algorithmic performance, not a proof that efficient classical factoring is impossible or that every large integer is difficult.

Choose $a$ with $1<a<N$. A nontrivial greatest common divisor $\gcd (a,N)$ already supplies a factor; otherwise find the multiplicative order $r$ of $a$ modulo $N$. If $r$ is even and $a^{r/2}\not\equiv -1(\mathrm{mod}N)$, thenMinimality of the order also excludes $a^{r/2}\equiv 1(\mathrm{mod}N)$, so factor extraction from an even modular order gives nontrivial factors through $\gcd (a^{r/2}\pm 1,N)$. Unhelpful choices of $a$ or odd orders require another trial. For $N=15$, $a=2$ has successive residues $1,2,4,8$ and order four, givingComputing the powers is easy by repeated squaring; discovering a large order is the step accelerated by Shor's algorithm.^[ref]

Put $Q=2^L$ and suppose $Q\ge r$. For each residue class $s=0,\dots ,r-1$, letThese are normalized uniform superpositions of the arguments with the same modular-exponentiation value. Their amplitudes repeat at separation $r$ within the finite register window. Exact cyclic periodicity requires $r\mid Q$. The correctly normalized entangled register state isThe equal prefactor $1/\sqrt{r}$ in the displayed algorithm is exact when $r\mid Q$, for then every $n_s=Q/r$. It is not generally exact for an arbitrary unknown order. A physical implementation uses quantum modular exponentiation as a reversible map; its specified action on second-register input zero is extended to a unitary operator on the whole register space.

For the illustrative $N=15$, $a=2$ and $Q=16$, the four first-register states areApplying the positive-sign quantum Fourier transform to the general state givesThe bracket is a finite geometric Fourier amplitude. If $r\mid Q$, it vanishes unless $k=\ell Q/r$ for $\ell =0,\dots ,r-1$, when it equals $Q/r$. HenceThe second-register states are orthogonal, so their different phases do not change the marginal first-register probabilities. Measurement givesIn the $Q=16$ example the possible outcomes are $0,4,8,12$. A nonzero observed ratio $k/Q$ estimates $\ell /r$, not a prime factor directly. Reducing it gives denominator $r/\gcd (\ell ,r)$; repeating avoids uninformative outcomes or recovers missing order factors. For example, $k=4$ or $12$ gives denominator four, whereas $k=8$ alone gives only two.

When $r\nmid Q$, the Fourier probabilities have narrow peaks near $k/Q=\ell /r$ instead of support only on an exact reciprocal grid. The general marginal distribution isChoosing $Q\ge N^2$ supplies the usual precision for continued-fraction recovery in quantum order finding: a nearest grid sample differs from the target rational by at most $1/(2Q)<1/(2r^2)$. Candidate denominators and extracted divisors are checked classically, and repetitions provide useful samples. The small $Q=16$ example works exactly because its order divides the register size; it is not a general precision guarantee for factoring every four-bit integer.

A sufficiently large reliable quantum computer would undermine RSA by efficient factorization. The related discrete-logarithm algorithm also threatens Diffie-Hellman key exchange and elliptic-curve public-key schemes. This does not imply that every communication scheme or symmetric cipher is broken by the same algorithm; post-quantum cryptography studies alternatives based on other problems. The mathematical speedup assumes a scalable quantum computation with enough precision and error control, not merely a small demonstration of factoring fifteen.

Nielsen's pure-state conversion theorem concerns exact deterministic transformations of bipartite pure states by local operations and classical communication. Let $\lambda (\psi )$ be the decreasing vector of squared Schmidt coefficients, equivalently the eigenvalues of either party's reduced density matrix, padded with zeros when necessary. ThenThe majorization relation means ${\sum }_{j=1}^k{\lambda }_j(\psi )\le {\sum }_{j=1}^k{\lambda }_j(\chi )$ for every $k$, with equality for the total sum. The direction allows a maximally entangled state to become a product state, not the reverse. Local-unitary invariance of reduced-state spectra alone would require equality of all the weights; measurements and communicated outcomes permit this larger class of conversions. A comparison of entanglement entropies alone is not a sufficient test in higher dimension.^[ref]

For the supplied states, the weight vectors and cumulative sums areAt $k=2$, $0.8>0.75$, violating the required inequality. The desired conversion is impossible with certainty using LOCC alone. The reverse conversion also fails, already at $k=1$, so these states are incomparable under this deterministic ordering.

Taking a tensor product with the catalyst multiplies every original weight by each catalyst weight. Regrouping the two local systems on Alice's side and the two on Bob's side leaves a Schmidt decomposition across the Alice–Bob partition. After sorting, the resulting weight vectors areThe actual nonnegative Schmidt amplitudes are $\sqrt{x_j}$ and $\sqrt{y_j}$; the displayed numbers are their squares. The cumulative sums areEvery component obeys $X_k\le Y_k$, so $x\prec y$. HenceThe final catalyst is exactly its initial state and is uncorrelated with the desired output. It can therefore be returned and reused. This is entanglement catalysis; it is stronger than merely retaining the same catalyst marginal while leaving correlations with the output.^[ref]

For the maximally entangled two-level auxiliary state, the sorted input weights are $(0.2,0.2,0.2,0.2,0.05,0.05,0.05,0.05)$, while the output weights are $(0.25,0.25,0.125,0.125,0.125,0.125,0,0)$. Their first four sums are $0.8$ and $0.75$. This maximally entangled auxiliary state cannot catalyze the conversion while being returned unchanged.

Nevertheless, $(0.5,0.5)\prec (0.6,0.4)$, so it can first be converted deterministically into the nonmaximal catalyst. The desired conversion can then proceed, after which Alice and Bob can return $|\varphi ⟩$, rather than the borrowed maximally entangled state. Turning that returned pair alone back into a maximally entangled pair would increase its entanglement entropy and is forbidden by LOCC. No joint restoration procedure can both keep the exact desired $|{\psi }_2⟩$ and return the original maximally entangled auxiliary state deterministically: its composition with the preceding steps would contradict the failed four-weight inequality above.

Set $N=2^n$, $a=N^{-1/2}=\sin t$ and $c=\cos t$, with $N>1$. The ordered vectors $|w⟩,|s⟩$ are normalized but nonorthogonal, since $⟨w|s⟩=a$. Their coordinate Gram matrix is thereforeAn operator matrix in this basis is obtained from the coefficients in the images of its basis vectors, not by treating those vectors as orthogonal measurement outcomes. Directly applying the two reflection operators givesTheir columns are consequentlyThese are physical unitary operators even though the coordinate matrices are not unitary in the ordinary Euclidean coordinate norm: they preserve $S$, so $U^{†}SU=S$.

The Grover iteration in a nonorthogonal basis isIt has determinant one and trace $2-4a^2=2\cos 2t$, hence eigenvalues $e^{\pm 2it}$. For example, the invertible matrix of eigenvectorssatisfiesThis diagonalization is exact for $N>1$; no large-$n$ approximation is needed.

To extract an actual probability using the Born rule, introduce the orthonormal unmarked superposition $|b⟩=(|s⟩-a|w⟩)/c$. In the ordered basis $|w⟩,|b⟩$, the same iteration is the rotationAfter $r$ iterations,Equivalently the original coordinates are $[\sin (2rt)/c,\cos ((2r+1)t)/c{]}^T$. The overlap with $|w⟩$ is the first coordinate plus $a$ times the second, recovering the same amplitude. Squaring just the first coordinate would be incorrect in a nonorthogonal basis.

For large $n$, $t\simeq N^{-1/2}$, and dropping the initial angle $t$ gives the requested approximation $P_r\simeq {\sin }^2(2rt)$. The first near-unit success occurs at the integer closest to $\pi /(4t)-1/2$:One can choose $r_{\mathrm{opt}}=\lfloor \pi /(4t)\rfloor$, with either neighbor equivalent in a tie. Further iterations overshoot and reduce success rather than monotonically improving it. The special $N=1$ problem needs no search and the two-vector coordinate construction becomes singular.

For an unstructured search, a reversible Boolean quantum oracle implements a phase change on the marked entry, while the diffusion reflection about a uniform state is known. Repeating the pair of reflections amplifies the marked amplitude and measurement yields a candidate that can be checked by another oracle query. The bounded-error query count is $O(\sqrt{N})$ for one marked item, compared with classical $\Theta (N)$ queries. It is a quadratic oracle-query speedup: state preparation, the cost of implementing the oracle and access to a classical database still matter. The method does not reveal an unknown marked value without the promised query access.^[ref]

In a deterministic local hidden-variable model, write $C^{+}(R,\lambda )$ or $D^{+}(I,\lambda )$ without an argument for the remote splitter setting. That omission is the parameter independence assumption: the local response for a fixed complete hidden state does not change when the other wing changes its apparatus. Measurement independence also requires the hidden-state ensemble to be independent of the freely selected settings, allowing the same $\lambda$ assignments to be compared across configurations.

The zero probabilities derived above then constrain those assignments, apart from sets of hidden states of zero measure:

For a trial with $D^{+}(I,\lambda )D^{-}(I,\lambda )=1$, the last two implications force $C^{+}(R,\lambda )=C^{-}(R,\lambda )=1$, contradicting the first condition. Thus these deterministic local assignments predict zero probability for the double-$D$ event, whereas quantum theory predicts $1/16$. This is Hardy's paradox, an inequality-free ideal contradiction. With imperfect apparatus the zero-event conditions become small nonzero rates and require a statistical inequality rather than declaring a contradiction from one imperfect detection.^[ref]

The logical contradiction combines counterfactual hidden-variable assignments; it does not assign simultaneously observed path properties to a quantum state. Nor does it allow a message to be sent by changing a distant splitter: the observable local marginal obeys quantum no-signalling. For example, fixing the plus-side splitter to $I$ gives $P(D^{+})=1/8$ for either minus-side setting in the results above.

Outcome determinism means that a complete hidden state $\lambda$, together with the chosen measurement settings, fixes each outcome. The observed probabilities can still arise from an ensemble of unknown $\lambda$. This differs from deterministic unitary evolution of a wavefunction, which does not by itself specify a unique measurement outcome. Quantum nonlocality means failure of a Bell-local account of the correlations, under assumptions including measurement independence; it is stronger than the existence of entanglement and does not imply controllable faster-than-light signaling.

Use the first ket for the Positron and the second for the electron. Before either final beam splitter, the first pair of splitters and annihilation produceThe photon state $|\gamma ⟩$ is orthogonal to the surviving charged-particle sector. Its probability is $1/4$, while the remaining sector has squared norm $3/4$. The states below retain that photon amplitude and are normalized over all trials, without conditioning on nonannihilation. For compactness write $|cc⟩=|c^{+}{c}^{-}⟩$, and similarly for $|cd⟩,|dc⟩,|dd⟩$.

Include Alice's detector and environment before taking a partial trace. Ideal measurement produces the global stateOrthogonality of the two record states removes their cross terms from the reduced state of the particles:This nonselective quantum measurement has changed the initially entangled singlet into a separable, classically anticorrelated reduced state. Its entropy is one bit, although the full particles-plus-records state is still pure under the assumed unitary dynamics. The reduced density matrix is an improper mixture; tracing the environment does not by itself assert a literal collapse of that global state.

The Born rule gives Alice outcomes zero and one with equal probability. Conditional on a recorded result, the selective quantum measurement assigns $|01⟩$ or $|10⟩$ to the particles. The unitary measurement coupling and orthogonal records explain decoherence in this basis; they do not supply an additional rule selecting a unique outcome. That is part of the measurement problem. In a collapse postulate the individual outcome is stochastic; other interpretations account for outcome experience differently while retaining these operational probabilities.

When Bob makes the same kind of measurement, the global state becomesTracing both laboratories gives the same reduced matrix, ${\rho }_{AB}^{(2)}={\rho }_{AB}^{(1)}$. Bob has added a correlated record, not restored the lost reduced coherence. If Alice's outcome is known, Bob's opposite outcome is certain in this ideal common basis. Without that record, his marginal is $I/2$, so his outcome remains equiprobable. Alice cannot choose her random result or use this correlation for faster-than-light signalling, consistently with quantum no-signalling.

These common-basis measurements alone do not distinguish quantum predictions from a local source sending opposite preassigned bits. To test that explanation, prepare fresh singlets and let the observers independently choose among incompatible measurement axes before recording each result. For singlet spin measurements along unit vectors $\mathbf{a},\mathbf{b}$, quantum mechanics predicts $E(\mathbf{a},\mathbf{b})=-\mathbf{a}\cdot \mathbf{b}$. The CHSH inequality bounds $|S|\le 2$ for Bell-local models with measurement-independent settings. Choosinggives $S=E(\mathbf{a},\mathbf{b})+E(\mathbf{a},{\mathbf{b}}^{\prime })+E({\mathbf{a}}^{\prime },\mathbf{b})-E({\mathbf{a}}^{\prime },{\mathbf{b}}^{\prime })=-2\sqrt{2}$. A suitable Bell test constrains that class of explanations. Independently chosen settings, control of detection bias and separation of the measurement events matter when interpreting an actual experiment.

If Alice first performs the fixed-axis irreversible measurement described above, the resulting mixed state has $E(\mathbf{a},\mathbf{b})=-a_z{b}_z$ and cannot supply that singlet violation. The incompatible settings must belong to the Bell measurement itself. Moreover, Bell violations do not choose among all interpretations of quantum mechanics: interpretations sharing the Born predictions remain observationally equivalent for this experiment. Objective-collapse modifications could instead require additional interference tests with specified departures from unitary dynamics.

Use the computational basis in the stated order and let the rightmost operation act first. The controlled phase gate is $|0⟩⟨0|\otimes I+|1⟩⟨1|\otimes Z$. From the rotation definition,The control-zero block remains the identity, and the control-one block becomes $X$. ThusThis proves the relation for arbitrary superpositions, rather than only for computational-basis probabilities.

For the second relation write $S=U_{\mathrm{SW}}^{1/2}$. Its central block is $\left(\begin{array}{cc}a& b\\ b& a\end{array}\right)$, with $a=(1+i)/2$, $b=(1-i)/2$. Because $a^2=i/2$, $b^2=-i/2$ and $ab=1/2$, direct multiplication givesMeanwhile $R_z^{(1)}(\pi /2)R_z^{(2)}(-\pi /2)=\mathrm{diag}(1,-i,i,1)$. Multiplying these diagonal matrices and the overall factor $i$ givesThe supplied $S$ is indeed a square root of the SWAP gate: $S^2$ exchanges $|01⟩$ and $|10⟩$ while fixing the other basis states. It acts as one on the triplet subspace and as $i$ on the singlet subspace.

For an isotropic exchange interaction with Hamiltonian $H=J(t){\mathbf{\sigma }}_1\cdot {\mathbf{\sigma }}_2/4$, define $\phi =\int J(t)dt/\hslash$. Triplet and singlet energies differ by $J$, soAn exchange pulse with $\phi =\pi /2$ therefore implements $e^{-i\pi /8}S$. Two such pulses, interspersed with the specified local rotations, implement the controlled phase gate; the initial and final target rotations then turn it into a CNOT gate. Their common overall phase has no effect on an isolated gate's outcome probabilities; a subsequently controlled version must keep track of conditional phases.

The construction converts a physically available two-spin interaction into a standard entangling gate, which together with arbitrary one-qubit rotations supplies universal quantum computation. Practical operation needs calibrated exchange pulse area and timing, individually controllable rotations, and reproducible phase references. Charge noise can change $J$; magnetic-field gradients add unwanted single-spin evolution, and anisotropic exchange modifies the assumed Hamiltonian. Pulses must suppress leakage into unwanted orbital states while finishing before excessive decoherence. Readout, preparation, cross-talk and the extra operations in this decomposition all affect the achieved quantum gate fidelity. The algebraic identity alone does not establish a fault-tolerant quantum computation implementation.