The Deutsch algorithm can be generalised to many input bits and is then called the Deutsch-Josza algorithm. Suppose there is an n-bit function for ({x}) : {0, 1}" (0, 1), where {0, 1}" means a string of n integers each taking the value either 0 or 1. Suppose we know that either foy ((x}) is the same, either 0 or 1, for all n-bitinputs, called constant, or foy ((x}) = 0 for precisely half the {x} E {0, 1}" and fDJ((x)) = 1 for the other half, called balanced. Classically one would need to sample foy ({x}) 2"- + 1 times to determine with certainty whether for ({x) ) was constant or balanced. The quantum computing Deutsch-Josza algorithm, which will be developed here, can determine this with one iteration. Define the oracle Olx)n = (-1) for ((x) [ x)n. Show that 141) = Han OHSO) = E E (-1) fDJ ({x))+x.y 2n ly)n, ye{0, 1}" xE(0, 1 )n where the sum for x or y is over a string of n integers each taking the value either 0 or 1. Examine the amplitude (0|41). Show that if foy ({x}) is constant, then this amplitude is +1 depending on whether the constant is 0 or 1 and this amplitude is 0 if fDy ({x}) is balanced