# How are qubits better than classical bit?

WHAT I KNOW:

classical computers store information in bits which can either be 0 or 1, but in quantum computer the qubit can store 0 , 1 or a state that is the superposition of these two states. Now when we make a "measurement" (to determine the state of qubit), it changes the state of qubit, collapsing it from its superposition of 0 and 1 to the specific state consistent with the measurement result.

MY QUESTION:

If, from measurement of a qubit we obtain only a single bit of information (0 or 1 beacuse the qubit collapses to either of the states) then how is a qubit better than a classical bit..... since ultimately we are only able to get either 0 or 1 from either classical or quantum bit.

[I hope that i have made the question clear enough to convey what i think].

To those who answer this please try to explain with an example if you can.

-

You are right that there's not much you can do with a single qubit. However it doesn't take many before you can do things that can't be done with classical bits. Here are a few illustrative examples.

## Communication

Imagine I make this offer to you and a friend of yours: I will give you each a classical bit, and then you will each give me a classical bit. If the XOR of the bits you give me is equal to the AND of the bits I gave you, you win.

You're allowed to come up with any strategy you want with your friend, but once I give you the bits, you can no longer communicate.

Well it is easy to show that the best you and your friend can hope to achieve is a 3/4 probability of winning. You just take the average over all deterministic strategies.

On the other hand, if only you and your friend each had one qubit, the combined state of which was $$\frac{\left| 00 \right> + \left| 11 \right>}{\sqrt{2}},$$ then you could win with probability $\approx 0.85$.

What I've just described is called the CHSH game. You can also come up with games where classically you can only win with some probability, but quantumly you can win with certainty.

## Computation

Let's say you have a problem where you know how to check if a solution is valid, but you don't know how to come up with a solution. The class of problems for which this is the case is called NP-complete.

If you know a solution takes at most $n$ bits to encode, that means there are $2^n$ possible solutions. If you have $n$ qubits, you can put them in an equal superposition of all $n$-bit strings.

Now you can't exactly "check all strings to find a solution" all in one go, but there is something you can do.

When all strings are in an equal superposition, measuring your qubits will give you a completely random string. However, if you can make a circuit which verifies if a given string is a solution, then you can "amplify" the probability that your measurement gives you a solution.

After $\mathcal{O} \left( \sqrt{2^n} \right)$ iterations of the amplitude amplification process, measuring your qubits will give you a solution.

Notice that this works for any problem as long as you can verify an answer. If we didn't have qubits, the "check all $n$-bit strings" approach would take $\mathcal{O} \left( 2^n \right)$ checks.

-
Just a little nitpicking: NP-complete is a specific class, where checking a solution has polynomial time-complexity, while finding one has exponential time-complexity (for all we know!) - and there are often approaches that are better than trying every single candidate solution, but they are still exponential. However, there are other complexity classes, where checking a solution is significantly faster than finding one - so this applies to all of these. –  Martin Büttner May 5 '13 at 21:24
@kansi Yes, you save all measurements until the end, otherwise you collapse the state. –  Alex L May 5 '13 at 21:24
in the computation section: if you make a measurement then the "n" qubits will collapse into the state that u observed. So the next time u make a measurement u know wat to expect, because the measurement u just made collapsed the qubits into one of the states and this is wat u would observe the next time. So how would u get to the answer if u didnt get the right string, the first time? –  kansi May 5 '13 at 21:32
@kansi The amplitude amplification process doesn't require measurements. Only at the very end do you measure to get your answer. –  Alex L May 5 '13 at 21:33
@AlexL first of all Thanx for replies :) ... u said: "On the other hand, if only you and your friend each had one qubit ..." i think u are talking about entanglement, can u elaborate on that. –  kansi May 5 '13 at 21:52