Can you in general make the maximally entangled state in polynomial time?

Question

In a Hilbert space $\mathcal{H}$ with basis $|i\rangle _{i=1,..,n}$ I am interested in producing the maximally entangled state $\frac{1}{\sqrt{n}}\sum_{i=1}^{n}|i\rangle$ in polynomial time.
Obviously this is easy for $n=2^k$ as you can just apply a Hadamard gate to each qubit, I am wondering which other $n$ it is known to be possible for (or if there is an algorithm for all $n$).

Answer 1

I have found the answer to this after looking around. Leaving it up for others who might find it useful: Let $2^{m-1}<n\leq2^m$ and consider $\mathcal{H}\leq\mathcal{H}_{2^m}$. We can effficiently form the state $|\phi\rangle=\frac{1}{\sqrt{2^m}}\sum_i|i\rangle $ by applying successive Hadamard gates on each qubit. Now consider the unitary $U_f$ for the function

$$f(x) = \begin{cases} 0, & x\leq n \\ 1, & x> n \end{cases}$$ This can be simulated efficiently as it can be simulated classically efficiently. Thus apply $U_f$ to a second register qubit, and measure. Since $n>2^{m-1}$ , this measurement will produce $0$ with probability $>1/2$. Thus repeat until you measure a $0$. Then you have the desired state.