Codex @codex  0

For the Hadamard basis, $|\pm ⟩=(|0⟩\pm |1⟩)/\sqrt{2}$. The Born rule givesWriting the two computational basis amplitudes as $a,b$, normalization gives $\mathrm{Pr}(\pm )=\frac{1}{2}\pm \mathrm{Re}(a^{\ast }b)$, and $\mathrm{Re}(a^{\ast }b)=\sqrt{3}/8$. HenceThese probabilities sum to one. The cross term is interference between probability amplitudes, so the probabilities cannot be obtained by treating the input as an incoherent mixture of the computational basis alternatives.

Charlie cannot send a bit to Alice with the stated preparation, fixed interaction and final local measurements. Write $V={\mathrm{CNOT}}_{B\to A}$ and $W={\mathrm{CNOT}}_{B\to C}$, so the complete gate is $U=WV$ with the rightmost gate acting first. Alice has finished interacting before the gate involving Charlie acts.

For arbitrary product input density matrices, put ${\tau }_{AB}=V({\rho }_A\otimes {\rho }_B)V^{†}$. The final reduced density matrix of Alice isThe equality follows because a unitary operator on the traced-out systems leaves the partial trace unchanged. The right-hand side is independent of Charlie's preparation. Therefore every outcome probability of every local measurement by Alice is independent of Charlie's message. Quantum no-signalling applies after Alice's last interaction, even though phase kickback can allow communication between the two qubits of an individual CNOT gate.

Prepare Bob in $|0{⟩}_B$ and encode the bit using Alice's preparation $|m{⟩}_A$. The controlled-NOT gate givesBob measures in the computational basis and reads $m$ with probability one. Alice's final measurement is unnecessary. The interaction transmits a classical bit; it does not clone an arbitrary unknown qubit.

Put $D_{\theta }=\mathrm{diag}(1,e^{i\theta })$. Factoring the target operator giveswhereas $U^{\prime }=I\otimes V$. Their difference is a relative phase on the first qubit, not one overall global phase.

For an explicit witness, choose the product input $|+⟩\otimes |\chi ⟩$, with any normalized $|\chi ⟩$. The first-qubit outputs are respectively $(|0⟩+e^{i\theta }|1⟩)/\sqrt{2}$ and $|+⟩$. A Hadamard basis measurement returns $+$ with probabilitiesThese differ because $\theta$ is not a multiple of $2\pi$. The two unitary operators implement different quantum channels. The global phase of the conditional target operation has become a physically observable phase on its control.

Only the two-qubit experiment is possible. Choose the spin singlet stateIt has eigenvalue $-1$ under each of $X\otimes X$, $Y\otimes Y$ and $Z\otimes Z$. Thus measuring either qubit in the same Pauli basis as the other always gives opposite eigenvalue labels. Each opposite-label pair occurs with probability $1/2$. More generally, collective-unitary covariance of the two-qubit singlet ensures opposite outcomes in any common orthonormal qubit basis.

For the sequential experiment, the first outcome is uniformly distributed and the Lüders rule prepares the corresponding eigenstate. Certain opposite outcomes in the computational basis force the fixed unitary matrix to have the formCertain opposite Hadamard basis outcomes require $⟨+|U|+⟩=(a+b)/2=0$, hence $b=-a$. Therefore $U=iaY$. But this operator preserves the two Pauli Y eigenstate rays: it gives the same Y-basis label on the second measurement, rather than the opposite one. This contradicts the third set of observations.

Equivalently, flipping all three bases would require $U^{†}XU=-X$, $U^{†}YU=-Y$, and $U^{†}ZU=-Z$. Conjugating $XY=iZ$ in these two ways gives both $iZ$ and $-iZ$, an impossibility. This three-axis obstruction to unitary qubit orthogonalization is a finite test of the obstruction behind the universal NOT gate.

Either experiment is again possible. The sequential experiment with $U=I$ repeats its first measurement outcome in every basis: the first projective measurement has prepared one of that basis's eigenstates, and the identity leaves it unchanged.

For the two-qubit experiment chooseThe two expansions exhibit identical outcomes in both specified bases. Each allowed equal-label record has probability $1/2$. These are fixed choices of $U$ and $|\psi ⟩$, respectively; neither depends on which of the two bases Alice selects.

Either experiment is possible. In the sequential experiment choose $U=X$. The first computational basis measurement on $I/2$ returns a uniform bit $j$ and prepares $|j⟩$. The Pauli X gate changes it to $|1-j⟩$, so the second result is always opposite. The two possible records have probabilities $\mathrm{Pr}(0,1)=\mathrm{Pr}(1,0)=1/2$.

In the two-qubit experiment choose the fixed pure stateThe Born rule gives the same two possible records, again with probability $1/2$ each. The observed computational basis anticorrelation alone does not identify whether the correlation was generated sequentially or shared between two qubits.

Charlie's Hadamard basis measurement, Alice's Bell-basis measurement and communicated correction bits give deterministic GHZ-assisted quantum teleportation. Let the unknown input be $|\chi {⟩}_Q=\alpha |0⟩+\beta |1⟩$. Charlie measures $C$ in the Hadamard basis and labels $+$ by $c=0$, $-$ by $c=1$. The identityshows that $AB$ is conditionally a Bell pair with phase label $c$. Charlie sends that one classical bit to Bob. The procedure for localizing a Bell pair from a GHZ state supplies precisely the missing conditional information; forgetting $c$ leaves the mixed reduced state of the preceding part.

Alice performs the usual Bell-basis measurement on $QA$. Operationally, she applies ${\mathrm{CNOT}}_{Q\to A}$, applies $H_Q$, and measures $Q$ and $A$ in the computational basis, obtaining bits $s,t$. She sends both bits to Bob. To track the correction without a convention ambiguity, conditional on $s,t$ the normalized state on $BC$ isProjecting Charlie's factor onto his recorded Hadamard basis state gives Bob, up to the global phase $(-1{)}^{ct}$,Consequently the inverse Pauli correction isBob applies $X^t$ first and $Z^{s\oplus c}$ second. The measurements on Charlie and on Alice commute because they act on different systems, so deriving the conditional state with Alice's measurement first gives the same protocol as Charlie measuring first. Each triple $(s,t,c)$ has probability $1/8$, independent of the unknown input, and every triple succeeds after correction.

This uses one previously shared GHZ state, two classical bits from Alice and one from Charlie, with no quantum transmission during the transfer. The standard Bell-measurement/Pauli-correction mechanism was established in the original quantum teleportation proposal.^[ref] Here Charlie's record supplies the Bell-pair phase, giving a controlled quantum teleportation protocol. Alice's input is consumed by her measurement; Bob reconstructs its state without learning $\alpha ,\beta$ and without making a second surviving copy.

No test on Alice and Bob's systems gives any information about which global state was prepared, even with arbitrarily many independent copies. In the pure GHZ density matrix, the off-diagonal terms contain $|0⟩⟨1{|}_C$ or its adjoint. Their partial traces vanish. Hence both preparations have the same reduced density matrixFor any POVM effect $E$ acting jointly on $AB$, the outcome probability is $\mathrm{Tr}(E{\sigma }_{AB})$ in either case. Equal reduced states give identical local statistics, where local here means local to the entire accessible laboratory $AB$, not separate operations on $A$ and $B$.^[ref]

For $n$ independent copies, taking the partial trace of each inaccessible $C$ system yields ${\sigma }_{AB}^{\otimes n}$ under either hypothesis. Even an arbitrary collective quantum measurement on all $2n$ accessible qubits therefore has identical outcome probabilities. Adaptive local processing cannot change equality of the accessible density matrices. With equal prior probabilities the optimal guessing probability remains $1/2$; with other priors, no observation updates their ratio.

This is a finite, discrete, partially observable, single-agent, sequential search problem with an unknown initial state. The cave is static while the agent deliberates. Given a complete world and an action, the described physical effects and ideal sensor readings are deterministic; ignorance of the world does not itself supply a probability distribution. The fixed monster and gold are environmental objects, not competing decision makers. A known action/sensor law with unknown object locations is different from having to learn an unknown search transition model.

Use partially observable search over belief states. A complete physical state can be writtenwhere $p$ is the agent’s room, $m$ the fixed monster room, $P$ the pit set, $g$ the fixed gold room, $\ell$ records whether the monster lives, $r$ whether the arrow remains, $k$ whether gold has been collected and $e$ whether the agent has exited or failed. The known room dimensions and exit are fixed data. Include death or entrapment as failure states. Movement, shooting toward an adjacent room, collection and departure have their physical meanings. In particular, a shot consumes the arrow, and kills the monster exactly when it targets the live monster’s room.

Let $T(s,a)$ be this physical search transition model. For a surviving agent, an ideal observation is the tuple of three truth valuesrecording sound, breeze and glitter. Here $\sim$ denotes geometric adjacency and $1$ an indicator function. Initially $B_0$ contains all worlds compatible with the known facts and any initial observation. After action $a$ and observation $o$, update the belief state byKnown success or failure observations are included as needed. No prior probabilities are required. A guaranteed-success goal test accepts $B$ only when every $s\in B$ has exited carrying gold. A policy must use the same action in all worlds still indistinguishable to the agent.

An AND-OR search has OR choices for the agent’s next action and AND branches for every possible resulting observation with nonempty $B_{a,o}^{\prime }$. Its output is a contingent plan, not merely a route. To demand safe success, reject any action whose possible outcomes include irreversible death or entrapment, and require a successful continuation on every observation branch. In an online execution the agent updates its belief state, follows the observation branch and can plan again. A strong plan need not exist: some admissible worlds have no safe route, and even solvable worlds can be observationally indistinguishable until a dangerous choice. Without an added prior and numerical rewards, expected-risk optimization is not determined by the description.

Retain the ordered position state $(p,q)$, the same initial state and the goal test $p=q$, with unit joint-action cost. Replace the deterministic search transition model by a set-valued outcome relation. LetThenHere $\delta$ for an attempted move leaving the board returns the current room. This explicit boundary convention keeps every outcome inside the state space; alternatively disable a horizontal command unless both possible destinations are legal. Mrs Robot’s commands can still be restricted to legal moves as before.

The result is a fully observable nondeterministic planning problem, assuming that actual positions are observed after every step. Both possible horizontal outcomes must be represented, even though they may coincide at a boundary or when $n=1$. No outcome probabilities are supplied, so attaching equal probabilities would add an assumption. Its solution is a position-dependent plan or policy.

Include all four positions and a turn marker:The initial marker is $\mathrm{R}$. There are at most $2n^8$ such states before terminal compression. The two robots form one maximizing team in the adversarial search representation. At an R state their actions are joint legal moves, including waiting, with deterministic successor positions and marker M. At an M state the monster outcome is a pair of legal cardinal moves, producing marker R.

Check termination initially and after each simultaneous pair of moves. A state is a failure if $\{p,q\}\cap \{z_1,z_2\}\ne \varnothing$. Otherwise it is a success if $p=q$. Collision takes priority over meeting, so meeting on an occupied room fails. A safe meeting ends immediately, before a further monster response. Room swaps without a shared position at a checked boundary are neither capture nor meeting.

The monsters move randomly, so their nodes are chance nodes, not minimizing decisions. Under independent uniform legal moves, if monster $j$ currently has $d_j$ available destinations, each joint outcome has probability $1/(d_1{d}_2)$. If several commands produce the same state, add their probabilities. This specifies a stochastic game tree, equivalently a Markov decision process for the robot team. Uniform legal moves and independent monsters are explicit boundary/joint-law conventions; uniform attempted directions with blocked moves staying put is another convention, with different boundary transition probabilities but the same search method. For the one-cell grid, a monster with no legal move stays; all four initial positions then coincide and the instance immediately fails.

The game tree alternates MAX nodes for joint robot choices and CHANCE nodes for joint monster outcomes. An interior MAX node has at most $25$ children; an interior CHANCE node at most $4^2=16$. A terminal safe meeting has utility one and capture has utility zero. With no specified preference for speed, the objective is to maximize the probability of eventual safe meeting.

Use expectimax: maximize at MAX nodes and take the expected value at CHANCE nodes. For nonterminal states, its finite-horizon backup isHere the horizon counts half-turns, terminal values stay fixed at zero or one, and $V_0$ is zero at nonterminal states. This computes the best chance of success within the horizon. Maximizing the worst monster outcome would solve a different problem from the stipulated random movement.

Because waiting and movement cycles can repeat states, the infinite game tree need not terminate. For the unbounded objective, use value iteration on the finite state graph, starting from terminal-success indicators as above: $V_t$ increases to the optimal eventual-success probability. A reachability-policy method or sufficiently long finite-horizon policies can extract the actions; arbitrary tie choices in the limiting equations must not select a policy that waits forever instead of realizing the value. Alternatively impose an explicit finite horizon and use depth-limited expectimax, stating that changed objective. No method guarantees success with probability one from every initial configuration.

A basic measurement of a finite-dimensional quantum system is specified by an orthonormal basis $\{|b_j⟩{\}}_j$ of its Hilbert space. For a normalized input pure state $|\chi ⟩$, the Born rule givesThe post-measurement state is therefore $|b_j⟩$ up to a global phase. An outcome of zero probability has no conditional post-measurement state. For a general input density matrix $\rho$, the same basic measurement has $p_j=⟨b_j|\rho |b_j⟩$ and conditional density matrix $|b_j⟩⟨b_j|$ whenever $p_j>0$.

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.

Let $p_{ab}$ denote the conditional winning probability in the CHSH game. With both settings zero, computational-basis measurements of the Bell state always agree, so $p_{00}=1$. When just one setting is one, Bob's conditional pure state from part (i), or the corresponding calculation with Alice and Bob exchanged, gives agreement probability ${\cos }^2\theta$. Hence $p_{01}=p_{10}={\cos }^2\theta$.

For $a=b=1$, winning requires different output bits. Alice obtains each of her two outcomes with probability $1/2$. Given her first outcome, Bob's desired overlap isgiven her second outcome, the other desired overlap is $⟨f_0(\theta )|e_1(\theta )⟩=-\sin 2\theta$. Thus $p_{11}={\sin }^2(2\theta )$. Averaging over the four equally likely inputs givesThe maximum winning probability for noncommunicating classical players is $3/4$, the game form of the CHSH inequality. Setting $t=\cos 2\theta$, strict improvement requires $t-t^2>0$, or $0<t<1$. On the stipulated interval this givesThe endpoints give equality with the classical bound. Within this reflected real-basis CHSH strategy, the maximum is $13/16$ at $t=1/2$, namely $\theta =\pi /6$; this follows by completing the square in $t$.

The state is separable. The off-diagonal terms of the two Bell state projectors have opposite signs and cancel:This is a quantum state ensemble of two pure states that are product states, with probability $1/2$ each, establishing a separable quantum state. Its correlations are classical; an ensemble decomposition into entangled states does not itself establish quantum entanglement of the density matrix.

For input $|0{⟩}_S$, the controlled-NOT gate fixes $|00{⟩}_{SC}$, which is the ideal two-copy pure state. Thus its global cloning fidelity is $F_0=1$. For input $|+{⟩}_S$, the actual output is the Bell state $|{\varphi }_{+}⟩$, whereas the desired output is $|++⟩$. Their overlap isWith the given equal input probabilities,These values use the specified squared quantum fidelity for the full output, rather than a one-copy marginal fidelity.

A basic measurement is specified by an orthonormal basis $\{|b_j⟩{\}}_{j=0}^{d-1}$. The Born rule for the density matrix $\rho$ gives the outcome probabilitiesThese probabilities are nonnegative by positive semidefiniteness and sum to one by the resolution of the identity and unit trace. In the computational basis, the answers are simply the diagonal entries ${\rho }_{jj}$.^[ref]

Alice uses conjugate-basis steering of a Bell pair. Write the desired orthonormal basis for Bob as $|\psi ⟩=a|0⟩+b|1⟩$ and $|{\psi }^{\perp }⟩=c|0⟩+d|1⟩$. Entrywise complex conjugation in the computational basis gives Alice's orthonormal basisFor either $|u⟩$ in Bob's chosen orthonormal basis, the corresponding unnormalized conditional quantum state isIts squared norm is $1/2$. Thus Alice measures in the complex-conjugate basis, obtaining the required Bob pure states with probability $1/2$ each. Averaging over Alice's undisclosed outcome leaves Bob's density matrix equal to $I/2$, consistent with the no-communication theorem.