In this paper the concept of a multi-valued non-deterministic (propositional) matrix, in which non-deterministic computations of truth values are allowed, is extended to languages with quantifiers. We describe the difficulties involved in applying the two main classical approaches to interpreting quantifiers, the objectual and the substitutional, and solve the difficulties in the case of the latter. Then we turn to the two-valued case, and explore the effects in this context of each of the four standard Gentzen-type rules for the classical quantifiers. As an example, a sound and complete two-valued non-deterministic semantics is provided for a family of first-order proof systems.