With every new hardware architecture comes an accompanying software architecture, and when the two meet, there is a cambrian explosion of invention and innovation. We are experiencing this now with GPUs + transformers.

Driven primarily by curiosity, I wondered what one of the use cases for quantum computers would be. We hear about how they break encryption algorithms, but besides that, there really isn’t anything. So what can you do on a quantum computer that you can’t on a classical computer?

Biotech

Most of my work in the past couple of years has been at the intersection of computers, engineering, and biology. When we design a drug, we are designing a smaller molecule that can fit into a larger molecule to turn off the larger molecule or activating some desired function. At the molecular level, this is how a lot of biology works- stuff is expressed/repressed based on turning it on or off.

Last year, I found this paper where the authors used new computational tools to make antivenom binders to neutralize cobra toxins. The design and filtering process was done completely in silico. They then injected these binders into mice poisoned with cobra venom, and every treated mouse survived.

We could do the same simulation with a quantum computer, but there are too few qubits in the world to simulate a binder docking into a protein. A physicist I met recently that works on applying qubits to chemical models was basically fundraising to port Boltz2 to quantum, but said we are orders of magnitude away (but does not mean it is impossible, just expensive).

All that to say, we can work through a toy example today that can someday compound into fitting a binder into a protein.

What are we actually trying to compute?

Almost everything we care about in a molecule, whether a bond holds, how a reaction proceeds, how tightly a drug sits in a binding pocket; is governed by the energy of its electrons. Formally, the electronic structure problem is an eigenvalue problem:

The quantity that matters most is the ground-state energy, E0: the smallest eigenvalue of the molecular Hamiltonian H^. Differences in E0 across geometries give us potential energy surfaces, reaction barriers, and binding affinities.

…WIP

I found this really cool X post where this lab created an algorithm to make density function theory scale linearly with input size. Out of laziness, here is Claude on it:

What DFT is. Density functional theory is the workhorse method for simulating molecules and materials at the quantum level. The exact quantum description of a molecule is a wavefunction that depends on every electron's position at once, which is hopelessly expensive. DFT's trick (Hohenberg, Kohn, and Sham, mid-1960s, hence "60-year-old") is that you don't need the full wavefunction. The electron density — just a 3D cloud of "how much electron is here" — is enough to determine the energy, forces, and structure. So instead of one monstrous many-electron problem, you solve a set of one-electron problems that each feel an averaged-out field from the density. You solve those, get a new density, rebuild the field, and repeat until it stops changing.

Currently, quantum-mechanical simulations take $O(N^3)$, where if you want to double the input size (or resolution), it costs 8x! (double, so $2^3$ = 8)

They had it scale quasi-linearly, which wasn’t quite their goal, but still a massive improvement. They have some word slop with “Using a novel Fourier neural operator variant, we learn the underlying Kohn–Sham equation map to produce physics-informed, self-consistent answers,” but they basically used some new AI methods and it brought the complexity down to $O(N log(N))$.

Why is it n³? Those one-electron problems are solved together as one big matrix problem. You describe each electron's orbital as a combination of some set of basis functions, and the number of basis functions grows in proportion to the number of atoms. Call that N. The physics gets encoded as an NxN matrix (the Hamiltonian), and the core step of each iteration is to diagonalize it- find its eigenvectors, which are the orbitals, and its eigenvalues, which are their energies. Diagonalizing an NxN matrix costs about N³ operations. It's the same reason inverting a big matrix or multiplying two of them is cubic: for each of N outputs you're combining N things, each of which involves N terms. Also, to keep all N orbitals orthogonal to each other, you're comparing every orbital against every other one -- N² pairs, each pair costing N to evaluate- cubic again.

Doubling atoms doubles N, and 2³ = 8× the cost. Ten times the atoms is 1,000× the cost, which is why a few hundred atoms is comfortable and tens of thousands is not.

How is it possible that it is not cubic? The cubic cost comes from treating every orbital as spread over the whole system, so everything interacts with everything. But physically, that's wasteful. An electron on one end of a protein doesn't care much about atoms 50 Å away; its influence dies off with distance. This is called "nearsightedness," and it means the true information content of the problem grows only linearly with size. Linear-scaling DFT methods exploit that by working with localized orbitals and throwing away the far-apart interactions. The catch is that doing this well is hard: in metals the nearsightedness is weak, the approximations can wreck accuracy, and the bookkeeping introduces its own overhead. That's the six-decade struggle.

The AI angle in the tweet is that a learned model can, in effect, absorb the local physics. It can predict what the density or the Hamiltonian looks like around each atom from its neighborhood, so the cost is roughly "number of atoms x cost per neighborhood," which is linear, plus a log factor from things like neighbor lookups and long-range electrostatics. The hard part the tweet is emphasizing is that such a model has to extrapolate: it's trained on small systems, because generating quantum-mechanical training data is itself expensive, and it has to remain correct on systems far larger than anything it saw.