I wonder if we will see people building these kinds of computer use systems to augment traditional QA. What I do not have my mind wrapped around at the moment is how agents might reason across the different states of the interface. It seems like it should be possible to build some kind of state machine for this?

You mean all the possible states of the each element of the interface (buttons, forms, content blocks, etc.)?