We develop a theory of quantum M-ary phase shift keying in which quantum states of optical modes are modulated at the transmitter by applying one of M uniformly-spaced phase shifts. We allow full freedom in choosing modulation states with any number of signal, i.e., transmitted, and ancilla modes, subject only to an average energy, i.e., photon number, constraint in either the signal modes alone or in the signal and ancilla modes together. For lossless operation and unrestricted POVM measurements at the receiver, we find the explicit form of the modulation state that minimizes the average error probability under an energy constraint of N photons. Multiple signal modes, mixed states, and entanglement with an ancilla are shown to be unnecessary for optimum performance. We show that communication with zero error is possible if and only if N ≥ (M − 1)/2.