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

Quantum Information / Quantum Information Apps

Quantum Information Apps

Exercise PLAN-420

intermediate · boundary · test_public

primary source nl only. Explicit question version 2 with distinct contract-change review; the predecessor question is not equivalent current gold. Core, family and split are retained. No new Lean verification is claimed for this NL view.

Assumptions and conventions

      This question explicitly revises its historical contract. A Lean companion must bind the current contract hash, not the predecessor hash. This is one reserved core, not two exercises.

      Question

      Write Sym^n(C^d) for the vectors fixed by every tensor-factor permutation, and q_d(n) for its dimension. (a) For d>=1 and integer n>=0, construct and normalize an occupation-number basis and prove q_d(n)=binom(n+d-1,n) by stars and bars. (b) For fixed d>=2, give the polynomial's exact degree and leading coefficient and prove q_d(n)/d^n->0. State the d=1, n=0 and zero-dimensional boundaries without using a meaningless fraction.

      (c) Assess, rather than assume, the assertion that de Finetti/cloning constructions 'live entirely inside Sym^n(C^d)' and that polynomial symmetric dimension alone makes their dimension ratios close to one. Give a permutation-invariant density operator not supported in the original symmetric subspace, and prove that a general permutation-invariant density operator on (C^d)^{tensor n} instead admits a purification in Sym^n(C^d tensor C^d), under the explicit regrouping into n system-reference pairs. Explain the partial-trace route from the pure symmetric de Finetti construction to the mixed one. For fixed d>=1 as m->infinity, determine when q_d(m)/q_d(m+k) tends to one, and exhibit a growing-k regime where it does not; relate this to q_d(N)/q_d(M) for cloning. For the displayed projected cloning core K(X)=[q_d(N)/q_d(M)]Pi_M(X tensor I^{tensor(M-N)})Pi_M, M>=N, distinguish symmetric-input trace preservation and symmetric output support from trace preservation on the full input algebra and from an arbitrary channel completion. Finally explain why a single polynomial-dimensional symmetric block neither replaces all Schur-Weyl blocks in spectrum estimation nor establishes efficient circuit complexity. Retain the original count/asymptotic target; do not salvage(c) by silently assuming original symmetric support.

      Hint: mathematical route

      Occupation orbits give the exact symmetric dimension and polynomial/exponential gap. Those facts do not put invariant mixed states in the original symmetric subspace: mixed de Finetti uses paired symmetric purification, while a projected cloning core and its full-channel completion have different support/trace domains.

      1. Normalized occupation-orbit vectors form an orthonormal basis of the permutation-fixed vector space; conjugation-invariant density operators need not have that support, whereas the explicit paired-system purification does.
      2. Stars and bars gives q_d(n)=binom(n+d-1,n); the exact dimension ratios determine de Finetti/cloning regimes, and the projected cloner has trace tr(Pi_N X) before a full-channel completion.
      3. At fixed d>=2 q_d(n) has degree d-1 and leading coefficient1/(d-1)!, so q_d(n)/d^n vanishes; this alone implies neither arbitrary-support reduction, all-regime ratio closeness nor an efficient implementation, and tensor-unit/zero-space cases remain explicit.
      Reference solution

      (a) Fix a product orthonormal basis e_1,...,e_d. For each tuple f=(f_1,...,f_d) of nonnegative integers with sum n, let W_f be the set of distinct words with those occupations and m_f=|W_f|=n!/product_i(f_i!). The vector |f>=m_f^{-1/2}sum_{w in W_f}|w> has norm one. Different f have disjoint word supports, so these vectors are orthogonal. A vector is fixed by every factor permutation exactly when its coefficients are constant on each word orbit W_f; hence the |f> span the fixed-vector space. Stars and bars counts the tuples as binom(n+d-1,d-1)=binom(n+d-1,n), proving the dimension formula rather than merely citing Weyl.

      (b) For fixed d>=1, q_d(n)=product_{j=1}^{d-1}(n+j)/(d-1)! with empty product one. It has degree d-1 and leading coefficient 1/(d-1)!. For d>=2 its ratio to d^n tends to zero: for example the successive-term ratio of q_d(n)/d^n tends to 1/d<1. For d=1 both dimensions are one and the fraction stays one. For n=0 the tensor unit and Sym^0 are C, of dimension one, also when d=0; this is a tensor-unit convention, not a negative-top binomial identity. For d=0,n>0 both spaces have dimension zero and there is no trace-one density operator; the fraction 0/0 is undefined.

      (c) Invariant density operators and fixed vectors are different notions. On two qubits put |a>=(|01>-|10>)/sqrt(2). The swap sends |a> to -|a>, so rho=|a><a| is invariant under conjugation by permutations, but Pi_2 rho Pi_2=0. For a genuinely mixed example, I_4/4 is also permutation invariant and has nonzero antisymmetric support. Thus the original blanket support assertion is false, not a consequence of the dimension count.

      Here is the actual enlarged-space route, for a nonempty state carrier d>=1. Choose matching product bases on A=(C^d)^{tensor n} and R=(C^d)^{tensor n}, and the UNNORMALIZED maximally entangled vector |Omega>=sum_w |w>_A|w>_R. Define |Psi>=(sqrt(rho) tensor I_R)|Omega>. Its squared norm is tr(rho)=1 and tr_R|Psi><Psi|=rho. If Q_pi rho Q_pi^dagger=rho, spectral functional calculus gives Q_pi sqrt(rho)=sqrt(rho)Q_pi. The permutation matrices are real in the chosen product basis, so (Q_pi tensor Q_pi)|Omega>=|Omega>, and therefore the same simultaneous permutations fix |Psi>. Explicitly reorder A_1...A_n R_1...R_n into (A_1 R_1)...(A_n R_n); this identifies |Psi> with a vector in Sym^n(C^d tensor C^d). Its local dimension is d^2, not d. Applying the pure symmetric de Finetti approximation to the paired systems and tracing each retained reference system gives a mixture of sigma_A^{tensor k} (generally mixed sigma_A), with trace-norm error not increased by partial trace. This uses the pure theorem as an input and the exact purification bridge, not a claim of original-space symmetric support or a new proof of the entire de Finetti theorem.

      For fixed d and nonnegative integers m,k, q_d(m)/q_d(m+k)=product_{j=1}^{d-1}(m+j)/(m+k+j). For d>=2 and m->infinity, this tends to one precisely when k/m->0. Sufficiency holds factor by factor; conversely the product is at most (m+d-1)/(m+k+d-1), so convergence to one forces k/m->0. If k/m->c in (0,infinity), the limit is (1+c)^{-(d-1)}; if k/m->infinity it is zero. In particular d=2,k=m gives (m+1)/(2m+1)->1/2, despite both dimensions being polynomial. For d=1 the ratio is always one. These are asymptotic statements, not a division-by-m formula at m=0; the exact product remains defined there. Cloning has M=N+k: fixed M-N, or more generally M-N=o(N), gives a ratio tending to one at fixed d, but M/N->c>1 gives c^{-(d-1)}. For the mixed de Finetti route the relevant pure-space dimensions have local parameter d^2. Merely knowing polynomial-versus-exponential growth proves none of these ratio regimes by itself.

      For d>=1 and M>=N>=0, let Pi_r denote the symmetric projector. The displayed K is completely positive (tensoring with identity is CP, compression is CP) and every output is supported in Sym^M. To check its actual trace domain, A=tr_{M-N}(Pi_M) is supported in Sym^N because every fully symmetric M-vector is fixed by permutations of its first N factors. A commutes with U^{tensor N}; irreducibility of Sym^N and tr(A)=q_d(M) give A=[q_d(M)/q_d(N)]Pi_N. Hence tr K(X)=tr(Pi_N X), which equals tr X for symmetric-supported inputs and is <=tr X for positive X. K is trace nonincreasing on the full input algebra, not in general trace preserving there. N=M=2,d=2 and the antisymmetric rho above give K(rho)=0 as an explicit failure of full trace preservation.

      For any fixed output density sigma, the completion Ktilde(X)=K(X)+tr[(I-Pi_N)X]sigma is a CP trace-preserving full channel: the added functional is positive and hence CP, and the trace deficit is exactly supplied. It agrees with K on symmetric-supported inputs. But if sigma is not symmetric-supported and I-Pi_N is nonzero, its full output need not lie in Sym^M. Choosing symmetric-supported sigma gives a completion with symmetric range; the formula and source exercise do not say that every completion, or every arbitrary cloning channel, has that property. When the input already equals its symmetric space (N=0 or1, or d=1), K itself is trace preserving. These formulas are undefined through division by zero on zero-dimensional positive-power spaces and are not asserted there.

      Finally, for rho=I_2/2 and n=2, the antisymmetric Schur-Weyl block has probability tr(Pi_anti rho^{tensor2})=1/4. Spectrum estimation therefore cannot discard every nonsymmetric block. Polynomial dimension of the ONE symmetric irrep, the number of all partition labels, and the exponentially large ambient Hilbert-space dimension are different quantities. The count supports structural compression in the stated domains; it is not a gate-count, finite-precision algorithm, or universal implementation theorem.

      Assessment rubric
      1. Builds normalized sums over DISTINCT word orbits with m_f=n!/product f_i!, checks orthogonality and spanning of the fixed-vector space, including n=0. (1 weight)
      2. Counts occupations by stars and bars and gives the exact degree d-1/leading coefficient1/(d-1)!; proves the vanishing fraction only at fixed d>=2, and handles d=1, d=0 and tensor-unit boundaries without 0/0 or an invalid binomial formula. (1 weight)
      3. Refutes invariant-density implies original symmetric support; explicitly constructs and normalizes the sqrt(rho) purification, verifies its marginal and simultaneous permutation invariance under paired regrouping, and correctly uses local dimension d^2 and partial-trace contractivity for the mixed de Finetti route. (1 weight)
      4. Derives the exact dimension-ratio product and the fixed-d k=o(m) regime (and counterregime k~m), distinguishes the projected cloner's symmetric input/output and full trace-nonincreasing domain via tr K(X)=tr(Pi_N X), explains a full-channel completion and its possible nonsymmetric output, and does not replace all Schur sectors or infer efficient complexity from one polynomial dimension. (1 weight)

      Graph-grounded prerequisites

      These are support/source anchors, not an automatically extracted theorem-dependency proof.

      • Matrix analysis (frozen curriculum anchor; see graph registry)
      • Probability and sampling (frozen curriculum anchor; see graph registry)
      • Operator and semigroup theory (frozen curriculum anchor; see graph registry)
      • Tensor networks (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: 45a21ee48e1dc2c02a9beeb998788a1beaa4f9d6d20c4546d8471e8639fa0f64

      Item digest: 27e88d8c63a6fe35198046aa617e4f523d7ca861541dc630b50b35f6bb407732

      Graph snapshot: qcb-snapshot-ffa644f0da3031a1ce754b9a

      Authored support steps: 3. This is not measured graph distance or model difficulty.

      Question revision lineage

      { "question_version": 2, "predecessor_key": "qcb-core-plan-420-symmetric-dimension-weyl-formula-boundary", "predecessor_item_digest": "1951692e1270730eeefd5b8d7e53d434e0046252fa59c28cb2f041fce9ee1ac7", "predecessor_contract_hash": "1857618de806df562b2c3ddb17c912a9afd8dfb57dc32230d8c73ca62d140170", "current_contract_hash": "45a21ee48e1dc2c02a9beeb998788a1beaa4f9d6d20c4546d8471e8639fa0f64", "changed_contract_fields": [ "question" ], "repair_record": "shared/repairs/plan-420-symmetric-support-dimension-question-successor.json", "repair_record_digest": "a4516f2e94dc0f7150f8f8fc581ebfad4dd3c5d1110bae63036c4353f90c4367", "review_record": "reports/textbook-v1/repairs/plan-420-symmetric-support-dimension-question-successor-review.json", "review_digest": "7a0c60fc1030e4cf8efc43e1af1508e216037648680acd1cacb72bae53ae87ad", "equivalence_to_predecessor_claimed": false, "additional_core_count": 0 }