Quantum State Space Explosion
I often find that when people claim that Quantum Computers leverage an explosion in state space to outperform classical computers more questions are raised instead of answered.
So, lets state that much of the power from quantum computers comes from a state space explosion.
And now lets ask some key questions:
- What is a state?
- What is a state space?
- Why does the state space explode for QCs?
What is a state?
Let us first look at a classical bit. A bit can be either a 0 or a 1. And, importantly it can ONLY be a 0 or a 1, it cannot be both. The value that the bit holds is called its state. For a single bit there are only 2 states and we can put it in a table like below.
| Binary | Decimal |
|---|---|
| 0 | 0 |
| 1 | 1 |
This is a bit boring so lets up it to 2 bits. There are 4 states here.
| Binary | Decimal |
|---|---|
| 00 | 0 |
| 01 | 1 |
| 10 | 2 |
| 11 | 3 |
And 3 bits is where it starts to become a bit obnoxious. And we double our number of states again.
| Binary | Decimal |
|---|---|
| 000 | 0 |
| 001 | 1 |
| 010 | 2 |
| 011 | 3 |
| 100 | 4 |
| 101 | 5 |
| 110 | 6 |
| 111 | 7 |
What is a state space?
A state space is the set of all states available to a bit string.
For each bit added to the string, we will double the number of states. The number of possible states available for an \(n\) bit string is \(2^n\). For a 5 bit string we would require a table with \(2^5 = 32\) rows. But, that’s just too much effort for this blog post.
Using classical bits, there are \(2^n\) possible states but there is only \(1\) state that exists at any time. On our table, we can represent this by adding another column labeled State. In this column, if the register exists in that state (row), then the value will be \(1\), otherwise the value will be \(0\). Let’s see an example by representing the decimal value \(2\) on a 2 bit register.
| Binary | Decimal | State |
|---|---|---|
| 00 | 0 | 0 |
| 01 | 1 | 0 |
| 10 | 2 | 1 |
| 11 | 3 | 0 |
It doesn’t matter how large this chart grows, there is only ever going to be a single \(1\) in the State column. As that is the state we are interested in, we only need to show that 1 row.
| Binary | Decimal | State |
|---|---|---|
| 10 | 2 | 1 |
Why does the state space explode for QCs?
Qubits (not qudits) have access to the same sized state space as Bits, \(2^n\). To make it clear that we are talking about about quantum states, we will encapsulate the binary and decimal representations in \(|ket\rangle\) notation. So for the classical state \(2\), \(10\) will be used. For the quantum state \(|2\rangle\), \(|10\rangle\) will be used.
| Binary | Decimal |
|---|---|
| $$|00\rangle$$ | $$|0\rangle$$ |
| $$|01\rangle$$ | $$|1\rangle$$ |
| $$|10\rangle$$ | $$|2\rangle$$ |
| $$|11\rangle$$ | $$|3\rangle$$ |
So far, this looks the same as Fig. 2 sans the \(|ket\rangle\) notation. The change comes when we add in the state column. Qubits can be in a state of superposition where the quantum state is in multiple states in the statespace at the same time. (To those advanced readers, the wording here is to build understanding of the situation, not to be true to physics.) Lets represent a quantum state where we are equally in all states in the state space at the same time.
| Binary | Decimal | State |
|---|---|---|
| $$|00\rangle$$ | $$|0\rangle$$ | .25 |
| $$|01\rangle$$ | $$|1\rangle$$ | .25 |
| $$|10\rangle$$ | $$|2\rangle$$ | .25 |
| $$|11\rangle$$ | $$|3\rangle$$ | .25 |
There we go! Whats that? Whats the \(.25\)?
That’s the probability that when we read the quantum system it will fall into that state. Quantum systems can be split across multiple states at one time, but when we read the value the quantum system collapses into a classical state.
|
READ ⇨ |
|
In this case we start out with a Quantum System in equal superposition across the states and once we measure it, we are solidly in the \(|2\rangle\) state. There was only a 25% chance we would get out the \(|2\rangle\) state.
Just like before, if we know we are only going to be in 1 state out in the whole state space, we can reduce the table to one row.
|
READ ⇨ |
|
Notice that once the Quantum System collapses, its easy to represent the Quantum State, the same as a classical state. But while the Quantum State is in superposition, \(2^n\) rows are required to represent the state. The state now has as many rows as the state space. This is Quantum State Space Explosion and its a huge problem.
*NOTE: In a Quantum System the probability shown in the state column for each state can be any value between 0 and 1 as long as the whole column adds up to exactly 1. To represent the generic probability we can use \(\alpha\) like so.
| Binary | Decimal | State |
|---|---|---|
| $$|00\rangle$$ | $$|0\rangle$$ | $$\alpha_{00}$$ |
| $$|01\rangle$$ | $$|1\rangle$$ | $$\alpha_{01}$$ |
| $$|10\rangle$$ | $$|2\rangle$$ | $$\alpha_{10}$$ |
| $$|11\rangle$$ | $$|3\rangle$$ | $$\alpha_{11}$$ |
**NOTE: The probabilities we are talking about here aren’t just simple probabilities or else quantum computers would not be able to achieve anything that probabilisic computing is able to achieve. Diving deeper into that is outside the scope of this post.
Napkin Math
Lets imagine we can represent each row of the table with a single float value. It depends on the language, but lets say that’s a single float is 64 bits. If we want to simulate 32 qubits, then there will be \(2^{32}\) rows. That’s 4,294,967,296 rows multiplied by 64 bits is 274,877,906,944 bits. Or, about 34 Gigabytes.
You would need 34 Gigabytes to represent a Quantum State of 32 qubits. And each time you add another qubit the classical requirement doubles, so at 40 qubits you need 8.8 Terabytes to store the quantum state.
This is with no optimization and the numbers can be brought down a bit through some smart manipulation of math, but its very difficult to simulate beyond a 60 qubit quantum computer on classical hardware. The table just grows too quickly. Its almost like an Exponential Explosion in the number of rows.
Ain’t nobody got time for that!
No one wants to go around creating tables for every quantum state they want to represent, so we use equations that combine elements of the State column and either the Binary or Decimal column. \(\psi\) is often the greek letter we use to represent an arbitrary Quantum State.
An arbitrary equation for a 2 qubit state might look like this: \(|\psi\rangle = \alpha_{00}|00\rangle + \alpha_{01}|01\rangle + \alpha_{10}|10\rangle + \alpha_{11}|11\rangle\) .
OR like this: \(|\psi\rangle = \alpha_{0}|0\rangle + \alpha_{1}|1\rangle + \alpha_{2}|2\rangle + \alpha_{3}|3\rangle\) .
For an \(n\) qubit state: \(|\psi\rangle = \alpha_{0}|0\rangle + ... + \alpha_{n-1}|n-1\rangle\) .