The Most Effective Way To Compare Numbers Encoded In A Quantum System

The answer is in the Fourier basis

The comparison of numbers is a fundamental building block for many quantum algorithms. From arithmetic routines in quantum chemistry to quantum classifiers for machine learning. Ensuring that we can efficiently decide whether one quantum-encoded integer exceeds another is not just an academic exercise. It is paramount.

Today, we learn how to compare two numbers by interleaving two QFT/IQFT pairs with nothing but phase rotations. This approach uses two n-qubit registers with only one additional flag qubit. No further auxiliary qubits required.