# Number of States and Required Info for Bits vs Qubits

So with classical bits, if you have 2 bits, there are 4 possible outcomes that are possible. To determine these states, you only need 2 pieces of info, the state of each bit. With 3 bits, you can have 8 outcomes and you only need 3 pieces of info, again the state of each bit. For the number of outcomes, there are $2^n$ outcomes, where n is the number of bits and you need n pieces of information (just the number of bits) to determine which state the bits are in.

With qubits, if you have n qubits, then you need 2^n pieces of information just to determine the state due to the superposition possible. And are there a defined number of states (assuming that you have the required information) for a given number of qubits?

If you measured the qubits, that would collapse the superposition and then there would be 2^n states, same as classical bits? But for qubits, you need 2^n pieces of information just to describe the states completely? And this is more powerful because 2 qubits could then theoretically contain much more information than 2 classical bits can?

Thanks and go easy on the answer, I am just learning...

• A single qubit, by itself, can only hold one classical bit of information. In an entangled 2 qubit system (for example, the bell state) $${\mid 00\rangle + \mid 11\rangle}\over \sqrt 2$$ you can pass one qubit through certain universal gates and transfer 2 classical bits on a single, albeit entangled, qubit. However, a qubit entangled with the rest of the world can only carry one single classical bit. – Goodies Oct 24 '14 at 21:01

Yes, in the classical case, if you have $n$ bits, you have $2^n$ different "messages" that you can encode and the state of each bit is all you need to describe the state of the systems.

In the quantum case, if you have $n$ qubits, that is $n$ 2-level quantum systems, you also have $2^n$ different "messages" you can encode (never more), for, as you say correctly, when you measure, you obtain an $n$-bit string. If you want to play encoding/decoding, however there is more you need than in the classical case: You need to know the basis in which to measure your state.

If you want to have a complete knowledge of the state, then, as you said, you need many more parameters - essentially the amplitude (which is a complex number) for every possible measurement outcome. That's $2^n$ complex numbers (normalization aside). So what's the number of states? That's not an interesting answer - it's infinite. However, you can't do anything with them. In order to use them, you'd ALWAYS need the knowledge of the $2^n$ amplitudes. Otherwise all you can retrieve is $n$ bits. Given $n$ qubits, you can always only store and faithfully retrieve or send and faithfully receive $n$ bits of information (without noise). This is called the "Holevo-bound".

Before you go on and get confused: There is something called "superdense coding", where they tell you that you only need one qbit to send two bits of information. That's somewhat true - but it's also "cheating". The reason is that in order to do this, you need to have a preshared pair of entangled qubits - so in a sense you have to send two qubits: one bit when sending a message and another, before you even know what you are going to send later on. If you don't consider preshared entanglement, the Holevo-bound is as good as it gets.

So where is the speedup? As I already said, the accessible information is not more than in classical information, however, the superposition does seem to become handy. For example, if we want to simulate a physical system with, say $n$ qubits, we'd have to keep track of all $2^n$ amplitudes in a classical computer. The real-world quantum system, however, of course only needs the $n$ qubits.

How about algorithms? I'm not really an expert on this, but there are not yet many truly different algorithms that actually offer a speedup compared to classical algorithms. Shor's algorithm of course is a candidate - but then, we don't know whether factoring is maybe not efficiently solvable on a classical computer after all. Grover's search is a real speedup. It's "just" a square-root improvement, but at least it's something (as far as I know) that a classical algorithm definitely can't do.

In short, we don't really know how much more powerful QC will be - except for simulating quantum mechanics. As I see it, there is also no simple reason as to why QC can be more powerful (such as: "It contains much more information" - no, it doesn't, "It can do all computations at once" - no, it can't, see Scott Aaronson's blog http://www.scottaaronson.com/blog/ for more on that). Mostly, the results are based on some structure that can be exploited differently given quantum mechanics.

• Maybe I am trying to relate the quantum computing to classical incorrectly. When you say if we want to simulate a physical system with n qubits, then we would need %2^n% amplitudes 'in a classical computer' but the quantum system only needs the n qubits. Are those amplitudes inherent in the quantum states and wouldn't we still want to know those amplitudes to determine the states of superposition? – Prevost Oct 27 '14 at 13:41
• What do you mean by "determine the states of superposition"? We can choose any basis we like and this will give us different amplitudes depending on what state we prepared. These amplitudes are then "inherent in the quantum states", but we usually don't want to know them - and we can't with just one measurement. – Martin Oct 27 '14 at 13:51