Quantum mechanics allows measurements that surpass the fundamental sensitivity limits of classical methods. To benefit from the quantum advantage in a practical setting, the receiver should use communication channel resources optimally; this can be done employing large communication alphabets. Here we show the fundamental sensitivity potential of a quantum receiver for coherent communication with frequency shift keying. We introduce an adaptive quantum protocol for this receiver and show that its sensitivity outperforms other receivers for alphabet sizes above 4 and scales favorably, whereas quantum receivers explored to date suffer from degraded sensitivity with the alphabet size. In addition, we show that the quantum measurement advantage allows much better use of the frequency space in comparison to classical frequency keying protocols and orthogonal frequency division multiplexing.