Past exam of the computer science course of the University of Oxford / 2021

Source paper: released examination archive.

All three variants are complete search algorithms under the usual finite-branching factor, nonnegative-heuristic function assumptions. Here $0\le h\le h^{\ast }$, with zero at goals; the supplied positive lower bound on step costs is also essential. The root is processed once before a parent-dependent priority is needed.^[ref] Completeness means finding a solution if one exists, not necessarily terminating when none exists.

Fix a finite solution path. Every search node on that path has a finite priority, so let $K$ bound all of its relevant priorities. For ordinary A-star search and the second variant, the priority is at least $g(n)$. Thus any search node with priority at most $K$ has depth at most $\lfloor K/ϵ\rfloor$. In the third variant the priority is at least $g(n^{\prime })$, so its depth is at most $\lfloor K/ϵ\rfloor +1$. A finitely branching search tree has finitely many search nodes at these depths. Therefore finitely many earlier search nodes can delay each successive search node on the chosen solution path; eventually its goal is generated or selected, as appropriate.

Moving the goal test to generation cannot destroy that existence guarantee, although it can destroy optimality. Likewise the altered parent-dependent priorities remain bounded below by the accumulated cost to the search node or its parent, which is enough for this completeness argument. If “admissible” were interpreted to allow arbitrarily negative estimates, the lower-bound argument would need an additional hypothesis; the conventional nonnegative interpretation is being used explicitly. For the literal upper-bound-only interpretation, all three can fail completeness: attach an infinite unit-cost dead-end chain with $g(n_d)=d$ and $h(n_d)=-2d$ beside a finite goal branch beginning with a cost-$3$ edge and estimate zero. Its successive low priorities can starve the finite branch. Every negative chain estimate is still at most its infinite true remaining cost.

None of the three variants is an optimal search algorithm in general. The following single search tree supplies counterexamples for all three. Its heuristic function is nonnegative, admissible and even a consistent heuristic.

The least-cost goal is $G_4$, reached at cost $1+3=4$; the other goal $G_5$ costs $5$. Assign $h(S)=0$, $h(P)=3$, and zero to both goals. For the first variant, expanding $S$ generates $G_5$ and immediately returns it, before $P$ can be expanded. A goal test at generation therefore returns cost $5$.

For priority $g(n)+h(n^{\prime })$, the root's children have priorities $1$ for $P$ and $5$ for $G_5$. Expanding $P$ generates $G_4$ with priority $4+3=7$. The algorithm next selects $G_5$, again returning cost $5$.

For priority $g(n^{\prime })+h(n)$, the root's children instead have priorities $3$ for $P$ and $0$ for $G_5$. The suboptimal goal is selected immediately. The example uses no tie-breaking assumption. In contrast, ordinary A-star search with its goal test on selection compares the genuine estimated total costs and returns $G_4$.

Maintain a certified solution-cost ceiling and prune only search nodes whose lower bound strictly exceeds it. Initially let $B=\infty$, or set $B=u(r)$ at the root $r$ when that value is finite. Whenever a search node $n$ is generated, updateRun ordinary A-star search with $f(n)=g(n)+h(n)$ and a goal test when removing a search node from the search frontier. Discard a generated search node, or a queued search node encountered after a later bound improvement, ifThis is branch and bound using a lower bound $f$ and an upper bound $B$. A finite $u(n)$ certifies that some goal is reachable from $n$ within that remaining-cost ceiling; for a dead end, $h^{\ast }(n)=\infty$ forces $u(n)=\infty$ too. Every finite quantity $g(n)+u(n)$ is consequently at least the global optimum $C^{\ast }$.

On an optimal solution path, admissible heuristic estimates ensure $f(n)\le C^{\ast }\le B$. Hence no search node of that path is pruned. The finite-branching factor and positive step-cost hypotheses from (a) still ensure completeness, and the usual A-star search argument makes the first selected goal optimal. A smaller bound can remove branches earlier; it need not improve every instance.

The strict inequality matters: $u$ is only a numerical bound and need not provide an actual stored solution path. If $B=C^{\ast }$, pruning at $f(n)\ge B$ could remove every optimal continuation. Nor may the algorithm return a path merely because its lower bound meets $B$ when no witnessing path has been constructed. With an actual incumbent solution, the familiar equality-pruning variant can instead retain and return that incumbent.

Yes. Greedy best-first search needs only the ordering of remaining-cost estimates. Store generated but unexpanded search nodes in a search frontier. To choose the next search node, compare candidates with $\kappa$ and retain the one it returns; a linear scan suffices, or a priority queue can use the comparison rule. Remove that search node, apply the goal test, and otherwise generate its children.

This implements best-first search ordered by $h^{\ast }$ without ever evaluating $h^{\ast }$. If stable tie handling is wanted, comparing both argument orders distinguishes equality, after which insertion order can break ties. No estimate of accumulated-plus-remaining cost is required for this greedy ordering.

The comparator alone cannot generally reproduce informed A-star search priorities. A valid weaker fallback is uniform-cost search, namely A-star search with $h=0$. The issue is that ordering $h^{\ast }(n)$ and $h^{\ast }(m)$ does not supply the numerical difference needed to compare $g(n)+h^{\ast }(n)$ with $g(m)+h^{\ast }(m)$.

For example, take accumulated costs $g(n)=5$, $g(m)=1$. Remaining costs $h^{\ast }(n)=1$, $h^{\ast }(m)=2$ rank $n$ ahead under $\kappa$ but give total estimates $6$ and $3$, so informed A-star search selects $m$. Remaining costs $1$ and $10$ give the same pairwise comparator ranking but totals $6$ and $11$, selecting $n$. Thus the comparator's ordering cannot simply replace the cardinal heuristic function inside $f=g+h$.

If “do A-star search” includes choosing any available admissible heuristic, set it identically to zero and prioritize by the known accumulated cost $g$. Apply the goal test on removal from the search frontier. This is complete and optimal under the stated finiteness and step-cost assumptions, but it does not recover the unavailable perfect-heuristic function ordering or its search reduction. The distinction is between implementing the informed priority from $\kappa$ and retaining the algorithm's guarantees through this uninformed special case.

Minimax search applies because this is a finite, deterministic two-player zero-sum game with perfect information. Each move assigns a previously unassigned Boolean variable, so play terminates after exactly $N$ moves. Both players observe the whole partial Boolean valuation, and there are no chance moves. Give terminal positions payoff $+1$ when the propositional formula is true and $-1$ when it is false, measured for $A$. At an $A$-node take the maximum child value and at a $B$-node the minimum. Backward induction then computes the winner and a corresponding winning strategy.

Depth $N$; at most $2^{N}N!$ complete plays; $3^N$ partial-assignment states; and ${\sum }_{k=0}^N{2}^{k}N!/(N-k)!$ tree nodes. Here “different games” means complete move histories for the fixed propositional formula, rather than different syntactic formulas or merely different terminal Boolean valuations.

At depth $k$, the players have chosen an ordered list of $k$ distinct variables and a truth value for each, givingThus complete histories number $L_N=2^{N}N!$: $N!$ variable orders and $2^N$ assignments. Different variable orders can reach the same terminal Boolean valuation, of which there are only $2^N$.

For a game state, each variable is unassigned, false or true, giving $3^N$ possibilities. Ownership and variable-assignment order are irrelevant in this version, and the next player is determined by the parity of the number already assigned. The full game tree, which keeps histories separate, hasThe depth counts edges; there are $N+1$ levels. These bounds explore the full tree even when a formula's truth might be inferable from a partial assignment, since the stated stopping rule waits for all variables.

Take ${\phi }_1=p$ for an $A$ win and ${\phi }_2=p\wedge \neg p$ for a $B$ win. In the first case $A$ assigns $p$ true and play terminates immediately. In the second, either value of $p$ completes an assignment making the contradiction false, so $B$ wins regardless of $A$'s move. These examples force termination and do not rely on a stalling convention.

For the subsequent parts, adopt the explicit convention that an infinite play is a draw, with payoff $0$, between an $A$ win at $+1$ and a $B$ win at $-1$. The source does not assign a value to nontermination. Different conventions can change values of cyclic positions; the forced finite wins above remain valid.

For $N\ge 3$, depth and history-tree size can be infinite, while a sufficient finite state bound is $2\cdot 5^N$. The number of possible completed histories also becomes unbounded. With variables $p,q,r$, first let $A$ assign $p$ and $B$ assign $q$. Both can then keep flipping their own variable, leaving $r$ unassigned. After four such flips the same assignment, ownership and player-to-move recur. Arbitrarily many repetitions can precede assignment of $r$, so there are infinitely many distinct finite complete histories as well as legal infinite plays.

A state must now record ownership: for each variable the possibilities are unassigned, $A$-owned false, $A$-owned true, $B$-owned false, and $B$-owned true. Include the player to move, since flips break the old link between turn parity and the number assigned. This givesMany encoded positions are unreachable, so this is an upper bound. Each nonterminal state has at most $2N$ legal moves: two assignments per unassigned variable and one flip per variable owned by the acting player. Thus the finite directed graph has at most $2N|V|$ edges even though its unrolled game tree is infinite. The $2^N$ possible final Boolean valuations are unchanged, but they no longer count distinct plays or complete ownership states. For $N=1,2$, no player gets a legal opportunity to flip before all variables are assigned, so the original finite bounds still apply.

Solve the finite state graph by winning-set fixed-point iteration, treating positions outside both winning regions as draws. A naive recursive minimax search over histories may run forever around a cycle. Store each ownership-sensitive state once, with a player-to-move flag and all legal successors.

Let $T_A$ and $T_B$ be terminal states where the propositional formula is true and false, respectively. Initialize $W_A^0=T_A$. Repeatedly add nonterminal positions as follows:For $W_B$, start at $T_B$ and exchange the players in the existential and universal conditions. Terminal states keep their original labels and are excluded from these predecessor rules, avoiding a vacuous all-successors test at a terminal loss. Each process stabilizes after at most $|V|$ strict growth steps; predecessor counters implement both regions via the winning-position attractor in an infinite game construction in $O(|V|+|E|)$ graph time.

The admission round supplies a decreasing rank. At a state controlled by the winning player, choose a successor of smaller rank; at an opposing state, every successor already has smaller rank. Hence these strategies force a finite terminal win. The two winning regions are disjoint. Outside both, each player can keep the play outside the opponent's winning region, so neither can force a terminal win against best defence. Under the convention in (h), assign those remaining positions value $0$; the other regions have values $+1$ and $-1$.

This is a finite reachability game calculation, with memoryless strategies read from successor choices. Merely calling the first back-edge encountered a draw is unsound: a cycle can have an exit through which one player can force a win.

The audience assumptions are part of the constraint satisfaction problem. Talks occupy whole common-length slots, room capacity and travel times impose no additional restrictions, and different CS year cohorts do not overlap. Physics attendees are treated as separate from those cohorts and the Head of Department. To protect possible society overlaps, assume society members occur in each relevant student cohort and that the Head of Department may also need to attend $E$. No additional overlap between otherwise distinct audience groups is assumed. These are declared modelling choices, rather than claims about the actual membership of any group.

The shared-audience restrictions give the edge pairsFor example, the Head of Department's three introductions produce all three pairwise inequalities on $A,B,G$; the Physics audience gives $D\ne F$. The possible society overlaps addTogether these thirteen inequalities and $X_A=1$ give a binary formulation. There is no need for an all-different constraint on all seven variables: compatible talks may run in parallel. At least two rooms suffice for the solution below.

If the Head of Department is stipulated not to attend $E$, remove just $EA$; the exhibited schedule remains valid. If actual society membership excludes a specified cohort, remove its corresponding additional conflicts too. This separation makes clear which restrictions are direct requirements and which protect assumed overlapping attendance.

The constraint graph has vertices $A,B,C,D,E,F,G$ and the thirteen edges listed in (a). The following original drawing distinguishes named shared-audience edges from the additional society-overlap edges. Vertex colours show one valid slot assignment; they are not extra constraints.

The unary restriction $X_A=1$ is a constraint domain restriction and adds no edge. For reference, $E$ is adjacent to every other vertex; among the remaining vertices there is a triangle $ABG$, a cycle $BDFG$, and the edge $CD$.

A solution is $(A,B,C,D,E,F,G)=(1,2,1,3,4,2,3)$. Here is a backtracking search with forward checking, listing the chosen value order rather than assuming ascending values. No backtrack is needed on this branch.

Start with the constraint domains in (a). Assign $A=1$; remove $1$ from $B,G,E$. Choose $E=4$; remove $4$ from each remaining neighbour. Now $B,G$ both have domain $\{2,3\}$ and $C,D,F$ each have $\{1,2,3\}$. Choose $B=2$. Its inequality removes $2$ from $G$, forcing $G=3$, and also removes $2$ from $D$, leaving $D\in \{1,3\}$. Assigning $G=3$ removes $3$ from $F$, leaving $F\in \{1,2\}$.

Choose $D=3$. The edge $DC$ reduces $C$ to $\{1,2\}$; $DF$ makes no further deletion because $3$ is already absent from $F$. Choose $F=2$ and then $C=1$. All variables are assigned, and every constrained pair has different values.

In time order, the schedule is

The Head of Department attends slots $1,2,3$ for $A,B,G$; first-year attendees see $C,D$ in slots $1,3$; second-year attendees see $F,G$ in $2,3$; the third-year Keble group sees $B,D$ in $2,3$; Physics attendees see $D,F$ in $3,2$. Slot $4$ is free of every competing talk, so all assumed society overlaps are respected.

A tree decomposition of width $3$ has bagswith tree edges $K_1{K}_2$, $K_2{K}_3$, $K_2{K}_4$.

Every graph vertex occurs in a bag and every constraint edge has both endpoints in some bag. The bags containing any fixed vertex form a connected connected subgraph of a tree: $B$ occurs in $K_1,K_2$, $G$ in $K_1,K_2,K_3$, $D$ in $K_2,K_3,K_4$, and $E$ in all four. The remaining vertices occur once. Hence the running-intersection condition holds. The maximum bag size is four, giving width $4-1=3$.

Under the stated overlap assumptions, $\{A,B,E,G\}$ is a four-vertex clique, so the treewidth is at least $3$; this decomposition attains it. A proof of that lower bound is not needed to use the displayed decomposition.

This is a graph colouring constraint satisfaction problem, with four available colours and one fixed colour. Interpret slot labels as colours. Every conflict edge requires distinct endpoint colours, exactly as in proper graph colouring; independent sets of vertices can share a slot. The unary restriction on $A$ fixes its colour to $1$.

The lecture's 3-colouring problem is the same construction with domains $\{1,2,3\}$. For the present graph under the assumptions in (a), the clique $\{A,B,E,G\}$ prevents a 3-colouring, while (c) supplies a 4-colouring. The fixed colour on $A$ does not otherwise change existence, since an unconstrained colouring can have its colour names permuted to put $A$ in colour $1$.

This four-colour necessity is conditional on the explicit $EA$ overlap. Removing that one edge permits, for example, the 3-colouring $(A,B,C,D,E,F,G)=(1,2,2,3,1,2,3)$; the four-slot schedule remains valid in either model. Thus attendee modelling, rather than the mere availability of four slots, determines the required number of colours.

There is exactly one solution: $X_i=i$ for $i=1,\dots ,n$. Strict increase makes all $n$ values distinct. Since all lie in the $n$-element domain $\{1,\dots ,n\}$, they must use every value, and their increasing order fixes their positions.

Equivalently, $X_i\ge i$ by propagation from the lower endpoint, and $X_i\le i$ by propagating backwards from $X_n\le n$. For general $m\ge n$, choosing any $n$-element subset determines one increasing solution, giving the binomial coefficient $\left(\genfrac{}{}{0ex}{}{m}{n}\right)$; the case $m=n$ gives $1$.

Choose one global direction and impose it on every adjacent pair. Keep $X_i\in \{1,\dots ,m\}$, introduce $D\in \{+,-\}$, and impose for each $i<n$ the relationBecause the same $D$ occurs everywhere, transitivity gives either a strictly increasing whole sequence or a strictly decreasing one. Choosing independently between $<$ and $>$ at each edge would merely require adjacent values to differ and would incorrectly allow zigzags.

If a binary formulation is required, replace each ternary relation by a hidden-variable encoding. Add a variable $Y_i$ with domainUse three binary constraints: the sign component of $Y_i$ equals $D$, its first numeric component equals $X_i$, and its second equals $X_{i+1}$. These enforce exactly the relation above while leaving the original variable domains unchanged. Each auxiliary domain has $m(m-1)$ values.

For $n\ge 2$, the projected solutions in the original $X_i$ variables number $2\left(\genfrac{}{}{0ex}{}{m}{n}\right)$ when $m\ge n$, and zero otherwise. In particular $m=n=3$ gives exactly $(1,2,3)$ and $(3,2,1)$. For $n=1$, direction is irrelevant and the projected solutions number $m$, not $2m$.

Use location, holding and hand-capacity planning fluents, together with static object types. Write $\mathrm{In}(b,k)$, $\mathrm{Holding}(b)$, $\mathrm{At}(k)$ and $\mathrm{Empty}$ for a ball's bucket, the held ball, the arm's location and an empty hand. Static predicates $\mathrm{Ball}(b)$, $\mathrm{Bucket}(k)$ and $\mathrm{Different}(k,\ell )$ identify types and distinct buckets. The latter can equivalently be a action grounding restriction.

For typed parameters, the STRIPS actions areUntyped notation adds the appropriate $\mathrm{Ball}$ and $\mathrm{Bucket}$ facts to every precondition set. Static type and inequality facts have no add or delete effects. A state is a set of true ground facts under the closed-world assumption, and an applicable action produces $(S\setminus \mathrm{Del})\cup \mathrm{Add}$.

Start from a physically valid state: each ball is in exactly one bucket or held; at most one ball is held; the arm is at exactly one bucket; and $\mathrm{Empty}$ is true exactly when no ball is held. The operators preserve these planning state invariants. In particular, picking requires an empty hand, dropping releases the held ball, and moving deletes the old arm location. Moving while holding a ball is permitted, so a separate carried-ball movement action is unnecessary.

Label the balls $a,b,c,d$ and buckets $1,2,3$. Ignoring unchanged static type facts, the initial state's true planning fluents areExpanding it produces exactly three successors. The held ball makes $\mathrm{Empty}$ false, so neither ball in bucket $1$ can be picked up yet.

For $\mathrm{Drop}(d,1)$, replace $\mathrm{Holding}(d)$ by $\mathrm{In}(d,1)$ and $\mathrm{Empty}$; the arm stays at bucket $1$. All four balls are then in buckets, with $a,b,d$ in $1$ and $c$ in $2$.

For $\mathrm{Move}(1,2)$, replace $\mathrm{At}(1)$ by $\mathrm{At}(2)$ and leave every ball planning fluent unchanged, including $\mathrm{Holding}(d)$.

For $\mathrm{Move}(1,3)$, similarly replace only the arm-location planning fluent by $\mathrm{At}(3)$. The arm is now over the destination while still holding $d$; it has not yet dropped that ball.

No other action is applicable: the other drop locations fail their arm-location precondition, no pick has an empty hand, and moves from another source bucket fail their source-location precondition. None of these three successors satisfies ${\bigwedge }_{z\in \{a,b,c,d\}}\mathrm{In}(z,3)$. This describes one forward state-space planning expansion, not an assertion that the search has already found a complete plan.

There are $G=2mn+n(n-1)$ distinct ground actions, or $tG$ time-indexed action variables over $t$ transition steps. Each of STRIPS's pick and drop action schemas has $mn$ type-correct instantiations. A move chooses an ordered pair of distinct buckets, giving $n(n-1)$. Every physical action is a ground action before it receives a time index in SATPlan.These counts exclude static type checks after action grounding and exclude optional persistence/no-op action symbols. Using successor-state axioms supplies persistence without separate no-op action variables. If one action occurrence is allowed per layer, it is selected from the same ground-action set; a parallel encoding also begins with these physical ground actions, but has a different exclusion policy.

A sufficient sequential bound is $T_{\max }=4m+2$ for any physically valid initial and goal states, assuming every bucket is directly reachable. A goal must be consistent with the stated one-hand and one-location invariants. No bound can guarantee a satisfying plan for an inconsistent goal, such as requiring the same ball in two buckets simultaneously.

Here is a constructive bound independent of the number of buckets. If the hand initially holds a ball, drop it in the current bucket, costing at most one action. For each ball that should end in a bucket, move to its current bucket, pick it up, move to its target bucket, and drop it: at most four actions per ball, omitting unnecessary actions. If the final state requires a held ball, reserve it for last, move to its current bucket and pick it up, costing at most two more actions. Finally move the arm to its prescribed final location, costing at most one action.

If the final hand is empty, this costs at most $1+4m+1=4m+2$. If it holds a ball, only $m-1$ balls need bucket placement, giving at most $1+4(m-1)+2+1=4m$ for $m\ge 1$. Thus the common bound is valid. A partially specified, physically consistent goal can first be completed to a valid target state. For the special goal of putting all balls in one bucket with no specified final arm location, $4m$ is already a sufficient bound.

A separate finite-state check is available: physically valid configurations numbercounting an empty hand or the choice of a held ball, and the arm's location. A shortest plan never repeats a state, so $|S|-1$ also bounds a shortest solution whenever one exists. The constructive bound is much smaller.

For an encoding requiring a fixed horizon, permit idle layers, or run SATPlan through all horizons up to the bound. A plan shorter than $T_{\max }$ need not be padded by arbitrary physical actions. The sequential bound also suffices for a parallel encoding, since a serial plan is a permitted special case.

Use balls $a,b$, buckets $1,2$, transition index $k$ and the grounded action schemas from (a). Under a sequential encoding, one example successor-state axiom isBall $a$ is in bucket $1$ afterwards exactly when it is dropped there now, or it was there and is not picked up. Actions involving other balls or arm movement leave this fact unchanged. This is both an effect rule and a persistence rule, rather than an implication that permits spontaneous appearances.

An example action precondition axiom isA selected pick action must have the ball, arm and empty hand in the appropriate current state. The static type conditions have already been satisfied by action grounding.

An example action exclusion axiom isThe single arm cannot pick up both balls in one step. For a serial encoding include such an exclusion for every pair of distinct action occurrences at one layer; with at-most-one rather than exactly-one actions, a layer may idle. Initial-state clauses, goal clauses and corresponding successor-state axioms for all other planning fluents complete the plan-as-SAT construction. The plan-as-SAT approach was introduced by Henry Kautz and Bart Selman in 1992.^[ref]

Use backward deletion of achieved goal requirements; this decides precondition-free ground STRIPS planning in polynomial time. Let $I$ be the initial set of true facts, $G$ the positive conjunctive goal set and $\mathcal{A}$ the ground actions. Assume the usual disjoint add and delete lists; if both lists contain a fact, first normalize the net effect according to the action semantics.

Maintain residual goal set $R=G$ and an initially empty list $L$. While $R⊈I$, look for an action $a$ satisfyingIf no such action exists, reject. Otherwise record $a$ in $L$ and replace $R$ by $R\setminus \mathrm{Add}(a)$. When $R\subseteq I$, return the actions in reverse order of recording. All actions are applicable because their precondition sets are empty.

For soundness, the selected action can be put last in a plan for the current residual goals: it supplies the removed goals and deletes none of the goals still being required. Reversing all recorded selections makes the final state satisfy the original $G$.

For completeness, suppose $R$ is not already satisfied initially but a plan achieves it. Consider the last action in that plan that changes any fact of $R$. Its effective changes cannot delete any member of $R$, because no later action repairs it; it must add at least one member. Thus a candidate exists. Moreover any candidate chosen by the algorithm is safe: removing some requirements gives a subset of $R$, so a plan for $R$, if one exists, also establishes the smaller goal set. Appending the chosen last action then restores the removed requirements without harming the rest. Mathematical induction therefore preserves solvability during all choices.

Each successful iteration removes at least one residual goal, so there are at most $|G|$ iterations and the returned plan has at most $|G|$ actions. Scanning all actions and their effect lists per iteration is polynomial in the input size, for example $O(|G||\mathcal{A}||P|)$ with simple fact-set representations over $P$. Merely taking the union of all add effects would be unsound, since actions can delete each other's achievements. This algorithm is the last-achiever algorithm for precondition-free planning.

Source paper: released examination archive, member 2020/T/a16608w1.pdf. The printed sitting is 27 May 2021; the ZIP directory names 2020. All three questions and all 21 marked subparts are answered. This is the canonical CS paper; the raster-identical Physics-held copy is a source reference, while Mathematics C7.4 is a different examination.^[ref]

An identical copy is available in the released combined PDF, pages 111–115. Its historical folder and attachment name do not change the Computer Science cover identity.

Tensor factors follow their displayed subsystem order, and the rightmost operator acts first. Computational labels are $0,1$; Hadamard- and Pauli-Y-basis labels are the corresponding plus/minus eigenvalue labels. The exact correlations in Question 2 are interpreted as ideal probability-one predictions, not certainty inferred from a finite experimental sample.

In an orthonormal computational basis, the squared norm is the sum of the squared moduli of the coefficients:Thus the vector is normalized and represents a pure state of a qubit. The imaginary part contributes positively to the squared modulus; squaring the coefficient without complex conjugation would give the wrong norm.

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.

No. Perfect discrimination of pure states requires orthogonality, whereasTo see the obstruction directly for a basic measurement, let $\{|b_j⟩\}$ be its orthonormal basis. Certain identification would require disjoint sets of possible outcome labels for two different preparations. For every $j$, at least one of $⟨b_j|{\varphi }_0⟩$ and $⟨b_j|{\varphi }_1⟩$ would therefore vanish. Completeness would then givecontradicting the computed overlap. Failure to distinguish just this pair already rules out certain identification of the three-state family.

Identification is stronger than quantum state exclusion. Here an outcome only needs to rule out its associated preparation. Use the following orthonormal basis for a basic measurementIts defining overlaps satisfy $⟨b_m|{\varphi }_m⟩=0$ for $m=0,1,2$. By the Born rule, observing $b_m$ makes preparation ${\varphi }_m$ impossible. Measure in this basis and send its outcome label $m$; the prize is guaranteed.

For completeness, the conditional probability matrix, with rows $m$ and columns the prepared-state label $j$, isEvery column sums to one and the diagonal vanishes. Each result leaves two possible preparations, so this projective state exclusion does not contradict the impossibility of perfect identification. The family consists of antidistinguishable quantum states.

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.

Reverse communication is also possible. Prepare Alice in $|+{⟩}_A$. Bob encodes $m=0$ as $|+{⟩}_B$ and $m=1$ as $|-{⟩}_B$. Since $X|\pm ⟩=\pm |\pm ⟩$, phase kickback giveswhere $|(-{)}^0⟩=|+⟩$ and $|(-{)}^1⟩=|-⟩$. Alice measures in the Hadamard basis: $+$ means zero and $-$ means one, deterministically.

The target's Pauli X gate eigenvalue becomes a relative phase on the control. This is the operational content of CNOT control reversal in the Hadamard basis; the computational basis control arrow alone does not determine every possible direction of communication.

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.

Alice cannot send a bit to Charlie either. An argument based only on the apparent chronological chain would be insufficient: Alice interacts with Bob before Bob interacts with Charlie. The extra fact is that these particular gates commute.

In Bob's computational basis the complete gate isBoth controlled-NOT gates preserve Bob's control label, and their target operations act on different systems. Thus $WV=VW$. We may consequently regard Bob–Charlie as the first interaction and Bob–Alice as the last one. The final operation on $AB$ cannot change Charlie's reduced density matrix, and Charlie's earlier state cannot depend on Alice's initially separate preparation.

The target no-signalling in a common-control unitary formula makes the independence explicit:Alice's density matrix does not appear. The formula includes arbitrary complex initial amplitudes and every final measurement on Charlie. This conclusion uses the specified pair of gates; a general intervening operation on Bob could change the communication possibilities.

Factor the sum before making an entanglement claim:The state is not entangled: it is a product state. A sum written with several tensor-product terms need not be entangled; those terms may combine into a single tensor product.

The displayed computational basis expansion is already a Schmidt decomposition, with coefficients $\sqrt{1-p}$ and $\sqrt{p}$. For $0<p<1$ both are nonzero, so the Schmidt rank is two. A pure product state has Schmidt rank one. The state is therefore entangled throughout the specified open interval.

Equivalently, the reduced density matrix isThe reduced state is a mixed state, which is impossible for one factor of a pure product state. At the excluded endpoints the Schmidt rank drops to one, giving $|00⟩$ or $|11⟩$.

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.

No: $U$ is not an entangling gate. Its factorization gives, for every product input,which remains a product state. More generally, a convex mixture of product density matrices remains separable under these local unitary operators. Thus being distinguishable from $I\otimes V$ does not require creating entanglement. The first qubit undergoes a genuine local phase gate, while the target undergoes the same $V$ in both branches.

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.

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.

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.

Prepare $|0⟩$, then apply $H$, then $T$. With $T=\mathrm{diag}(1,e^{i\pi /4})$,This uses only the allowed state preparation and elementary gates. The rightmost operator acts first, so $TH$ denotes the temporal order $H$ followed by $T$.

The required superposition is the Bell statePrepare $|00⟩$, apply $H$ to the first qubit, then apply CNOT from the first to the second. The intermediate state is $(|00⟩+|10⟩)/\sqrt{2}$, and the controlled-NOT gate gives the required Bell state. No final basis change is needed: the two displayed expressions represent exactly the same vector.

Write ${\rho }_0=|\varphi ⟩⟨\varphi |=(I+r_{x}X+r_{y}Y+r_{z}Z)/2$. Conjugating by a Pauli matrix keeps its own Bloch component and reverses the other two; for example,In the average of the four conjugations, the coefficient of every nonidentity Pauli matrix is zero. ConsequentlyThe Pauli operator basis gives the Bloch representation of a qubit density operator.^[ref]

This is the qubit Pauli twirl, the dimension-two case of the Heisenberg-Weyl twirling channel. The argument uses only trace one, so it also works for mixed qubit inputs. The preparation label must be forgotten: conditioning on the label would retain a known pure branch rather than the maximally mixed state obtained by the ensemble average.

Take the trine state ensembleAll three states are normalized. Since $1+\omega +{\omega }^2=0$, their average density matrix isGeometrically, their unit Bloch vectors form an equilateral triangle on the equator and sum to zero. Orthogonality is unnecessary for an ensemble decomposition of a mixed state: three distinct, nonorthogonal pure states can give the same maximally mixed average as two orthogonal states.