Halving the Number of Qubits of Quantum Comparators
摘要
Quantum comparators are of significant importance within the realm of various quantum algorithms. In this work we improve the number of qubits needed to perform a comparison of two N-bit strings from \(2N+1\) qubits to \(N+2\) . To achieve this, we resort to an encoding of the bits in which one qubit is not wasted for each bit entered. This encoding is based on the one proposed in the work of Pérez-Salinas et al. (2020), but in our case, we adapt it for use in arithmetic operations. We also use the implementation of the AND operation proposed by Gidney (2018) to reduce the number of T gates (significantly more expensive than the rest of the gates) necessary for comparison. The result is a circuit that equals the T-count of the best comparator for quantum computing currently available while halving the number of qubits required.