Entangling capacity of global phases and implications for Deutsch-Jozsa algorithm

We investigate the creation of entanglement by the application of phases whose value depends on the state of a collection of qubits. First we give the necessary and sufficient conditions for a given set of phases to result in the creation of entanglement in a state comprising of an arbitrary number of qubits. Then we analyze the creation of entanglement between any two qubits in three qubit pure and mixed states. We use our result to prove that entanglement is necessary for Deutsch-Jozsa algorithm to have an exponential advantage over its classical counterpart.