We analyze the performance of a generalized Kitaev’s phase-estimation algorithm where N phase gates, acting on M qubits prepared in a product state, may be distributed in an arbitrary way. Unlike the standard algorithm, where the mean square error scales as 1/N, the optimal generalizations offer the Heisenberg 1/N2 error scaling and we show that they are in fact very close to the fundamental Bayesian estimation bound.