AN IMPROVED QUANTUM SCHEDULING ALGORITHM
Lov K. Grover · International Journal of Foundations of Computer Science · 2003
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 ∊N. Classically, it needs Ω(∊N log 2 N) bits of communication to find the common 1. The best known quantum algorithms require about [Formula: see text] qubits of communication. This paper gives a quantum algorithm to find the common 1 with only [Formula: see text] qubits of communication.