The phase sensitivity of interferometers is limited by the so-called Heisenberg limit, which states that the optimum phase sensitivity is inversely proportional to the number of interfering particles $N$, a $1∕\sqrt{N}$ improvement over the standard quantum limit. We have used simulated annealing, a global optimization strategy, to systematically search for quantum interferometer input states that approach the Heisenberg-limited uncertainty in estimates of the interferometer phase shift. We compare the performance of these states to that of other nonclassical states already known to yield Heisenberg-limited uncertainty.