An Improved Quantum Scheduling Algorithm

The scheduling problem consists of finding a common 1 in two remotely located N bit strings. Denote the number of 1s in the string with the fewer 1s by espilonN. Classically, it needs at least O(epsilonN logsub2 N) bits of communication to find the common 1. The best known quantum algorithm would require O(sq.rootN logsub2 N) qubits of communication. This paper gives a quantum algorithm to find the common 1 with only O(sq.root epislonN logsub2 N) qubits of communication.