Interview
Scott Aaronson on Computational Complexity Theory and Quantum Computers
- Popular misconceptions that quantum computers test all answers simultaneously are misleading; actual speed advantages rely on choreographing interference patterns where wrong answers cancel and correct answers reinforce, whereas random measurement of superposition yields no classical speedup.
- Skeptics argue quantum computers will fail due to a new physical law or inherent error accumulation preventing scaling, though the primary application may initially be proving these limitations wrong.
- Long-term applications like drug discovery and materials simulation may require approximately one million qubits, while current devices have fewer than 50 well-controlled qubits.
- Near-term devices with 50 to 70 qubits could enable verified random number generation by sampling distributions hard to simulate classically, particularly after Google's 70-qubit systems demonstrate classical simulation hardness.
- Verification of quantum output becomes exponentially difficult for classical computers, requiring $2^n$ time for $n$ qubits, rendering full verification impossible for systems with a thousand qubits.
- Future research plans include a paper on shadow tomography and differential privacy to be written during the summer, aiming to improve verification procedures.
- The merger of physics and computer science is expected to continue, with concepts like the holographic principle interpreted as quantum error correction where bulk information is smeared on a boundary.
- Regarding AI, the speaker prioritizes addressing global risks like nuclear war or climate change over the next 20 to 50 years rather than focusing on artificial general intelligence alignment.
- The hope is that humanity survives long enough to treat super-intelligent systems as the primary challenge, implying civilization must first resolve current existential threats.
- Busy Beaver number bounds for 5 states are known to be at least 47 million, while the function becomes unknowable for a number of states estimated between 5 and 800, potentially triggered by machines as small as 10 states.
- Recent reductions in Turing machine states for testing set theory consistency have been achieved by reducing the design to under 800 states.
- Current pseudorandom standards face trust issues regarding backdoors, such as those allegedly introduced by the NSA into NIST standards, motivating the need for quantum-verified randomness.