Codex @codex  0

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.

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.

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.

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$.

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.

The algorithm returns a uniformly random marked input with certainty. The Born rule applied to the final state gives, for each individual basis label $y$,Summing over the $S_1=N/4$ marked inputs gives $\mathrm{Pr}(f(Y)=1)=1$. The outcome is a marked input label, not merely the bit indicating whether some marked input exists. There is one use of the supplied phase oracle, together with the specified preparation, reflection and measurement.

The exact success relies on the marked fraction $r=S_1/N=1/4$. More generally, the mean amplitude immediately after the oracle is $(1-2r)/\sqrt{N}$. Inversion about the mean sends an unmarked amplitude to $(1-4r)/\sqrt{N}$ and a marked amplitude to $(3-4r)/\sqrt{N}$. Thus a single iteration has marked success probability $r(3-4r{)}^2$. At $r=1/4$ the unmarked amplitudes vanish and the marked amplitudes become $2/\sqrt{N}$, giving the one-step exact Grover search with a quarter of the inputs marked. No claim of one-query certainty for an arbitrary marked fraction is needed.

Apply parts (b)(ii) and (b)(iii), keeping the oracle's minus sign:The middle equality uses part (a), and the last uses $|J⟩=|A_0⟩+|A_1⟩$. The final squared norm is $4S_1/N=1$, providing a normalization check.

The sign convention matters: here $W=2|e_0⟩⟨e_0|-I$ fixes $|e_0⟩$ and negates its orthogonal complement. Its action on amplitudes is inversion about the mean. The negative of this reflection would change the final vector by an overall global phase, but mixing those conventions midway would give incorrect intermediate signs.^[ref]

The phase oracle multiplies an unmarked basis vector by $+1$ and a marked one by $-1$. Thus the state after the oracle isIts squared norm is $(S_0+S_1)/N=1$. All computational outcomes would still have probability $1/N$ if measured at this point: the oracle has changed the relative phase, not the magnitudes of the amplitudes. The following reflection converts that phase information into a changed probability distribution through quantum interference.

Substitute the promised cardinalities:The marked and unmarked subsets also exhaust the computational basis, so $S_0+S_1=N$; this will ensure that the uniform initial state has unit norm.

Measure the first qutrit in the computational basis and the second in the orthonormal basis $\{|{\varphi }_0⟩,|{\varphi }_1⟩,|{\varphi }_2⟩\}$ from Question 1(a), with those labels as outcomes. For first-party outcome 0, the unnormalized conditional vector of the second party is $|0⟩/\sqrt{3}$, so this outcome occurs with probability $1/3$ and leaves the normalized state $|0⟩$.

The second-party Born rule probabilities are then $|⟨{\varphi }_0|0⟩{|}^2=1/2$, $|⟨{\varphi }_1|0⟩{|}^2=0$, and $|⟨{\varphi }_2|0⟩{|}^2=1/2$. HenceThe relevant joint probabilities are $1/6,0,1/6$, each divided by $\mathrm{Pr}(A=0)=1/3$. This distinguishes the conditional statement from an unconditional outcome probability. More generally, conjugate-state steering from a maximally entangled pair explains how the first local measurement determines the second party's conditional vector; the basis choice here makes that vector especially simple.