133 min listen
Scott Aaronson | Quantum Computing: Dismantling the Hype
Scott Aaronson | Quantum Computing: Dismantling the Hype
ratings:
Length:
185 minutes
Released:
Nov 22, 2022
Format:
Podcast episode
Description
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.
Part I. Introduction (Personal)
00:00: Biography
01:02: Shtetl Optimized and the ways of blogging
09:56: sabattical at OpenAI, AI safety, machine learning
10:54: "I study what we can't do with computers we don't have"
Part II. Introduction (Technical)
22:57: Overview
24:13: SMBC Cartoon: "The Talk". Summary of misconceptions of the field
33:09: How all quantum algorithms work: choreograph pattern of interference
34:38: Outline
Part III. Setup
36:10: Review of classical bits
40:46: Tensor product and computational basis
42:07: Entanglement
44:25: What is not spooky action at a distance
46:15: Definition of qubit
48:10: bra and ket notation
50:48: Superposition example
52:41: Measurement, Copenhagen interpretation
Part IV. Working with qubits
57:02: Unitary operators, quantum gates
59:03: Hadamard gate
1:03:34: Philosophical aside: How to "store" 2^1000 bits of information.
1:08:34: CNOT operation
1:09:45: quantum circuits
1:12:43: circuit notation, XOR notation
1:14:55: Subtlety on preparing quantum states
1:16:32: Building and decomposing general quantum circuits: Universality
1:21:30: Complexity of circuits vs algorithms
1:28:45: How quantum algorithms are physically implemented
1:31:55: Equivalence to quantum Turing Machine Part V. Quantum Speedup
1:35:48: Query complexity (black box / oracle model)
1:39:03: Objection: how is quantum querying not cheating?
1:42:51: Defining a quantum black box
1:45:30: Efficient classical f yields efficient U_f
1:47:26: Toffoli gate
1:50:07: Garbage and quantum uncomputing
1:54:45: Implementing (-1)^f(x))
1:57:54: Deutsch-Jozsa algorithm: Where quantum beats classical
2:07:08: The point: constructive and destructive interference
Part VI. Complexity Classes
2:08:41: Recap. History of Simon's and Shor's Algorithm
2:14:42: BQP
2:18:18: EQP
2:20:50: P
2:22:28: NP
2:26:10: P vs NP and NP-completeness
2:33:48: P vs BQP
2:40:48: NP vs BQP
2:41:23: Where quantum computing explanations go off the rails
Part VII. Quantum Supremacy
2:43:46: Scalabe quantum computing
2:47:43: Quantum supremacy
2:51:37: Boson sampling
2:52:03: What Google did and the difficulties with evaluating supremacy
3:04:22: Huge open question
Further Reading:
Scott Aaronson's Lecture Notes: https://www.scottaaronson.com/qclec.pdf
Scott Aaronson's Blog: https://scottaaronson.blog
Nielsen & Chuang. Quantum Computation and Quantum Information
Twitter: @iamtimnguyen
Webpage: http://www.timothynguyen.org
Apple Podcasts: https://podcasts.apple.com/us/podcast/the-cartesian-cafe/id1637353704
Spotify: https://open.spotify.com/show/1X5asAByNhNr996ZsGGICG
If you would like to support this series and future such projects:
Paypal: tim@timothynguyen.org
Bitcoin: 33thftjoPTHFajj8wJFcCB9sFiyQLFVp8S
Ethereum: 0x166a977F411d6f220cF8A56065D16B4FF08a246D
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.
Part I. Introduction (Personal)
00:00: Biography
01:02: Shtetl Optimized and the ways of blogging
09:56: sabattical at OpenAI, AI safety, machine learning
10:54: "I study what we can't do with computers we don't have"
Part II. Introduction (Technical)
22:57: Overview
24:13: SMBC Cartoon: "The Talk". Summary of misconceptions of the field
33:09: How all quantum algorithms work: choreograph pattern of interference
34:38: Outline
Part III. Setup
36:10: Review of classical bits
40:46: Tensor product and computational basis
42:07: Entanglement
44:25: What is not spooky action at a distance
46:15: Definition of qubit
48:10: bra and ket notation
50:48: Superposition example
52:41: Measurement, Copenhagen interpretation
Part IV. Working with qubits
57:02: Unitary operators, quantum gates
59:03: Hadamard gate
1:03:34: Philosophical aside: How to "store" 2^1000 bits of information.
1:08:34: CNOT operation
1:09:45: quantum circuits
1:12:43: circuit notation, XOR notation
1:14:55: Subtlety on preparing quantum states
1:16:32: Building and decomposing general quantum circuits: Universality
1:21:30: Complexity of circuits vs algorithms
1:28:45: How quantum algorithms are physically implemented
1:31:55: Equivalence to quantum Turing Machine Part V. Quantum Speedup
1:35:48: Query complexity (black box / oracle model)
1:39:03: Objection: how is quantum querying not cheating?
1:42:51: Defining a quantum black box
1:45:30: Efficient classical f yields efficient U_f
1:47:26: Toffoli gate
1:50:07: Garbage and quantum uncomputing
1:54:45: Implementing (-1)^f(x))
1:57:54: Deutsch-Jozsa algorithm: Where quantum beats classical
2:07:08: The point: constructive and destructive interference
Part VI. Complexity Classes
2:08:41: Recap. History of Simon's and Shor's Algorithm
2:14:42: BQP
2:18:18: EQP
2:20:50: P
2:22:28: NP
2:26:10: P vs NP and NP-completeness
2:33:48: P vs BQP
2:40:48: NP vs BQP
2:41:23: Where quantum computing explanations go off the rails
Part VII. Quantum Supremacy
2:43:46: Scalabe quantum computing
2:47:43: Quantum supremacy
2:51:37: Boson sampling
2:52:03: What Google did and the difficulties with evaluating supremacy
3:04:22: Huge open question
Further Reading:
Scott Aaronson's Lecture Notes: https://www.scottaaronson.com/qclec.pdf
Scott Aaronson's Blog: https://scottaaronson.blog
Nielsen & Chuang. Quantum Computation and Quantum Information
Twitter: @iamtimnguyen
Webpage: http://www.timothynguyen.org
Apple Podcasts: https://podcasts.apple.com/us/podcast/the-cartesian-cafe/id1637353704
Spotify: https://open.spotify.com/show/1X5asAByNhNr996ZsGGICG
If you would like to support this series and future such projects:
Paypal: tim@timothynguyen.org
Bitcoin: 33thftjoPTHFajj8wJFcCB9sFiyQLFVp8S
Ethereum: 0x166a977F411d6f220cF8A56065D16B4FF08a246D
Released:
Nov 22, 2022
Format:
Podcast episode
Titles in the series (18)
John Urschel | Tackling Graph Theory: John Urschel received his bachelors and masters in mathematics from Penn State and then went on to become a professional football player for the Baltimore Ravens in 2014. During his second season, Urschel began his graduate studies in mathematics at MIT ... by The Cartesian Cafe