复杂度

经典复杂度 Classical Complexity

What is the minimum number of operations you can do such that the system becomes maximally chaotic.

Consider K coins:
maximum complexity = $K/2$
maximum entropy = $K \log 2$

Suppose we start with something simple. We start with (000000...0), How long would it take before we reach a state close to the maximum complexity/entropy?
$t_{\rm maximum \, entropy}=t_{\rm maximum \, complexity} = K$
If you start with a simple state, how long does it take to come back to the simple state? Poincare recurrence time.
$t_{\rm recurrence} = 2^{K}$

量子复杂度 Quantum Complexity

Consider a state $|\psi\rangle = \sum_{i=1}^{2^{K}} \alpha_i |i\rangle$ which is the sum over all the possible states. Then how many parameters does it take to describe a quantum state?

Classical case: K binary digits
Quantum case: $2^K$ complex numbers

Gates: Operations on one or two qubits.

You can start from a simple state, and apply gates on it, to obtain the final state you are interested in.

How long does a quantum program has to run in order to get to the state that you want to get to?
The time it takes is $t = e^K$ .

What is the maximum entropy of a quantum computer?
The maximum entropy is also $K \log 2$ .

How long does it take to get to a maximum entropy state?
$t_{\rm thermal} = K$ .

What is the time that it takes to become maximally complex?
$e^K$ .

It is very different about the time that a system becomes thermal vs a system becomes complex.

What is the time that it takes to come back to the original state?
$t_{\rm recurrence} = e^{e^K}$ .

Einstein Rosen bridge gets longer and longer and longer.

Alice cannot travel through the wormhole to meet Bob. However, if Bob also jumps into the blackhole, they can meet each other inside.

For a solar mass black hole, it only takes a milli-second to thermalize.

Consider the following state
$| {\rm Alice} \,\, {\rm Bob} \rangle = | U U \rangle+| DD\rangle$
Now we add Charley. The rule is that he measures Bob. If he sees Bob up, he becomes up, if he sees Bob down, he becomes down. Then we obtain the state
$| {\rm Alice} \,\, {\rm Bob} \,\, {\rm Charley} \rangle = | U U U \rangle+| D D D\rangle$
This is the GHZ state.

We can make black holes made from GHZ state.

It is a very strange relationship. No two of them are married to each other, but each one of them is married to some combinations of the other two.

If you wait very long time, double exponential time, $e^{e^K}$ . This Einstein Rosen bridge will come back together again, come back to the original state. Quantum fluctuations build up and shorten the Einstein-Rosen bridge. That will be very convenient for Alice and Bob. If Alice and Bob wants to meet at the center, and they don't want to get around a long way, one strategy is to just wait for the double exponential time and jump in.

Quantum Zeno effect.

复杂度

经典复杂度 Classical Complexity

量子复杂度 Quantum Complexity

相关阅读更多精彩内容

友情链接更多精彩内容