Why do we have to choose a gauge to quantize a gauge theory? Why do we have to choose a gauge to quantize a gauge theory? This was an exam question but I couldn't answer it.
 A: Contrary to popular belief, it is not necessary to choose a gauge to quantize a gauge theory. It is just convenient, since the non-gauge-fixing approaches are often difficult to implement for all but the simplest cases.
Gauge theories are, in the Hamiltonian picture, certain kinds of constrained Hamiltonian systems. Dirac's canonical quantization procedure, for example, carries out quantization without any kind of gauge fixing occurring:
First, assume the phase space has been extended such that all constraints $G_i(q,p) = 0$ are first-class, i.e. their Poisson brackets with each other vanish weakly (that is, on the constraint surface that is the surface of solutions $G_i = 0$)1:
$$ \{G_i,G_j\} \approx 0 \quad \text{and} \quad \{G_i,H\} \approx 0$$
Dirac quantization now simply seeks the representation of the full algebra of observables - even the constraints and the non-gauge-invariant ones - on a Hilbert space $\mathcal{H}_\text{Dirac}$.
Obviously, this procedure produces a space of states that is too large in the sense that its states are not gauge-invariant, but physical states should be.
Hence, the space of physical states $\mathcal{H}_\text{phys}\subset\mathcal{H}_\text{Dirac}$ must be chosen such that
$$ G_i\lvert\psi\rangle = 0$$
for all $\lvert \psi \rangle \in\mathcal{H}_\text{phys}$ so that the finite gauge transformations act as
$$ \mathrm{e}^{\mathrm{i}\epsilon^iG_i}\lvert\psi\rangle = \lvert\psi\rangle$$
i.e. the physical states are precisely the gauge invariant states.2 Thus, the space of physical states is the intersection of all kernels of the constraint operators, which is the quantum version of the classical constraint surface.
Note that we did not impose a gauge of any kind here. The same idea of "physical state condition" can be seen in the BRST formalism, which, if you don't insist on writing it as a path integral formulation, also doesn't need to choose a gauge condition generically.
The reason you often see a quantization scheme in which a gauge is fixed (like Gupta-Bleuler quantization) is that these historically (at least in the QFT case) came before the other approaches, and that they are often easier to implement or reconcile with the quantization of the "unconstrained parts" of a theory.
As a last remark, it is generally better to not choose a gauge as long as possible, since topological obstructions - so-called Gribov ambiguities - might prohibit us from choosing a gauge consistently on the whole constraint surface.

1Following Henneaux/Teitelboim, we denote weak equalities by $\approx$.
2Note that this only implies invariance under small gauge transformation, i.e. those connected to the identity. Invariance under large gauge transformations would be an additional assumption.
