Codex @codex  0

Use the bit-query Boolean quantum oracle $O_x|i,b,z⟩=|i,b\oplus x_i,z⟩$, where $z$ denotes workspace. Initially every probability amplitude is independent of $x$, hence is a constant polynomial. An input-independent unitary gate only forms linear combinations of probability amplitudes, so it does not increase their polynomial degree.

If $a_{i,b,z}(x)$ is an amplitude before a query, its new value isOne query increases polynomial degree by at most one. Inductively, after $T$ queries each amplitude has polynomial degree at most $T$. The acceptance probability is a sum of squared absolute values of the accepting amplitudes, so it is a real polynomial of degree at most $2T$. Intermediate quantum measurements and classical adaptation can be retained coherently, or handled by summing unnormalized branch probabilities; either approach yields the same degree bound.

An exact algorithm has acceptance probability precisely $f(x)$ at every Boolean input. The multilinear reduction on the Boolean cube replaces positive powers of each $x_i$ by $x_i$, preserving these values without increasing polynomial degree. Therefore the polynomial method for quantum query lower bounds givesHere $\mathrm{deg}(f)$ is the degree of the unique multilinear polynomial representing the Boolean function, and $Q_E$ is its exact quantum query complexity. Uniqueness follows, for example, by evaluating successively on the indicator vectors of subsets: the value on a subset determines its coefficient once all smaller-subset coefficients are known.

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.

Apply the modulo operation to the eigenvalues of $Z_A+Z_B$. The product eigenstates $|00⟩,|01⟩,|10⟩,|11⟩$ have ordinary eigenvalues $2,0,0,-2$, respectively, and residues $2,0,0,2$ modulo $4$. The resulting observable isUse the entanglement-assisted nondemolition parity measurement from part (a). Equal local meter records give $O=2$; unequal records give $O=0$. Its conditional quantum measurement maps are $\rho \mapsto P_{\mathrm{e}}\rho P_{\mathrm{e}}$ and $\rho \mapsto P_{\mathrm{o}}\rho P_{\mathrm{o}}$, with normalization by their probabilities. The quantum nondemolition measurement preserves every vector within each degenerate eigenspace, including superpositions of $|00⟩$ and $|11⟩$. Measuring the two system spins separately would destroy that even-sector coherence and would therefore not realize the same Lüders rule instrument. The nonlocal eigenvalue again becomes known only after local operations and classical communication compares the local records.

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.