How many photons does it take to measure a linear polarization? A star emits perfectly (100%) linearly polarized light at an arbitrary angle.
How many photons must you detect to measure this angle to a precision of n binary digits?   (with greater than 50% probability of being correct.)
What is the best strategy for performing this measurement?
 A: Edited to add part III
$\newcommand\ket[1]{\left| #1 \right>}
\newcommand\ketbra[1]{\ket{#1}\left< #1 \right|}$
If you have $N=2^n$ possible polarization at angle $k\frac\pi N$ with $k\in[ 0 .. N-1 ]$, the possible states of $\nu$ photons can be written 
$\ket{k,\nu}=\left(\frac{\ket0+e^{2ik\pi/N}\ket1}{\sqrt2}\right)^{\otimes\nu}$.
A key parameter for the probability of confusing two different angle $k$ and $k'$ is the scalar product 
$$\left<k',\nu\middle|k,\nu\right>=\left(\cos\left([k-k']\frac\pi N\right)\right)^\nu$$
I. Discrimination between two states
If I restrict the problem to the discrimination between two angles $k$ and $k+1$, the optimal theoretical measurement is well known and is given by the Helstrom discrimination. The success probability is given by
$$P_c=\frac12\left[1+\sqrt{1-\left|\left<k',\nu\middle|k,\nu\right>\right|^2}\right]$$
If you want $P_c\ge 1-\varepsilon$ with $\varepsilon\ll1$, this becomes
$$\begin{align}
\left(\cos\frac\pi N\right)^\nu&\le2\sqrt{\varepsilon(1-\varepsilon)}\\
\nu&\ge\frac{\frac12\log\varepsilon+\log2+\frac12\log(1-\varepsilon)}{\log\left(\cos\frac\pi N\right)}
\end{align}$$
If $N=2^n\gg1$, we have $\cos\frac{\pi}{N}\simeq 1-\frac12\left(\frac\pi N\right)^2$ and therefore $\log\left(\cos\frac\pi N\right)\simeq-\frac{\log e}{2}\left(\frac\pi N\right)^2$
We have then
$$
\nu\ge N^2\frac2{\pi^2}(-\ln\varepsilon-\ln2-\ln(1-\varepsilon))
$$
So in this case, the number of needed photons in of the order of $N^2=2^{2n}$, with a prefactor depending on $\varepsilon$.
The Helstrom measurement itself seems difficult to perform, but an adaptative set-up (the Dolinar receiver) compining interferometric displacement and single photon detectors allows to achieve this performance when the states are coherent states. I suppose a similar set-up can be built for polarizations.
II. The more general problem, estimated through entropy
Your problem is not a discrimination problem, but the distinction among many angles. The amount of information one can encode in $\nu$ photons identically 
polarized along an arbitrary angle $\theta$ is given by by the von Neuman entropy of the mixed state $\rho_\nu=\int d\theta\ketbra{\theta,\nu}$. 
Rewriting $\ket{k,\nu}$ and some algebra can show that this entropy is the entropy of the binomial distribution of parameters $p=\frac12$ and $n=\nu$.
This entropy is $\frac12\log\frac{\pi e\nu}{2} + O\left(\frac1\nu\right)$. An order or magnitude of the $\nu$ needed to distinguish between $2^{2n}$ polarization is then given by
$$\begin{align}
n\simeq\frac12\log_2\frac{\pi e\nu}{2}\\
\nu\simeq\frac{2^{2n+1}}{e\pi},
\end{align}$$
Which is of the same order of magnitude than the discrimination.
III. Unambiguous discrimination
Another way to look at the problem is the number of photon needed to perform a na unambiguous discrimination (UD) measurement. A UD measurement is a measurement which never makes an error, but sometimes fails. Of course, given the non-orthogonality of the states, this failure probability can never be zero, and is 100% when the number of photon is too small. The problem is a special case of the one Chefles and Barnett studied here here. The first non-zero success probability is for $\nu=N-1$, but this probability is small ($\nu2^{-\nu}$). It increases every time $\nu$ increases by 2, but I've found no simple expression (and I've tried some time for a paper). I guess (from the previous parts) the probability becomes non-negligible only when $\nu\sim N^2$.
A: After thinking about it overnight, I think I can prove an upper limit of order 2^($2n+1$). Early in the search, I think it is advantageous to search at multiple angles, say 0, 45, 90 and 135 degrees equally until you now approximately where the angle is.  Thereafter, you can search primarily at 45 degrees away from the polarization angle.  That way your probability of success is approximately 50% for each photon, and you gain the maximum amount  of information per measurement.  Since there are $2^n$ equally spaced possibilities  and the standard deviation decreases with the square root, you need to make 2^($2n$) measurements.  The extra plus one allows you to measure on both sides and also allows for the greater inefficiency of the early part of the search. 
A: I'm going to have to agree with Jim Graber's ballpark calculation. I ran a couple of special cases assuming you just leave the polarizer fixed and take the ratio of the detection events as the tangent of the polarization angle. Ignoring the ambiguity relating to the polarity of the tangent (we can't readily distinguish +20 degrees from -20 degrees e.g.) I found the least favorable case to be the 45 degree case. In that example, one million detection events would give us a Poisson expectation of 500,000 with a standard deviation of 700 in each detector. (I think that's right: variance = expectation?) Examining this graphically gives me a range of .001 radians, which is 10 binary digits of accuracy. Of course to double the accuracy you need four times the hit count. This is pretty close to Jim's formula. 
