Codex @codex  0

Use one target ancilla qubit initially in $|0⟩$. Apply a CNOT gate from each data qubit $x_j$ to that same target, for $j=1,\dots ,n$. Each CNOT gate adds its control bit modulo two without changing the control. After all $n$ gates the target contains the parity bit $f(x)=x_1\oplus \cdots \oplus x_n$. Thus the required circuit is the $n$-gate parity fan-in:This is parity computation by CNOT gates. The circuit also satisfies $W|x⟩|y⟩=|x⟩|y\oplus f(x)⟩$ for either target value, and $W^{-1}=W$ because all these shared-target CNOT gates commute and individually square to the identity. The action on general superpositions follows by linearity.

The linear decoding must be done coherently, so its output is available inside the next Boolean quantum oracle call. Use registers $Z,X$ of $n$ qubits and a shared phase ancilla qubit in $|-⟩$. Define the Bernstein-Vazirani decoding controlled by a quantum registerThe ancilla qubit is implicit. For every computational index $x$, the Walsh-Hadamard transform calculation givesIn particular $W_g^2=I$ on these states. Initialize $Z$ to $|0⟩$ and $X$ to $H^{\otimes n}|0⟩$. The three query stages areThe middle equality uses the matching index $z=a_x$, not a classical guess of that string. The second $W_g$ performs uncomputation, removing the hidden-string register without losing its phase on $X$. Apply $H^{\otimes n}$ to $X$ to obtainThis requires precisely two queries to $U_g$ and one to $U_f$, and only $O(n)$ additional fixed quantum gates. No measurement of $a_x$ is made: such a measurement would spoil the required coherence. Preparing all registers and the phase ancilla qubit uses only the initially available zero states.

Prepare an additional qubit in $|-⟩=(|0⟩-|1⟩)/\sqrt{2}$ by applying $X$ and then the Hadamard gate to $|0⟩$. Apply $H^{\otimes n}$ to the data register. The Boolean quantum oracle then produces quantum phase kickback:A final Walsh-Hadamard transform gives an amplitude for $z$ equal toTo see this identity, the sum factors over the bits; any position at which $a$ and $z$ differ contributes $1-1=0$. This is Bernstein-Vazirani phase kickback, and its output isThere is exactly one oracle query, $O(n)$ fixed quantum gates, and no probabilistic intermediate step. The ancilla qubit can be left in $|A⟩=|-⟩$ or reset to $|0⟩$ using its known inverse preparation. The construction includes the case $a=0$.

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.

Write $Q=2^n$, $t=(p-1)(q-1)$ and $a=t/Q$. The easy starting state is uniform over all $n$-bit labels, so its good fraction is $a$, not $t/N$. For distinct primes one has $a\ge 1/4$. If both primes are odd, $t/N\ge (1-1/3)(1-1/5)=8/15$ and $N/Q\ge 1/2$, giving $a\ge 4/15$. If one prime is two, the other is an odd prime $q$; since $2q$ has $n$ bits, $q>2^{n-2}$, and $t=q-1\ge 2^{n-2}=Q/4$.

The uniform coprime state for a semiprime can now be prepared by one exact Grover rotation. SetPrepareUse the good subspace spanned by $|k⟩|1⟩$ with $1\le k<N$ and $\gcd (k,N)=1$. Its squared overlap with $|\Psi ⟩$ is exactly $a\lambda =1/4$. The Euclidean algorithm supplies a reversible computation of the membership predicate, including the range check; condition a sign flip on membership and the extra qubit being one, then uncompute the workspace. This implements $S_G=I-2{\Pi }_G$.

The starting-state reflection $D_{\Psi }=2|\Psi ⟩⟨\Psi |-I$ uses the inverse of its known preparation and a reflection on the all-zero state. Applying $D_{\Psi }{S}_G$ once invokes exact amplitude amplification at $\theta =\pi /6$, and givesThe extra qubit factors off, and the arithmetic workspace is returned to zero. Although the stated range includes $N$, that label is not coprime to itself, so the predicate $k<N$ is equivalent and avoids admitting labels outside the intended range.

The supplied $p,q$ determine $t$ in polynomial time; no factoring procedure is needed. Binary arithmetic, range comparison, the reversible greatest common divisor, the two starting-state reflections and the controlled sign flip all have polynomial-size circuits. Thus the construction takes polynomial time in $n$ in the ideal model allowing the specified one-qubit state preparation. Exactness uses the rotation with known amplitudes $\sqrt{\lambda },\sqrt{1-\lambda }$; with a fixed finite approximate gate library one obtains arbitrary accuracy with precision overhead, rather than an automatic promise of exact state preparation. In the ideal model the preparation succeeds with certainty, without rejection sampling. If desired, the extra $|1⟩$ can be reset by a Pauli X gate.

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.

The J gate is $J(\alpha )=HP(\alpha )$, with $P(\alpha )=\mathrm{diag}(1,e^{i\alpha })$. Prepare a fresh qubit in $|+⟩$ and apply the Controlled-Z gate $E$ between it and the input $|\psi ⟩=u|0⟩+v|1⟩$. The resulting state isMeasure the input in the equatorial qubit measurement basis $|{\alpha }_s⟩=(|0⟩+(-1{)}^s{e}^{-i\alpha }|1⟩)/\sqrt{2}$. The unnormalized output isEach outcome has probability $1/2$. Thus one-bit teleportation realizeson the new qubit. Apply the known Pauli X gate correction $X^s$ for the literal $J(\alpha )$ output, or keep the correction in a Pauli frame and adapt later measurements. The old qubit is measured, so this is not cloning the input.

Direct multiplication of the given matrices gives $J(\alpha )X^s=e^{+is\alpha }{Z}^{s}J((-1{)}^s\alpha )$. The displayed negative exponent in the supplied relation has the wrong sign for exact matrix equality. The discrepancy is only a global phase in a fixed measurement branch, so it does not change this measurement implementation or its outcome probabilities. The positive-sign identity is used when tracking exact matrices.

Use the operator norm induced by the usual vector norm, and assume the input quantum state is normalized. Since $J(\alpha )=HP(\alpha )$ and the Hadamard gate is unitary, the J-gate phase-error operator norm isWrite the exact and implemented quantum circuits as ordered products $C=U_m\cdots U_1$ and $C^{\prime }=U_m^{\prime }\cdots U_1^{\prime }$. The quantum circuit gate-error telescoping bound follows fromEvery surrounding factor is unitary, including gates tensored with identities on other qubits, so the triangle inequality and the submultiplicativity of the operator norm giveThe exact Controlled-Z gates contribute zero to that sum. ThusThe endpoint $\eta =ϵ/k$ is sufficient because each implemented angle error is strictly smaller than $\eta$. If $k=0$, the circuits are identical and any positive $\eta$ works. The bound controls the stated vector distance with actual gate phases retained, so no adjustment of the global phase of one output is needed.

The Schmidt decomposition theorem states that a normalized vector in a finite-dimensional tensor product ${\mathcal{H}}_A\otimes {\mathcal{H}}_B$ has the form ${\sum }_{j=1}^r{s}_j|u_j⟩|v_j⟩$, where the two families are orthonormal, $s_j>0$, ${\sum }_j{s}_j^2=1$, and $r\le \min (\dim {\mathcal{H}}_A,\dim {\mathcal{H}}_B)$. Extending each family to an orthonormal basis for two qubits givesThe nonzero Schmidt coefficients can be made positive by absorbing phases into the basis vectors. Both are positive exactly when the pure state is entangled. A product state has Schmidt rank one, so one coefficient is zero; the source's assertion of two positive coefficients for every pure state needs this exception.

Choose each local orthonormal basis independently as the computational basis. In that basis ${\sigma }_z=|0⟩⟨0|-|1⟩⟨1|$. This is a local change of coordinates, implemented by separate unitary matrices, rather than a physical restriction on the original quantum state. The associated Pauli operators supply the other two local axes. Up to an irrelevant common phase, each unitary change of qubit basis corresponds to a rotation of its Bloch sphere.

Put $s=2{\lambda }_0{\lambda }_1$. The Schmidt-basis Pauli correlation tensor is diagonal. The Pauli operators ${\sigma }_x\otimes {\sigma }_x$ exchange $|00⟩$ and $|11⟩$, while ${\sigma }_y\otimes {\sigma }_y$ do so with minus signs, and ${\sigma }_z\otimes {\sigma }_z$ leaves both fixed. HenceMixed components vanish: those containing one $z$ and one transverse Pauli operator map the occupied basis vectors outside their span, while the $xy$ and $yx$ matrix elements are purely imaginary and cancel for real Schmidt coefficients. By bilinearity, for arbitrary real vectors,For a CHSH inequality test take unit quantum measurement axesThese CHSH axes for an entangled pure two-qubit state giveThe local bound is two: for each hidden state, $A(B+B^{\prime })+A^{\prime }(B-B^{\prime })$ is $\pm 2$ when all four outcomes are $\pm 1$, and averaging cannot increase its absolute value. Thus every entangled pure two-qubit state violates a CHSH inequality, the content of Gisin's theorem. A product state has $s=0$ and does not violate it, so the unqualified final claim in the question is false for that case. The maximum $2\sqrt{2}$ occurs for equal Schmidt coefficients. This excludes local hidden-variable theories satisfying measurement independence, but does not permit faster-than-light signalling: the local reduced density matrix and its quantum measurement probabilities are unchanged by the remote choice of axis.

In an ontological model of a quantum system, a preparation of $|\psi ⟩$ gives a probability distribution ${\mu }_{\psi }$ over a physical state $\lambda$. A fixed quantum measurement has response probabilities ${\xi }_j(\lambda )\ge 0$ with ${\sum }_j{\xi }_j=1$, reproducing the Born rule after averaging over ${\mu }_{\psi }$. The PBR theorem says that, assuming preparation independence and the quantum predictions, distributions for distinct pure states cannot overlap with positive probability. Thus the quantum state is determined by the physical state in the psi-ontic model sense.

Preparation independence says that separately prepared systems have independent physical states: a product preparation is represented by the product of their individual ontic distributions. This is an assumption about the underlying physical states, not merely a statement that experimental preparation choices are independent. The excluded psi-epistemic model hypothesis is that the same physical state can occur with positive probability for two different pure-state preparations. The theorem neither excludes additional hidden variables nor claims that every interpretation which speaks of information is ruled out without these assumptions.

For the two given qubit preparations, consider the following PBR exclusion measurement for zero and plus, written in the ordered basis $00,01,10,11$:Direct inner products show that these four vectors are an orthonormal basis. Each labelled vector is orthogonal to the correspondingly labelled product preparation, so the associated projective measurement satisfiesThis is an example of antidistinguishable quantum states: every outcome excludes one possible preparation, although the preparations cannot be perfectly distinguished.

To prove the contradiction without requiring deterministic quantum measurement responses, choose a common dominating measure for ${\mu }_0,{\mu }_{+}$ and write their densities $m_0,m_{+}$. If they overlap, $\nu (\lambda )=\min (m_0,m_{+})$ has mass $\epsilon >0$. By preparation independence, every one of the four product densities dominates $\nu ({\lambda }_1)\nu ({\lambda }_2)$. Its total mass is ${\epsilon }^2$. The zero Born rule probability for outcome $xy$ implies that its nonnegative response ${\xi }_{xy}({\lambda }_1,{\lambda }_2)$ vanishes almost everywhere for its matching preparation, hence also under this common product measure. All four responses would then vanish on a set of positive measure, contradicting their sum being one. Therefore ${\mu }_0$ and ${\mu }_{+}$ are mutually singular.

For the second pair, group the $2n$ independent preparations into two blocks of $n$. Define $|{\Psi }_i⟩=|{\psi }_i{⟩}^{\otimes n}$. The tensor-power reduction of PBR overlap givesEach block therefore has an effective two-dimensional Hilbert space. Explicitly,are orthonormal and $|{\Psi }_2⟩=(|e_0⟩+|e_1⟩)/\sqrt{2}$. Embed the four-vector exclusion basis above into the tensor product of these two block spaces. To obtain a complete quantum measurement on all $2n$ qubits, add the orthogonal complement of that four-dimensional subspace to one of its four projectors. All four allowed preparations lie in the subspace, so the four forbidden probabilities remain zero.

If the single-copy preparation distributions overlap with common mass $\epsilon >0$, their $2n$-fold products all dominate the common measure ${\nu }^{\otimes 2n}$ of mass ${\epsilon }^{2n}>0$. The same zero-response contradiction now applies to the four block preparations. ThusThe argument is exact for the ideal devices specified in the question; no finite experimental resolution or noisy overlap bound is assumed.

Use one-bit remote preparation of real qubit states. Alice measures her qubit in the orthonormal basisBecause this change of basis is real and orthogonal, the shared Bell state has the expansionHer projective measurement gives each outcome with probability one half. She sends $m=0$ for the first outcome and $m=1$ for the second. Bob's conditional pure state is respectively $|{\alpha }_{\theta }⟩$ or $|{\beta }_{\theta }⟩$.

For $m=0$ Bob does nothing. For $m=1$ he applies the fixed unitary operatorwhere $Y$ is the Pauli Y gate. Bob need not know $\theta$, because this correction is the same for all real $\theta$. Both outcomes produce the exact density operator $|{\alpha }_{\theta }⟩⟨{\alpha }_{\theta }|$, using one classical bit and only local operations.

This remote state preparation consumes the shared entangled state. Before receiving the bit, Bob has the mixture $(|{\alpha }_{\theta }⟩⟨{\alpha }_{\theta }|+|{\beta }_{\theta }⟩⟨{\beta }_{\theta }|)/2=I/2$, independent of $\theta$, as required by quantum no-signalling. The real-state restriction is what permits a fixed unitary correction of the orthogonal outcome.

Use superdense coding. For the two-bit message $(a,b)\in \{0,1{\}}^2$, Alice applies $Z^a{X}^b$ to her half of the shared Bell state, where $X,Z$ are the Pauli X gate and Pauli Z gate. The encoded states areThese four Bell states are orthonormal. Alice then transmits her one qubit to Bob, who now holds both qubits. A Bell-basis measurement identifies the message with probability one.

More explicitly, Bob can apply a CNOT gate with the received qubit as control and his original qubit as target, followed by a Hadamard gate on the control. The CNOT gate sends the encoded state toand the Hadamard gate sends this to $|a⟩\otimes |b⟩$. Computational-basis projective measurements therefore read out $a,b$ exactly. One transmitted qubit, assisted by one previously shared Bell pair, communicates two classical bits.