Past exam of the quantum information course of the University of Cambridge / 2014

Original public paper: Physical PDF pages 684–686. All questions and optional notes are covered. The equal-length period-register assumption is distinguished from the general normalized order-finding state.

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.

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.

Consistent histories assigns probabilities to suitably compatible sequences of quantum alternatives without making an external measuring apparatus fundamental. At successive times choose complete orthogonal sets of projection operators. In the Heisenberg picture, a history has class operator $C_{\alpha }=P_{{\alpha }_n}(t_n)\cdots P_{{\alpha }_1}(t_1)$. For an initial density operator $\rho$, its decoherence functional isA common sufficient consistency condition is $D(\alpha ,\beta )=0$ for $\alpha \ne \beta$. Then $p(\alpha )=D(\alpha ,\alpha )$ is nonnegative and coarse-grained alternatives have additive probabilities: the interference cross-terms vanish. The weaker requirement on real cross-terms can suffice for individual probability sum rules. Predictions must stay within one compatible framework; mutually incompatible history families cannot simply be combined into one classical account.

The many-worlds interpretation instead treats unitary quantum evolution as universally valid and interprets the correlated outcome branches as components of one global state. A measurement interaction givesWhen the environment records become nearly orthogonal, quantum decoherence suppresses observable interference between stable apparatus records. Each relative state contains an observer correlated with a definite record; no additional physical collapse is postulated. Branch structure is an emergent approximation, rather than a unique literal splitting at every arbitrary choice of basis.

Both approaches use the ordinary unitary formalism and decoherence, but their interpretations of histories and branches differ. Decoherence alone does not prove that one unique branch is selected, nor does the unitary equation by itself settle every assumption needed to justify Born rule probabilities. Neither interpretation predicts ordinary interference experiments incorrectly merely by interpreting the same state differently.

In quantum teleportation, Alice transfers an arbitrary unknown qubit $|\chi ⟩=\alpha |0⟩+\beta |1⟩$ using one shared Bell pair and two bits of classical communication. Define $|{\beta }_{mn}⟩=(I\otimes X^n{Z}^m)|{\Phi }^{+}⟩$, with $m,n\in \{0,1\}$. Regrouping the initial three-qubit state into this Bell basis givesAlice's Bell-basis measurement selects each label with probability $1/4$. She sends $(m,n)$ to Bob, who applies the inverse $Z^m{X}^n$, restoring $|\chi ⟩$. The correction depends on the measurement label, not on the unknown amplitudes. Before the message, Bob's average state is $I/2$, independent of the input; quantum no-signalling therefore prevents superluminal communication. The shared pair is consumed and Alice does not retain an independent copy, in agreement with the no-cloning theorem.

The Bouwmeester quantum teleportation experiment used photon polarization, a down-conversion entangled pair, a beam-splitter Bell-state analyzer and coincidence-conditioned output polarization measurements. Temporal indistinguishability of the two analyzer photons was essential. Its successful selected Bell outcome demonstrated the state transfer, rather than a deterministic implementation of all four outcomes.^[ref]

The general experimental tasks are to distribute entanglement, prepare and synchronize the input, perform a sufficiently discriminating joint measurement, communicate the label and apply or account for the correction. A demonstration must test nonorthogonal input states, not merely transfer a known classical basis label. Finite efficiency, accidental coincidences, distinguishability and phase drift reduce success probability or teleportation fidelity. Postselected verification, a heralded usable output and unconditional deterministic teleportation are distinct experimental claims.

Schrödinger's cat exposes the quantum measurement problem by correlating a microscopic alternative with macroscopically distinct records. Under unitary evolution a schematic state becomesThe difficulty is explaining why a definite macroscopic outcome is observed if the isolated total state is always governed by the linear Schrödinger equation. It is not a claim that one classically contradictory record has literally been observed. Environmental interactions rapidly entangle the records with different environment states, making their reduced density matrix approximately diagonal. That explains the practical loss of interference but does not, by itself, turn a global pure superposition into a selected single branch.

Wigner's friend places an observer's physical memory inside the quantum description. A friend measuring $|+⟩=(|0⟩+|1⟩)/\sqrt{2}$ can become correlated asConditioned on one friend record, the corresponding relative state contains a definite outcome. An external observer applying unitary theory to the perfectly isolated entire laboratory instead assigns the entangled vector $|\Psi ⟩$. In principle, a coherent joint measurement could distinguish it from the collapsed mixturewhereas projecting the pure state onto $|\Psi ⟩$ succeeds with probability one. Preserving that laboratory coherence, including all records and environment correlations, is an extreme idealization for macroscopic observers.

The paradox concerns how state assignment, definite records and universal unitary dynamics fit together. It does not show that an observer can send messages faster than light or that consciousness must be given a special dynamical role. The many-worlds interpretation retains the global unitary state with branch-relative records; interpretations with a physical collapse must specify when and how unitary evolution changes. Stating the chosen assumptions prevents the friend's conditional state and the external observer's unconditioned state from being treated as the same mathematical object.