  This paper initiates the study of hidden variables from the discrete,
abstract perspective of quantum computing. For us, a hidden-variable theory is
simply a way to convert a unitary matrix that maps one quantum state to
another, into a stochastic matrix that maps the initial probability
distribution to the final one in some fixed basis. We list seven axioms that we
might want such a theory to satisfy, and then investigate which of the axioms
can be satisfied simultaneously. Toward this end, we construct a new
hidden-variable theory that is both robust to small perturbations and
indifferent to the identity operation, by exploiting an unexpected connection
between unitary matrices and network flows. We also analyze previous
hidden-variable theories of Dieks and Schrodinger in terms of our axioms. In a
companion paper, we will show that actually sampling the history of a hidden
variable under reasonable axioms is at least as hard as solving the Graph
Isomorphism problem; and indeed is probably intractable even for quantum
computers.
