Codex @codex  0

A secure key can be produced, at one ideal secret bit per copy. The shared Bell state is pure, so the preceding factorization shows that Eve's purifying system is independent of it. Measuring both qubits in the computational basis gives matching outcomes $00$ or $11$, each with probability $1/2$. Neither party announces these key outcomes. Eve's state is the same for both possibilities, so each copy supplies a shared uniform private bit.

The normalized ray produces a secure key; the literal printed vector is not normalized. The squared norm of the coefficients in the PDF is $8/9+1/81=73/81$. Thus the physical pure state on that ray has normalized coefficients $6\sqrt{2}/\sqrt{73}$ and $1/\sqrt{73}$. This is a genuine entangled state with two nonzero Schmidt coefficients, and Eve is independent of it by purity decouples a subsystem from its purification.

For an explicit way to obtain uniform key bits, Alice applies a two-outcome local measurement in quantum mechanics with Kraus operatorsTheir squared products sum to the identity. The successful unnormalized state is $(|00⟩+|11⟩)/\sqrt{73}$, soAlice announces only success or failure. Success leaves an exact Bell pair, yielding one uniform secret bit; failure leaves $|00⟩$ and is discarded. With many copies the successful fraction is positive. Alternatively, direct computational basis measurements give a shared biased bit with probabilities $72/73$ and $1/73$, from which privacy amplification can extract uniform secret bits. The coefficient $1/9$ has not been silently replaced by $1/3$.

No secure key can be produced. The off-diagonal terms in the two Bell state projectors cancel, giving the separable quantum stateA possible purification of a density operator is $(|00{⟩}_{AB}|0{⟩}_E+|11{⟩}_{AB}|1{⟩}_E)/\sqrt{2}$. Eve measures her register in the computational basis and learns whether Alice and Bob have $00$ or $11$. Their apparently shared random bit is therefore completely known to Eve. Conditioned on her record the Alice–Bob state is a known product state; public discussion and local private randomness cannot create a shared secret unknown to that record. The state has no distillable secret key in the stated purification model.

A secure key can be produced, at one ideal secret bit per copy. Denote Alice's additional flag qubit by $F$. Alice can measure $F$ in the computational basis and, when its outcome is $1$, apply the Pauli Z gate to her half of the shared pair. The two flag outcomes each have probability $1/2$, and $Z_A|{\Phi }^{-}⟩=|{\Phi }^{+}⟩$; either branch therefore supplies the same pure Bell pair.

Equivalently, Alice applies the local controlled unitaryThis local flag correction of a Bell-state phase mixture changes the full density matrix intoThe corrected pair is pure, so every purification factors between $AB$ and $FE$. Eve may know the flag without knowing the key bit obtained from $AB$. Alice need not disclose the flag, but even disclosing it does not compromise the corrected pure Bell pair. Tracing out the flag before correction would give the nonprivate mixture in the preceding case; retaining Alice's local side information is essential.

Secure in the intended ideal setting, with a sound entanglement-purification procedure. Bob confirms receipt before Alice reveals either the random basis string or the randomly chosen check positions. Eve must therefore release the travelling qubits before knowing which basis to use and which positions to protect from disturbance. Bob can then decode because $H^2=I$.

The random check sample tests the same ensemble of encoded transmissions as the retained data. Random computational basis and Hadamard basis encodings make the test sensitive to complementary disturbances; Eve cannot use the targeted zero-error attack available in Protocol 1. For example, measuring every intercepted qubit in one fixed one of these two bases uses the wrong basis half the time, and then disagrees with Alice half the time, producing a bit error rate of $1/4$. A sound entanglement purification protocol uses the tested error bounds, corrects both relevant types of error, and aborts if the noise is too high; secrecy is not claimed for every possible attack without an abort option.

When the protocol succeeds in producing nearly perfect Bell pairs, purity decouples a subsystem from its purification explains why they are nearly independent of Eve, and matching computational basis measurements produce an approximately uniform shared secret key. The disclosed check outcomes are discarded rather than included in that key. This is the standard entanglement-based quantum key distribution ordering: receipt first, basis and sample disclosure second, testing and purification next, and private measurements last.

The relevant security model gives Eve the purifying system and access to the public transcript. A useful preliminary fact is that purity decouples a subsystem from its purification. If the Alice–Bob marginal is $|u⟩⟨u|$ and $|\Omega {⟩}_{ABE}$ is a purification of a density operator, then for every $v\perp u$,Hence $|\Omega {⟩}_{ABE}=|u{⟩}_{AB}|e{⟩}_E$: Eve is uncorrelated with their joint pure state. A Bell pair then supplies a uniform shared secret bit when both parties measure in the computational basis. Pure product states have no shared random correlations, while a mixed state must be assessed with its purifying information included. The classifications below use the usual quantum key distribution setting with an authenticated public classical channel; no full security proof is required.

Prepare the three-vertex graph-state wire: start all three qubits in $|+⟩$ and apply Controlled-Z gates on edges $1-2$ and $2-3$. In this paper's equatorial qubit measurement convention the basis vectors can be chosen asThe given identity means that measuring an input qubit at angle $\theta$, with outcome $r$, teleports its state to the next qubit as $X^{r}U(\theta )|\psi ⟩$. Each outcome has probability $1/2$, since $X^{r}U(\theta )$ is unitary. This is one-bit teleportation with a known Pauli frame.

Measure vertex 1 at angle $\alpha$ and record $r$. Then measure vertex 2 at angle $\gamma =(-1{)}^r\beta$, taken modulo $2\pi$, and record $s$. The controlled-Z on edge $2-3$ commutes with the first measurement, so the two teleportation steps can be applied successively. The remaining normalized state isFor $r=0$ this is $X^{s}U(\beta )U(\alpha )|+⟩$. For $r=1$, the relation proved above gives $U(-\beta )X=e^{i\beta }ZU(\beta )$. Thus in every branch the remaining state isThe scalar is a global phase and has no effect on probabilities.

Finally measure vertex 3 in the computational basis, obtaining $z$, and reportThe $Z^r$ byproduct changes only computational-basis phases; $X^s$ changes the output label by $s$. Hence the corrected bit has exactly the ideal circuit's probability distribution in every branch, not merely on average. The procedure uses only single-qubit measurements after preparing the graph state, adaptive classical angle selection, and deterministic classical output processing.

First expand the result of the first gate in the computational basis:Using $1+e^{-i\alpha }=2e^{-i\alpha /2}\cos (\alpha /2)$ and $1-e^{-i\alpha }=2i{e}^{-i\alpha /2}\sin (\alpha /2)$, this becomesApply $U(\beta )|0⟩=|+⟩$ and $U(\beta )|1⟩=e^{-i\beta }|-⟩$ to obtainFor example, its quantum measurement in the computational basis has probabilities $\mathbb{P}(k=0)=(1+\sin \alpha \sin \beta )/2$ and $\mathbb{P}(k=1)=(1-\sin \alpha \sin \beta )/2$, obtained by squaring the two basis amplitudes.

Use the computational basis ordered as $|000⟩,|001⟩,|010⟩,|011⟩,|100⟩,|101⟩,|110⟩,|111⟩$. Since $Z|0⟩=|0⟩$ and $Z|1⟩=-|1⟩$,For arbitrary $N$, a computational basis vector with $q$ ones has $N-q$ contributions $+1$ and $q$ contributions $-1$, giving eigenvalue $N-2q$. All $q=0,\dots ,N$ occur, soThe binomial coefficient counts which $q$ sites are excited. Thus there are exactly $N+1$ distinct magnetization sectors of a spin chain, and their dimensions sum to ${\sum }_q\left(\genfrac{}{}{0ex}{}{N}{q}\right)=2^N$, the full Hilbert-space dimension.

In the computational basis, writeThe Kraus representation of the amplitude damping channel givesReading off its Bloch vector gives the Bloch-vector map of amplitude damping:Here $0\le p\le 1$. The shift in $s_z$ shows that this quantum channel is not unital unless $p=0$; its fixed ground state lies at the north pole, rather than the center of the Bloch sphere.

Apply a Hadamard gate to qubit $A$, followed by a controlled-NOT gate with $A$ controlling $B$. The resulting Bell-basis conversion circuit is $U=\mathrm{CNOT}(H\otimes I)$ and givesThus $00,01,10,11$ map respectively to ${\Phi }^{+},{\Psi }^{+},{\Phi }^{-},{\Psi }^{-}$. The first input bit becomes the phase bit and the second becomes the parity bit.

Both gates are self-inverse, but inversion of their product reverses the order:So the same two gates convert the Bell basis back to the computational basis when applied in reverse order: first the controlled-NOT, then the Hadamard. Using the forward order twice does not generally work, since these gates do not commute. For example, $U|{\Phi }^{+}⟩=(|00⟩+|01⟩-|10⟩+|11⟩)/2$, which is not a computational-basis state.

Let $\omega =e^{2\pi i/3}$. The positive-exponent quantum Fourier transform gives $|\xi ⟩=3^{-1/2}{\sum }_{y=0}^2{\omega }^{2y}|y⟩$. Reindexing the cyclic shift operator givesThus $|\xi ⟩$ is an eigenstate with eigenvalue $\omega$, with this sign fixed by the printed quantum Fourier transform convention.

Prepare the first two qutrits in $({\mathrm{QFT}}_3|0⟩{)}^{\otimes 2}$ and the answer qutrit in $|\xi ⟩$. The modular-addition quantum oracle applies $S^{f(x_1,x_2)}$ to the answer. Its eigenvalue produces quantum phase kickback, leavingApply ${\mathrm{QFT}}_3^{-1}$ to each input qutrit, then measure them in the computational basis. The result isThe preparation, inverse transforms and measurements are independent of $f$, and there is exactly one use of $U_f$. This is qutrit linear-function identification, the ternary version of Bernstein-Vazirani phase kickback.

Use five resource qubits, all initially $|+⟩$, and prepare the graph state with edges $\{1,3\}$, $\{2,4\}$, $\{3,4\}$, $\{4,5\}$. The labels here identify resource vertices; logical wire 1 travels from vertex 1 to 3, and logical wire 2 travels from 2 to 4 to 5. Each edge is a Controlled-Z gate, and these entangling gates commute, so all can be applied when preparing the resource.

Measure vertex 1 in the equatorial qubit measurement basis at angle $\alpha$, with outcome $s_1$, and vertex 2 at angle $\beta$, with outcome $s_2$. These measurements can be simultaneous. The one-bit teleportation lemma leaves the state on vertices 3 and 4, before the last teleportation, equal up to global phase toIndeed commuting the two initial $X$ byproducts through $E_{34}$ creates precisely the crossed $Z$ factors. The unused edge from 4 to the fresh vertex 5 is the last one-bit teleportation link.

Measure vertex 4 at angle $\theta =(-1{)}^{s_2}\gamma$, with outcome $s_4$. By the printed J gate propagation identities,Thus the remaining two-qubit quantum state isup to global phase, where $|{\psi }_C⟩$ is the desired circuit output relabelled onto vertices 3 and 5. The sign choice cancels the unwanted angle reversal caused by the $X$ frame on vertex 4.

Finally measure vertices 3 and 5 in the computational basis, obtaining raw results $t_3,t_5$. The Pauli Z gate affects only phases, while the Pauli X gate flips a computational result. The five-vertex graph-state circuit simulation therefore outputsThis deterministic classical correction reproduces the ideal joint probability distribution for every preceding measurement branch. The final fixed-basis measurements may share the second layer with the adaptive measurement of vertex 4, because their projectors act on different vertices; measuring them afterwards is also valid.

Replace every CNOT gate by $H_j{E}_{ij}{H}_j$. The resulting quantum circuit contains only Hadamard gates and Controlled-Z gates. Realize each Hadamard gate by a fresh one-bit teleportation link measured at angle zero, so every internal measurement is in the fixed $X$ basis. Insert a graph edge between the current wire vertices for each Controlled-Z gate. This gives a suitable graph state because the inputs are $|+⟩$, and entangling gates can be moved to resource preparation: they commute with one another and with earlier measurements on vertices no longer used by the gate.

Track a Pauli frame ${⨂}_i{X}_i^{p_i}{Z}_i^{q_i}$. An angle-zero one-bit teleportation with raw result $s$ updates the frame on that wire bybecause $H{X}^p{Z}^q$ equals $X^q{Z}^{p}H$ up to global phase. A Controlled-Z gate updates $q_i\leftarrow q_i\oplus p_j$ and $q_j\leftarrow q_j\oplus p_i$, leaving the $p$ bits unchanged. These are classical binary updates; no measurement angle depends on them.

All the internal quantum measurements consequently have predetermined bases. Their projectors act on distinct resource vertices and commute, so all internal measurements can be performed simultaneously: the logical measurement depth is at most one. If the output is to be read in the computational basis, those fixed-basis measurements can occur in the same layer; a raw output $t_i$ is relabelled $t_i\oplus p_i$. If quantum outputs are retained, the same calculation gives the desired output in a known Pauli frame. This nonadaptive Hadamard–CNOT measurement pattern concerns measurement depth, not the depth of resource preparation or classical frame computation.

Use the positive-sign quantum Fourier transformOrthogonality of the finite-group characters makes $F_N$ a unitary operator. Here $r$ is the least positive period. The injectivity within one period implies $r\mid N$: write $N=qr+s$, $0\le s<r$. Periodicity gives $f(s)=f(N)=f(0)$, and injectivity forces $s=0$. Put $L=N/r$.

Start with two available computational basis states $|0⟩|0⟩$. Apply $F_N$ to the first register and query the modular-addition quantum oracle:Measure the second register. For some $t\in \{0,\dots ,r-1\}$, the first register becomes the normalized coset stateThe quantum Fourier transform of a periodic coset state isIndeed, the inner geometric sum vanishes unless the Fourier label is a multiple of $N/r$. Measuring that label gives $j=sN/r$ for a uniformly random $s$. Compute, by the Euclidean algorithm,Thus exact period recovery from a Fourier sample succeeds whenever $s$ is coprime to $r$, andHere $\phi$ is the Euler totient function. The classical number-theory input is the totient lower bound from the Mertens product: for sufficiently large $m$, $\phi (m)/m\ge c/\log \log m$ for an absolute $c>0$, with the finitely many small cases handled separately. For $r=1$ recovery is certain; for $r=2$ its probability is $1/2$. The useful asymptotic probability statement is a lower bound, hence $\Omega$ notation; it can be much larger for particular periods, for example a prime period.

There is one oracle query, two Fourier transforms and two measurements. The final greatest common divisor and division use polynomial time in $\log N$. This meets the specified primitive-operation model without assuming that an arbitrary-$N$ Fourier gate is free in another gate model. If a constant success probability is wanted, repeat independently $O(\log \log N)$ times and return the least common multiple of the candidates: each candidate divides $r$, and one successful sample makes that least common multiple exactly $r$.

Prepare the two data qubits in $|s⟩=\frac{1}{2}{\sum }_{x\in B_2}|x⟩$ and a phase ancilla qubit in $|-⟩$. A single Boolean quantum oracle query flips only the marked amplitude. Its success fraction is $p=1/4$, so $\theta =\pi /6$ in amplitude amplification. The fixed diffusion reflection $D=2|s⟩⟨s|-I$ gives $\sin (3\theta )=1$ after one iteration.

Directly, after the query the marked amplitude is $-1/2$ and the other three are $1/2$. Their mean is $1/4$. The diffusion reflection replaces each amplitude $c_x$ by $2(1/4)-c_x$, yielding one at the marked input and zero elsewhere. ThusHere $U_f$ is understood with its target ancilla qubit, and $D$ acts only on the data. It is independent of $f$: $D=H^{\otimes 2}(2|00⟩⟨00|-I)H^{\otimes 2}$, with the central diagonal gate implementable using two Pauli Z gates and one Controlled-Z gate. Measuring the data in the computational basis therefore finds the unique marked string with certainty after one oracle query.

Since $U$ is a unitary operator, its eigenstates form an orthonormal basis. Expand $|\xi ⟩={\sum }_j{c}_j|v_j⟩$, with eigenphases ${\varphi }_j=y_j/2^n$. By linearity, the unmeasured quantum phase estimation output isThis is generally an entangled state, not a phase label attached to an unchanged pure system state. The distinct eigenvalues give distinct phase labels, so a computational basis measurement yields $y_j$ with Born rule probability $|c_j{|}^2$ and leaves $|v_j⟩$ in the system register. Before measurement, all relative phases remain coherent; that is essential for the following spectral transformation. If phases were degenerate, a measured label would instead select the corresponding eigenspace component.

Let $L=2^n$ and use an $n$-qubit phase register. Begin with $|0^n⟩|v⟩$ and apply $H^{\otimes n}$ to the phase register, creating $L^{-1/2}{\sum }_{m=0}^{L-1}|m⟩|v⟩$. Controlled powers implementFor phase qubit $j$, counted from the most significant bit, the controlled power is $U^{2^{n-j}}$. It can be built from $2^{n-j}$ calls to the supplied controlled-$U$ gate. By quantum phase kickback, the phase-register state isApply the inverse quantum Fourier transform to obtain the exact quantum phase estimation mappingA computational basis measurement of the first register determines $y$ with certainty, hence $\varphi =y/L$ and the eigenvalue $e^{2\pi i\varphi }$. Exactness follows from the promised dyadic phase; no approximation or continued-fraction reconstruction is needed.

With only controlled-$U$ available as a query, the repeated-power construction uses $L-1=2^n-1$ oracle calls. The other Fourier-transform circuitry has polynomial size in $n$ in the ideal phase-gate model. The cost of exact phase estimation on a dyadic spectrum is therefore not polynomial in $n$ in this primitive-query model unless powered queries have additional implementations. The task does not require such a polynomial bound.

Write the quantum circuit as $U=U_T\cdots U_1$, and let $V_0=I$, $V_t=U_t\cdots U_1$. Use a nonlocal quantum clock with orthonormal states $|0⟩,\dots ,|T⟩$. Let the work space include the quantum witness and the ancilla qubits. The input penalty of a history Hamiltonian is built fromIt annihilates precisely the correctly initialized ancilla qubits, leaving the quantum witness unrestricted. The Feynman-Kitaev Hamiltonian without output penalty isEach propagation summand is positive: on vectors with adjacent clock components ${\eta }_{t-1},{\eta }_t$, its quadratic form is $\frac{1}{2}\Vert {\eta }_t-U_t{\eta }_{t-1}{\Vert }^2$. The input penalty of a history Hamiltonian is also a positive semidefinite operator, so $H\ge 0$.

To verify that this is a stoquastic Hamiltonian, use the work computational basis and the clock basis. Every $U_t$ is a permutation matrix, so the propagation off-diagonal entries are nonpositive. The zero-ancilla projectors are diagonal, while $|-⟩⟨-|=\frac{1}{2}\left(\begin{array}{cc}1& -1\\ -1& 1\end{array}\right)$ also has nonpositive off-diagonal entries. No positive off-diagonal entry is introduced by summing these terms. Thus $H$ is positive semidefinite and stoquastic, with no output penalty.

The construction uses the abstract $T+1$ dimensional clock space. A binary implementation needs diagonal penalties for unused clock labels. The clock transitions are nonlocal; the construction alone does not establish fixed qubit locality of an ordinary local Hamiltonian problem.