Prof with script on Quantum + Computational Complexity seeks producer/animator + maybe editor

[odonnell-cmu]

About the author

I am a professor of Computer Science at Carnegie Mellon University, working on computational complexity and quantum computation. I also have a YouTube channel with ~250 videos (mostly filmed lectures): https://youtube.com/ryanodonnellteaching

Quick Summary

I have written a script (and a tiny bit of storyboarding) for an explainer about: "Why quantum computers cannot be simulated by classical computers unless P = NP*." (Asterisk for the super-experts: Actually, unless a slightly higher collapse in the Polynomial Hierarchy happens. It's that the Deutsch--Josza expert implies co-C_=P = NP.) The idea is to explain one of the simplest quantum algorithms (simpler than Shor or Grover), which also arguably gives our best evidence that quantum computers have exponential advantage over classical ones.

I think that there are many explainers about Shor and Grover, but not about Deutsch--Josza, which is a bit of an opportunity because Deutsch--Josza is simpler than Shor/Grover. The downside is that the task the quantum computer solves exponentially faster than a classical one is... a completely useless one. So the motivation is merely to show "quantum advantage".

I think the audience can be undergrads or even strong high schoolers. The concepts it would help the viewer to be familiar with are: elementary computation ('every function can be computed with AND, OR, NOT gates') and very elementary probability.

Target medium

My favorite math YouTubers are Mathologer and 3B1B and I aspire to their style. For this particular video I have in mind more the 3B1B style of voiceover and animation.

A downside is that my current script looks to be ~1 hour long, which rivals even Mathologer's longest in length. I wouldn't mind making such a long video, in principle, but I would also be interested in getting some thoughtful editing assistance.

More details

(If this is a topic you've written about elsewhere, e.g. in a paper or blog post, please leave a link.)

I don't want to literally post the whole script here, but I'll post the first page at the end. I also made a sample 30 seconds of video content -- https://youtu.be/upPOngvgaYc -- but I think it would literally take me at least 30 hours to finish it well. (A typical 20 minute video on my channel probably takes 10 hours....)

Contact details

Twitter DM: @BooleanAnalysis

Additional context

Script first page, with bad formatting:

Quantum computers! They take advantage of the laws of quantum mechanics to do some kinds of computations that seem to be practically impossible on regular old “classical” computers. But are classical computers really at a disadvantage? Or Could we come up with a clever way to efficiently simulate quantum computers using classical computers? Well according to the best evidence from the field of computational complexity theory, the answer is NO --- FACT: Classical computers cannot* efficiently simulate quantum computers

Assuming (a 2nd-level version of) P /= NP. <EXPERT NOTE: “polynomial hierarchy collapses to the 2nd level, in fact to AM \cap coAM”> My goal for this video is to explain almost all of this statement. To begin, let me say a few words about the P and NP part. Now you may have heard of the “P vs. NP problem”; it’s the most famous unsolved problem in theoretical computer science, and one of the most famous unsolved problems in all of mathematics. The poetic way to describe what “p EQUALS np” means is that “creativity can be automated”. [--Avi] Now almost all theoretical computer scientists believe that this is false! So for the purposes of this video, you should think of this “P \neq NP” (and its “second level version”) assumption as spiritually similar to something like “nothing travels faster than the speed of light.” It’s kind of a bedrock assumption for all of theoretical computer science. So this fact I want to tell you about, “Classical computers cannot efficiently simulate quantum computers *assuming (a 2nd-level version of) P \neq NP -- you can think of it as similar to saying that “Classical computers cannot efficiently simulate quantum computers unless something as unlikely as faster-than-light travel is true.” I’ll talk a bit more about P and NP later in this video, but let’s move along now to talking about quantum computers.

[reduccionista]

What kind of animations do you think you will use the most in this video?

[vaclavrozhon]

Dear Ryan, 1) I would be happy to help you, though I am not sure how ;) On one hand, I know a bit of manim and saw Deutsch-Josza at some point. On the other hand, I am not a big manimator and this sounds like a very time-consuming project.

2) Speaking of big projects, dont you think your lecture about godel's incompleteness theorem in great tcs ideas is a nice topic? I think it is a shame that the theorem is considered to be technical/complicated when the hardest part is understanding what it is saying. Though unfortunately it is really quite hard to understand what it is saying so maybe it is too ambitious to have 30-60 minute explainer from scratch? Anyway, if you were interested in pursuing that project, I would be even more excited to join that one!

Best, Vasek