Scott Aaronson | Quantum Computing: Dismantling the Hype from The Cartesian Cafe

The Cartesian Cafe

Timothy Nguyen

Episodes

About

Reviews

Promote

Scott Aaronson | Quantum Computing: Dismantling the Hype

3 hour 5 minutes Posted Nov 22, 2022 at 5:04 pm.

: The matrix denoted as "Hadamard gate" is actually a 45 degree rotation matrix. The Hadamard gate differs from this matrix by a sign flip in the last column. See 1:11:00 for the Hadamard gate.

: Biography

: Shtetl Optimized and the ways of blogging

: sabattical at OpenAI, AI safety, machine learning

: "I study what we can't do with computers we don't have"

: Overview

: SMBC Cartoon: "The Talk". Summary of misconceptions of the field

: How all quantum algorithms work: choreograph pattern of interference

: Outline

: Review of classical bits

: Tensor product and computational basis

: Entanglement

: What is not spooky action at a distance

: Definition of qubit

: bra and ket notation

: Superposition example

: Measurement, Copenhagen interpretation

: Unitary operators, quantum gates

: Philosophical aside: How to "store" 2^1000 bits of information.

: CNOT operation

: quantum circuits

: Hadamard gate

: circuit notation, XOR notation

: Subtlety on preparing quantum states

: Building and decomposing general quantum circuits: Universality

: Complexity of circuits vs algorithms

: How quantum algorithms are physically implemented

: Equivalence to quantum Turing Machine

: Query complexity (black box / oracle model)

: Objection: how is quantum querying not cheating?

: Defining a quantum black box

: Efficient classical f yields efficient U_f

: Toffoli gate

: Garbage and quantum uncomputing

: Implementing (-1)^f(x))

: Deutsch-Jozsa algorithm: Where quantum beats classical

: The point: constructive and destructive interference

: Recap. History of Simon's and Shor's Algorithm

: BQP

: EQP

: P

: NP

: P vs NP and NP-completeness

: P vs BQP

: NP vs BQP

: Where quantum computing explanations go off the rails

: Scalable quantum computing

: Quantum supremacy

: Boson sampling

: What Google did and the difficulties with evaluating supremacy

: Huge open question

0:00

3:05:08

Download MP3

Share at current time

Show notes

Scott Aaronson is a professor of computer science at University of Texas at Austin and director of its Quantum Information Center. Previously he received his PhD at UC Berkeley and was a faculty member at MIT in Electrical Engineering and Computer Science from 2007-2016. Scott has won numerous prizes for his research on quantum computing and complexity theory, including the Alan T Waterman award in 2012 and the ACM Prize in Computing in 2020. In addition to being a world class scientist, Scott is famous for his highly informative and entertaining blog Schtetl Optimized, which has kept the scientific community up to date on quantum hype for nearly the past two decades.

In this episode, Scott Aaronson gives a crash course on quantum computing, diving deep into the details, offering insights, and clarifying misconceptions surrounding quantum hype.

Patreon: https://www.patreon.com/timothynguyen

Correction:

Part I. Introduction (Personal)

Part II. Introduction (Technical)

Part III. Setup

Part IV. Working with qubits

Part V. Quantum Speedup

Part VI. Complexity Classes

Part VII. Quantum Supremacy

Twitter: @IAmTimNguyen

Homepage: www.timothynguyen.org

← See all 22 episodes of The Cartesian Cafe