How can a disentangled state be contextual? I (re-)learned about Bell tests from the ground up based on this very intuitive lecture by Spekkens. In a nutshell, realism is violated whenever measurement statistics cannot be reproduced by preexisting states. In algebraic terms, realism is a convex hull and any measurement statistics outside of that hull are essentially violations of realism. One can thus think of the surface of the hull as essentially the "border" represented by Bell's inequality.
Enter quantum mechanics: The textbook example is that of an entangled state which turns out to generate statistics outside the realism hull. I therefore concluded (perhaps wrongly) that it is the entanglement, i.e., the multi-modal quantum coherence at the measurement endpoints, that is the one and only secret ingredient for trespassing beyond the realism boundary.
You can then imagine my horror when reading about the Peres-Mermin square of Kochen-Specker fame, where realism can be defeated by any state, be it disentangled or even mixed (aka. "classical", by my book).
Where did I go wrong in my understanding of realism and the importance of quantumness in violating it? (Cf. for example, this article on demonstrating violations of realism using IBM's quantum computer.)
 A: Contextuality has some relation with entanglement but it enters quantum theory from another route regarding observables and not states.
The idea is to try to construct a hidden variable theory where each quantum observable $A$ (every selfadjoint operator on the Hilbert space of the system we are considering) of a quantum system has always a definite value (realism) $v_\lambda(A)\in \mathbb{R}$ and this value does not depend on the other observables one intends to measure (non-contextuality). $v_\lambda(A)$ only depends on the hidden variable $\lambda$. This variable stochastically fluctuates for some classical reason (as in classical statistical mechanics) and this accounts for the apparent stochasticity of outcomes.
The problem arises when one also assumes that, referring to pairwise compatible observables, standard classical relations must be  valid
$$v_\lambda(A+B)= v_\lambda(A)+ v_\lambda(B)\quad v_\lambda(AB)=
v_\lambda(A)v_\lambda(B)\qquad (1)$$
for all observables. Or, in another version, for all YES-NO observables.
If the Hilbert space $H$ has finite dimension, the an assignment $B(H)_{sa} \ni A \mapsto v_\lambda(A)$ satisfying the requirements above (realism, non-contextuality, and functional relations (1)) does not exist as a consequence of Gleason's theorem.
As you see I have never mentioned quantum states, entangled or not. The problem is with the structure of the space $B(H)_{sa}$ of observables.
However states enter the proof of the above version of the Kochen-Specker theorem: the assignment $B(H)_{sa} \ni A \mapsto v_\lambda(A)$ with the said properties defines a quantum state, but this type of quantum state is not allowed by a topological consequence of Gleason's theorem.
If $H$ is infinite dimensional, as far as I know, a weak continuity hypothesis should be added to obtain the stated no-go result.
There is however a relation with entanglement. It is possible to prove that for a bipartite quantum system (momentum + polarization of a single photon), the CHSH inequality cannot be violated if there exist a hidden variable theory which satisfies the above hypotheses capable to explain the outcomes of two pairs of Bell-like observables. Outcomes of measurements on entangled states (Bell states) produce an explicit no go result.
A: As clarified in a comment, the question asks for more insight about how the Peres-Mermin square manages to show that hidden variables must be contextual (i.e., chosen differently based on what else is being measured) even when they're only required to reproduce quantum theory's predictions for states that are initially unentangled. In other words, how can a no-go theorem about hidden variables not involve entanglement in some way?
The Peres-Mermin demonstration works for any initial state, even if it's not entangled. However, I'll show that entanglement is still involved in this sense: for at least one of the observables in the Peres-Mermin demonstration, a measurement of that observable necessarily produces an entangled state if the initial state was not already entangled. I'll prove this after reviewing the Peres-Mermin setup to establish notation.
 Review of the Peres-Mermin setup 
Let $|0\rangle$ and $|1\rangle$ be an orthonormal basis for a single qubit, and define operators $X$ and $Z$ by
\begin{align}
\newcommand{\la}{\langle}
\newcommand{\ra}{\rangle}
 X|0\ra &= |1\ra
&
 Z|0\ra &= |0\ra
\\
 X|1\ra &= |0\ra
&
 Z|1\ra &= -|1\ra.
\end{align}
These satisfy $X^2=1$, $Z^2=1$, and $XZ=-ZX$. For arbitrary single-qubit states $|a\ra$ and $|b\ra$, use the abbreviation
$$
 |ab\ra\equiv|a\ra\otimes |b\ra.
$$
Let $X_1$ and $Z_1$ denote the operators that apply $X$ and $Z$ to the first qubit, and let $X_2$ and $Z_2$ denote the operators that apply $X$ and $Z$ to the second qubit. The Peres-Mermin setup uses this set of nine operators, arranged in a $3\times 3$ array to make the pattern clear:
$$
\begin{matrix}
    X_1 & \  \ X_2 & \  \ X_1 X_2\\
    Z_2 & \  \ Z_1 & \  \ Z_1 Z_2\\
    X_1 Z_2 & \  \ Z_1 X_2 & \  \ X_1 X_2 Z_1 Z_2
\end{matrix}
$$
These nine operators are all hermitian, and they all have eigenvalues $\pm 1$. Let's suppose they are all observables, which is allowed by the general principles of quantum theory.
 Example 
I won't repeat the whole Peres-Mermin argument here, but recall that it doesn't assume any particular state. What I will do here is illustrate the fact that no matter what state we choose, at least one of these observables produces an entangled state when it is measured. I'll prove that in the next section.
First consider an example: suppose we start with the state $|00\ra$. What happens when $X_1 X_2$ is measured? The possible outcomes are represented by the projection operators onto the observable's eigenspaces. Since $(X_1 X_2)^2=1$, these projection operators are
$$
 P_\pm\equiv \frac{1\pm X_1 X_2}{2}.
$$
Applied to the state $|00\ra$, these give
$$
 P_\pm |0 0\ra = \frac{|0 0\ra\pm |1 1\ra}{2},
$$
which is entangled. This illustrates how measuring one of the Peres-Mermin observables can lead to entanglement even if the initial state was not entangled.
 Proof 
To prove that entanglement is unavoidable, suppose that the initial state has the form $|ab\ra$, so it is not yet entangled. Consder the observable $Z_1 Z_2$. Using the projection operators $(1\pm Z_1 Z_2)/2$, we can see that this observable has two eigenspaces. The eigenspace with eigenvalue $+1$ is spanned by $|00\ra$ and $|11\ra$, and the eigenspace with eigenvalue $-1$ is spanned by $|01\ra$ and $|10\ra$. Within the $+1$ eigenspace, only two states are unentangled, namely $|00\ra$ and $|11\ra$. Within the $-1$ eigenspace, the only two unentangled states are $|01\ra$ and $|10\ra$. Therefore, to ensure that entanglement is not produced by a measurement of $Z_1 Z_2$, the initial state (if it's not already entangled) must satisfy both of these conditions:

*

*It must be orthogonal to either $|00\ra$ or $|11\ra$.


*It must be orthogonal to either $|01\ra$ or $|10\ra$.
Now let $|\pm\ra\equiv |0\ra\pm|1\ra$ denote the eigenstates of $X$. Applying the same logic to the observable $X_1 X_2$, we see that the initial state must also satisfy both of these conditions:


*It must be orthogonal to either $|++\ra$ or $|--\ra$.


*It must be orthogonal to either $|+-\ra$ or $|-+\ra$.
Applying the same logic to the observables $X_1 Z_2$ and $Z_1 X_2$ leads to these conditions on the initial state:


*It must be orthogonal to either $|0+\ra$ or $|1-\ra$.


*It must be orthogonal to either $|0-\ra$ or $|1+\ra$.


*It must be orthogonal to either $|{+}0\ra$ or $|{-}1\ra$.


*It must be orthogonal to either $|{-}0\ra$ or $|{+}1\ra$.
Altogether, we have a list of eight conditions that the initial state $|ab\ra$ must satisfy in order to remain unentangled whenever any of the Peres-Mermin observables is measured. But satisfying all eight of these conditions is impossible! To see why, note that if $|ab\ra$ is orthogonal to $|a'b'\ra$, then either $\la a'|a\ra=0$ or $\la b'|b\ra=0$. Therefore, in order to satisfy the eight conditions listed above, the initially unentangled state $|ab\ra$ must satisfy these conditions:


*$|a\ra$ is orthogonal to either $|0\ra$ or $|1\ra$ or $|+\ra$ or $|-\ra$.


*$|b\ra$ is orthogonal to either $|0\ra$ or $|1\ra$ or $|+\ra$ or $|-\ra$.
But if $|a\ra$ and $|b\ra$ are both orthogonal to $|0\ra$, then we know that $|ab\ra = |11\ra$, which violates condition 3. This example should make the pattern clear: no matter what other two-qubit combination we choose to satisfy conditions 9 and 10, it will violate at least one of the conditions 1-8. In conclusion, no matter what initially unentangled state we choose, at least one of the observables in the Peres-Mermin setup will produce an entangled state when measured, for at least one of the two possible outcomes. In this sense, the Peres-Mermin demonstration necessarily involves entanglement at some point, even though it doesn't care which initial state we use.
 Perspective 
This result doesn't necessarily mean that our concept of quantumness should revolve around entanglement. A related result called the Kochen-Specker theorem uses a three-dimensional Hilbert space, and since three is a prime number, that Hilbert space can't be factorized, which means the usual concept of entanglement can't be applied in that case. The quantumness of quantum theory is better regarded as a consequence of having mutually noncommuting observables. Entanglement enters the picture because most states in a (factorized) Hilbert space are entangled, and because demonstrations of quantumness must explore enough of the Hilbert space to exploit the observables' noncommutativity.
