Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
I have recently watched this introductory video on quantum computing where the speaker talks about $n$ Q-bits and the representation of $2^n$ states.
What I didn't get is the word state.How is it different from a classical computer working with $1$'s and $0$s in which each bit can represent 2 states ($0$ or $1$) so that the $n$ bits can generate $2^n$ states.
I think something worth pointing out early on is the ambiguity of the word state. In quantum information most things have very strong (shall I say natural?) physical interpretations / origins. In classical information we represent information as bits. A bit might correspond to the state of some classical system, such as an electric sign in a circuit, etc. Evolution of classical bit vectors is arbitrary in the sense that its enforced by us humans.
In quantum computing information is represented using states of a quantum system (for example polarization of a photon). The states of a quantum system can be identified with vectors of a Hilbert space. Qubits $|0\rangle, |1\rangle$ are just an arbitrary choice bases of a two dimensional space. A two-qubit state represents a quantum system which is a composite of two two-dimensional subsystems. Evolution of quantum state vectors are governed by the laws of physics.
For a classical two-bit vector, the permissible values are $00,01,10,11$, whereas for a two-qubit system you can have any $a|00\rangle+b|01\rangle+c|10\rangle+d|11\rangle$ for $a,b,c,d\in\mathbb{C}$ provided that $|a|^2+|b|^2+|c|^2+|d|^2=1$. This, together with the postulates of quantum mechanics, permits a completely different range of behaviors of quantum systems (and qubit vectors), behaviors that are unseen in classical systems. This gives the above representation of information a lot more power compared to classical information representation. A number of physical phenomena allow various interesting information theoretic operations (such as teleportation, superdense coding, etc), which are not admissible using classical systems.
The emphasis here really is on the fact that in quantum computing you can exploit a range of physical phenomena that is not typical in classical information theory.
The point is you can have a linear combination of qubits which is not possible for classical bits. $$\alpha |0\rangle + \beta |1\rangle$$
where $\alpha$ and $\beta$ are probability amplitudes and can in general both be complex numbers. See more details here.
The state of an $n$-bit quantum system is described by $2^n$ complex numbers $c_x$ – indexed by vectors in $\{0,1\}^n$ – such that $\sum_x |c_x|^2 = 1$. (Some people consider these numbers only up to "rotation", that is, up to multiplication by a complex number of unit modulus.) Compare this to an $n$-bit classical system, whose state is a single vector in $\{0,1\}^n$, and to an $n$-bit classical system with randomness, whose state is a probability distribution over $\{0,1\}^n$, that is, it is described by $2^n$ non-negative real numbers $r_x$ summing to 1, $\sum_x r_x = 1$.
The state of a system is what you need to know in order to follow the evolution of the system, and eventually determine the output. The evolution of a quantum system is described by (local) unitary operations, which you can think of as $2^n \times 2^n$ complex unitary matrices which operate on the state by multiplying it. At the very end, the state of the system is measured, and then it collapses to the deterministic state $x$ with probability $|c_x|^2$ (you can also measure just some of the qubits during the computation, but let's ignore that). Notice how you need to know all $c_x$ in order to understand how the system evolves and what is its output. In contrast, to understand the evolution and output of a classical system, you just need to know the contents of all the bits, which is described by a vector in $\{0,1\}^n$.
