So, John Horgan, the End of Science guy, interviewed Scott Aaronson, a theoretical computer scientist interested in quantum computing and computational complexity theory.
In the following, some random quotes.
On Quantum Mechanics
[Q]uantum mechanics is astonishingly simple—once you take the physics out of it! In fact, QM isn’t even “physics” in the usual sense: it’s more like an operating system that the rest of physics runs on as application software.[A]ccepting quantum mechanics didn’t mean giving up on the computational worldview: it meant upgrading it, making it richer than before. There was a programming language fundamentally stronger than BASIC, or Pascal, or C—at least with regard to what it let you compute in reasonable amounts of time. And yet this quantum language had clear rules of its own; there were things that not even it let you do (and one could prove that); it still wasn’t anything-goes.
The Computational Universe
If it’s worthwhile to build the LHC or LIGO—wonderful machines that so far, have mostly triumphantly confirmed our existing theories—then it seems at least as worthwhile to build a scalable quantum computer, and thereby prove that our universe really does have this immense computational power beneath the surface.Firstly, quantum computing has supplied probably the clearest language ever invented—namely, the language of qubits, quantum circuits, and so on—for talking about quantum mechanics itself.
[...]
Secondly, one of the most important things we’ve learned about quantum gravity—which emerged from the work of Stephen Hawking and the late Jacob Bekenstein in the 1970s—is that in quantum gravity, unlike in any previous physical theory, the total number of bits (or actually qubits) that can be stored in a bounded region of space is finite rather than infinite. In fact, a black hole is the densest hard disk allowed by the laws of physics, and it stores a “mere” 1069 qubits per square meter of its event horizon! And because of the dark energy (the thing, discovered in 1998, that’s pushing the galaxies apart at an exponential rate), the number of qubits that can be stored in our entire observable universe appears to be at most about 10122.
[...]
So, that immediately suggests a picture of the universe, at the Planck scale of 10^-33 meters or 10^-43 seconds, as this huge but finite collection of qubits being acted upon by quantum logic gates—in other words, as a giant quantum computation.
The Big Picture
Ideas from quantum computing and quantum information have recently entered the study of the black hole information problem—i.e., the question of how information can come out of a black hole, as it needs to for the ultimate laws of physics to be time-reversible. Related to that, quantum computing ideas have been showing up in the study of the so-called AdS/CFT (anti de Sitter / conformal field theory) correspondence, which relates completely different-looking theories in different numbers of dimensions, and which some people consider the most important thing to have come out of string theory.[S]ome of the conceptual problems of quantum gravity turn out to involve my own field of computational complexity in a surprisingly nontrivial way. The connection was first made in 2013, in a remarkable paper by Daniel Harlow and Patrick Hayden. Harlow and Hayden were addressing the so-called “firewall paradox,” which had lit the theoretical physics world on fire (har, har) over the previous year.
In summary, I predict that ideas from quantum information and computation will be helpful—and possibly even essential—for continued progress on the conceptual puzzles of quantum gravity.
If civilization lasts long enough, then there’s absolutely no reason why there couldn’t be further discoveries about the natural world as fundamental as relativity or evolution. One possible example would be an experimentally-confirmed theory of a discrete structure underlying space and time, which the black-hole entropy gives us some reason to suspect is there.
P/NP
[T]he ocean of mathematical understanding just keeps monotonically rising, and we’ve seen it reach peaks like Fermat’s Last Theorem that had once been synonyms for hopelessness. I see absolutely no reason why the same ocean can’t someday swallow P vs. NP, provided our civilization lasts long enough. In fact, whether our civilization will last long enough is by far my biggest uncertainty.More seriously, it was realized in the 1970s that techniques borrowed from mathematical logic—the ones that Gödel and Turing wielded to such great effect in the 1930s—can’t possibly work, by themselves, to resolve P vs. NP. Then, in the 1980s, there were some spectacular successes, using techniques from combinatorics, to prove limitations on restricted types of algorithms. Some experts felt that a proof of P≠NP was right around the corner. But in the 1990s, Alexander Razborov and Steven Rudich discovered something mind-blowing: that the combinatorial techniques from the 1980s, if pushed just slightly further, would start “biting themselves in the rear end,” and would prove NP problems to be easier at the same time they were proving them to be harder! Since it’s no good to have a proof that also proves the opposite of what it set out to prove, new ideas were again needed to break the impasse.
Musings
This characteristic of quantum mechanics—the way it stakes out an
“intermediate zone,” where (for example) n qubits are stronger than n
classical bits, but weaker than 2n classical bits, and where
entanglement is stronger than classical correlation, but weaker than
classical communication—is so weird and subtle that no science-fiction
writer would have had the imagination to invent it. But to me, that’s
what makes quantum information interesting: that this isn’t a resource
that fits our pre-existing categories, that we need to approach it as a
genuinely new thing. [I]f scanning my brain state, duplicating it like computer software, etc. were somehow shown to be fundamentally impossible, then I don’t know what more science could possibly say in favor of “free will being real”!
I hate when the people in power are ones who just go with their gut, or their faith, or their tribe, or their dialectical materialism, and who don’t even feel self-conscious about the lack of error-correcting machinery in their methods for learning about the world.
Just in the fields that I know something about, NP-completeness, public-key cryptography, Shor’s algorithm, the dark energy, the Hawking-Bekenstein entropy of black holes, and holographic dualities are six examples of fundamental discoveries from the 1970s to the 1990s that seem able to hold their heads high against almost anything discovered earlier (if not quite relativity or evolution).
