Exploit Reversible Gates to Implement Fast Quantum Sorting Algorithm

This paper proposes an algorithm of divide-compare-swap-based (DCS) sorting that reduces time complexity by utilizing quantum parallelism. A new cost optimized comparator circuit has been designed and simulated using qiskit for comparing two quantum numbers. The sorting process consists of divide, compare-swap and merge. The set of n quantum numbers are divided equally into two sub arrays followed by comparing-swapping of two middle elements. This process continues in two sub arrays till array with single element is found. The sorting circuit performs well in qiskit with time complexity n, which has a significant improvement over existing quantum sorting technique.