QuantumComputinglib learn · inspect · formalize
Checked on this commit 4,524 public declarations commit 4e2c5b2c0be5 Build record

Quantum Scientific Computing / Scientific Algorithms

Scientific Algorithms

Exercise PLAN-204

advanced · counterexample · test_public

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.

  1. 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.
  2. 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).
  3. The forced two-effect sum has trace2/(1-|c|^2)>2 for0<|c|<1, contradicting completeness on the two-dimensional space.
  4. Thus overlapping distinct states cannot have a valid unambiguous measurement with only the two conclusive labels.
  5. 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
  1. 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)
  2. 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)
  3. 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)
  4. 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)

Download the shared core 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.

Read the Lean track and existing diagnostic warmups

Sources and provenance

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" }