What is meant by the term "computational basis"?

Question

What is meant by the term "computational basis" in the context of quantum computing and quantum algorithms?

Answer 1

When we have just one qubit, there's nothing particularly special about the computational basis; it's just nice to have a canonical basis. In practice you could think that first you implement a gate $Z$ with $Z^2 = I$ and $Z\neq I$, and then you say that the computational basis is the eigenbasis of this gate.

However, when we talk about multi-qubit systems, the computational basis is meaningful. It comes from picking a basis for each qubit, and then taking the basis which is the tensor product of all these bases. Picking the same basis for each qubit is nice just to keep everything uniform, and calling them $0$ and $1$ is a nice notational choice. What's really important is that our basis states are product states across our qubits: the computational basis states can be prepared by initializing our qubits separately and then bringing them together. This isn't true for arbitrary states! For example, the cat state $\frac1{\sqrt2}\left(|0^n\rangle + |1^n\rangle\right)$ requires a log-depth circuit in order to prepare it from a product state.

Answer 2

Quantum computing deals (mostly) with finite-dimensional quantum systems called qubits. If you know basic quantum mechanics then you know that the Hilbert space of a qubit is $\mathbb{C}^2$, i.e., the two-dimensional complex Hilbert space over $\mathbb{C}$ (for the more technical people, the state space is $\mathbb{C}P^1$).

Therefore, to describe the vectors (or physically, the quantum state of the qubit) in this two-dimensional Hilbert space we need at least two basis elements. If you think of the state of the qubit as a column vector,

$${{\bigl [}{\begin{smallmatrix}a\\b\end{smallmatrix}}{\bigr ]}},$$ then you would need to specify what $a,b$ are to specify the state of the qubit. Note that what $a,b$ are depends on what the basis of the system is $-$ there can be two different looking column vectors (in different bases) that represent the same state $|\psi\rangle$ of the qubit. In any case, we need some basis to work with and this is where the "computational basis" comes into play.

The computational basis is simply the two basis states composed by (any of) the two distinct quantum states that the qubit can be in physically. However, just like in linear algebra, which two (linearly independent) states you choose is kinda arbitrary (I say kinda because in some physical situations there is a natural choice of the basis; see Einselection).

For example, if you have an electron in a magnetic field (pointing in the z-axis say), then the states of the spin pointing upwards and downwards in the z-axis are a typical choice for the computational basis $-$ this is clearly not the only choice, since the z-axis can point in any arbitrary direction. These two states, the $|\uparrow\rangle$ and $|\downarrow\rangle$ pointing states of the spin of the electron are the eigenstates of the $\sigma_z$ (Pauli-z) operator and are usually called the "computational basis".

Answer 3

The "computational basis" is just a basis that is "most natural" in a given context, and is conventionally denoted with $|0\rangle$ and $|1\rangle$ in the case of qubits.

To give a few examples:

1. If the qubits are encoded into the polarization of single photons, the computational basis is typically the basis formed by the horizontal and vertical polarization states of the photon.
2. If the qubits are encoded into the spins of something like ions, atoms or electrons, then the "computational basis" is typically assumed to be the basis of the eigenstates of $S_z$, that is, the spin angular momentum the vertical direction (of course, what "vertical" means also depends on the context).
3. If a qubit is encoded into the presence or absence of a photon in a given mode, then the "computational basis" is, well, the occupational state of that mode.

I could go on. One also often speaks of "computational basis" for higher-dimensional states (qudits), in which case the same applies: a basis is called "computational" when it's the most "natural" in a given context.

From a purely theoretical point of view, the "computational basis" is nothing but some basis that is usually denoted with $\{|0\rangle, |1\rangle,...\}$, to distinguish it from some other basis having some relation with it. It is fundamental to understand that from a purely theoretical point of view, all bases are equivalent to each other, and they only acquire meaning when one decides that a given basis represents a specific set of states of some physical system.

Answer 4

A quantum state is a vector in a high-dimensional vector space (the Hilbert space). There is one basis that comes natural to any quantum algorithm (or quantum computer) that is based on qubits: The states that correspond to the binary numbers are special, they are the so-called computational basis states.