Scientific Algorithms
Exercise PLAN-204
primary source nl only. Additive answer successor with distinct content-bound review; historical rejected answer retained only for audit. No new Lean verification is claimed for this NL view.
Assumptions and conventions
- 0 < |c| < 1 (states overlap but are distinct)
- The ambient space is span{|psi>,|phi>}, two-dimensional
- Unambiguity means a conclusive label never fires on the wrong state
- |psi_perp>, |phi_perp> are the normalized complements defined in the problem
- A POVM must have PSD elements summing to I on the relevant space
Question
Two normalized but possibly non-orthogonal pure states |psi> and |phi> are given with overlap c := <psi|phi>, |c| < 1, and we are promised the unknown state is one of them. Consider the three-element POVM with P_psi = (1/(1+|c|)) |phi_perp><phi_perp|, P_phi = (1/(1+|c|)) |psi_perp><psi_perp|, and P_? = I - P_psi - P_phi, where |psi_perp> := (|phi> - c|psi>)/sqrt(1-|c|^2) and |phi_perp> := (|psi> - c*|phi>)/sqrt(1-|c|^2). Demonstrate by a concrete counterexample-style argument that NO two-element POVM {E_psi, E_phi} (with only the two conclusive labels and no inconclusive outcome) can be unambiguous, i.e. cannot simultaneously satisfy <phi|E_psi|phi> = 0 and <psi|E_phi|psi> = 0 while being a valid POVM, whenever 0 < |c| < 1. Then verify that the given three-element POVM is unambiguous and explain why introducing P_? is exactly the structural escape that restores validity.
Hint: mathematical route
Correct complex conjugation fixes the forced-weight contradiction for conclusive-only unambiguous discrimination; the positive inconclusive effect provides the slack for a valid three-outcome POVM.
- PSD zero expectation implies E_psi annihilates phi; in the two-dimensional span its support is the normalized phi_perp line, and similarly for the other effect.
- With phi_perp=(psi-conj(c)phi)/sqrt(1-|c|^2), the correct overlap is sqrt(1-|c|^2); completeness forces both weights to1/(1-|c|^2).
- The forced two-effect sum has trace2/(1-|c|^2)>2 for0<|c|<1, contradicting completeness on the two-dimensional space.
- Thus overlapping distinct states cannot have a valid unambiguous measurement with only the two conclusive labels.
- The given smaller weights make the conclusive sum a positive contraction with spectrum1 and(1-|c|)/(1+|c|); its positive complement restores completeness while preserving unambiguity.
Reference solution
Use the bra-ket convention of the question: c=<psi|phi>, conjugate-linear in the bra and linear in the ket. Put r=|c| and d=1-r^2>0. Let u=phi_perp=(psi-conj(c)*phi)/sqrt(d) and v=psi_perp=(phi-c*psi)/sqrt(d). Expanding the inner products gives ||u||=||v||=1, <phi|u>=0 and <psi|v>=0. In particular <psi|u>=(1-conj(c)*c)/sqrt(d)=sqrt(d), and <phi|v>=sqrt(d). The coefficient here is conj(c), not c; replacing it by c would incorrectly equate 1-c^2 with 1-|c|^2 for a complex overlap. No rephasing assumption is imposed.
Suppose a two-element POVM with just the two conclusive labels existed. Positivity and <phi|E_psi|phi>=0 imply E_psi*phi=0, since that expectation is ||sqrt(E_psi)*phi||^2. Self-adjointness then places its range in phi's orthogonal complement. In the specified two-dimensional span this forces E_psi=a*|u><u| for some a>=0. Likewise E_phi=b*|v><v|. Completeness evaluated on psi, with the other expectation zero by unambiguity, gives a*d=1; evaluating on phi gives b*d=1. Hence a=b=1/d. But the resulting sum has trace2/d>2, whereas the identity on the two-dimensional space has trace2. This is a contradiction for every 0<r<1. A sharp alternate check is E_psi*psi=psi from completeness and E_phi*psi=0; then self-adjointness and E_psi*phi=0 would force c=<psi|phi>=<psi|E_psi*phi>=0, contradicting the same assumption.
For the proposed three effects, let F be the linear map whose two columns are u and v. Their overlap is <u|v>=-c, so F^dagger*F has diagonal entries1 and off-diagonal entries -c,-conj(c). Its characteristic polynomial is (1-lambda)^2-r^2; the eigenvalues are 1+r and 1-r. Since r<1, F is invertible on the two-dimensional span and F*F^dagger has the same eigenvalues. Therefore S=P_psi+P_phi=(F*F^dagger)/(1+r) has eigenvalues1 and (1-r)/(1+r). It is positive and at most the identity, so P_?=I-S is positive, with eigenvalues0 and 2r/(1+r). Each conclusive effect is positive and completeness holds by definition. The orthogonality relations above give zero probability for either wrong conclusive label.
On input psi, the correct conclusive probability is d/(1+r)=1-r, the wrong probability is zero and the inconclusive probability is r; the same holds with psi and phi exchanged. Introducing P_? supplies exactly the positive slack missing from a conclusive-only complete measurement. This verifies the stated construction, not uniqueness or optimality among every possible prior-weighted discrimination scheme. At r=0 the obstruction disappears and two orthogonal projectors suffice; r=1 is excluded because the complement formulas divide by zero. The question's actual regime is 0<r<1. No circuit, finite-bit cost or new Lean closure is inferred from these operator calculations.
Assessment rubric
- Uses positivity/zero expectation to annihilate the wrong state and two-dimensional self-adjointness to obtain a|phi_perp><phi_perp| and b|psi_perp><psi_perp|. (1 weight)
- Computes <psi|phi_perp>=(1-conj(c)c)/sqrt(1-|c|^2)=sqrt(1-|c|^2), with the actual complex conjugate, and derives a=b=1/(1-|c|^2) from completeness without restricting c to real. (1 weight)
- Obtains trace2/(1-|c|^2)>2, or an equivalent self-adjointness contradiction forcing c=0, to rule out every conclusive-only two-element POVM for overlapping states. (1 weight)
- Verifies the given three effects are PSD and complete, with zero wrong-label probabilities. Derives the rank-one-sum spectrum1±|c| and explains the positive inconclusive slack; does not assert a unique measurement or arbitrary-prior optimum. (1 weight)
Graph-grounded prerequisites
These are support/source anchors, not an automatically extracted theorem-dependency proof.
- Operator and semigroup theory (frozen curriculum anchor; see graph registry)
- Probability and sampling (frozen curriculum anchor; see graph registry)
- Block Encoding (frozen curriculum anchor; see graph registry)
- Matrix analysis (frozen curriculum anchor; see graph registry)
Lean view and evidence boundary
No aligned Lean view has been admitted for this native core in this textbook checkpoint. This is not a claim that the underlying mathematics lacks a formal proof. Contributions must preserve this exact target contract and split.
Sources and provenance
- website/research/sources.json
lin-wiebe-2026-qasc
Source SHA-256:9f85f45f20ed5a46931ad0dec3b94ee09748bc56e39fae29b0aefe910440b0ae· MIT metadata only - Primary source
Contract: b1569085f93b8ecb592f938cc36e92f9283b3fe8ac30012a7073869eb995671f
Item digest: 978453b6eb90931fa2ea361e9bf82185e9a84e1604d41632767f0242a529507e
Graph snapshot: qcb-snapshot-ffa644f0da3031a1ce754b9a
Authored support steps: 5. This is not measured graph distance or model difficulty.
Answer revision lineage
{ "predecessor_item_digest": "d925946e833792c3cf95b2b993cd3b820be35abfd5c259fdb68384b3f29d3558", "predecessor_key": "qcb-core-plan-204-unambiguous-discrimination-inconclusive-necessity", "repair_record": "shared/repairs/plan-204-complex-conjugation-repair.json", "repair_record_digest": "bf3c01e5a75f04338bc73b1803fe7dbd7447f815747aee41380175ead74b16fb", "review_record": "reports/textbook-v1/repairs/plan-204-complex-conjugation-repair-migration-revalidation-review.json", "review_digest": "79dfb46418a93cef899a657194add6a16e21e6257ffd1ce97b40ae92fa68cde9" }