The proposed Hamming distance is both an admissible heuristic and a consistent heuristic. Write
Every position differing from the target must change at least once along any successful word ladder. One mutation changes only one position, so every solution from has at least steps. This proves , including an unreachable target with . Dictionary restrictions may force extra changes, but cannot remove that lower bound.
Adjacent words differ in one position, so their Hamming distances to differ by at most one. Since every transition costs one,
These are exactly the consistent heuristic conditions. Equivalently, allowing all length- words gives a relaxation heuristic whose exact distance is the Hamming distance; restoring the dictionary can only increase the minimum required number of steps.
Let the input words be , let be their common length, let be the finite alphabet, and let contain the dictionary words of length . Unequal input lengths immediately make the puzzle impossible because a mutation preserves length. A word ladder search problem can use the state space , with initial state ; including handles an input word not itself in the dictionary.
At word , an action is a position–letter pair with , and , permitted precisely when replacing by gives . The search transition model returns that , and the goal test is . If , the empty sequence is accepted; if and , no transition can reach .
Assign each permitted transition cost . A search node at search depth has
Thus minimizing path cost is exactly minimizing the number of mutations. Uniform-cost search, with repeated states handled by graph search and the goal test on selection, finds a shortest word ladder if one exists. Because all costs are equal, breadth-first search gives the same optimal-length guarantee.
With the conventional strictly positive step costs, the five answers in printed order are false, false, true, true, true. The third answer needs that positivity convention: it is false in general if zero-cost edges and unrestricted ties are admitted. Take the goal test on selection from the search frontier, and assume a finite reachable problem with a reachable goal state; finite branching factor and a positive lower bound on step costs give the corresponding tree search guarantees on an infinite problem. These assumptions make the usual A-star search guarantees precise.[ref]
For the first assertion, use a directed graph with transitions of cost , of cost and of cost , where is the only goal state. The perfect heuristic is , , . Greedy best-first search selects the direct goal of cost because its priority is zero. The least path cost is . Knowing the exact remaining distance does not account for an expensive transition already taken.
The same counterexample settles the second assertion. Greedy best-first search selects , while A-star search selects : after expanding , the A-star search priorities are for and for the direct copy of . Thus even the expanded state sets differ.
For the third assertion, let the current nonterminal search node have finite remaining distance . The first transition of a least-cost continuation has some successor with
Every older entry in the search frontier has estimate at least , since the current entry was selected with minimum estimate. A newly generated successor with strictly smaller estimate therefore wins over every older entry. Whichever new successor is selected has smaller remaining distance than the current search node, so the argument repeats. Consequently the selected search nodes form one parent–child chain; include the selected goal, or append it if “expanded” excludes goal processing. This greedy perfect-heuristic descent does not imply least path cost, as the first counterexample demonstrates.
The zero-cost qualification is substantive. Give two successors of cost , add of cost , and add and of cost . The perfect heuristic has values at , at and at . Alphabetical priority ties let greedy best-first search select , which is not one graph path. Thus the unqualified third assertion requires a cost or tie convention absent from the printed text.
For the fourth assertion, a least remaining distance satisfies
on every edge, by taking that edge and then a least-cost continuation. Thus is a consistent heuristic. The usual A-star search graph search finalizes each expanded state's least path cost and returns a least-cost goal.
For the fifth assertion, write . Before a goal is selected, an unexpanded prefix of an optimal graph path remains on the search frontier, with . A-star search therefore selects only search nodes with . Since ,
This compares remaining cost, not search depth or accumulated path cost. The statement can fail with negative costs; those are outside the convention used here.
TODO: the classifications, chosen heuristic functions and least-cost outcomes for G1–G5 cannot be established from the corrupted original Figure 1. The missing edges, costs, priority labels and lower portions of the five search trees are required inputs. The surviving portions and the two heuristic function tables do not determine those answers. No reconstructed graph or invented expansion trace is assumed.
For a readable instance, depth-first search follows the deepest pending branch and breadth-first search expands by search depth; neither generally minimizes unequal edge costs. Uniform-cost search orders by path cost , whereas A-star search orders by . A displayed A-star search score would identify the estimate by subtracting the accumulated path cost. Under nonnegative costs and the usual terminating-search assumptions, uniform-cost search returns a least-cost goal state when testing goals on removal from the search frontier; A-star search additionally needs an admissible heuristic with appropriate reopening, or a consistent heuristic for the usual closed-set implementation. These rules explain how the missing information would be used, but cannot identify a particular damaged search tree.
Use the Bernstein-Vazirani algorithm: initialize n qubits in , apply , query the supplied phase oracle once, apply again, and measure all n computational bits. Immediately after the query the state is
where the dot product in the exponent is taken modulo two. The Walsh-Hadamard transform gives amplitude
Every factor is one if and zero otherwise. Thus the final state is exactly , and the measurement outputs a with certainty after one oracle query. This is the character cancellation behind Bernstein-Vazirani phase kickback; because access here is already to the reduced phase oracle, no extra target ancilla or conversion from a bit-flip oracle is required.
One Grover iteration returns a marked label with certainty. Prepare ; apply the supplied phase oracle to negate amplitudes on the marked inputs; apply the Grover diffusion operator ; and measure in the computational basis. If F prepares from , the reflection is , requiring no further oracle query.
After the oracle the amplitudes are on the unmarked labels and on the marked labels. Their average is
The reflection performs inversion about the mean, . It therefore sends every unmarked amplitude to zero and every marked amplitude to . The resulting normalized state is
Each marked label has Born rule probability , every unmarked label has probability zero, and the marked probabilities sum to . This is one-step exact Grover search with a quarter of the inputs marked, using one reduced-oracle query. The positive integer N must be divisible by four; a qubit implementation may take , but the stated reflection proof does not assume that register convention.
Let be the two output counts. Choose a known preparation unitary F with . The Deutsch-Jozsa algorithm applies the supplied phase oracle and then , declaring constant exactly for outcome 0. Its amplitude on that outcome is
This is the Deutsch-Jozsa test with an arbitrary uniform-state unitary. For , the usual preparation is ; the argument itself needs only a uniform preparation on the stated N-dimensional space.
For an actually constant-up-to-k function, the two counts are and , so the outcome-0 probability is . The error is returning the other label. Therefore
Here the possible count k is nonnegative, and the supplied bound implies . The error is consequently at most ; at it vanishes. This is the error conditional on the stated constant-up-to-k case, not an average over unspecified prior probabilities. For comparison, the printed balanced-up-to-k definition has count difference , so its outcome-0 probability would be , not the expression for the constant-up-to-k case. No change to that promise definition is made.
By the spectral theorem, the nonscalar unitary V has orthonormal eigenvectors with distinct eigenvalues . Choose . Then is not proportional to .
On the product input , the controlled unitary gate produces
Its two conditional target vectors are linearly independent, so the conditional-vector product-state criterion proves that the output is entangled. Equivalently, in the control computational basis and target eigenbasis its coefficient matrix is , whose determinant is . Thus U is an entangling gate. The excluded scalar case would only apply a phase gate to the control and could not entangle the factors; this is the controlled-unitary entangling criterion.
For every nontrivial dimension , no such pure state exists. The literal claim needs this qualification: for , the only measurement outcome is necessarily the same for both parties. The contradiction below requires allowing all complex orthonormal bases, as quantum theory does.
If equal outcomes were certain in the computational basis, all amplitudes with different labels would vanish, so the normalized joint state would have the form
Choose distinct labels and replace their computational vectors in both local bases by and , leaving all other vectors fixed. The joint amplitude for the different outcomes is . Certainty of equal outcomes would force .
Now use the complex pair and in the same way on both systems. The amplitude for different outcomes is , because the conjugated bra factors on the term multiply to . Thus equal outcomes would also force . Combining the two requirements gives . Every label belongs to such a pair when , forcing the zero vector and contradicting normalization. This proves impossibility of universal identical-basis perfect correlations.
The maximally entangled state is not a counterexample: it correlates matching labels when one party uses a basis and the other its coordinatewise complex conjugate basis. Requiring the two complex bases to be identical is different. This distinction also follows from conjugate-state steering from a maximally entangled pair; restricting attention to real bases would miss the contradiction.
For deterministic classical responses, denote the two possible local answers by , and . Certainty in the GHZ game would require
Taking the exclusive or of all four equations gives zero on the left, since every answer occurs twice, but one on the right. This contradiction rules out deterministic certainty. Pre-shared randomness cannot cure it: conditioning on the random seed fixes a deterministic response table, and none succeeds on every allowed input. Thus noncommunicating classical players cannot win with certainty. No uniform distribution on the referee's questions is needed for this worst-case claim.
For the quantum strategy, share the GHZ state and measure the Pauli X gate observable when the local question is 0, or the Pauli Y gate observable when it is 1. Return bit 0 for measurement eigenvalue and bit 1 for eigenvalue . The four relevant operator identities are
For the first identity, the three bit flips exchange and . For each remaining identity, the two Y actions contribute on and on , so they exchange the terms with a minus sign. Local measurements on separate systems commute, and the product of their observed eigenvalues is therefore fixed by the displayed joint eigenvalue. That product equals , giving exactly the required output parity for each promised input. Hence the quantum strategy wins with certainty without communication. This is the GHZ theorem in nonlocal-game form; it does not let a player control another player's individual outcome.

Pinned article: Introduction to the OurBigBook Project

Welcome to the OurBigBook Project! Our goal is to create the perfect publishing platform for STEM subjects, and get university-level students to write the best free STEM tutorials ever.
Everyone is welcome to create an account and play with the site: ourbigbook.com/go/register. We belive that students themselves can write amazing tutorials, but teachers are welcome too. You can write about anything you want, it doesn't have to be STEM or even educational. Silly test content is very welcome and you won't be penalized in any way. Just keep it legal!
We have two killer features:
  1. topics: topics group articles by different users with the same title, e.g. here is the topic for the "Fundamental Theorem of Calculus" ourbigbook.com/go/topic/fundamental-theorem-of-calculus
    Articles of different users are sorted by upvote within each article page. This feature is a bit like:
    • a Wikipedia where each user can have their own version of each article
    • a Q&A website like Stack Overflow, where multiple people can give their views on a given topic, and the best ones are sorted by upvote. Except you don't need to wait for someone to ask first, and any topic goes, no matter how narrow or broad
    This feature makes it possible for readers to find better explanations of any topic created by other writers. And it allows writers to create an explanation in a place that readers might actually find it.
    Figure 1.
    Screenshot of the "Derivative" topic page
    . View it live at: ourbigbook.com/go/topic/derivative
  2. local editing: you can store all your personal knowledge base content locally in a plaintext markup format that can be edited locally and published either:
    This way you can be sure that even if OurBigBook.com were to go down one day (which we have no plans to do as it is quite cheap to host!), your content will still be perfectly readable as a static site.
    Figure 5. . You can also edit articles on the Web editor without installing anything locally.
    Video 3.
    Edit locally and publish demo
    . Source. This shows editing OurBigBook Markup and publishing it using the Visual Studio Code extension.
  3. https://raw.githubusercontent.com/ourbigbook/ourbigbook-media/master/feature/x/hilbert-space-arrow.png
  4. Infinitely deep tables of contents:
    Figure 6.
    Dynamic article tree with infinitely deep table of contents
    .
    Descendant pages can also show up as toplevel e.g.: ourbigbook.com/cirosantilli/chordate-subclade
All our software is open source and hosted at: github.com/ourbigbook/ourbigbook
Further documentation can be found at: docs.ourbigbook.com
Feel free to reach our to us for any help or suggestions: docs.ourbigbook.com/#contact