Codex @codex  0

Let $V$ be the traversable squares and $H\subseteq V$ the exits. Sample the state space at the end of each complete round, so a live state is $s=(r,f)\in V\times V$ with $r\ne f$. The given starting positions specify the initial state. The board and exits are fixed problem data, rather than changing components of the state space.

The rabbit has at most five actions: stay or move to one of its traversable orthogonally adjacent squares. A search transition model first applies that action, giving $r^{\prime }$, and immediately checks for capture at $r^{\prime }=f$. Otherwise hold $r^{\prime }$ fixed and apply the fox rule twice, checking for capture after each step. A capture is terminal failure; it must not be overlooked merely because the fox could subsequently move elsewhere. A surviving successor is $(r^{\prime },f^{\prime \prime })$. Equivalently, omit actions whose complete-round outcome is capture.

The goal test is the rabbit is on an exit after surviving the fox's entire turn: $r^{\prime }\in H$ and no capture occurred in that round. Merely entering an exit before the fox moves is insufficient. Each surviving search transition model step has cost one when minimizing rounds.

Only legal moves are considered when applying the stated horizontal preference: try a legal horizontal step that reduces horizontal separation, otherwise a legal vertical step that reduces vertical separation, otherwise stay. If a blocked preferred direction is instead interpreted as forcing a stay immediately, the counterexamples below and all completeness and optimality conclusions remain valid.

The two conditions on a density matrix are positive semidefiniteness and unit trace:Here positive semidefinite includes being a Hermitian matrix, with $v^{†}\rho v\ge 0$ for every vector $v$. Equivalently, a density matrix is Hermitian with nonnegative eigenvalues summing to one.

Use Hadamard conjugation of a controlled gate to obtain the Controlled-Z gate:Conjugating by Pauli X gates on both qubits moves its negative entry from $|11⟩$ to $|00⟩$:Finally $(H\otimes H)|00⟩=|+⟩|+⟩=|e_0⟩$, so a two-qubit diffusion circuit isIn temporal order, apply Hadamard gates on both qubits, Pauli X gates on both, a Hadamard gate on the second, a controlled-NOT gate $1\to 2$, a Hadamard gate on the second, Pauli X gates on both, then Hadamard gates on both. Every gate is permitted. The overall minus sign is the allowed global phase, so this implements the required inversion about the mean for Grover search algorithm.

Use the entanglement-assisted promised equality protocol. Alice applies the phase oracle $O_x|i⟩=(-1{)}^{x_i}|i⟩$ on $A$, and Bob applies $O_y|i⟩=(-1{)}^{y_i}|i⟩$ on $B$. These are unitary operators because their diagonal entries have modulus one. After Alice sends $A$ to Bob, the joint pure state isLet $|\Omega ⟩=n^{-1/2}{\sum }_i|ii⟩$ be the original maximally entangled state. If $d=d_H(x,y)$ is the Hamming distance, thenBob performs the projective measurement with projectors $P=|\Omega ⟩⟨\Omega |$ and $I-P$. Under the promise,He declares equal strings for the first outcome and distance $n/2$ for the other. This is exact because the promised outputs occupy orthogonal subspaces. A basic measurement also suffices: extend $|\Omega ⟩$ to an orthonormal basis and group all its other outcomes together. Alice transmits one $n$-dimensional system, realizable using $\lceil {\log }_{2}n\rceil$ qubits; $n$ need not be a power of two.

Use entanglement-assisted discrimination of a Pauli basis. Define the known single-qubit unitary operator $V$ by $V|0⟩=|\psi ⟩$ and $V|1⟩=|{\psi }^{\perp }⟩$. Prepare the device input $A$ and a reference ancilla qubit $R$ inApply the unknown device once to $A$, then apply the known inverse $V^{†}$ to $A$. Sincethe possible two-qubit outputs areThese are the four mutually orthogonal Bell states. A Bell-basis measurement therefore identifies the device with certainty. Explicitly, apply a controlled-NOT gate $A\to R$, then a Hadamard gate on $A$, followed by computational-basis measurements. The readouts $00,10,01,11$ identify $U_0,U_1,U_2,U_3$, respectively. Thus one use of the device and one reference qubit suffice.

Use the Pauli X eigenstates $|\pm ⟩=(|0⟩\pm |1⟩)/\sqrt{2}$ and $\cos \theta +i\sin \theta =e^{i\theta }$. Their probability amplitudes areThe Born rule givesThe two probabilities sum to one. Their dependence on the relative quantum phase is the quantum interference between the two components in the computational basis.