Thanks to everyone who asked whether I’m OK! Yeah, I’ve been living, loving, learning, teaching, worrying, procrastinating, just not blogging.<\/p>\n\n\n\n
Last week, Takashi Yamakawa and Mark Zhandry posted a preprint to the arXiv, “Verifiable Quantum Advantage without Structure,”<\/a> that represents some of the most exciting progress in quantum complexity theory in years. I wish I’d thought of it. tl;dr they show that relative to a random oracle (!), there’s an NP search problem that quantum computers can solve exponentially faster than classical ones. And yet this is 100% consistent with the Aaronson-Ambainis Conjecture!<\/p>\n\n\n\n A student brought my attention to Quantle<\/a>, a variant of Wordle where you need to guess a true equation involving 1-qubit quantum states and unitary transformations. It’s really well-done! Possibly the best quantum game I’ve seen.<\/p>\n\n\n\n Last month, Microsoft announced on the web<\/a> that it had achieved an experimental breakthrough in topological quantum computing: not quite<\/em> the creation of a topological qubit, but some of the underlying physics required for that. This followed their needing to retract<\/a> their previous claim of such a breakthrough, due to the criticisms of Sergey Frolov and others. One imagines that they would’ve taken far greater care this time around. Unfortunately, a research paper doesn’t seem to be available yet. Anyone with further details is welcome to chime in.<\/p>\n\n\n\n Woohoo! Maximum flow, maximum bipartite matching, matrix scaling, and isotonic regression on posets (among many others)—all algorithmic problems that I was familiar with way back in the 1990s—are now solvable in nearly-linear time, thanks to a breakthrough by Chen et al.<\/a>! Many undergraduate algorithms courses will need to be updated.<\/p>\n\n\n\n
\n\n\n\n
\n\n\n\n
\n\n\n\n
\n\n\n\n