[Cryptography] How does bitcoin find if a transaction output has already been used.

[Garlo Nicon]

"How does the validator figure out if one of the transaction outputs
has already been used?"
"Is there a global and canonical lookup mechanism for the mutable
state that is a defined part of the protocol, or could each peer
implement its own custom idiosyncratic magic mechanism?"

The second option. As long as nodes sharing more than half computing
power are honest and producing the same results, the whole network is
considered honest.

"How do the peers know they all have the same mutable state?"

They do not have, because not all of them are collecting everything.
There are two types of nodes: full nodes and light nodes. Only full
nodes are checking everything from genesis block to present. Light
nodes trust other peers that there is some point when they can "throw
away earlier blocks". Each light node can choose that point
differently, but sooner or later they find out they need some
transactions placed in that "earlier blocks". In this case they can
either download missing blocks and validate transaction by themselves
or trust other peers and skip that transaction.

"Do they have a checksum for the mutable state at block X?"

Internally they can do everything to improve performance, as long as
they generate results accepted by the network.