Coding and Expansion Foundations Assessment Rubric¶

Use this rubric after the learner completes the nine fresh-start foundation lessons, or as a placement test if the learner wants to skip ahead to Conjecture 3 Frontier Alignment.

Passing standard: at least 16/20, with no 0 on questions 2, 6, 7, or 9.

Scoring:

2: correct, concrete, and connected to the Conjecture 3 research map.
1: directionally correct but missing a key definition, example, or research linkage.
0: incorrect, generic, or unable to distinguish the foundation from the frontier claim.

Question 1¶

Prompt: Explain why GF(2) is the natural arithmetic for binary linear codes and give one concrete Hamming-code calculation.

Expected answer:

Binary codewords are vectors in \(\mathbb F_2^n\), with addition modulo 2.
A parity check is a row vector \(h\) and a valid codeword \(c\) satisfies:

\[ h c^T=0 \]

over GF(2).

In the \([7,4,3]\) Hamming code, columns of a parity-check matrix label nonzero binary triples; a single-bit error gives a syndrome equal to the corresponding column, so the syndrome identifies the error location.

Common mistakes:

using real arithmetic instead of modulo 2;
describing the Hamming code only as a memorized parameter triple;
not connecting syndrome to parity-check columns.

Primary lessons:

Question 2¶

Prompt: State the relation between generator matrices, parity-check matrices, dual codes, and CSS commutativity.

Expected answer:

A generator matrix \(G\) spans the code \(C\).
A parity-check matrix \(H\) defines the code as \(\ker H\).
The row space of \(H\) is \(C^\perp\) when \(H\) is a full parity-check matrix.
For a CSS code with \(X\)-check matrix \(H_X\) and \(Z\)-check matrix \(H_Z\), commutativity requires:

\[ H_XH_Z^T=0. \]

Common mistakes:

treating \(G\) and \(H\) as interchangeable;
forgetting the transpose in the CSS condition;
explaining commutativity in Pauli words without the binary matrix condition.

Primary lessons:

Question 3¶

Prompt: Define a Tanner graph and explain what LDPC means in that graph.

Expected answer:

A Tanner graph is a bipartite graph with variable nodes for coordinates or qubits and check nodes for rows of a parity-check matrix.
An edge means that the variable participates in the check.
LDPC means check weight and variable degree are bounded by constants independent of block length.
In a QLDPC stabilizer code, stabilizer checks have bounded weight and qubits participate in boundedly many checks.

Common mistakes:

saying LDPC only means sparse for one finite matrix without the asymptotic bounded-degree condition;
not distinguishing variable degree from check weight;
ignoring the quantum stabilizer interpretation.

Primary lessons:

Question 4¶

Prompt: Explain why girth and local views matter for Tanner codes, and why they are not enough by themselves for the Conjecture 3 barrier.

Expected answer:

Large girth makes small neighborhoods tree-like, which helps local decoding and local independence intuition.
Tanner codes use local constraints on neighborhoods of an underlying graph.
But the Conjecture 3 barrier needs global expansion or cut structure, not just local tree-likeness.

Common mistakes:

treating high girth as the same as expansion;
claiming local views alone prove a hardware lower bound;
forgetting that local checks can still be globally poorly connected.

Primary lessons:

Question 5¶

Prompt: Explain the role of spectral expansion in the course, using the Petersen graph or another bounded-degree example.

Expected answer:

Spectral expansion is a way to certify that a regular graph has no sparse cuts at the relevant scale.
For a bounded-degree graph family, constant spectral gap implies robust edge expansion up to constants.
The Petersen graph is a small example for seeing regularity, local cycles, and expansion-like behavior, but the research program needs asymptotic expander families.

Common mistakes:

treating one small graph as an asymptotic family;
saying spectral gap is only an eigenvalue fact without cut consequences;
using expansion as a vague synonym for "large."

Primary lessons:

Question 6¶

Prompt: Derive the expander-versus-grid bottleneck at the level of balanced cuts.

Expected answer:

A bounded-degree expander-like Tanner graph has \(\Omega(n)\) demand across balanced cuts.
A near-square 2D grid has only \(O(\sqrt n)\) edges across a geometric balanced separator.
If each hardware edge can provide only \(O(1)\) service per layer, then serving \(\Omega(n)\) cross-cut demand through \(O(\sqrt n)\) boundary capacity requires \(\Omega(\sqrt n)\) depth.

Common mistakes:

deriving the result from distance alone instead of cut bottlenecks;
forgetting the bounded-degree or balanced-cut assumptions;
stating the result without the depth calculation.

Primary lessons:

Question 7¶

Prompt: State what an asymptotically good QLDPC family is and describe the Quantum Tanner construction at the level needed for this project.

Expected answer:

Asymptotically good means constant rate and linear distance:

\[ k=\Theta(n), \qquad d=\Theta(n). \]

QLDPC additionally requires bounded-weight stabilizer checks and bounded qubit degree.
Quantum Tanner codes are built from left-right Cayley or related expander structure plus local classical codes such as \(C_0\) and \(C_1\).
For this project, the important point is that theorem-level Quantum Tanner families provide good QLDPC codes and an explicit local-generator structure used in the chosen-presentation route.

Common mistakes:

saying QLDPC means good by definition;
forgetting bounded degree;
describing Quantum Tanner codes only as "some expander code" without local codes or diagonal/incidence structure.

Primary lessons:

Question 8¶

Prompt: Explain what a syndrome-extraction circuit must do and why hardware locality turns it into a depth question.

Expected answer:

Syndrome extraction measures stabilizer checks while preserving the encoded state.
On local hardware, gates can only act along available hardware edges in each layer.
Nonlocal stabilizer support or nonlocal check-service requirements must be compiled into local interactions, which can force depth when many independent demands cross a small hardware separator.

Common mistakes:

treating syndrome extraction as just computing \(Hc^T\) classically;
ignoring ancilla and measurement constraints;
not connecting hardware locality to circuit depth.

Primary lessons:

Question 9¶

Prompt: Distinguish the solved static 2D syndrome-depth result from the remaining CD(T_n,G) frontier.

Expected answer:

The static 2D theorem says good Quantum Tanner families require \(\Omega(\sqrt n)\) depth on near-square 2D local hardware with linear total qubits.
The remaining frontier is not simply proving any 2D lower bound.
It is to formulate and prove the right compiler-native CD(T_n,G) statement, including stabilizer cut-rank demand, submodular cut congestion, and the limits of classical routing semantics.

Common mistakes:

saying the static 2D result is still the main unsolved theorem;
treating CD as already identical to ordinary packet routing;
ignoring presentation-invariance issues.

Primary lessons:

Question 10¶

Prompt: Explain what you would load first before doing new Conjecture 3 research with Codex.

Expected answer:

Start from learner-progress.md to determine the learner state.
For research state, read ../../../index.md and ../../../research/graph-audit.md.
Then load only the named lesson, chapter, or graph nodes needed for the current question.
If a new theorem node or literature update is needed, use the bounded graph literature workflow before teaching it as fact.

Common mistakes:

loading the entire graph by default;
relying on old Heptabase prose as authoritative theorem text;
teaching a new bridge as fact before it exists in the local graph.

Primary sources:

Recording Results¶

After grading, update learner-progress.md with:

assessment date;
score out of 20;
questions missed or partially answered;
whether to continue foundations or start the frontier course;
next recommended lesson.

Also update alignment-dashboard.md if the learner passes this readiness gate.