Question: I'm curious about how to form arbitrary-sized uniform superpositions, i.e., 
$$\frac{1}{\sqrt{N}}\sum\_{x=0}^{N-1}\vert x\rangle$$
for $N$ that is not a power of 2. 

If this is possible, then one can use the inverse of such a circuit to produce $\sqrt{p}\vert 0\rangle+\sqrt{1-p}\vert 1\rangle$ (up to some precision). Kitaev [offers a method for the reverse](https://arxiv.org/abs/quant-ph/9511026) procedure, but as far as I can tell there is no known method to do one without the other. 

Clearly such a circuit is *possible*, and there are lots of general results on how to asymptotically make any unitary I want, but it seems like a massive headache to distill those results into this one simple, specific problem.

Is there a known, efficient, Clifford+T circuit that can either produce arbitrary uniform superpositions or states like $\sqrt{p}\vert 0\rangle+\sqrt{1-p}\vert 1\rangle$?

Answer: 
As long as you want to set arbitrary states for a single qubit, like in your example, the solution is straightforward and it makes use of standard 2x2 $R\_y$ gate. In there if you set 

$\theta = 2\arctan(\sqrt{1-p}/\sqrt{p})$

and apply $R\_y(\theta)$ in the form 
$$
\begin{pmatrix}
\cos(\theta/2) & -\sin(\theta/2)\\
\sin(\theta/2) & \cos(\theta/2)
\end{pmatrix}
$$

to an input qubit in superimposed state (i.e. passed through a H gate), you get what you're looking for. 

Of course things get more complicated in case you want to set an arbitrary state over a qubit register of size > 1. In that case there are algorithms like Ventura's one (Initializing the Amplitude Distribution of a Quantum State) which can do it with polynomial complexity.
I did not thought much about that issue, so my answer may not be the best one, but it has the advantage of being quite simple to understand, it is exact even if you restrict yourself to Clifford+T, and can be generalized to more complicated relations. On the other side, this is not a unitary process because you need to repeat it a polynomial number of times until you get your expected states (see other answers if you want to have a unitary process).

Let $k = \lceil\log N\rceil$ be the smallest number of bits used to represent $N$. Then, you create the state
$$\sum\_{x =0}^{2^k-1} |x\rangle$$
by applying $k$ Hadamard gates on $k$ states initialized to $|0\rangle$. Then, if we define $f(x) = 1$ iff $x < N$, and $f(x)=0$ otherwise (here you can put any relation you like depending on the states you are interested in, you just want to have a constant fraction of $x$ such that $f(x)=1$ to ensure the algorithm is efficient, which is the case here because at least half of the $x$ have this property by definition of $k$). Then, you add one auxiliary qubit, and you apply the unitary associated to $f$ (which is $U\_f |x\rangle|b\rangle =|x\rangle|b \oplus f(x)\rangle$ and can be done with Clifford+T operations) in order to obtain the state:
$$\sum\_{x=0}^{2^k-1}|x\rangle |f(x)\rangle$$
Then, you measure this second register. If you obtain a $1$, the state you obtain is:
$$\sum\_{x \in \{x \mid f(x)=1\}} |x\rangle = \sum\_{x = 0}^{N-1} |x\rangle$$
(so you have the expected state) Otherwise, you start again from scratch (the probability to obtain the expected state depends on the fraction of $x$ such that $f(x) = 1$. In our case, this is lower bounded by $1/2$ by definition of $k$ so you need to repeat it only a few times before you succeed)