I finished the proof of "ETH false" (#3SAT in subexponential time) in my grad complexity class at CMU today (mod some easy exercises).

I think it's nice that it can be done just using classical complexity theory ingredients - it fits well in the course!

youtube.com/watch?v=3CdlC4…

I lectured on the "ETH false" (#3SAT in subexponential time) result in my grad complexity class at CMU today.

Didn't have time in 80 mins to do the full proof, but I hope I got across the main plan, and some of the basic TCS ingredients going into it.

youtu.be/_HlQGMcQWhA

#ETH: I hit the annoying max-chat-length, so good time to pause.

cs.cmu.edu/~odonnell/some…
Still badly written, but I'm happy with this progression of ideas for # 3SAT (sparse permament) in time ~2^(n/sqrt(log n)).

It's 5-page overview, 10 pages of stuff, 5 page bonus appendix.

A couple of my course lectures about ETH and SETH and related things:

youtube.com/watch?v=dVQrj5…

youtube.com/watch?v=NMOMDz…
(From last week!)

I will be the first to admit, I was repeatedly on the record as believing SETH :-)

William Hoza on the BPL=L result:

youtube.com/watch?v=2hVv47…

Cf. my Laci Lovász anecdote: youtube.com/watch?v=t-lkFa…

I gave a talk at Carnegie Mellon about the recent proof (by OpenAI) of the existence of a non-sofic group:

youtu.be/uOQvzLjJK6c

To be fair, many people (e.g. Sivakanth Gopi) gave a simple n=5 counterexample to the similar 'Majority Is Least Stable' problem 10+ years ago...

Here's screencaps of excerpts of the other one...

Note that the answer is correct, but it has never given me a non-nonsensical proof. The proof always looks good until the key moment... A correct proof is the second paragraph of Theorem 4.1 here: cs.cmu.edu/~odonnell/pape…

In case you're in Cambridge, MA on Tue. Dec. 10, I'll give a talk at 4pm (MIT 32-G449) about coboundary expansion in high-dimensional expanders.

It's kind of about group theory, though.

toc.csail.mit.edu/node/1671

Besides coauthor @singerng_, here's the cast of characters:

I don't know how to sell this any better than to say this is an extremely enjoyable video about Math + Halloween: youtube.com/watch?v=JlXUiq…

So good!

In case you're in the Boston area, I'll talk about "Quartic quantum speedups for planted inference" tomorrow (Sep. 13) at Harvard at 4pm.

This is at the Freedman CSMA Seminar. cmsa.fas.harvard.edu/event/freedman…

Probably the largest set of different home countries I've gotten the chance to lecture to. :)

Thanks to Jan Hązła and the rest of @AIMS_Next for inviting me to participate!

(1/3) Quantum course tidbit #6: youtube.com/playlist?list=…

Why is |EPR> = |00> + |11> special? Because when you draw it as a square, it's the 2x2 identity matrix.

(4/6) Now suppose Bob does "Add & Dif on C". (Nerds call this "Hadamard C" and get 1/sqrt(2)'s involved, yuck.)

C is the front-back direction, so on each of the four front-back edges, we place the sum of the amplitudes on the |0> (front) side and the diff of the amplitudes on the |1>

(3/6) Now say Bob does "If C then toggle B". (Nerds call this "CNOT C B".) Well, C is true (1) on the back face, and B is the horizontal direction, so we swap amplitudes on the back face's horizontal edges, getting to:

(2/6) If Charlie hands Bob a new qubit C initialized to x|0> + y|1>, the resulting 3-qubit state has x amount of |EPR> on the front face and y amount on the back face:

(1/6) Quantum course tidbit #5: youtube.com/playlist?list=…

I really enjoy depicting 2- and 3-qubit states as labelings of the vertices of the square/cube by amplitudes. E.g., here is |EPR> = |00> + |11> (remember, we like unnormalized states):

Quantum course tidbit #4 youtube.com/watch?v=Wv83nz…:

I often rename Hadamard to "Add & Dif". Applying it to qubit in state (x,y) takes you to (x+y,x-y). (Remember, we're cool with unnormalized states.) I feel this has somewhat more intuition / is more memorable.

I *also* often rename it to "Avg & Dev". This takes (x,y) to the pair (avg{x,y}, "deviation of x,y from average"). (Remember, we're cool with unnormalized states.) To illustrate, if the amplitudes on |0> and |1> are 13 and 3, the new amplitudes are 8 and 5, reflecting that 13,3 = 8±5.

"Add & Dif" and "Avg & Dev" are exact inverses. That's nice because almost every quantum algorithm does Hadamard an even number of times; moreover, it's almost always natural to replace half of the Hadamards with "Add & Dif" and half with "Avg & Dev". Then you don't even end up unnormalized at the end.

Add & Difs are nice for preparing the uniform superposition (namely amplitude 1 on every basic state), starting from |00...0>.

Avg & Devs are nice for the Hadamard transform; it becomes very clear that the final amplitude on |00...0>, e.g., is the *Average* of all the original amplitudes.

Quantum course youtube.com/watch?v=XtDJXH… tidbit #3:

I introduce unnormalized states very early.

Every schoolkid knows 1/2 and 3/6 and -4/-8 are same number. As long as you multiply all the numbers you see by the same c (≠0), you get same result.

Same for amplitudes of a state.

I also like to motivate this by going on a rant about how much the expression 1/√2 annoys me...

Quantum course youtube.com/watch?v=XtDJXH… pedagogical choice #2:

First third of the course (thru Bernstein-Vazirani) does not mention vectors.

A typical state is described like ".8 amplitude on |0> and .6 amplitude on |1>".

Might sound verbose, but compare elementary probability, wherein states are usually described like ".8 probability on H and .2 probability on T".

STOC 2024 talk videos are now online:
youtube.com/playlist?list=…

If you'd like to dip in, a nice one to start with is
"Tree Evaluation is in Space O(log n log log n)"
by James Cook & Ian Mertz (presented by Ian):
youtube.com/watch?v=pWT4kr…

A student in my quantum course made four wonderful, short, 3B1B-style videos that summarize its approach to the Bernstein-Vazirani ("Mystery Toggles") algorithm. (Analyzes Hadamard transform differently, though.)

Check them out! youtu.be/8kqXnLzYYqQ?si…

What are my mistakes on these?

Wow, didn't realize "mathematics = cilantro" was a known metaphor!

youtube.com/watch?v=khyrgb…

I like to add that 'some people claim to have a gene that makes them hate it, but I'm not totally sure this gene exists, and anyway you should at least try it...'

No need for Stirling! Same as it ever was... :-)

For the Tim Gowers 60th Workshop (newton.ac.uk/event/ooew04/) I gave a talk (youtu.be/AOqwetaRAUE) about reversible circuits, cryptography, derandomization, expanders, quantum, black holes...& do check out the other 23 talks on combinatorics, probability, analysis, complexity...!

Really insightful tutorial by @RobinKothari at QIP2024 on *how* to design quantum algorithms. Hopefully the video will be available soon!

p.288 of Spivak's 𝘊𝘢𝘭𝘤𝘶𝘭𝘶𝘴:

IIRC, this ver. of the paper, besides having the great prank :) also has a minor bug. The fixed ver. (and my college homework interp.) is below.
Another great pedagogical thing about Adam's paper: it's a prob. num theory paper with real probability content, unlike eg Miller-Rabin

Remember I made that quantum computer simulator in Scratch? And I had that video demoing, among other things, the Bernstein--Vazirani algorithm?

I made a new video explaining the math behind the algorithms -- in (what I hope are) simple terms...

youtu.be/VuWklQM_3q8

The great Yassine Hamoudi just finished his grad summer school lectures on Quantum Query Complexity here at @the_IAS PCMI. Lecture vids:
youtube.com/watch?v=ivSG82…
(Hybrid, Polynomial, Compressed Oracle, & Adversary Methods all cleanly in one spot!)
Stay tuned for further updates...

Quantum computing hall-of-famer 𝐁𝐚𝐫𝐛𝐚𝐫𝐚 𝐓𝐞𝐫𝐡𝐚𝐥 is @the_IAS Karen Uhlenbeck Distinguished Scholar here at PCMI.

Check out her fantastic overview of both the math, and the contemporary engineering details, of quantum error-correcting codes:

youtube.com/watch?v=WRqMIv…

Scott Aaronson speaking at @the_IAS Park City Math Institute's research program this week, on recent work with Harry Buhrman and William Kretschmer (arxiv.org/abs/2302.10332). No video, sorry -- you had to be there in person :-)

Super excited that the great Bill Kuszmaul (sites.google.com/site/williamku…) will soon be joining the faculty of CMU @CSDatCMU!

Super excited that the great Jason Li (q3r.github.io) will be joining the faculty of CMU @CSDatCMU in the fall!

A nice talk at IAS by Microsoft physicist Matt Hastings on the Sum-of-Squares method for upper- and lower-bounding the ground state energy of Hamiltonians from the SYK model (a noncommutative analogue of the Sherrington-Kirkpatrick model):

youtube.com/watch?v=VKYmyJ…

Always watch Tom7 videos:
youtu.be/Ae9EKCyI1xU

("But what if you could make a nonlinear transfer function by combining linear functions and IEEE floating point arithmetic?")

Anupam Gupta (@anupamg) in conversation with Anıl Ada (@Anil_Ada_):

youtube.com/watch?v=RyIMhX…

Apropos of this nice article by @jordanacep:
quantamagazine.org/mathematicians…

Say you want a 3D shape that tiles space according to the integer lattice. What's the smallest possible surface area? You can do better than the cube (6).

I know how to get 5.602, can you beat that? :-)

A very cool and well-told research tale from @b_subercaseaux...

Quantum faculty/researchers:

Want to spend a week this summer at the QC workshop below, org'd by PCMI w/ David Gosset, @quantum_aram, @staceymjeffery, & Thomas Vidick?

Apply withing the next 2 weeks: ias.edu/pcmi/pcmi-2023…

∃ lodging/meal support and spouse/family options.

Yes! Another lover of PowerPoint! @mathemaniacyt

youtu.be/hRTBVrEkb6A

There are dozens of us!

I really enjoyed this Nikhil Srivastava talk on the bit complexity of computing Jordan Normal Form (joint with Dey, Kannan, Ryder, and improving on an older work of Jin-Yi Cai):

youtu.be/wVBRQ_ZUteE

Grad students: want accessible lectures on cutting-edge quantum computing research?
Apply (by Jan15) to this PCMI summer school (Jul16-Aug5) in Park City, UT:
ias.edu/pcmi/pcmi-2023…

S. Arunachalam
N. Delfosse
O. Fawzi
W. Fefferman
A. Gilyén
J. Haah
Y. Hamoudi
S. Irani
E. Tang!

This person (with a CS PhD from CMU!) ran every street in Pittsburgh over the course of 16 years:
youtube.com/watch?v=1c8i5S…

The video has it all, from sewing to Dijkstra's algorithm.

youtube.com/watch?v=qZIa9B…
I made this video about an activity for finding the Greatest Common Divisor.

(Tried it out with some paper, a marker, and an actual 9-year-old, and he was mildly entertained.)

Know an undergraduate student who'd like to learn the math of Quantum Computing, in Park City in July/Aug?
Looking for diverse range of ugrads, all levels! Only bkground needed: some linear algebra.
ias.edu/pcmi/programs/…
Or: know any ugrad groups/societies we can advertise to?

Fractran video by @Anil_Ada_ :

youtu.be/cZwFdQSgC7Y

The 2023 PCMI (@the_IAS) summer session is on Quantum Computation!

July 16-Aug 5, in Park City, UT.

ias.edu/pcmi

Apply now, to be there with all your fave quantum researchers!

I'll plug the various features (grad/ugrad schools, research, etc.) in future tweets :-)

Cool news from the Nobel Prize! If you want to learn exactly about what Aspect and Clauser did, you could check out this old video of mine:
youtube.com/watch?v=1nh-pj…
(Sorry the volume is so low, do use headphones!)

The explanation uses that 🔴≈🟠≈🟡≈🟢≉🔴...

A probabilistic primality test, below.
As easy to analyze as Miller-Rabin, but easier to state.
Error probability ≤ (1/2)⁵⁰.

Neat: this is the only natural probabilistic algorithm I know (for 𝐴𝑁𝑌 task, not just primality) having both false positives 𝐚𝐧𝐝 false negatives.

*sigh*

𝘈𝘭𝘴𝘰, 𝘧𝘪𝘨𝘶𝘳𝘦 𝘰𝘶𝘵 𝘩𝘰𝘸 𝘵𝘰 𝘮𝘢𝘬𝘦 𝙖𝙣𝙮 "𝘈𝘥𝘥 𝘧(𝘱,𝘲,𝘳,...) 𝘵𝘰..." 𝘸𝘪𝘵𝘩 '𝘳𝘦𝘤𝘺𝘤𝘭𝘪𝘯𝘨'.

What, you need another hint on how to do this?
OK, as long as we're scratching, I can't make it clearer than Young Einstein does: youtube.com/watch?v=_Ig8X2…

You really need a hint?

OK, here's a one-sentence hint: youtube.com/watch?v=_Ig8X2…

𝘛𝘰 𝘮𝘢𝘬𝘦 𝘪𝘵 𝘵𝘰 𝘓𝘦𝘷𝘦𝘭 2, 𝘢𝘯𝘴𝘸𝘦𝘳 𝘵𝘩𝘦𝘴𝘦 𝘲𝘶𝘦𝘴𝘵𝘪𝘰𝘯𝘴: 𝘏𝘰𝘸 𝘮𝘢𝘯𝘺 𝘥𝘪𝘴𝘵𝘪𝘯𝘤𝘵 𝘵𝘩𝘪𝘯𝘨𝘴 𝘤𝘢𝘯 𝘺𝘰𝘶 𝘮𝘢𝘬𝘦? 𝘊𝘢𝘯 𝘵𝘩𝘪𝘯𝘨𝘴 𝘩𝘢𝘷𝘦 𝘵𝘩𝘦 𝘴𝘢𝘮𝘦 𝘯𝘢𝘮𝘦?

You search for some more wholesome SMB1 speedrunning content, but Google 'helpfully' 'corrects' your spelling...

The resulting top hit is a bit of a mystery, though.

scratch.mit.edu/projects/72374…

You click it, but it just seems to be some unfinished Scratch program...

youtu.be/W3aLlgrINxE
A video on Quantum Monte Carlo / "Mean Estimation when you have the source code", based on the new joint paper with @RobinKothari.

Check it out if you want to remember just one theorem that subsumes Grover/Quantum Counting/Amplitude Estimation/...

Good point! My example is definitely not the trickiest possible! How about the one pictured below? It 'only' uses 1024 random bits. I'll give a prize of $100 to anyone who can tell me the mean 𝙚𝙭𝙖𝙘𝙩𝙡𝙮 ;-)
[PS/hint: the mean is not 0.0]

That's true.
Here's another concrete example... what if BlackBoxCode.py is this?

A randomized process returns a number Y.
Your budget allows for n samples.
You want to estimate mean μ of Y, so let μᴱˢᵗ be the avg of n samples.

OK, there's a 99% chance μᴱˢᵗ is within 10σ/√n of μ,
where σ is the standard deviation of Y.

Would seeing the code for Y help?

Congratulations to Pedro Paredes of @CSDatCMU
cs.cmu.edu/~preisben/
who defended his PhD thesis on Graph Expansion today!

Next stop, @PrincetonCS!

If you like graph algorithms, quantum information, group theory, gradient descent, invariant theory, computational complexity, or real analysis, you will like this talk by Avi Wigderson at the ICM!

youtube.com/watch?v=HxhwVq…

A problem in chemistry / black holes(!):
Certifying good energy bounds in the "SYK model" (i.e. certifying good bounds on random degree-4 polynomials over "anticommuting Boolean variables"). Quantum computers can do it efficiently; can classical computers?
youtu.be/gzYbp5aWzro

Finale of Learning About Quantum States:
youtu.be/67UbBxLQYzo

(Playlist here: youtube.com/playlist?list=…)

I finally talk about estimating eigenvectors. I delve a bit into representation theory of GL(d) and highest weight vectors; bit more mathematical than the preceding vids...

Part 7 of Learning About Quantum States:
youtu.be/plz_-yC9j7w
just combinatorics.

E.g. let w,x ~ [d]ⁿ be drawn randomly, w's letters from dist. p & x's from q. Assume p majorizes q. Can you couple w and x so that longest union of k increasing seqs in w is at least that in x?

Part 6 of Learning About Quantum States:
youtu.be/kKopdauoBbU

Let c be a random word in [d]ⁿ, with letters i.i.d. from distribution p.
Apply the Pokémon process to get λ = RSK(c).
[Alicki-Rudnicki-Sadowski'88] showed λ/n → p, with a CLT.
But is a CLT even good enough?

Part 5 of Learning About Quantum States:
youtu.be/kH-Qv5wq1us

The Schur--Weyl measurement on n copies of a quantum state with eigenvalues p_1, ..., p_d produces a random Young diagram λ...

Lotta complicated terminology... kinda how I feel when my kids discuss Pokémon...

Part 4 of Learning About Quantum States:
youtu.be/4HQl6Mv-3PA

But say you have 𝟑 copies of a d-dim. quantum state?

u⊗u⊗v is not fully symmetric; it's also "0% alternating", due to the repeated u.

Hmm, ℂ^d ⊗ ℂ^d ⊗ ℂ^d must have some 3𝑟𝑑 symmetry type...

☐☐
☐

Part 3 of Learning About Quantum States:
youtu.be/1oe-GFcsnb8

Given a 100-sided die. Promised:
(i) one face comes up with prob. >99%; OR
(ii) all faces come up with prob. <2%.
Can roll the die 2 times. How best to distinguish (i) from (ii)?

Now what if it's a quantum die?

Part 2 of Learning About Quantum States:
youtu.be/Wi0Um6i8e48

In this video I describe the basic elements of quantum probability...
⠀classical die → (mixed) quantum state
⠀event → subspace
⠀mut. excl. & exhaustive events → orthog. decomp.
⠀(p|A)|B = (p|B)|A → nope

New video on Learning Quantum States:
youtu.be/gelxMbpb9YY

It's the first part of a 7-part series I'm recording, based on lectures from the 2022 Harvard/MIT Current Developments in Math conference.

(Intended level is maybe 'advanced undergrad', up until the final part.)