We propose two optimal phase-estimation schemes that can be used for quantum-enhanced long-baseline interferometry. By using distributed entanglement, it is possible to eliminate the loss of stellar photons during transmission over the baselines. The first protocol is a sequence of gates using nonlinear optical elements, optimized over all possible measurement schemes to saturate the Cramer-Rao bound. The second approach builds on an existing protocol, which encodes the time of arrival of the stellar photon into a quantum memory. Our modified version reduces both the number of ancilla qubits and the number of gate operations by a factor of two.