Entangling capacity of global phases and implications for the Deutsch-Jozsa algorithm - art. no. 062308

We investigate the creation of entanglement by the application of phases wh ose 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 consider the maximum entanglement generation by global p hases. We analyze the creation of entanglement between any two qubits in th ree-qubit pure and mixed states. We use our result to prove that entangleme nt is necessary for the Deutsch-Jozsa algorithm to have an exponential adva ntage over its classical counterpart.