Sunday, 8 September 2013

The Binary and Decimal Representations of Qubits

The labels used to represent basis states are essentially arbitrary, but different ways of representing states will be useful in different contexts. The most common labellings of basis states for a register of qubits are the binary and decimal representations. To understand how these two are related recall that there are $N=2^n$ distinct bitstrings $\omega\in\{0,1\}^n$ of the form $\omega=b_1b_2...b_n$, where $b_i\in\{0,1\}$. Each bitstring $\omega=b_1b_2...b_n$ can be made to correspond to an integer $k\in\{0,1,2,...,N-1\}$ via the map
$\displaystyle\sum\limits_{i=1}^{n}b_i2^{n-i}=b_12^{n-1}+b_{2}2^{n-2}+...+b_{n-1}2+b_n=k.$
In this way the $N$ distinct bit strings in $\{0,1\}^n$ can be indexed by the numbers $0,1,2,...,N-1$, and then used to label the $N$ basis states of the Hilbert space $\mathcal{H}=\bigotimes_{i=1}^n\mathcal{H}^2$ corresponding to a register of $n$ qubits. Thus, an arbitrary normalized state $\left|\psi\right>\in\mathcal{H}=\bigotimes_{i=1}^n\mathcal{H}^2$ can be expressed as
$\left|\psi\right>=\displaystyle\sum\limits_{k=0}^{N-1}\alpha_k\left|k\right>,$
or equivalently as
$\left|\psi\right>=\displaystyle\sum\limits_{b_1=0}^1\displaystyle\sum\limits_{b_2=0}^1...\displaystyle\sum\limits_{b_n=0}^1\alpha_{b_1b_2...b_n}\left|b_1b_2...b_n\right>,$
where $\alpha_{b_1b_2...b_n}=\alpha_k$ if $b_12^{n-1}+b_{2}2^{n-2}+...+b_{n-1}2+b_n=k$. The former labeling of basis states will be called the decimal representation and the latter the binary representation, and both can be considered as the standard computational basis. These two basis representations will be used throughout the presentation of quantum algorithms and it is helpful to be able to use the two interchangeably.