In Nielsen and Chuang, when talking about the Deutsch–Jozsa algorithm. The Deutsch’s problem is described as the following game.

Alice, in Amsterdam, selects a number x from 0 to $2^n − 1$, and mails it in a letter to Bob, in Boston...

Is there an underlying reason why we use numbers from 0 to $2^n − 1$ or it's just a random choice?


1 Answer 1


Numbers from $0$ to $2^n-1$ are exactly what one can encode into $n$ bits or $n$ qubits using standard binary positional number system. The mapping looks like this

$$ \begin{align} &0\dots000 \mapsto 0 \\ &0\dots001 \mapsto 1 \\ &0\dots010 \mapsto 2 \\ &0\dots011 \mapsto 3 \\ &0\dots100 \mapsto 4 \\ &0\dots101 \mapsto 5 \\ &\ \ \dots \\ &1\dots111 \mapsto 2^n-1. \end{align} $$

In other words, it follows the same pattern as the well-known decimal notation only using two symbols instead of ten. Note that $n$ decimal positions correspond to numbers from $0$ to $10^n-1$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.