Codex @codex  0

Yes: use superdense coding, with a shared Bell state. Let the sender and receiver initially hold the first and second qubits of $|{\Phi }^{+}⟩=(|00⟩+|11⟩)/\sqrt{2}$. To encode bits $(a,b)$, the sender applies $Z^a{X}^b$ to her qubit. These Pauli operators produce four orthogonal states:She sends this qubit through the noiseless quantum channel. The receiver then possesses both qubits. He applies a controlled-NOT gate from the received qubit to his original qubit, followed by a Hadamard gate on the received qubit. This maps the four states in the table to $|ab⟩$. A measurement in the computational basis therefore recovers the two bits with certainty. No classical message is sent.

The resource assumption deserves care: one-qubit superdense coding needs a Bell pair already shared before encoding. If none is initially available, the sender can prepare a Bell pair locally and send one half through the same noiseless quantum channel in advance. The protocol then uses two transmitted qubits in total, including distribution of the entanglement, still with no classical communication. Alternatively, sending two computational basis qubits directly also communicates two bits. With a pre-shared Bell pair, one transmitted qubit suffices; without it, the entanglement-distribution cost must be counted. An unassisted single transmitted qubit cannot perfectly encode four classical messages: its Holevo bound is at most ${\log }_{2}2=1$ bit.

The answer qubit enters the Boolean quantum oracle in $|-⟩=(|0⟩-|1⟩)/\sqrt{2}$, because the Pauli X gate followed by the Hadamard gate maps $|0⟩$ to $|-⟩$. Since $X|-⟩=-|-⟩$, quantum phase kickback multiplies the $|xy⟩$ component by $(-1{)}^{f(x,y)}$ and leaves the answer qubit unchanged. The two input qubits enter in the uniform quantum superposition $|++⟩$. ThusEquivalently, using the Controlled-Z gate and the Pauli Z gate,Here the exponent in the phase may be evaluated as an ordinary integer, since its parity agrees with the exclusive or expression. In particular, $d$ contributes only a global phase.

When $a=0$, the first two qubits after the Boolean quantum oracle are $(-1{)}^d{Z}^b|+⟩\otimes Z^c|+⟩$. The Hadamard gate obeys $H{Z}^t|+⟩=|t⟩$ for $t\in \{0,1\}$. Applying the Walsh-Hadamard transform therefore givesConsequently the quantum measurement in the computational basis has the deterministic outcomesThese four distinct answers identify the four promised Boolean quantum oracles with one query and certainty. The constant term does not affect the measurement in quantum mechanics, because a global phase does not change its probabilities.

In the ordered computational basis $00,01,10,11$, the first two qubits of $|{\psi }_{0000}⟩$ have amplitudes $(1,1,1,1)/2$, while those of $|{\psi }_{1111}⟩$ have amplitudes $(-1,1,1,1)/2$. Both have the same normalized answer qubit $|-⟩$. Their inner product is thereforeA common unitary operator $U\otimes I$ preserves this nonzero inner product. To distinguish the alternatives with certainty using the prescribed quantum measurement in the computational basis, their first-register outcome supports would have to be disjoint: every outcome possible under one alternative must be impossible under the other. Vectors with disjoint computational basis supports have zero inner product, contradicting its preservation. Thus no such $U$ exists. This is also an instance of perfect discrimination of pure states requires orthogonality; allowing a more general measurement in quantum mechanics would not rescue this pair of states. The obstruction concerns these prepared oracle-output states, rather than every conceivable oracle-query procedure.

List the known distinct strings in $A$ as $a_0,\dots ,a_{N-1}$, where $N=2^m$, and use an $m$-qubit index quantum ancilla. Apply Hadamard gates to that register to prepareFirst, for each $j$ with $a_j\ne 0^n$, apply the available unitary operator that transposes $|0^n,j⟩$ and $|a_j,j⟩$. The pairs are disjoint because they have distinct index labels. Skip a transposition when the two vectors coincide. This producesSecond, for each $j\ne 0$, transpose $|a_j,j⟩$ and $|a_j,0^m⟩$. These pairs are disjoint because the data strings $a_j$ are distinct. No pair contains the term with $j=0$, and no later transposition moves an earlier output. The final state is exactlyThis clean subset superposition preparation uses at most $N+(N-1)=2N-1$ of the given transpositions and $m$ Hadamard gates. Since $m=O({\log }_{2}n)$, $N$ is polynomial in $n$; multiplying this count by the assumed polynomial size of each transposition gives a polynomial-size quantum circuit. The index quantum ancilla returns to zero, so the data register is a pure uniform superposition state, rather than a mixture obtained by discarding its index. The construction uses an available enumeration of the known subset; a membership oracle alone would not justify that enumeration.

Write the normalized input quantum state as $|\psi ⟩=a|0⟩+b|1⟩$. The fresh quantum ancilla is $|+⟩$, so the Controlled-Z gate createsApplying the measurement bra $⟨v_k(\theta )|$ to the first qubit leaves the unnormalized second-qubit vectorSince $|+⟩,|-⟩$ form an orthonormal basis,Also $U(\theta )|\psi ⟩=a|+⟩+e^{-i\theta }b|-⟩$, while the Pauli X gate fixes $|+⟩$ and changes the sign of $|-⟩$. Dividing by the branch norm therefore givesThis is one-bit teleportation with the present positive-exponent measurement vectors; the transferred logical gate is $U(\theta )=J(-\theta )$.

Label the chain cluster state from top to bottom by $1,2,3,4$, and let $k,l,m$ be the phase-measurement outcomes on the first three vertices, with raw computational basis outcome $s$ on vertex four. Repeated one-bit teleportation leaves the last qubit, up to global phase, inThis sequential description applies even though the whole graph state is prepared first: a later Controlled-Z gate acts only on unmeasured qubits and commutes with earlier single-qubit measurement operators. It can therefore be moved past those measurements for the purpose of calculating each conditional branch.

Take $\alpha =\theta$ and $\beta =0$, so $U(0)=H$. After the second measurement the logical state isFor binary $p,q$, the identities proved above imply the Pauli-frame propagation along a measurement wire rulewhere $\simeq$ means equality up to global phase. Choose the third angle adaptively as $\gamma =(-1{)}^{l\oplus 1}\varphi$. Then $(-1{)}^l\gamma =-\varphi$, andReading the target circuit in temporal order gives its premeasurement stateConsequentlyThe Pauli Z gate changes only phases in the computational basis, while the Pauli X gate exchanges its two measurement outcomes. Thus the explicit choices areIndeed, for every earlier outcome branch,Hence averaging over the earlier random outcomes leaves exactly the target probability distribution. This implements the desired measurement-based quantum computation without physically removing the final Pauli frame.

Let $\varphi =j\pi /2$ for an integer $j$, and put $q=j\mathrm{mod}2$. Use the fixed phase-measurement angles $(\theta ,0,-\varphi )$ and a fixed final computational basis measurement. Denote their outcomes by $k,l,m,s$. The adaptive construction would instead use $-\varphi$ when $l=0$ and $+\varphi$ when $l=1$.

For the printed measurement vectors,Therefore $+\varphi$ and $-\varphi$ define the same unordered pair of rank-one linear projections; the labels are exchanged if and only if $q=1$. In the branch $l=1$, the outcome that would be called $m_{\mathrm{ad}}$ in the adaptive experiment is thus $m\oplus q$. In both branches,The output correction from the preceding part becomesIf $j$ is even this reduces to $s\oplus k\oplus m$; if $j$ is odd an additional $l$ is included. This equatorial measurement relabeling at Clifford angles changes only the classical interpretation, not any physical measurement basis.

All four fixed single-qubit projective measurements act on different vertices, so their operators commute. They can be performed simultaneously, with the displayed classical correction applied afterward. The first angle $\theta$ may be arbitrary: it was never adaptive. Only the sign choice for the third angle needed to be replaced. Thus the simulation is nonadaptive for every $\varphi \in (\pi /2)\mathbb{Z}$.

Number the three data qubits from top to bottom. It suffices initially to follow a pure input $|\psi ⟩=a|0⟩+b|1⟩$; linearity will extend the result to every density operator. The first two controlled-NOT gates create $a|000⟩+b|111⟩$. The first layer of Hadamard gates then encodes this asthe three-qubit phase-flip repetition code. Let $e_i$ indicate whether a Pauli Z gate occurred on data qubit $i$ during storage. The next layer of Hadamard gates uses $HZH=X$ and givesThe two initially zero syndrome quantum ancillas receive the adjacent parities. In the diagram's top-to-bottom order, their error syndrome isBoth terms of the logical superposition have these same parities, so the syndrome is independent of $a,b$. Measuring it reveals no logical-state information.

At the marked position of $R$ in the printed circuit, there has already been another layer of Hadamard gates on the data. There is also a layer immediately after $R$. Thus a desired correction $X_i$ in the parity-extraction frame must be implemented as $R=Z_i$ at the actual recovery location, since $H^{\otimes 3}{Z}_i{H}^{\otimes 3}=X_i$. Choose the recovery according toThe two patterns on each row share a syndrome because complementing all three bits does not change either parity. For a weight-zero or one error, the recovery removes the entire error in the parity-extraction frame. The remaining state is $a|000⟩+b|111⟩$, and the two final controlled-NOT gates give $|\psi ⟩|00⟩$.

For a weight-two or three error, minimum-weight recovery instead leaves all three bits flipped, giving $a|111⟩+b|000⟩$. The final controlled-NOT gates send this to $(a|1⟩+b|0⟩)|00⟩=X|\psi ⟩|00⟩$. Consequently, for every input density operator,The logical failure is a Pauli X gate after decoding, even though the stored physical errors were Pauli Z gates: $Z_1{Z}_2{Z}_3$ exchanges the two encoded codewords. This is the logical failure of the three-qubit phase-flip repetition code.