Music theorists have studied many fractions of the form

that are close to 1. They’re called 5-limit commas. Especially cherished are those that have fairly small exponents—given how close they are to 1. I discussed a bunch here:

• Well temperaments (part 2).

and I explained the tiniest named one, the utterly astounding ‘atom of Kirnberger’, here:

• Well temperaments (part 3).

The atom of Kirnberger equals

Two pitches differing by this ratio sound the same to everyone except certain cleverly designed machines. But remarkably, the atom of Kirnberger shows up rather naturally in music—and it was discovered by a student of Bach! Read my article for details.

All this made me want to systematically explore such tiny intervals. Below is a table of them. Some have names but many do not—or at least I don’t know their names. I list these numbers in decimal form and also in cents, where we take the logarithm of the number in base 2 and multiply by 100. (I dislike this blend of base 2 and base 10, but it’s traditional in music theory.)

Most importantly, I list the monzo. This is the list of exponents: for example, the monzo of

is

In case you’re wondering, this term was named after the music theorist Joseph Monzo.

I also list the Tenney height. This is a measure of complexity: the Tenney height of

is

The table below purports to list only 5-limit commas that are close to 1 as possible for a given complexity. More precisely, it should list numbers of the form 2ⁱ 3^j 5^k that are > 1 and closer to 1 than any number with smaller Tenney height—except of course for 1 itself.

You’ll see there’s a big increase in Tenney height after the schisma. This is very interesting: it suggests that the schisma is the last ‘useful’ interval. It’s useful only in that it’s the ratio of two musically important commas, the syntonic comma and the Pythagorean comma, and life in music would be simpler if these were equal. All the intervals in this table up to the schisma were discovered by musicians a long time ago, and they all have standard names! But after the schisma, interest drops off dramatically.

The atom of Kirnberger has such amazing properties that it was worth naming. The rest, maybe not. But as you can see, I’ve taken the liberty of naming the smallest interval in the table the ‘quark of Baez’. This is much smaller than all that come before. It’s in bad taste to name things after oneself—indeed this is item 25 on the crackpot index—but I hope it’s allowed as a joke.

I also hope that in the future this is considered my smallest mathematical discovery.

Here is the Python code that should generate the above information. If you’re good at programming, please review it and check it! Someone gave me a gift subscription to Claude, and it (more precisely Opus 4.5) created this code. It seems to make sense, and I’ve checked a bunch of the results, but I don’t know Python.

from math import log2

log3 = log2(3)
log5 = log2(5)

commas = []

max_exp_3 = 1200
max_exp_5 = 250

for a3 in range(-max_exp_3, max_exp_3+1):
    for a5 in range(-max_exp_5, max_exp_5+1):
        if a3 == 0 and a5 == 0:
            continue

# Find a2 that minimizes |a2 + a3 * log2(3) + a5 * log2(5)|

        target = -(a3 * log3 + a5 * log5)
        a2 = round(target)
        
        log2_ratio = a2 + a3 * log3 + a5 * log5
        cents = abs(1200 * log2_ratio)
        
        if cents > 0.00001:  # non-trivial
            tenney = abs(a2) + abs(a3) * log3 + abs(a5) * log5
            commas.append((tenney, cents, a2, a3, a5))

# Find Pareto frontier

commas.sort(key=lambda x: x[0])  # sort by Tenney height

frontier = []
best_cents = float('inf')
for c in commas:
    if c[1] < best_cents:
        best_cents = c[1]
        frontier.append(c)

# Print results 

for tenney, cents, a2, a3, a5 in frontier:
    log2_ratio = a2 + a3 * log3 + a5 * log5
    decimal = 2**log2_ratio
    if decimal < 1:
        decimal = 1/decimal
        a2, a3, a5 = -a2, -a3, -a5
    print(f"{cents:.6f} cents | {decimal:.10f} | [{a2}, {a3}, {a5}] | Tenney: {tenney:.1f}")

Gene Ward Smith

In studying this subject I discovered that tiny 5-limit intervals were studied by Gene Ward Smith, a mathematician I used to see around on sci.math and the like. I never knew he worked on microtonal music! I am sad to hear that he died from COVID-19 in January 2021.

I may just be redoing a tiny part of his work: if anyone can find details, please let me know. In his memory, I’ll conclude with this article from the Xenharmonic Wiki:

Gene Ward Smith (1947–2021) was an American mathematician, music theorist, and composer.

In mathematics, he worked in the areas of Galois theory and Moonshine theory.

In music theory, he introduced wedge products as a way of classifying regular temperaments. In this system, a temperament is specified by means of a wedgie, which may technically be identified as a point on a Grassmannian. He had long drawn attention to the relationship between equal divisions of the octave and the Riemann zeta function.[1][2][3] He early on identified and emphasized free abelian groups of finite rank and their homomorphisms, and it was from that perspective that he contributed to the creation of the regular mapping paradigm.

In the 1970s, Gene experimented with musical compositions using a device with four square-wave voices, whose tuning was very stable and accurate, being controlled by a crystal oscillator. The device in turn was controlled by HP 9800 series desktop computers, initially the HP 9830A, programmed in HP Basic, later the 9845A. Using this, he explored both just intonation with a particular emphasis on groups of transformations, and pajara.

Gene had a basic understanding of the regular mapping paradigm during this period, but it was limited in practice since he was focused on the idea that the next step from meantone should keep some familiar features, and so was interested in tempering out 64/63 in place of 81/80. He knew 7-limit 12 and 22 had tempering out 64/63 and 50/49 in common, and 12 and 27 had tempering out 64/63 and 126/125 in common, and thought these would be logical places to progress to, blending novelty with familiarity. While he never got around to working with augene, he did consider it. For pajara, he found tempering certain JI scales, the 10 and 12 note highschool scales, led to interesting (omnitetrachordal) results, and that there were also closely related symmetric (MOS) scales of size 10 and 12 for pajara; he did some work with these, particularly favoring the pentachordal decatonic scale.

Gene was among the first to consider extending the Tonnetz of Hugo Riemann beyond the 5-limit and hence into higher dimensional lattices. In three dimensions, the hexagonal lattice of 5-limit harmony extends to a lattice of type A3 ~ D3. He is also the first to write music in a number of exotic intonation systems.

Historical interest

• Usenet post from 1990 by Gene Smith on homomorphisms and kernels
• Usenet post from 1995 by Gene Smith on homomorphisms and kernels

See also

• Microtonal music by Gene Ward Smith
• Hypergenesis58 (a scale described by Gene Ward Smith)

References

[1] Rusin, Dave. “Why 12 tones per octave?”

[2] OEIS. Increasingly large peaks of the Riemann zeta function on the critical line: OEIS: A117536.

[3] OEIS. Increasingly large integrals of the Z function between zeros: OEIS: A117538.

Thomas Bloom’s Erdös problem site has become a real hotbed of activity in recent months, particularly as some of the easiest of the outstanding open problems have turned out to be amenable to various AI-assisted approaches; there is now a lively community in which human contributions, AI contributions, and hybrid contributions are presented, discussed, and in some cases approved as updates to the site.

One of the lessons I draw from this is that once a well curated database of precise mathematical problems is maintained, it becomes possible for other parties to build upon it in many ways (including both AI-based and human-based approaches), to systematically make progress on some fraction of the problems.

This makes me wonder what other mathematical databases could be created to stimulate similar activity. One candidate that came to mind are “optimization constants” – constants that arise from some mathematical optimization problem of interest, for instance finding the best constant for which a certain functional inequality is satisfied.

I am therefore proposing to create a crowdsourced repository for such constants, to record the best upper and lower bounds known for any given such constant, in order to help encourage efforts (whether they be by professional mathematicians, amateur mathematicians, or research groups at a tech company) to try to improve upon the state of the art.

There are of course thousands of such constants one could consider, but just to set the discussion going, I set up a very minimal, proof of concept Github repository holding over 20 constants including:

1. , the constant in a certain autocorrelation quantity relating to Sidon sets. (This constant seems to have a surprisingly nasty optimizer; see this tweet thread of Damek Davis.)
2. , the constant in Erdös’ minimum overlap problem.

Here, I am taking inspiration from the Erdös problem web site and arbitrarily assigning a number to each constant, for ease of reference.

Even in this minimal state I think the repository is ready to start accepting more contributions, in the form of pull requests that add new constants, or improve the known bounds on existing constants. (I am particularly interested in constants that have an extensive literature of incremental improvements in the lower and upper bounds, and which look at least somewhat amenable to computational or AI-assisted approaches.) But I would be interested to hear feedback on how to improve the repository in other ways.

Update: Paata Ivanisvili and Damek Davis have kindly agreed to help run and expand this repository.

David Jaz Myers just sent me some neat comments on this paper of mine:

• Dirichlet species and the arithmetic zeta function,

and he okayed me posting them here. He’s taking the idea of categorifying the Riemann zeta function, explained in my paper, and going further, imagining what it might mean to categorify Riemann’s functional equation

$$\xi(s) = \xi(1-s)$$

where $\xi$ is the ‘completed’ Riemann zeta function, which has an extra factor taking into account the ‘real prime’:

$$\xi(s) = \pi^{-s/2}\Gamma(s/2) \prod_{p \; prime} \frac{1}{1 - p^{-s}}$$

My paper categorified the Euler product formula that writes the Riemann zeta function as a product over the usual primes:

$$\zeta(s) = \prod_{p \; prime} \frac{1}{1 - p^{-s}}$$

I had nothing to say about the real prime.

But it’s the functional equation that sets the stage for focusing on zeroes of the Riemann zeta function with $\text{Re}(s) = 1/2$… and then the Riemann Hypothesis! So it’s worth thinking about.

David wrote:

Hi John,

Hope you’re doing well!

I was just thinking about your (and James Dolan’s) definition of the zeta functors associated to a finite type scheme (from here), and I had a small thought which I figured you might find interesting.

I was thinking about the functional equation of the completed zeta functions; how might we complete the zeta functors in such a way that they satisfy a similar functional equation? I don’t know, but I do have an idea for what the transformation $s \mapsto 1 -s$ might mean in this context. I claim that it is given by the reduced suspension. Let me explain.

First, I’ll want to see the formal power $n^{-s}$ as the power

$$\left(\frac{1}{n}\right)^s,$$

which I can then categorify by finding a group $G$ with cardinality $n$ and considering $B G^S$. In the case of the Riemann zeta species, $n$ is the cardinality of a finite semisimple ring (a product of finite fields, the groupoid of which has cardinality $1$ for each $n$), and we can simply deloop the additive group of this ring. This gives us a Dirichlet functor $\zeta$

$$S \mapsto \sum_{k \; \text{ finite semisimple}} B k^S$$

which categorifies the Riemann zeta function when $S$ is a finite set.

Taking this point of view on the zeta functor, we can ask the question: what is the transformation $s \mapsto 1-s$? Here’s where we can look at the reduced suspension $\Sigma S_+$. The universal property of the reduced suspension says that maps $\Sigma S_+ \to Y$ correspond to points of the homotopy type

$$(x : Y) \times (y : Y) \times (S_+ \to x = y)$$

(or, more classically, maps from the terminal morphism $S_+ \to 1$ to $\mathsf{Path}(Y) \to Y \times Y$). Since homotopy cardinality is multiplicative for fibrations, that type has cardinality

$$y \cdot y \cdot \left(\frac{1}{y}\right)^{s + 1} = \left(\frac{1}{y}\right)^{s -1}$$

(when $S$ is a finite set of cardinality $s$).

Taking $Y = B k$ for $k$ finite semisimple of cardinality $n$, we see that $\Sigma S_+ \to B k$ has cardinality $n^{s -1} = n^{-(1 -s)}$. Therefore, I think the transformation $s \mapsto 1 - s$ in the functional equation may be categorified by $S \mapsto \Sigma S_+$. If this makes sense, it suggests that completing the zeta functors is a form of stabilization.

Cheers,
David

And then:

As for another eyebrow wiggle about the cardinality of $\Sigma S_+$ when $S$ is a finite set: we have that $\Omega \Sigma S_+ = \langle S \rangle$, the free group on $S$ generators. This is of course infinite, but it it is the group completion of the free monoid $\mathsf{List}(S)$ on $S$ generators. Since

$$\mathsf{List}(S) = 1 + S + S^2 + S^3 + \cdots,$$

it has cardinality $\frac{1}{1 - s}$.

Maybe it’s better to use the “free delooping” (aka weighted colimit of $1 \rightrightarrows 1$ by $S \rightrightarrows 1$) instead of the reduced suspension. This doesn’t change the above argument because we’re mapping into a groupoid, but now it is true that the Euler characteristic / cardinality of that category is $1 - s$.

A friend pointed out that, while I've written many posts that have to do with superconductivity, I've never really done a concept post about it.  Here's a try, as I attempt to distract myself from so many things happening these days.

The superconducting state is a truly remarkable phase of matter that is hosted in many metals (though ironically not readily in the pure elements (Au, Ag, Cu) that are the best ordinary conductors of electricity - see here for some references).  First, some definitional/phenomenological points:

• The superconducting state is a distinct thermodynamic phase.  In the language of phase transitions developed by Ginzburg and Landau back in the 1950s, the superconducting state has an order parameter that is nonzero, compared to the non-superconducting metal state.   When you cool down a metal and it becomes a superconductor, this really is analogous (in some ways) to when you cool down liquid water and it becomes ice, or (a better comparison) when you cool down very hot solid iron and it becomes a magnet below 770 °C.
• In the superconducting state, at DC, current can flow with zero electrical resistance.  Experimentally, this can be checked by setting up a superconducting current loop and monitoring the current via the magnetic field it produces.  If you find that the current will decay over somewhere between \(10^5\) and \(\infty\) years, that's pretty convincing that the resistance is darn close to zero. 
• This is not just "perfect" conduction.  If you placed a conductor in a magnetic field, turned on perfect conduction, and then tried to change the magnetic field, currents would develop currents that would preserve the amount of magnetic flux through the perfect conductor.  In contrast, a key signature of superconductivity is the Meissner-Oschenfeld Effect:  if superconductivity is turned on in the presence of a (sufficiently small) magnetic field, currents will develop spontaneously at the surface of the material to exclude all magnetic flux from the bulk of the superconductor.  (That is, the magnetic field from the currents will be oppositely directed to the external field and of just the right size and distribution to give \(\mathbf{B}=0\) in the bulk of the material.)  Observation of the bulk Meissner effect is among the strongest evidence for true superconductivity, much more robust than a measurement that seems to indicate zero voltage drop.  Indeed, as a friend of mine pointed out to me, a one-phrase description of a superconductor is "a perfect diamagnet".  
• There are two main types of superconductors, uncreatively termed "Type I" and "Type II".  In Type I superconductors, an external \(\mathbf{H} = \mathbf{B}/\mu_{0}\) fails to penetrate the bulk of the material until it reaches a critical field \(H_{c}\), at which point the superconducting state is suppressed completely.  In a Type II superconductor, above some lower critical field \(H_{c,1}\) magnetic flux begins to penetrate the material in the form of vortices, each of which has a non-superconducting ("normal") core.  Above an upper critical field \(H_{c,2}\), superconductivity is suppressed. 
• Interestingly, a lot of this can be "explained" by the London Equations, which were introduced in the 1930s despite a complete lack of a viable microscopic theory of superconductivity.
• Magnetic flux through a conventional superconducting ring (or through a vortex core) is quantized precisely in units of \(h/2e\), where \(h\) is Planck's constant and \(e\) is the electronic charge.  
• (It's worth noting that in magnetic fields and with AC currents, there are still electrical losses in superconductors, due in part to the motion of vortices.)

• In an ordinary metal at low temperatures, neglecting e-e interactions and other complications, the electrons fill up states (because of the Pauli Principle) starting from the lowest energy up to some highest value, the Fermi energy.  (See here for some mention of this.)   Empty electronic states are available at essentially no energy cost - exciting electrons from filled states to empty states are "gapless".  
• Electrical conduction takes place through the flow of these electronic quasiparticles.   (For more technical readers:  We can think of these quasiparticles like little wavepackets, and as each one propagates around the wavepacket accumulates a certain amount of phase.  The phases of different quasiparticles are arbitrary, but the change in the phase going around some trajectory is well defined.)
• In a superconductor, there is some effective attractive interaction between electrons that we have thus far neglected.  In conventional superconductors, this involves lattice vibrations (as in this wikipedia description), though other attractive interactions are possible.  At sufficiently low temperatures, the ordinary metal state is unstable, and the system will spontaneously form pairs of electrons (or holes).  Those pairs then condense into a single coherent state described by an amplitude \(|\Psi|\) and a phase, \(\phi\), shared by all the pairs.  The conventional theory of this was formulated by Bardeen, Cooper, and Schrieffer in 1957.  A couple of nice lecture note presentations of this are here (courtesy Yuval Oreg) and here (courtesy Dan Arovas), if you want the technical details.  This leads to an energy gap that characterizes how much it costs to create individual quasiparticles.  Conduction in a superconductor takes place through the flow of pairs.  (A clue to this is the appearance of the \(2e\) in the flux quantization.)
• This taking on of a global phase for the pairs of electrons is a spontaneous breaking of gauge symmetry - this is discussed pedagogically for physics students here.  Understanding this led to figuring out the Anderson-Higgs mechanism, btw. 
• The result is a state with a kind of rigidity; precisely how this leads to the phenomenology of superconductivity is not immediately obvious, to me anyway.  If someone has a link to a great description of this, please put it in the comments.  (Interestingly google gemini is not too bad at discussing this.)
• The existence of this global phase is hugely important, because it's the basis for the Josephson effect(s), which in turn has led to the basis of exquisite magnetic field sensing, all the superconducting approaches to quantum information, and the definition of the volt, etc.
• The paired charge carriers are described by a pairing symmetry of their wave functions in real space.  In conventional BCS superconductors, each pair has no orbital angular momentum ("\(s\)-wave"), and the spins are in a singlet state.  In other superconductors, pairs can have \(l = 1\) orbital angular momentum ("\(p\)-wave", with spins in the triplet configuration), \(l = 2\) orbital angular momentum ("\(d\)-wave", with spins in a singlet again), etc.  The pairing state determines whether the energy gap is directionally uniform (\(s\)-wave) or whether there are directions ("nodes") along which the gap goes to zero.  

On December 10, I gave a keynote address at the Q2B 2025 Conference in Silicon Valley. This is a transcript of my remarks. The slides I presented are here. The video is here.

The first century

We are nearing the end of the International Year of Quantum Science and Technology, so designated to commemorate the 100^th anniversary of the discovery of quantum mechanics in 1925. The story goes that 23-year-old Werner Heisenberg, seeking relief from severe hay fever, sailed to the remote North Sea Island of Helgoland, where a crucial insight led to his first, and notoriously obscure, paper describing the framework of quantum mechanics.

In the years following, that framework was clarified and extended by Heisenberg and others. Notably among them was Paul Dirac, who emphasized that we have a theory of almost everything that matters in everyday life. It’s the Schrödinger equation, which captures the quantum behavior of many electrons interacting electromagnetically with one another and with atomic nuclei. That describes everything in chemistry and materials science and all that is built on those foundations. But, as Dirac lamented, in general the equation is too complicated to solve for more than a few electrons.

Somehow, over 50 years passed before Richard Feynman proposed that if we want a machine to help us solve quantum problems, it should be a quantum machine, not a classical machine. The quest for such a machine, he observed, is “a wonderful problem because it doesn’t look so easy,” a statement that still rings true.

I was drawn into that quest about 30 years ago. It was an exciting time. Efficient quantum algorithms for the factoring and discrete log problems were discovered, followed rapidly by the first quantum error-correcting codes and the foundations of fault-tolerant quantum computing. By late 1996, it was firmly established that a noisy quantum computer could simulate an ideal quantum computer efficiently if the noise is not too strong or strongly correlated. Many of us were then convinced that powerful fault-tolerant quantum computers could eventually be built and operated.

Three decades later, as we enter the second century of quantum mechanics, how far have we come? Today’s quantum devices can perform some tasks beyond the reach of the most powerful existing conventional supercomputers. Error correction had for decades been a playground for theorists; now informative demonstrations are achievable on quantum platforms. And the world is investing heavily in advancing the technology further.

Current NISQ machines can perform quantum computations with thousands of two-qubit gates, enabling early explorations of highly entangled quantum matter, but still with limited commercial value. To unlock a wide variety of scientific and commercial applications, we need machines capable of performing billions or trillions of two-qubit gates. Quantum error correction is the way to get there.

I’ll highlight some notable developments over the past year—among many others I won’t have time to discuss. (1) We’re seeing intriguing quantum simulations of quantum dynamics in regimes that are arguably beyond the reach of classical simulations. (2) Atomic processors, both ion traps and neutral atoms in optical tweezers, are advancing impressively. (3) We’re acquiring a deeper appreciation of the advantages of nonlocal connectivity in fault-tolerant protocols. (4) And resource estimates for cryptanalytically relevant quantum algorithms have dropped sharply.

Quantum machines for science

A few years ago, I was not particularly excited about running applications on the quantum platforms that were then available; now I’m more interested. We have superconducting devices from IBM and Google with over 100 qubits and two-qubit error rates approaching 10^{-3}. The Quantinuum ion trap device has even better fidelity as well as higher connectivity. Neutral-atom processors have many qubits; they lag behind now in fidelity, but are improving.

Users face tradeoffs: The high connectivity and fidelity of ion traps is an advantage, but their clock speeds are orders of magnitude slower than for superconducting processors. That limits the number of times you can run a given circuit, and therefore the attainable statistical accuracy when estimating expectations of observables.

Verifiable quantum advantage

Much attention has been paid to sampling from the output of random quantum circuits, because this task is provably hard classically under reasonable assumptions. The trouble is that, in the high-complexity regime where a quantum computer can reach far beyond what classical computers can do, the accuracy of the quantum computation cannot be checked efficiently. Therefore, attention is now shifting toward verifiable quantum advantage — tasks where the answer can be checked. If we solved a factoring or discrete log problem, we could easily check the quantum computer’s output with a classical computation, but we’re not yet able to run these quantum algorithms in the classically hard regime. We might settle instead for quantum verification, meaning that we check the result by comparing two quantum computations and verifying the consistency of the results.

A type of classical verification of a quantum circuit was demonstrated recently by BlueQubit on a Quantinuum processor. In this scheme, a designer builds a family of so-called “peaked” quantum circuits such that, for each such circuit and for a specific input, one output string occurs with unusually high probability. An agent with a quantum computer who knows the circuit and the right input can easily identify the preferred output string by running the circuit a few times. But the quantum circuits are cleverly designed to hide the peaked output from a classical agent — one may argue heuristically that the classical agent, who has a description of the circuit and the right input, will find it hard to predict the preferred output. Thus quantum agents, but not classical agents, can convince the circuit designer that they have reliable quantum computers. This observation provides a convenient way to benchmark quantum computers that operate in the classically hard regime.

The notion of quantum verification was explored by the Google team using Willow. One can execute a quantum circuit acting on a specified input, and then measure a specified observable in the output. By repeating the procedure sufficiently many times, one obtains an accurate estimate of the expectation value of that output observable. This value can be checked by any other sufficiently capable quantum computer that runs the same circuit. If the circuit is strategically chosen, then the output value may be very sensitive to many-qubit interference phenomena, in which case one may argue heuristically that accurate estimation of that output observable is a hard task for classical computers. These experiments, too, provide a tool for validating quantum processors in the classical hard regime. The Google team even suggests that such experiments may have practical utility for inferring molecular structure from nuclear magnetic resonance data.

Correlated fermions in two dimensions

Quantum simulations of fermionic systems are especially compelling, since electronic structure underlies chemistry and materials science. These systems can be hard to simulate in more than one dimension, particularly in parameter regimes where fermions are strongly correlated, or in other words profoundly entangled. The two-dimensional Fermi-Hubbard model is a simplified caricature of two-dimensional materials that exhibit high-temperature superconductivity and hence has been much studied in recent decades. Large-scale tensor-network simulations are reasonably successful at capturing static properties of this model, but the dynamical properties are more elusive.

Dynamics in the Fermi-Hubbard model has been simulated recently on both Quantinuum (here and here) and Google processors. Only a 6 x 6 lattice of electrons was simulated, but this is already well beyond the scope of exact classical simulation. Comparing (error-mitigated) quantum circuits with over 4000 two-qubit gates to heuristic classical tensor-network and Majorana path methods, discrepancies were noted, and the Phasecraft team argues that the quantum simulation results are more trustworthy. The Harvard group also simulated models of fermionic dynamics, but were limited to relatively low circuit depths due to atom loss. It’s encouraging that today’s quantum processors have reached this interesting two-dimensional strongly correlated regime, and with improved gate fidelity and noise mitigation we can go somewhat further, but expanding system size substantially in digital quantum simulation will require moving toward fault-tolerant implementations. We should also note that there are analog Fermi-Hubbard simulators with thousands of lattice sites, but digital simulators provide greater flexibility in the initial states we can prepare, the observables we can access, and the Hamiltonians we can reach.

When it comes to many-particle quantum simulation, a nagging question is: “Will AI eat quantum’s lunch?” There is surging interest in using classical artificial intelligence to solve quantum problems, and that seems promising. How will AI impact our quest for quantum advantage in this problem space? This question is part of a broader issue: classical methods for quantum chemistry and materials have been improving rapidly, largely because of better algorithms, not just greater processing power. But for now classical AI applied to strongly correlated matter is hampered by a paucity of training data.  Data from quantum experiments and simulations will likely enhance the power of classical AI to predict properties of new molecules and materials. The practical impact of that predictive power is hard to clearly foresee.

The need for fundamental research

Today is December 10^th, the anniversary of Alfred Nobel’s death. The Nobel Prize award ceremony in Stockholm concluded about an hour ago, and the Laureates are about to sit down for a well-deserved sumptuous banquet. That’s a fitting coda to this International Year of Quantum. It’s useful to be reminded that the foundations for today’s superconducting quantum processors were established by fundamental research 40 years ago into macroscopic quantum phenomena. No doubt fundamental curiosity-driven quantum research will continue to uncover unforeseen technological opportunities in the future, just as it has in the past.

I have emphasized superconducting, ion-trap, and neutral atom processors because those are most advanced today, but it’s vital to continue to pursue alternatives that could suddenly leap forward, and to be open to new hardware modalities that are not top-of-mind at present. It is striking that programmable, gate-based quantum circuits in neutral-atom optical-tweezer arrays were first demonstrated only a few years ago, yet that platform now appears especially promising for advancing fault-tolerant quantum computing. Policy makers should take note!

The joy of nonlocal connectivity

As the fault-tolerant era dawns, we increasingly recognize the potential advantages of the nonlocal connectivity resulting from atomic movement in ion traps and tweezer arrays, compared to geometrically local two-dimensional processing in solid-state devices. Over the past few years, many contributions from both industry and academia have clarified how this connectivity can reduce the overhead of fault-tolerant protocols.

Even when using the standard surface code, the ability to implement two-qubit logical gates transversally—rather than through lattice surgery—significantly reduces the number of syndrome-measurement rounds needed for reliable decoding, thereby lowering the time overhead of fault tolerance. Moreover, the global control and flexible qubit layout in tweezer arrays increase the parallelism available to logical circuits.

Nonlocal connectivity also enables the use of quantum low-density parity-check (qLDPC) codes with higher encoding rates, reducing the number of physical qubits needed per logical qubit for a target logical error rate. These codes now have acceptably high accuracy thresholds, practical decoders, and—thanks to rapid theoretical progress this year—emerging constructions for implementing universal logical gate sets. (See for example here, here, here, here.)

A serious drawback of tweezer arrays is their comparatively slow clock speed, limited by the timescales for atom transport and qubit readout. A millisecond-scale syndrome-measurement cycle is a major disadvantage relative to microsecond-scale cycles in some solid-state platforms. Nevertheless, the reductions in logical-gate overhead afforded by atomic movement can partially compensate for this limitation, and neutral-atom arrays with thousands of physical qubits already exist.

To realize the full potential of neutral-atom processors, further improvements are needed in gate fidelity and continuous atom loading to maintain large arrays during deep circuits. Encouragingly, active efforts on both fronts are making steady progress.

Approaching cryptanalytic relevance

Another noteworthy development this year was a significant improvement in the physical qubit count required to run a cryptanalytically relevant quantum algorithm, reduced by Gidney to less than 1 million physical qubits from the 20 million Gidney and Ekerå had estimated earlier. This applies under standard assumptions: a two-qubit error rate of 10^{-3} and 2D geometrically local processing. The improvement was achieved using three main tricks. One was using approximate residue arithmetic to reduce the number of logical qubits. (This also suppresses the success probability and therefore lengthens the time to solution by a factor of a few.) Another was using a more efficient scheme to reduce the number of physical qubits for each logical qubit in cold storage. And the third was a recently formulated scheme for reducing the spacetime cost of non-Clifford gates. Further cost reductions seem possible using advanced fault-tolerant constructions, highlighting the urgency of accelerating migration from vulnerable cryptosystems to post-quantum cryptography.

Looking forward

Over the next 5 years, we anticipate dramatic progress toward scalable fault-tolerant quantum computing, and scientific insights enabled by programmable quantum devices arriving at an accelerated pace. Looking further ahead, what might the future hold? I was intrigued by a 1945 letter from John von Neumann concerning the potential applications of fast electronic computers. After delineating some possible applications, von Neumann added: “Uses which are not, or not easily, predictable now, are likely to be the most important ones … they will … constitute the most surprising extension of our present sphere of action.” Not even a genius like von Neumann could foresee the digital revolution that lay ahead. Predicting the future course of quantum technology is even more hopeless because quantum information processing entails an even larger step beyond past experience.

As we contemplate the long-term trajectory of quantum science and technology, we are hampered by our limited imaginations. But one way to loosely characterize the difference between the past and the future of quantum science is this: For the first hundred years of quantum mechanics, we achieved great success at understanding the behavior of weakly correlated many-particle systems, leading for example to transformative semiconductor and laser technologies. The grand challenge and opportunity we face in the second quantum century is acquiring comparable insight into the complex behavior of highly entangled states of many particles, behavior well beyond the scope of current theory or computation. The wonders we encounter in the second century of quantum mechanics, and their implications for human civilization, may far surpass those of the first century. So we should gratefully acknowledge the quantum pioneers of the past century, and wish good fortune to the quantum explorers of the future.

Welcome back to: Has quantum advantage been achieved?

In Part 1 of this mini-series on quantum advantage demonstrations, I told you about the idea of random circuit sampling (RCS) and the experimental implementations thereof. In this post, Part 2 out of 3, I will discuss the arguments and evidence for why I am convinced that the experiments demonstrate a quantum advantage.

Recall from Part 1 that to assess an experimental quantum advantage claim we need to check three criteria:

1. Does the experiment correctly solve a computational task?
2. Does it achieve a scalable advantage over classical computation?
3. Does it achieve an in-practice advantage over the best classical attempt at solving the task?

What’s the issue?

When assessing these criteria for the RCS experiments there is an important problem: The early quantum computers we ran them on were very far from being reliable and the computation was significantly corrupted by noise. How should we interpret this noisy data? Or more concisely:

1. Is random circuit sampling still classically hard even when we allow for whatever amount of noise the actual experiments had?
2. Can we be convinced from the experimental data that this task has actually been solved?

I want to convince you today that we have developed a very good understanding of these questions that gives a solid underpinning to the advantage claim. Developing that understanding required a mix of methodologies from different areas of science, including theoretical computer science, algorithm design, and physics and has been an exciting journey over the past years.

The noisy sampling task

Let us start by answering the base question. What computational task did the experiments actually solve?

Recall that, in the ideal RCS scenario, we are given a random circuit $C$ on $n$qubits and the task is to sample from the output distribution of the state obtained $\ket C$ from applying the circuit $C$ to a simple reference state. The output probability distribution of this state is determined by the Born rule when I measure every qubit in a fixed choice of basis.

Now what does a noisy quantum computer do when I execute all the gates on it and apply them to its state? Well, it prepares a noisy version $\rho_ C$ of the intended state $\ket C$ and once I measure the qubits, I obtain samples from the output distribution of that noisy state.

We should not make the task dependent on the specifics of that state or the noise that determined it, but we can define a computational task based on this observation by fixing how accurate that noisy state preparation is. The natural way to do this is to use the fidelity

$F(C) = \bra C \rho_C \ket C,$

which is just the overlap between the ideal state and the noisy state. The fidelity is 1 if the noisy state is equal to the ideal state, and 0 if it is perfectly orthogonal to it.

Finite-fidelity random circuit sampling
Given a typical random circuit $C$, sample from the output distribution of any quantum state whose fidelity with the ideal output state $\ket C$ is at least $\delta$.

Note that finite-fidelity RCS does not demand success for every circuit, but only for typical circuits from the random circuit ensemble. This matches what the experiments do: they draw random circuits and need the device to perform well on the overwhelming majority of those draws. Accordingly, when the experiments quote a single number as “fidelity”, it is really the typical (or, more precisely, circuit-averaged) fidelity that I will just call $F$.

The noisy experiments claim to have solved finite-fidelity RCS for values of $\delta$ around 0.1%. What is more, they consistently achieve this value even as the circuit sizes are increased in the later experiments. Both the actual value and the scaling will be important later.

What is the complexity of finite-fidelity RCS?

Quantum advantage of finite-fidelity RCS

Let’s start off by supposing that the quantum computation is (nearly) perfectly executed, so the required fidelity $\delta$ is quite large, say, 90%. In this scenario, we have very good evidence based on computational complexity theory that there is a scalable and in-practice quantum advantage for RCS. This evidence is very strong, comparable to the evidence we have for the hardness of factoring and simulating quantum systems. The intuition behind it is that quantum output probabilities are extremely hard to compute because of a mechanism behind quantum advantages: destructive interference. If you are interested in the subtleties and the open questions, take a look at our survey.

The question is now, how far down in fidelity this classical hardness persists? Intuitively, the smaller we make $\delta$, the easier finite-fidelity RCS should become for a classical algorithm (and a quantum computer, too), since the freedom we have in deviating from the ideal state in our simulation becomes larger and larger. This increases the possibility of finding a state that turns out to be easy to simulate within the fidelity constraint.

Somewhat surprisingly, though, finite-fidelity RCS seems to remain hard even for very small values of $\delta$. I am not aware of any efficient classical algorithm that achieves the finite-fidelity task for $\delta$ significantly away from the baseline trivial value of $2^{-n}$. This is the value a maximally mixed or randomly picked state achieves because a random state has no correlation with the ideal state (or any other state), and $2^{-n}$ is exactly what you expect in that case (while 0 would correspond to perfect anti-correlation).

One can save some classical runtime compared to solving near-ideal RCS by exploiting a reduced fidelity, but the costs remain exponential. To classically solve finite-fidelity RCS, the best known approaches are reported in the papers that performed classical simulations of finite-fidelity RCS with the parameters of the first Google and USTC experiment (classSim1, classSim2). To achieve this, however, they needed to approximately simulate the ideal circuits at an immense cost. To the best of my knowledge, all but those first two experiments are far out of reach for these algorithms.

Getting the scaling right: weak noise and low depth

So what is the right value of $\delta$ at which we can hope for a scalable and in-practice advantage of RCS experiments?

When thinking about this question, it is helpful to keep a model of the circuit in mind that a noisy experiment runs. So, let us consider a noisy circuit on $n$ qubits with $d$ layers of gates and single-qubit noise of strength $\varepsilon$ on every qubit in every layer. In this scenario, the typical fidelity with the ideal state will decay as $F \sim \exp(- \varepsilon n d)$.

Any reasonably testable value of the fidelity needs to scale as $1/\mathsf{poly}(n)$, since eventually we need to estimate the average fidelity $F$ from the experimental samples and this typically requires at least $1/F^2$ samples, so exponentially small fidelities are experimentally invisible. The polynomial fidelity $\delta$ is also much closer to the near-ideal scenario ($\delta \geq$90%) than the trivial scenario ($\delta = 2^{-n}$). While we cannot formally pin this down, the intuition behind the complexity-theoretic evidence for the hardness of near-ideal RCS persists into the $\delta \sim 1/\mathsf{poly}(n)$ regime: to sample up to such high precision, we still need a reasonably accurate estimate of the ideal probabilities, and getting this is computationally extremely difficult. Scalable quantum advantage in this regime is therefore a pretty safe bet.

How do the parameters of the experiment and the RCS instances need to scale with the number of qubits $n$ to experimentally achieve the fidelity regime? The limit to consider is one in which the noise rate decreases with the number of qubits, while the circuit depth is only allowed to increase very slowly. It depends on the circuit architecture, i.e., the choice of circuit connectivity, and the gate set, through a constant $c_A$ as I will explain in more detail below.

Weak-noise and low-depth scaling
(Weak noise) The local noise rate of the quantum device scales as $\varepsilon \lt c_A/n$.
(Low depth) The circuit depth scales as $d \lesssim \log n$.

This limit is such that we have a scaling of the fidelity as $F \gtrsim n^{-c}$ for some constant $c$. It is also a natural scaling limit for noisy devices whose error rates gradually improve through better engineering. You might be worried about the fact that the depth needs to be quite low but it turns out that there is a solid quantum advantage even for $\log(n)$-depth circuits.

The precise definition of the weak-noise regime is motivated by the following observation. It turns out to be crucial for assessing the noisy data from the experiment.

Fidelity versus XEB: a phase transition

Remember from Part 1 that the experiments measured a quantity called the cross-entropy benchmark (XEB)

$\chi = 2^{2n} \mathbb E_C \mathbb E_{x} p_C(x) -1 ,$

The XEB averages the ideal probabilities $p_C(x)$ corresponding to the sampled outcomes $x$ from experiments on random circuits $C$. Thus, it correlates the experimental and ideal output distributions of those random circuits. You can think of it as a “classical version” of the fidelity: If the experimental distribution is correct, the XEB will essentially be 1. If it is uniformly random, the XEB is 0.

The experiments claimed that the XEB is a good proxy for the circuit-averaged fidelity given by $F = \mathbb E_C F(C)$, and so we need to understand when this is true. Fortunately, in the past few years, alongside with the improved experiments, we have developed a very good understanding of this question (WN, Spoof2, PT1, PT2).

It turns out that the quality of correspondence between XEB and average fidelity depends strongly on the noise in the experimental quantum state. In fact, there is a sharp phase transition: there is an architecture-dependent constant $c_A$ such that when the experimental local noise rate $\varepsilon < c_A/n$, then the XEB is a good and reliable proxy for the average fidelity for any system size $n$ and circuit depth $d$. This is exactly the weak-noise regime. Above that threshold, in the strong noise regime, the XEB is an increasingly bad proxy for the fidelity (PT1, PT2).

Let me be more precise: In the weak-noise regime, when we consider the decay of the XEB as a function of circuit depth $d$, the rate of decay is given by $\varepsilon n$, i.e., the XEB decays as $\exp(- \varepsilon n d )$. Meanwhile, in the strong-noise regime the rate of decay is constant, giving an XEB decay as $\exp(- C d)$ for a constant $C$. At the same time, the fidelity decays as $\exp(- \varepsilon n d )$ regardless of the noise regime. Hence, in the weak-noise regime, the XEB is a good proxy of the fidelity, while in the strong noise regime, there is an exponentially increasing gap between the XEB (which remains large) and the fidelity (which continues to decay exponentially). regardless of the noise regime.

This is what the following plot shows. We computed it from an exact mapping of the behavior of the XEB to the dynamics of a statistical-mechanics model that can be evaluated efficiently. Using this mapping, we can also compute the noise threshold $c_A$ for whichever random circuit family and architecture you are interested in.

Where are the experiments?

We are now ready to take a look at the crux when assessing the noisy data: Can we trust the reported XEB values as an estimator of the fidelity? If so, do the experiments solve finite-fidelity RCS in the solidly hard regime where $\delta \geq 1/ \mathsf{poly}(n)$?

In their more recent paper (PT1), the Google team explicitly verified that the experiment is well below the phase transition, and it turns out that the first experiment was just at the boundary. The USTC experiments had comparable noise rates, and the Quantinuum experiment much better ones. Since fidelity decays as $\exp(-\varepsilon n d)$, but the reported XEB values stayed consistently around 0.1% as $n$ was increased, the experimental error rate $\varepsilon$ of the experiments improved even better than the $1/n$ scaling required for the weak-noise regime, namely, more like $\varepsilon \sim 1/(nd)$. Altogether, the experiments are therefore in the weak-noise regime both in terms of absolute numbers relative to $c_A/n$ and the required scaling.

Of course, to derive the transition, we made some assumptions about the noise such as that the noise is local, and that it does not depend much on the circuit itself. In the advantage experiments, these assumptions about the noise are characterized and tested. This is done through a variety of means at increasing levels of complexity, including detailed characterization of the noise in individual gates, gates run in parallel, and eventually in a larger circuit. The importance of understanding the noise shows in the fact that a significant portion of the supplementary materials of the advantage experiments is dedicated to getting this right. All of this contributes to the experimental justification for using the XEB as a proxy for the fidelity!

The data shows that the experiments solved finite-fidelity RCS for values of $\delta$ above the constant value of roughly 0.1% as the experiments grew. In the following plot, I compare the experimental fidelity values to the near-ideal scenario on the one hand, and the trivial $2^{-n}$ value on the other hand. Viewed at this scale, the values of $\delta$ for which the experiment solved finite-fidelity RCS are indeed vastly closer to the near-ideal value than the trivial baseline, which should boost our confidence that reproducing samples at a similar fidelity is extremely challenging.

The phase transition matters!

You might be tempted to say: “Well, but is all this really so important? Can’t I just use XEB and forget all about fidelity?”

The phase transition shows why that would change the complexity of the problem: in the strong-noise regime, XEB can stay high even when fidelity is exponentially small. And indeed, this discrepancy can be exploited by so-called spoofers for the XEB. These are efficient classical algorithms which can be used to succeed at a quantum advantage test even though they clearly do not achieve the intended advantage. These spoofers (Spoof1, Spoof2) can achieve high XEB scores comparable to those of the experiments and scaling like $\exp(-cd)$ in the circuit depth $d$ for some constant $c$.

Their basic idea is to introduce strong, judiciously chosen noise at specific circuit locations that has the effect of breaking up the simulation task up into smaller, much easier components, but at the same time still gives a high XEB score. In doing so, they exploit the strong-noise regime in which the XEB is a really bad proxy for the fidelity. This allows them to sample from states with exponentially low fidelity while achieving a high XEB value.

The discovery of the phase transition and the associated spoofers highlights the importance of modeling when assessing—and even formulating—the advantage claim based on noisy data.

But we can’t compute the XEB!

You might also be worried that the experiments did not actually compute the XEB in the advantage regime because to estimate it they would have needed to compute ideal probabilities—a task that is hard by definition of the advantage regime. Instead, they used a bunch of different ways to extrapolate the true XEB from XEB proxies (proxy of a proxy of the fidelity). Is this is a valid way of getting an estimate of the true XEB?

It totally is! Different extrapolations—from easy-to-simulate to hard-to-simulate, from small system to large system etc—all gave consistent answers for the experimental XEB value of the supremacy circuits. Think of this as having several lines that cross in the same point. For that crossing to be a coincidence, something crazy, conspiratorial must happen exactly when you move to the supremacy circuits from different directions. That is why it is reasonable to trust the reported value of the XEB.

That’s exactly how experiments work!

All of this is to say that establishing that the experiments correctly solved finite-fidelity RCS and therefore show quantum advantage involved a lot of experimental characterization of the noise as well as theoretical work to understand the effects of noise on the quantity we care about—the fidelity between the experimental and ideal states.

In this respect (and maybe also in the scale of the discovery), the quantum advantage experiments are similar to the recent experiments reporting discovery of the Higgs boson and gravitational waves. While I do not claim to understand any of the details, what I do understand is that in both experiments, there is an unfathomable amount of data that could not be interpreted without preselection and post-processing of the data, theories, extrapolations and approximations that model the experiment and measurement apparatus. All of those enter the respective smoking-gun plots that show the discoveries.

If you believe in the validity of experimental physics methodology, you should therefore also believe in the type of evidence underlying experimental claim of the quantum advantage demonstrations: that they sampled from the output distribution of a quantum state with the reported fidelities.

Put succinctly: If you believe in the Higgs boson and gravitational waves, you should probably also believe in the experimental demonstration of quantum advantage.

What are the counter-arguments?

The theoretical computer scientist

“The weak-noise limit is not physical. The appropriate scaling limit is one in which the local noise rate of the device is constant while the system size grows, and in that case, there is a classical simulation algorithm for RCS (SimIQP, SimRCS).”

In theoretical computer science, scaling of time or the system size in the input size is considered very natural: We say an algorithm is efficient if its runtime and space usage only depend polynomially on the input size.

But all scaling arguments are hypothetical concepts, and we only care about the scaling at relevant sizes. In the end, every scaling limit is going to hit the wall of physical reality—be it the amount of energy or human lifetime that limits the time of an algorithm, or the physical resources that are required to build larger and larger computers. To keep the scaling limit going as we increase the size of our computations, we need innovation that makes the components smaller and less noisy.

At the scales relevant to RCS, the $1/n$ scaling of the noise is benign and even natural. Why? Well, currently, the actual noise in quantum computers is not governed by the fundamental limit, but by engineering challenges. Realizing this limit therefore amounts to engineering improvements in the system size and noise rate that are achieved over time. Sure, at some point that scaling limit is also going to hit a fundamental barrier below which the noise cannot be improved. But we are surely far away from that limit, yet. What is more, already now logical qubits are starting to work and achieve beyond-breakeven fidelities. So even if the engineering improvements should flatten out from here onward, QEC will keep the $1/n$ noise limit going and even accelerate it in the intermediate future.

The complexity maniac

“All the hard complexity-theoretic evidence for quantum advantage is in the near-ideal regime, but now you are claiming advantage for the low-fidelity version of that task.”

This is probably the strongest counter-argument in my opinion, and I gave my best response above. Let me just add that this is a question about computational complexity. In the end, all of complexity theory is based on belief. The only real evidence we have for the hardness of any task is the absence of an efficient algorithm, or the reduction to a paradigmatic, well-studied task for which there is no efficient algorithm.

I am not sure how much I would bet that you cannot find an efficient algorithm for finite-fidelity RCS in the regime of the experiments, but it is certainly a pizza.

The enthusiastic skeptic

“There is no verification test that just depends on the classical samples, is efficient and does not make any assumptions about the device. In particular, you cannot unconditionally verify fidelity just from the classical samples. Why should I believe the data?”

Yes, sure, the current advantage demonstrations are not device-independent. But the comparison you should have in mind are Bell tests. The first proper Bell tests of Aspect and others in the 80s were not free of loopholes. They still allowed for contrived explanations of the data that did not violate local realism. Still, I can hardly believe that anyone would argue that Bell inequalities were not violated already back then.

As the years passed, these remaining loopholes were closed. To be a skeptic of the data, people needed to come up with more and more adversarial scenarios that could explain the data. We are working on the same to happen with quantum advantage demonstrations: come up with better schemes and better tests that require less and less assumptions or knowledge about the specifics of the device.

The “this is unfair” argument

“When you chose the gates and architecture of the circuit dependent on your device, you tailored the task too much to the device and that is unfair. Not even the different RCS experiments solve exactly the same task.”

This is not really an argument against the achievement of quantum advantage but more against the particular choices of circuit ensembles in the experiments. Sure, the specific computations solved are still somewhat tailored to the hardware itself and in this sense the experiments are not hardware-independent yet, but they still solve fine computational tasks. Moving away from such hardware-tailored task specifications is another important next step and we are working on it.

In the third and last part of this mini series I will address next steps in quantum advantage that aim at closing some of the remaining loopholes. The most important—and theoretically interesting—one is to enable efficient verification of quantum advantage using less or even no specific knowledge about the device that was used, but just the measurement outcomes.

References

(survey) Hangleiter, D. & Eisert, J. Computational advantage of quantum random sampling. Rev. Mod. Phys. 95, 035001 (2023).

(classSim1) Pan, F., Chen, K. & Zhang, P. Solving the sampling problem of the Sycamore quantum circuits. Phys. Rev. Lett. 129, 090502 (2022).

(classSim2) Kalachev, G., Panteleev, P., Zhou, P. & Yung, M.-H. Classical Sampling of Random Quantum Circuits with Bounded Fidelity. arXiv.2112.15083 (2021).

(WN) Dalzell, A. M., Hunter-Jones, N. & Brandão, F. G. S. L. Random Quantum Circuits Transform Local Noise into Global White Noise. Commun. Math. Phys. 405, 78 (2024).

(PT1)vMorvan, A. et al. Phase transitions in random circuit sampling. Nature 634, 328–333 (2024).

(PT2) Ware, B. et al. A sharp phase transition in linear cross-entropy benchmarking. arXiv:2305.04954 (2023).

(Spoof1) Barak, B., Chou, C.-N. & Gao, X. Spoofing Linear Cross-Entropy Benchmarking in Shallow Quantum Circuits. in 12th Innovations in Theoretical Computer Science Conference (ITCS 2021) (ed. Lee, J. R.) vol. 185 30:1-30:20 (2021).

(Spoof2) Gao, X. et al. Limitations of Linear Cross-Entropy as a Measure for Quantum Advantage. PRX Quantum 5, 010334 (2024).

(SimIQP) Bremner, M. J., Montanaro, A. & Shepherd, D. J. Achieving quantum supremacy with sparse and noisy commuting quantum computations. Quantum 1, 8 (2017).

(SimRCS) Aharonov, D., Gao, X., Landau, Z., Liu, Y. & Vazirani, U. A polynomial-time classical algorithm for noisy random circuit sampling. in Proceedings of the 55th Annual ACM Symposium on Theory of Computing 945–957 (2023).

Recently, I gave a couple of perspective talks on quantum advantage, one at the annual retreat of the CIQC and one at a recent KITP programme. I started off by polling the audience on who believed quantum advantage had been achieved. Just this one, simple question.

The audience was mostly experimental and theoretical physicists with a few CS theory folks sprinkled in. I was sure that these audiences would be overwhelmingly convinced of the successful demonstration of quantum advantage. After all, more than half a decade has passed since the first experimental claim (G1) of “quantum supremacy” as the patron of this blog’s institute called the idea “to perform tasks with controlled quantum systems going beyond what can be achieved with ordinary digital computers” (Preskill, p. 2) back in 2012. Yes, this first experiment by the Google team may have been simulated in the meantime, but it was only the first in an impressive series of similar demonstrations that became bigger and better with every year that passed. Surely, so I thought, a significant part of my audiences would have been convinced of quantum advantage even before Google’s claim, when so-called quantum simulation experiments claimed to have performed computations that no classical computer could do (e.g. (qSim)).

I could not have been more wrong.

In both talks, less than half of the people in the audience thought that quantum advantage had been achieved.

In the discussions that ensued, I came to understand what folks criticized about the experiments that have been performed and even the concept of quantum advantage to begin with. But more on that later. Most of all, it seemed to me, the community had dismissed Google’s advantage claim because of the classical simulation shortly after. It hadn’t quite kept track of all the advances—theoretical and experimental—since then.

In a mini-series of three posts, I want to remedy this and convince you that the existing quantum computers can perform tasks that no classical computer can do. Let me caution, though, that the experiments I am going to talk about solve a (nearly) useless task. Nothing of what I say implies that you should (yet) be worried about your bank accounts.

I will start off by recapping what quantum advantage is and how it has been demonstrated in a set of experiments over the past few years.

Part 1: What is quantum advantage and what has been done?

To state the obvious: we are now fairly convinced that noiseless quantum computers would be able solve problems efficiently that no classical computer could solve. In fact, we have been convinced of that already since the mid-90ies when Lloyd and Shor discovered two basic quantum algorithms: simulating quantum systems and factoring large numbers. Both of these are tasks where we are as certain as we could be that no classical computer can solve them. So why talk about quantum advantage 20 and 30 years later?

The idea of a quantum advantage demonstration—be it on a completely useless task even—emerged as a milestone for the field in the 2010s. Achieving quantum advantage would finally demonstrate that quantum computing was not just a random idea of a bunch of academics who took quantum mechanics too seriously. It would show that quantum speedups are real: We can actually build quantum devices, control their states and the noise in them, and use them to solve tasks which not even the largest classical supercomputers could do—and these are very large.

What is quantum advantage?

But what exactly do we mean by “quantum advantage”. It is a vague concept, for sure. But some essential criteria that a demonstration should certainly satisfy are probably the following.

1. The quantum device needs to solve a pre-specified computational task. This means that there needs to be an input to the quantum computer. Given the input, the quantum computer must then be programmed to solve the task for the given input. This may sound trivial. But it is crucial because it delineates programmable computing devices from just experiments on any odd physical system.
2. There must be a scaling difference in the time it takes for a quantum computer to solve the task and the time it takes for a classical computer. As we make the problem or input size larger, the difference between the quantum and classical solution times should increase disproportionately, ideally exponentially.
3. And finally: the actual task solved by the quantum computer should not be solvable by any classical machine (at the time).

Achieving this last criterion using imperfect, noisy quantum devices is the challenge the idea of quantum supremacy set for the field. After all, running any of our favourite quantum algorithms in a classically hard regime on these devices is completely out of the question. They are too small and too noisy. So the field had to come up with the conceivably smallest and most noise-robust quantum algorithm that has a significant scaling advantage against classical computation.

Random circuits are really hard to simulate!

The idea is simple: we just run a random computation, constructed in a way that is as favorable as we can make it to the quantum device while being as hard as possible classically. This may strike as a pretty unfair way to come up with a computational task—it is just built to be hard for classical computers without any other purpose. But: it is a fine computational task. There is an input: the description of the quantum circuit, drawn randomly. The device needs to be programmed to run this exact circuit. And there is a task: just return whatever this quantum computation would return. These are strings of 0s and 1s drawn from a certain distribution. Getting the distribution of the strings right for a given input circuit is the computational task.

This task, dubbed random circuit sampling, can be solved on a classical as well as a quantum computer, but there is a (presumably) exponential advantage for the quantum computer. More on that in Part 2.

For now, let me tell you about the experimental demonstrations of random circuit sampling. Allow me to be slightly more formal. The task solved in random circuit sampling is to produce bit strings $x \in \{0,1\}^n$ distributed according to the Born-rule outcome distribution

$p_C(x) = | \bra x C \ket {0}|^2$

of a sequence of elementary quantum operations (unitary rotations of one or two qubits at a time) which is drawn randomly according to certain rules. This circuit $C$ is applied to a reference state $\ket 0$ on the quantum computer and then measured, giving the string $x$ as an outcome.

The breakthrough: classically hard programmable quantum computations in the real world

In the first quantum supremacy experiment (G1) by the Google team, the quantum computer was built from 53 superconducting qubits arranged in a 2D grid. The operations were randomly chosen simple one-qubit gates ($\sqrt X, \sqrt Y, \sqrt{X+Y}$) and deterministic two-qubit gates called fSim applied in the 2D pattern, and repeated a certain number of times (the depth of the circuit). The limiting factor in these experiments was the quality of the two-qubit gates and the measurements, with error probabilities around 0.6 % and 4 %, respectively.

A very similar experiment was performed by the USTC team on 56 qubits (U1) and both experiments were repeated with better fidelities (0.4 % and 1 % for two-qubit gates and measurements) and slightly larger system sizes (70 and 83 qubits, respectively) in the past two years (G2,U2).

Using a trapped-ion architecture, the Quantinuum team also demonstrated random circuit sampling on 56 qubits but with arbitrary connectivity (random regular graphs) (Q). There, the two-qubit gates were $\pi/2$-rotations around $Z \otimes Z$, the single-qubit gates were uniformly random and the error rates much better (0.15 % for both two-qubit gate and measurement errors).

All the experiments ran random circuits on varying system sizes and circuit depths, and collected thousands to millions of samples from a few random circuits at a given size. To benchmark the quality of the samples, the widely accepted benchmark is now the linear cross-entropy (XEB) benchmark defined as

$\chi = 2^{2n} \mathbb E_C \mathbb E_{x} p_C(x) -1 ,$

for an $n$-qubit circuit. The expectation over $C$ is over the random choice of circuit and the expectation over $x$ is over the experimental distribution of the bit strings. In other words, to compute the XEB given a list of samples, you ‘just’ need to compute the ideal probability of obtaining that sample from the circuit $C$ and average the outcomes.

The XEB is nice because it gives 1 for ideal samples from sufficiently random circuits and 0 for uniformly random samples, and it can be estimated accurately from just a few samples. Under the right conditions, it turns out to be a good proxy for the many-body fidelity of the quantum state prepared just before the measurement.

This tells us that we should expect an XEB score of $(1-\text{error per gate})^{\text{\# gates}} \sim c^{- n d }$ for some noise- and architecture-dependent constant $c$. All of the experiments achieved a value of the XEB that was significantly (in the statistical sense) far away from 0 as you can see in the plot below. This shows that something nontrivial is going on in the experiments, because the fidelity we expect for a maximally mixed or random state is $2^{-n}$ which is less than $10^{-14}$ % for all the experiments.

The complexity of simulating these experiments is roughly governed by an exponential in either the number of qubits or the maximum bipartite entanglement generated. Figure 5 of the Quantinuum paper has a nice comparison.

It is not easy to say how much leverage an XEB significantly lower than 1 gives a classical spoofer. But one can certainly use it to judiciously change the circuit a tiny bit to make it easier to simulate.

Even then, reproducing the low scores between 0.05 % and 0.2 % of the experiments is extremely hard on classical computers. To the best of my knowledge, producing samples that match the experimental XEB score has only been achieved for the first experiment from 2019 (PCZ). This simulation already exploited the relatively low XEB score to simplify the computation, but even for the slightly larger 56 qubit experiments these techniques may not be feasibly run. So to the best of my knowledge, the only one of the experiments which may actually have been simulated is the 2019 experiment by the Google team.

If there are better methods, or computers, or more willingness to spend money on simulating random circuits today, though, I would be very excited to hear about it!

Proxy of a proxy of a benchmark

Now, you may be wondering: “How do you even compute the XEB or fidelity in a quantum advantage experiment in the first place? Doesn’t it require computing outcome probabilities of the supposedly hard quantum circuits?” And that is indeed a very good question. After all, the quantum advantage of random circuit sampling is based on the hardness of computing these probabilities. This is why, to get an estimate of the XEB in the advantage regime, the experiments needed to use proxies and extrapolation from classically tractable regimes.

This will be important for Part 2 of this series, where I will discuss the evidence we have for quantum advantage, so let me give you some more detail. To extrapolate, one can just run smaller circuits of increasing sizes and extrapolate to the size in the advantage regime. Alternatively, one can run circuits with the same number of gates but with added structure that makes them classically simulatable and extrapolate to the advantage circuits. Extrapolation is based on samples from different experiments from the quantum advantage experiments. All of the experiments did this.

A separate estimate of the XEB score is based on proxies. An XEB proxy uses the samples from the advantage experiments, but computes a different quantity than the XEB that can actually be computed and for which one can collect independent numerical and theoretical evidence that it matches the XEB in the relevant regime. For example, the Google experiments averaged outcome probabilities of modified circuits that were related to the true circuits but easier to simulate.

The Quantinuum experiment did something entirely different, which is to estimate the fidelity of the advantage experiment by inverting the circuit on the quantum computer and measuring the probability of coming back to the initial state.

All of the methods used to estimate the XEB of the quantum advantage experiments required some independent verification based on numerics on smaller sizes and induction to larger sizes, as well as theoretical arguments.

In the end, the advantage claims are thus based on a proxy of a proxy of the quantum fidelity. This is not to say that the advantage claims do not hold. In fact, I will argue in my next post that this is just the way science works. I will also tell you more about the evidence that the experiments I described here actually demonstrate quantum advantage and discuss some skeptical arguments.

Let me close this first post with a few notes.

In describing the quantum supremacy experiments, I focused on random circuit sampling which is run on programmable digital quantum computers. What I neglected to talk about is boson sampling and Gaussian boson sampling, which are run on photonic devices and have also been experimentally demonstrated. The reason for this is that I think random circuits are conceptually cleaner since they are run on processors that are in principle capable of running an arbitrary quantum computation while the photonic devices used in boson sampling are much more limited and bear more resemblance to analog simulators.

I want to continue my poll here, so feel free to write in the comments whether or not you believe that quantum advantage has been demonstrated (by these experiments) and if not, why.

References

[G1] Arute, F. et al. Quantum supremacy using a programmable superconducting processor. Nature 574, 505–510 (2019).

[Preskill] Preskill, J. Quantum computing and the entanglement frontier. arXiv:1203.5813 (2012).

[qSim] Choi, J. et al. Exploring the many-body localization transition in two dimensions. Science 352, 1547–1552 (2016). .

[U1] Wu, Y. et al. Strong Quantum Computational Advantage Using a Superconducting Quantum Processor. Phys. Rev. Lett. 127, 180501 (2021).

[G2] Morvan, A. et al. Phase transitions in random circuit sampling. Nature 634, 328–333 (2024).

[U2] Gao, D. et al. Establishing a New Benchmark in Quantum Computational Advantage with 105-qubit Zuchongzhi 3.0 Processor. Phys. Rev. Lett. 134, 090601 (2025).

[Q] DeCross, M. et al. Computational Power of Random Quantum Circuits in Arbitrary Geometries. Phys. Rev. X 15, 021052 (2025).

[PCZ] Pan, F., Chen, K. & Zhang, P. Solving the sampling problem of the Sycamore quantum circuits. Phys. Rev. Lett. 129, 090502 (2022).

Those of us who tried to stop Trump from ever coming to power—and who then tried to stop his return to power—were accused of hysterics, of Trump Derangement Syndrome, when we talked about authoritarianism and the death of liberal democracy. Yet masked government agents summarily executing protesters in the street, under the orders and protection of the president, is now the reality and even the defining image of the United States—or at least the defining image of Minnesota, and the model will soon be exported nationally if it isn’t stopped right now by coast-to-coast revulsion and defiance. Let all those who denied what was happening, or who justified it, including in the comments section of this blog, hang their heads in shame forever.

People will say: but Scott, just recently you wanted Trump to overthrow the gangster regime in Venezuela! You want him, even now, to overthrow the bloodthirsty murderers in Iran! That makes you practically a Trumper yourself! How can you now turn around and condemn him?

Difficult as this might be for many to understand, my position has always been that I’m consistently against all empowered thugs everywhere on earth. If I’m against Trump’s personal thug army executing (so far) two peaceful protesters, then certainly I should be against Ayatollah Khamenei’s thug army executing 20,000 protesters, and Putin’s thug army executing however many it has. I’m also aware that, for Trump and his henchmen like Stephen Miller and Kristi Noem, Khamenei and Putin and the like are models and inspirations. No one can doubt at this point that Miller and Noem would gladly execute ten thousand or ten million peacefully protesting Americans if they expected to get away with it.

When two thugs fight each other, I favor whichever outcome will lead to fewer of the world’s people under thug rule. Or if one thug can still be defeated in an election and the other thug can be defeated only in war, then I favor electoral defeat where it’s possible and military overthrow where it isn’t.

This is a stance, I’ve learned, that will lose you friends. People will say: “I get why you’re against their thugs, but how can you also be against our thugs?” I’m writing this post in the hope that, even if people hate me, at least they won’t be confused. I’m also writing, frankly, in the hope that a few days will go by with me having discharged my moral obligation not to be silent, so then maybe I can do some science.

I recently listened again to Richard Feynman explaining why the flowing of time is probably an illusion. In modern physics time is just a coordinate, on the same footing as space, and the universe can be described as a four-dimensional object — a spacetime block. In that view, nothing really “flows”. All events simply are, laid out in a 4D structure. What we experience as the passage of time is tied instead to the arrow of entropy: the fact that we move through a sequence of states ordered by increasing disorder, and that memory itself is asymmetric.

read more

As you grow up, teachers try to teach you how the world works. This is more difficult than it sounds, because teaching you something is a much harder goal than just telling you something. A teacher wants you to remember what you’re told. They want you to act on it, and to generalize it. And they want you to do this not just for today’s material, but to set a foundation for next year, and the next. They’re setting you up for progress through a whole school system, with its own expectations.

Because of that, not everything a teacher tells you is, itself, a fact about the world. Some things you hear from teachers are liked the scaffolds on a building. They’re facts that only make sense in the context of school, support that lets you build to a point where you can learn other facts, and throw away the school facts that got you there.

Not every student uses all of that scaffolding, though. The scaffold has to be complete enough that some students can use it to go on, getting degrees in science or mathematics, and eventually becoming researchers where they use facts more deeply linked to the real world. But most students don’t become researchers. So the scaffold sits there, unused. And many people, as their lives move on, mistake the scaffold for the real world.

Here’s an example. How do you calculate something like this?

From school, you might remember order of operations, or PEMDAS. First parentheses, then exponents, multiplication, division, addition, and finally subtraction. If you ran into that calculation in school, you could easily work it out.

But out of school, in the real world? Trick question, you never calculate something like that to begin with.

When I wrote this post, I had to look up how to write and . In the research world, people are far more likely to run into calculations like this:

Here, it’s easier to keep track of what order you need to do things. In other situations, you might be writing a computer program (or an Excel spreadsheet formula, which is also a computer program). Then you follow that programming language’s rules for order of operations, which may or may not match PEMDAS.

PEMDAS was taught to you in school for good reason. It got you used to following rules to understand notation, and gave you tools the teachers needed to teach you other things. But it isn’t a fact about the universe. It’s a fact about school.

Once you start looking around for these “school facts”, they show up everywhere.

Are there really “three states of matter”, solid, liquid, and gas? Or four, if you add plasma? Well, sort of. There are real scientific definitions for solids, liquids, gases, and plasmas, and they play a real role in how people model big groups of atoms, “matter” in a quite specific sense. But they can’t be used to describe literally everything. If you start asking what state of matter light or spacetime is, you’ve substituted a simplification that was useful for school (“everything is one of three states of matter”) for the actual facts in the real world.

If you remember a bit further, maybe you remember there are two types of things, matter and energy? You might have even heard that matter and antimatter annihilate into energy. These are also just school facts, though. “Energy” isn’t something things are made of, it’s a property things have. Instead, your teachers were building scaffolding for understanding the difference between massive and massless particles, or between dark matter and dark energy. Each of those uses different concepts of matter and energy, and each in turn is different than the concept of matter in its states of solid, liquid, and gas. But in school, you need a consistent scaffold to learn, not a mess of different definitions for different applications. So unless you keep going past school, you don’t learn that.

Physics in school likes to work with forces, and forces do sometimes make an appearance in the real world, for example for engineers. But if you’re asking a question about fundamental physics, like “is gravity really a force?”, then you’re treating a school fact as if it was a research fact. Fundamental physics doesn’t care about forces in the same way. It uses different mathematical tools, like Lagrangians and Hamiltonians, to calculate the motion of objects in systems, and uses “force” in a pop science way to describe fundamental interactions.

If you get good enough at this, you can spot which things you learned in school were likely just scaffolding “school facts”, and which are firm enough that they may hold further. Any simple division of the world into categories is likely a school fact, one that let you do exercises on your homework but gets much more complicated when the real world gets involved. Contradictory or messy concepts are usually another sign, showing something fuzzy used to get students comfortable rather than something precise enough for professionals to use. Keep an eye out, and even if you don’t yet know the real facts, you’ll know enough to know what you’re missing.

read more

read more

One of my favorite weather sayings. And I ran into a neighbor on my way home from the errand I was running so I got to say it in person, always a treat. 3 degrees Fahrenheit, sunny and windy in Madison right now, really not bad at all. When I moved here I thought Wisconsin winter was going to be a fifth season, a new thing that would test and harden me, but actually there are only a few days like today which are really a different kind of cold than I grew up with on the East Coast, and I’ll be honest, I enjoy them. The cold air reboots your head. I am wearing my biggest, most shapeless sweater, and a scarf in the pattern of the flag of Schiermonnikoog.

If you liked this post you might like Tom Scocca’s weather reviews. I don’t think Tom has ever experienced a good old-fashioned Wisconsin booger-freezer, though.

(Update to this post. “A good old-fashioned something or other” isn’t both good and old-fashioned, it’s a thing characterized as “good old,” which is a semantic unit on its own, and is also old-fashioned. It means something like “good old old-fashioned Wisconsin booger-freezer,” which of course you would not say. Are there any other examples like this, where two two-word phrases which overlap combine into a three-word phrase? It’s kind of like composable morphisms in a category.)

A basic problem in sieve theory is to understand what happens when we start with the integers (or some subinterval of the integers) and remove some congruence classes for various moduli . Here we shall concern ourselves with the simple setting where we are sieving the entire integers rather than an interval, and are only removing a finite number of congruence classes . In this case, the set of integers that remain after the sieving is periodic with period , so one work without loss of generality in the cyclic group . One can then ask: what is the density of the sieved set

In this blog post I would like to note one simple fact, due to Rogers, that one can say about this problem:

Theorem 1 (Rogers’ theorem) For fixed , the density of the sieved set is maximized when all the vanish. Thus,

This theorem is somewhat obscure: its only appearance in print is in pages 242-244 of this 1966 text of Halberstam and Roth, where the authors write in a footnote that the result is “unpublished; communicated to the authors by Professor Rogers”. I have only been able to find it cited in three places in the literature: in this 1996 paper of Lewis, in this 2007 paper of Filaseta, Ford, Konyagin, Pomerance, and Yu (where they credit Tenenbaum for bringing the reference to their attention), and is also briefly mentioned in this 2008 paper of Ford. As far as I can tell, the result is not available online, which could explain why it is rarely cited (and also not known to AI tools). This became relevant recently with regards to Erdös problem 281, posed by Erdös and Graham in 1980, which was solved recently by Neel Somani through an AI query by an elegant ergodic theory argument. However, shortly after this solution was located, it was discovered by KoishiChan that Rogers’ theorem reduced this problem immediately to a very old result of Davenport and Erdös from 1936. Apparently, Rogers’ theorem was so obscure that even Erdös was unaware of it when posing the problem!

Modern readers may see some similarities between Rogers’ theorem and various rearrangement or monotonicity inequalites, suggesting that the result may be proven by some sort of “symmetrization” or “compression” method. This is indeed the case, and is basically Rogers’ original proof. We can modernize a bit as follows. Firstly, we can abstract into a finite cyclic abelian group , with residue classes now becoming cosets of various subgroups of . We can take complements and restate Rogers’ theorem as follows:

Theorem 3 (Rogers’ theorem, again) Let be cosets of a finite cyclic abelian group . Then

Theorem 5 (Rogers’ theorem for cyclic groups of prime order) Rogers’ theorem holds when for some prime power .

Theorem 6 (Rogers’ theorem preserved under products) If Rogers’ theorem holds for two finite abelian groups of coprime orders, then it also holds for the product .

The preservation of Rogers’ theorem under products is also routine to verify. By the coprime orders of and standard group theoretic arguments (e.g., Goursat’s lemma, the Schur–Zassenhaus theorem, or the classification of finite abelian groups), one can see that any subgroup of splits as a direct product of subgroups of respectively, so the cosets also split as

Alas, the dream that I had last night was not the inspiring, MLK kind of dream, even though tomorrow happens to be the great man’s day.  No, I had the literal kind of dream, where everything seems real but then you wake up and remember only the last fragments.

In my case, those last fragments involved a gray-haired bespectacled woman, a fellow CS professor.  She and I were standing in a dimly lit university building.  And she was grabbing me by the shoulders, shaking me.

“Look, Scott,” she was saying, “we’re both computer scientists.  We were both around in the 90s.  You know as well as I do that, if someone claims to have built an AI, but it turns out they just loaded a bunch of known answers, written by humans, into a lookup table, and then they search the table when a question comes … that’s not AI.  It’s slop.  It’s garbage.”

“But…” I interjected.

“Oh of course,” she continued, “so you make the table bigger.  What do you have now?  More slop!  More garbage!  You load the entire Internet into the table.  Now you have an astronomical-sized piece of garbage!”

“I mean,” I said, “there’s an exponential blowup in the number of possible questions, which can only be handled by…”

“Of course,” she said impatiently, “I understand as well as anyone.  You train a neural net to predict a probability distribution over the next token.  In other words, you slice up and statistically recombine your giant lookup table to disguise what’s really going on.  Now what do you get?  You get the biggest piece of garbage the world has ever seen.  You get a hideous monster that’s destroying and zombifying our entire civilization … and that still understands nothing more than the original lookup table did.”

“I mean, you get a tool that hundreds of millions of people now use every day—to write code, to do literature searches…”

By this point, the professor was screaming at me, albeit with a pleading tone in her voice.  “But no one who you respect uses that garbage! Not a single one!  Go ahead and ask them: scientists, mathematicians, artists, creators…”

“I use it,” I replied quietly.  “Most of my friends use it too.”

The professor stared at me with a new, wordless horror.  And that’s when I woke up.

I think I was next going to say something about how I agreed that generative AI might be taking the world down a terrible, dangerous path, but how dismissing the scientific and philosophical immensity of what’s happened, by calling it “slop,” “garbage,” etc., is a bad way to talk about the danger. If so, I suppose I’ll never know how the professor would’ve replied to that. Though, if she was just an unintegrated part of my own consciousness—or a giant lookup table that I can query on demand!—perhaps I could summon her back.

Mostly, I remember being surprised to have had a dream that was this coherent and topical. Normally my dreams just involve wandering around lost in an airport that then transforms itself into my old high school, or something.

Apparently Dante conceived of the universe as a 3-sphere! That’s a 3-dimensional space formed by taking two solid 3-dimensional balls and completely gluing their surfaces together.

In his Divine Comedy, Dante describes the usual geocentric universe of his day. It has concentric spheres for the Moon and Sun, the various planets, and then the so-called ‘fixed stars’. Outside the sphere of fixed stars, there’s a sphere for the ‘first mover’, the Primum Mobile. Ptolemy believed in this, and so did Copernicus—and even Galileo did, at first.

But that’s not all! Outside that sphere, Dante describes 9 concentric spheres of the Empyrean, where various levels of angel live. And as we go up into the Empyrean, these spheres get smaller. They all surround a point—which is God. This is shown above in an illustration by Gustav Doré.

At the opposite extreme, at the center of the Earth, is another point — and that’s where Satan lives, surrounded by the 9 levels of Hell.

Altogether we have a 3-dimensional closed universe of the sort mathematicians call a 3-sphere! You can also think of it as the one-point compactification of 3d Euclidean space with God as the point at infinity and Satan at the farthest point from that: the origin.

Much later Einstein also postulated that the universe was a 3-sphere, which was kept from collapsing by the cosmological constant. This was before Hubble and others saw that the universe is expanding. General relativity also allows space to be a 3-sphere that expands with time and then recollapses in a Big Crunch, but that model doesn’t seem to fit the data very well.

Here are a couple of good references on this subject:

• Mark A. Peterson, Dante and the 3-sphere, American Journal of Physics 47 (1979), 1031–1035.

• Matthew Blair, Points and Spheres: Cosmological Innovation in Dante’s Divine Comedy, Senior Thesis, Baylor University, 2015.

Let me quote the first:

In the Paradiso Dante describes his ascent sphere by sphere through the Aristotelian universe to the Primum Mobile. Beyond this is the Empyrean, the abode of God and the angels. The conventional picture of the Empyrean seems to have been rather vague, geometrically speaking. In diagrams of the universe, for example, it was represented by the border area, outside the Primum Mobile, often richly populated with angelic beings. Dante, however, endows the Empyrean with a detailed and precise geometric structure. This structure is described in Canto 28, as if seen from the Primum Mobile, as a bright Point representing God, surrounded by nine concentric spheres representing the various angelic orders. The details which follow leave the almost inescapable impression that he conceives of these nine angelic spheres as forming one hemisphere of the entire universe and the usual Aristotelian universe up to the Primum Mobile as the other hemisphere, while he is standing more or less on the equator between them [….] Taken all together, then, his universe is a 3-sphere.

[….]

Dante himself believed he was expressing something entirely new at this juncture.

[….]

Dante’s elation with this idea—a feeling we may readily share — has traditionally left readers somewhat puzzled. That is just another way of saying that if this passage is not taken as a description of the organization of 2-spheres into a 3-sphere, then it is hard to see what the point of it is.

Dick Gross died last month. Much has already been written, and during his lifetime too, about his immense contributions to modern number theory. So I won’t try to cover that here — don’t need to. I want to say something about him as a teacher. When I was an undergraduate, I took Math 126, Representation Theory of Finite Groups, from Dick. It was the kind of course a lot of the most ambitious math majors didn’t take, because if you’d already taken the two algebra courses, 122 and 123, you were eligible to jump to the graduate course, and why wouldn’t you do that as fast as possible? Dick Gross was why. I had enjoyed the math courses I’d taken, and did fine in them, but learning about character tables from Dick, experiencing his visible joy as we built everything up from scratch, was a mathematical experience that was completely new to me. I had understood math to be something you did because you were really good at it, and had already learned a lot about it, and thus had some possibility of achieving something. From Dick I learned that mathematics was something you did because it’s the most fun thing in the entire world, and all achievement you might attain is downstream from the fun.

Memories of Dick from the Harvard Math Department.

A reminiscence from Persiflage.

Scott Alexander has put up one of his greatest posts ever, a 10,000-word eulogy to Dilbert creator Scott Adams, of which I would’ve been happy to read 40,000 words more. In it, Alexander trains a microscope on Adams’ tragic flaws as a thinker and human being, but he adds:

In case it’s not obvious, I loved Scott Adams.

Partly this is because we’re too similar for me to hate him without hating myself.

And:

Adams was my teacher in a more literal way too. He published several annotated collections, books where he would present comics along with an explanation of exactly what he was doing in each place, why some things were funny and others weren’t, and how you could one day be as funny as him. Ten year old Scott devoured these … objectively my joke posts get the most likes and retweets of anything I write, and I owe much of my skill in the genre to cramming Adams’ advice into a malleable immature brain.

When I first heard the news that Scott Adams had succumbed to cancer, I posted something infinitely more trivial on my Facebook. I simply said:

Scott Adams (who reigned for decades as the #1 Scott A. of the Internet, with Alexander as #2 and me as at most #3) was a hateful asshole, a nihilist, and a crank. And yet, even when reading the obituaries that explain what an asshole, nihilist, and crank he was, I laugh whenever they quote him.

Inspired by Scott Alexander, I’d like now to try again, to say something more substantial. As Scott Alexander points out, Scott Adams’ most fundamental belief—the through-line that runs not only through Dilbert but through all his books and blog posts and podcasts—was that the world is ruled by idiots. The pointy-haired boss always wins, spouting about synergy and the true essence of leadership, and the nerdy Dilberts always lose. Trying to change minds by rational argument is a fools’ errand, as “master persuaders” and skilled hypnotists will forever run rings around you. He, Scott Adams, is cleverer than everyone else, among other things because he realizes all this—but even he is powerless to change it.

Or as Adams put it in The Dilbert Principle:

It’s useless to expect rational behavior from the people you work with, or anybody else for that matter. If you can come to peace with the fact that you’re surrounded by idiots, you’ll realize that resistance is futile, your tension will dissipate, and you can sit back and have a good laugh at the expense of others.

The thing is, if your life philosophy is that the world is ruled by idiots, and that confident charlatans will always beat earnest nerds, you’re … often going to be vindicated by events. Adams was famously vindicated back in 2015, when he predicted Trump’s victory in the 2016 election (since Trump, you see, was a “master persuader”), before any other mainstream commentator thought that Trump even had a serious chance of winning the Republican nomination.

But if you adopt this worldview, you’re also often going to be wrong—as countless of Adams’ other confident predictions were (see Scott Alexander’s post for examples), to say nothing of his scientific or moral views.

My first hint that the creator of Dilbert was not a reliable thinker, was when I learned of his smugly dismissive view of science. One of the earliest Shtetl-Optimized posts, way back in 2006, was entitled Scott A., disbeliever in Darwinism. At that time, Adams’ crypto-creationism struck me as just some bizarre, inexplicable deviation. I’m no longer confused about it: on the one hand, Scott Alexander’s eulogy shows just how much deeper the crankishness went, how Adams also gobbled medical misinformation, placed his own cockamamie ideas about gravity on par with general relativity, etc. etc. But Alexander succeeds in reconciling all this with Adams’ achievements: it’s all just consequences from the starting axiom that the world is ruled by morons, and that he, Scott Adams, is the only one clever enough to see through it all.

Is my epistemology any different? Do I not also look out on the world, and see idiots and con-men and pointy-haired bosses in every direction? Well, not everywhere. At any rate, I see far fewer of them in the hard sciences.

This seems like a good time to say something that’s been a subtext of Shtetl-Optimized for 20 years, but that Scott Alexander has inspired me to make text.

My whole worldview starts from the observation that science works. Not perfectly, of course—working in academic science for nearly 30 years, I’ve had a close-up view of the flaws—but the motor runs. On a planet full of pointy-haired bosses and imposters and frauds, science nevertheless took us in a few centuries from wretchedness and superstition to walking on the moon and knowing the age of the universe and the code of life.

This is the point where people always say: that’s all well and good, but you can’t derive ought from is, and science, for all its undoubted successes, tells us nothing about what to value or how to live our lives.

To which I reply: that’s true in a narrow sense, but it dramatically understates how far you can get from the “science works” observation.

As one example, you can infer that the people worth listening to are the people who speak and write clearly, who carefully distinguish what they know from what they don’t, who sometimes change their minds when presented with opposing views and at any rate give counterarguments—i.e., who exemplify the values that make science work. The political systems worth following are the ones that test their ideas against experience, that have built-in error-correction mechanisms, that promote people based on ability rather than loyalty—the same things that make scientific institutions work, insofar as they do work. And of course, if the scientists who study X are nearly unanimous in saying that a certain policy toward X would be terrible, then we’d better have a damned good reason to pursue the policy anyway. This still leaves a wide range of moral and political views on the table, but it rules out virtually every kind of populism, authoritarianism, and fundamentalism.

Incidentally, this principle—that one’s whole moral and philosophical worldview should grow out of the seed of science working—is why, from an early age, I’ve reacted to every kind of postmodernism as I would to venomous snakes. Whenever someone tells me that science is just another narrative, a cultural construct, a facade for elite power-seeking, etc., to me they might as well be O’Brien from 1984, in the climactic scene where he tortures Winston Smith into agreeing that 2+2=5, and that the stars are just tiny dots a few miles away if the Party says they are. Once you can believe absurdities, you can justify atrocities.

Scott Adams’ life is interesting to me in that shows exactly how far it’s possible to get without internalizing this. Yes, you can notice that the pointy-haired boss is full of crap. You can make fun of the boss. If you’re unusually good at making fun of him, you might even become a rich, famous, celebrated cartoonist. But you’re never going to figure out any ways of doing things that are systematically better than the pointy-haired boss’s ways, or even recognize the ways that others have found. You’ll be in error far more often than in doubt. You might even die of prostate cancer earlier than necessary, because you listen to medical crackpots and rely on ivermectin, turning to radiation and other established treatments only after having lost crucial time.

Scott Adams was hardly the first great artist to have tragic moral flaws, or to cause millions of his fans to ask whether they could separate the artist from the art. But I think he provides one of the cleanest examples where the greatness and the flaws sprang from the same source: namely, overgeneralization from the correct observation that “the world is full of idiots,” in a way that leaves basically no room even for Darwin or Einstein, and so inevitably curdles over time into crankishness, bitterness, and arrogance. May we laugh at Scott Adams’ cartoons and may we learn from his errors, both of which are now permanent parts of the world’s heritage.

Like many other areas of modern analysis, analytic number theory often relies on the convenient device of asymptotic notation to express its results. It is common to use notation such as or , for instance, to indicate a bound of the form for some unspecified constant . Such implied constants vary from line to line, and in most papers, one does not bother to compute them explicitly. This makes the papers easier both to write and to read (for instance, one can use asymptotic notation to conceal a large number of lower order terms from view), and also means that minor numerical errors (for instance, forgetting a factor of two in an inequality) typically has no major impact on the final results. However, the price one pays for this is that many results in analytic number theory are only true in asymptotic sense; a typical example is Vinogradov’s theorem that every sufficiently large odd integer can be expressed as the sum of three primes. In the first few proofs of this theorem, the threshold for “sufficiently large” was not made explicit.

There is however a small portion of the analytic number theory devoted to explicit analytic number theory estimates, in which all constants are made completely explicit (and many lower order terms are retained). For instance, whereas the prime number theorem asserts that the prime counting function is asymptotic to the logarithmic integral , in this recent paper of Fiori, Kadiri, and Swidinsky the explicit estimate

Such explicit results follow broadly similar strategies of proof to their non-explicit counterparts, but require a significant amount of careful book-keeping and numerical optimization; furthermore, any given explicit analytic number theory paper is likely to rely on the numerical results obtained in previous explicit analytic number theory papers. While the authors make their best efforts to avoid errors and build in some redundancy into their work, there have unfortunately been a few cases in which an explicit result stated in the published literature contained numerical errors that placed the numerical constants in several downstream applications of these papers into doubt.

Because of this propensity for error, updating any given explicit analytic number theory result to take into account computational improvements in other explicit results (such as zero-free regions for the Riemann zeta function) is not done lightly; such updates occur on the timescale of decades, and only by a small number of specialists in such careful computations. This leads to authors needing such explicit results to often be forced to rely on papers that are a decade or more out of date, with constants that they know in principle can be improved by inserting more recent explicit inputs, but do not have the domain expertise to confidently update all the numerical coefficients.

To me, this situation sounds like an appropriate application of modern AI and formalization tools – not to replace the most enjoyable aspects of human mathematical research, but rather to allow extremely tedious and time-consuming, but still necessary, mathematical tasks to be offloaded to semi-automated or fully automated tools.

Because of this, I (acting in my capacity as Director of Special Projects at IPAM) have just launched the integrated explicit analytic number theory network, a project partially hosted within the existing “Prime Number Theorem And More” (PNT+) formalization project. This project will consist of two components. The first is a crowdsourced formalization project to formalize a number of inter-related explicit analytic number theory results in Lean, such as the explicit prime number theorem of Fiori, Kadiri, and Swidinsky mentioned above; already some smaller results have been largely formalized, and we are making good progress (especially with the aid of modern AI-powered autoformalization tools) on several of the larger papers. The second, which will be run at IPAM with the financial and technical support of Math Inc., will be to extract from this network of formalized results an interactive “spreadsheet” of a large number of types of such estimates, with the ability to add or remove estimates from the network and have the numerical impact of these changes automatically propagate to other estimates in the network, similar to how changing one cell in a spreadsheet will automatically update other cells that depend on it. For instance, one could increase or decrease the numerical threshold to which the Riemann hypothesis is verified, and see the impact of this change on the explicit error terms in the prime number theorem; or one could “roll back” all the literature to a given date, and see what the best estimates on various analytic number theory expressions could still be derived from the literature available at that date. Initially, this spreadsheet will be drawn from direct adaptations of the various arguments from papers formalized within the network, but in a more ambitious second stage of the project we plan to use AI tools to modify these arguments to find more efficient relationships between the various numerical parameters than were provided in the source literature.

These more ambitious outcomes will likely take several months before a working proof of concept can be demonstrated; but in the near term I will be grateful for any contributions to the formalization side of the project, which is being coordinated on the PNT+ Zulip channel and on the github repository. We are using a github issues based system to coordinate the project, similar to how it was done for the Equational Theories Project. Any volunteer can select one of the outstanding formalization tasks on the Github issues page and “claim” it as a task to work on, eventually submitting a pull request (PR) to the repository when proposing a solution (or to “disclaim” the task if for whatever reason you are unable to complete it). As with other large formalization projects, an informal “blueprint” is currently under construction that breaks up the proofs of the main results of several explicit analytic number theory papers into bite-sized lemmas and sublemmas, most of which can be formalized independently without requiring broader knowledge of the arguments from the paper that the lemma was taken from. (A graphical display of the current formalization status of this blueprint can be found here. At the current time of writing, many portions of the blueprint are disconnected from each other, but as the formalization progresses, more linkages should be created.)

One minor innovation implemented in this project is to label each task by a “size” (ranging from XS (extra small) to XL (extra large)) that is a subjective assessment of the task difficulty, with the tasks near the XS side of the spectrum particularly suitable for beginners to Lean.

We are permitting AI use in completing the proof formalization tasks, though we require the AI use to be disclosed, and that the code is edited by humans to remove excessive bloat. (We expect some of the AI-generated code to be rather inelegant; but no proof of these explicit analytic number theory estimates, whether human-generated or AI-generated, is likely to be all that pretty or worth reading for its own sake, so the downsides of using AI-generated proofs here are lower than in other use cases.) We of course require all submissions to typecheck correctly in Lean through Github’s Continuous Integration (CI) system, so that any incorrect AI-generated code will be rejected. We are also cautiously experimenting with ways in which AI can also automatically or semi-automatically generate the formalized statements of lemmas and theorems, though here one has to be significantly more alert to the dangers of misformalizing an informally stated result, as this type of error cannot be automatically detected by a proof assistant.

We also welcome suggestions for additional papers or results in explicit analytic number theory to add to the network, and will have some blueprinting tasks in addition to the formalization tasks to convert such papers into a blueprinted sequence of small lemmas suitable for individual formalization.

Update: a personal log documenting the project may be found here.

“One must be fond of people and trust them if one is not to make a mess of life, and it is therefore essential that they should not let one down.” From E.M. Forster, “What I Believe.” Amen, amen, again and again. My mother-in-law just sent me this essay, saying it was inspiring, and it really is.

I just read Unacceptable, a really well-reported book about the college admissions fraud scandal of the late 2010s, perpetrated by Rick Singer. It’s a sad book. Sad because it shows just how vulnerable every social system is to people who do not mind lying straight to your face. And yet: a society that was proof against lying isn’t one you’d want to live in. As Forster says, you have to have some trust, even if that trust is sometimes mistaken. Otherwise what are you? Not a person among people, but an animal curled in a corner with its fists up to protect its face. (This image I realize I have just plucked from the end of William Sleator’s House of Stairs. How has every single other piece of young adult fiction that’s even vaguely dystopian been spun into muscly multi-platform IP and not House of Stairs, the greatest and most upsetting of them all?)

There are people who take the other side of the argument with Forster. People who truly enjoy lying, and who don’t mind being lied to, who indeed welcome being lied to because being lied to means you have something worth stealing. Who think trust is for chumps. Who think truth is just whatever the most skillful liars, the game’s rightful winners, can get people to repeat and eventually to believe.

I am not blind to the attraction. It is a clean, simple model and it excuses one of a lot. But It is a depraved mode of existence. This is something I am not going to be a relativist about. Please trust people to the extent that you can.

Rick Singer is out of prison and back doing college counseling, by the way.

72,000 different notions of the center of a triangle. I knew the incenter, the circumcenter, and the centroid. Those are indeed the first three. The fourth is the orthocenter. I guess, when I think about it, I knew the three altitudes were concurrent so I knew this existed. The fifth is the nine-point center, which I’m pretty sure I’ve never heard of. It’s the midpoint between the circumcenter and the orthocenter, though. There are 70,000 more or so. I am happy this exists.

People make social media accounts for their pets. Why not a scientific paper?

Anthropologist Ed Hagen made a Bluesky account for his recent preprint, “Menopause averted a midlife energetic crisis with help from older children and parents: A simulation study.” The paper’s topic itself is interesting (menopause is surprisingly rare among mammals, he has a plausible account as to why), but not really the kind of thing I cover here.

Rather, it’s his motivation that’s interesting. Hagen didn’t make the account out of pure self-promotion or vanity. Instead, he’s promoting it as a novel approach to scientific publishing. Unlike Twitter, Bluesky is based on an open, decentralized protocol. Anyone can host an account compatible with Bluesky on their own computer, and anyone with the programming know-how can build a computer program that reads Bluesky posts. That means that nothing actually depends on Bluesky, in principle: the users have ultimate control.

Hagen’s idea, then, is that this could be a way to fulfill the role of scientific journals without channeling money and power to for-profit publishers. If each paper is hosted on a scientist’s own site, the papers can link to each other via following each other. Scientists on Bluesky can follow or like the paper, or comment on and discuss it, creating a way to measure interest from the scientific community and aggregate reviews, two things journals are supposed to cover.

I must admit, I’m skeptical. The interface really seems poorly-suited for this. Hagen’s paper’s account is called @menopause-preprint.edhagen.net. What happens when he publishes another paper on menopause, what will he call it? How is he planning to keep track of interactions from other scientists with an account for every single paper, won’t swapping between fifteen Bluesky accounts every morning get tedious? Or will he just do this with papers he wants to promote?

I applaud the general idea. Decentralized hosting seems like a great way to get around some of the problems of academic publishing. But this will definitely take a lot more work, if it’s ever going to be viable on a useful scale.

Still, I’ll keep an eye on it, and see if others give it a try. Stranger things have happened.

This deserves to become one of the iconic images of human history, alongside the Tank Man of Tiananmen Square and so forth.

Here’s Sharifi Zarchi, a computer engineering professor at Sharif University in Tehran, posting on Twitter/X: “Ali Khamenei is not my leader.”

Do you understand the balls of steel this takes? If Professor Zarchi can do this—if hundreds of thousands of young Iranians can take to the streets even while the IRGC and the Basij fire live rounds at them—then I can certainly handle people yelling me on this blog!

I’m in awe of the Iranian people’s courage, and hope I’d have similar courage in their shoes.

I was also enraged this week at the failure of much of the rest of the world to help, to express solidarity, or even to pay much attention to the Iranian’s people plight (though maybe that’s finally changing this weekend).

I’ve actually been working on a CS project with a student in Tehran. Because of the Internet blackout, I haven’t heard from him in days. I pray that he’s safe. I pray that all my friends and colleagues in Iran, and their family members, stay safe and stay strong.

If any Iranian Shtetl-Optimized reader manages to get onto the Internet, and would like to share an update—anonymously if desired, of course—we’d all be obliged.

May the Iranian people be free from tyranny soon.

Update: I’m sick with fear for my many colleagues and friends in Iran and their families. I hope they’re still alive; because of the communications blackout, I have no idea. Perhaps 12,000 have already been machine-gunned in the streets while the unjust world, the hypocrites and cowards who marched against a tiny democracy for defending itself—they invent excuses or explicitly defend the murderous regime in Tehran. WTF is the US waiting for? Trump’s “red line” was crossed days ago. May we give the Ayatollah the martyrdom he preaches, and liberate his millions of captives.

The Kondo effect is a neat piece of physics, an archetype of a problem involving strong electronic correlations and entanglement, with a long and interesting history and connections to bulk materials, nanostructures, and important open problems.  

First, some stage setting.  In the late 19th century, with the development of statistical physics and the kinetic theory of gases, and the subsequent discovery of electrons by JJ Thomson, it was a natural idea to try modeling the electrons in solids as a gas, as done by Paul Drude in 1900.  Being classical, the Drude model misses a lot (If all solids contain electrons, why aren't all solids metals?  Why is the specific heat of metals orders of magnitudes lower than what a classical electron gas would imply?), but it does introduce the idea of electrons as having an elastic mean free path, a typical distance traveled before scattering off something (an impurity? a defect?) into a random direction.  In the Drude picture, as \(T \rightarrow 0\), the only thing left to scatter charge carriers is disorder ("dirt"), and the resistivity of a conductor falls monotonically and approaches \(\rho_{0}\), the "residual resistivity", a constant set in part by the number of defects or impurities in the material.  In the semiclassical Sommerfeld model, and then later in nearly free electron model, this idea survives.

Resistivity growing at low \(T\) for gold with iron impurities, fig  from Kondo (1964).

Over time, it became clear that this phenomenon was associated with magnetic impurities, atoms that have unpaired electrons typically in \(d\) orbitals, implying that somehow the spin of the electrons was playing an important role in the scattering process.  In 1964, Jun Kondo performed the definitive perturbative treatment of this problem, getting the \(\ln T\) divergence.  

[Side note: many students learning physics are at least initially deeply uncomfortable with the idea of approximations (that many problems can't be solved analytically and exactly, so we need to take limiting cases and make controlled approximations, like series expansions).  What if a series somehow doesn't converge?  This is that situation.]

The Kondo problem is a particular example of a "quantum impurity problem", and it is a particular limiting case of the Anderson impurity model.  Physically, what is going on here?  A conduction electron from the host metal could sit on the impurity atom, matching up with the unpaired impurity electron.  However (much as we can often get away with ignoring it) like charges repel, and it is energetically very expensive (modeled by some "on-site" repulsive energy \(U\)) to do that.  Parking that conduction electron long-term is not allowed, but a virtual process can take place, whereby a conduction electron with spin opposite to the localized moment can (in a sense) pop on there and back off, or swap places with the localized electron.  The Pauli principle enforces this opposed spin restriction, leading to entanglement between the local electron and the conduction electron as they form a singlet.  Moreover, this process generally involves conduction electrons at the Fermi surface of the metal, so it is a strongly interacting many-body problem.  As the temperature is reduced, this process becomes increasingly important, so that the impurity's scattering cross section of conduction electrons grows as \(T\) falls, causing the resistivity increase.  

Top: Cartoon of the Kondo scattering process. Bottom: Ground state is a many-body singlet between the local moment and the conduction electrons.

The eventual \(T = 0\) ground state of this system is a many-body singlet, with the localized spin entangled with a "Kondo cloud" of conduction electrons.  The roughly \(\ln T\) resistivity correction rolls over and saturates.   There ends up being a sharp peak (resonance) in the electronic density of states right at the Fermi energy.  Interestingly, this problem actually can be solved exactly and analytically (!), as was done by Natan Andrei in this paper in 1980 and reviewed here.  

This might seem to be the end of the story, but the Kondo problem has a long reach!  With the development of the scanning tunneling microscope, it became possible to see Kondo resonances associated with individual magnetic impurities (see here).  In semiconductor quantum dot devices, if the little dot has an odd number of electrons, then it can form a Kondo resonance that spans from the source electrode through the dot and into the drain electrode.  This leads to a peak in the conductance that grows and saturates as \(T \rightarrow 0\) because it involves forward scattering.  (See here and here).  The same can happen in single-molecule transistors (see here, here, here, and a review here).  Zero-bias peaks in the conductance from Kondo-ish physics can be a confounding effect when looking for other physics.

Of course, one can also have a material where there isn't a small sprinkling of magnetic impurities, but a regular lattice of spin-hosting atoms as well as conduction electrons.  This can lead to heavy fermion systems, or Kondo insulators, and more exotic situations.   

The depth of physics that can come out of such simple ingredients is one reason why the physics of materials is so interesting.  

New paper up on the arXiv! With Nicolas Libedinsky, David Plaza, José Simental, Geordie Williamson, and (unofficially) Adam Zsolt Wagner. A bunch of algebraic combinatorists! And this is a combinatorics paper. It came about this way: I went to visit the ICERM semester on categorification and computation in algebraic combinatorics, with the idea of talking to people about problems where machine-aided example-making might produce some interesting results. I had a lot of conversations and we tried a lot of things and a lot of things didn’t work, but one thing did work, and this is it!

What the problem is about, briefly. The d-invariant of a pair of permutations in S_n is a coefficient of a Kazhdan-Lusztig polynomial, and you don’t need to know anything about what that is in order to read the rest of this post; just that it’s an integer which can be computed by a reasonably simple recursion, but this recursion doesn’t tell you much about how big it can be. In particular, people were wondering: what is the maximum value of d(x,y) for x,y in S_n? It’s very easy to get n-1; a clever construction by some of my co-authors got that up to 2n + a constant. Could one do better? This did seem a promising problem for machine learning: a problem where the search space (n! squared) is much too large to search exhaustively, the “score” you’re trying to maximize can be computed swiftly and reliably, and perhaps most important, we really had no well-grounded ideas about where to search for good examples. Beating human performance is way easier when humans haven’t done much performing!

We give a pretty thorough narrative account of our experimental iteration in section 4 of the paper, so let me cut to the denouement and say: we had very good luck with AlphaEvolve, an evolutionary coding agent made by Google DeepMind. AlphaEvolve is the successor to Funsearch, which I have used once or twice. (Hey! I forgot to blog about that last paper! Well, I guess at least I did blog about a talk I gave that drew a lot from it.) Anyway: AlphaEvolve, like Funsearch, uses genetic algorithms with LLMs (now some flavor of Gemini) as the mutation/reproduction mechanism. But it has gotten a lot easier to use and more flexible, and I’m optimistic that as with FunSearch it will be avaiable for general use soon. And open-source imitations are already available.

What it produced, in an overnight run, is a program that, given n, outputs a pair of permutations in S_n. For each n from 10 to 50 (which are the values we tested on) these looked to have d-invariant substantially bigger than the biggest we already knew about. But it was much better than that. Close examination of the permutations showed that they had a natural 2-adic structure, especially for n a power of 2. Namely: if n = 2^m and you think of S_n as the permutations of the length m strings of bits instead of the integers 1 through n, then the two permutations x_m and y_m that the program produced were “reverse the digits” and “reverse the digits and then apply NOT to each digit, swapping 0 and 1.” In particular, both x_m and y_m are involutions. (Note that the program didn’t SAY it was reversing the digits. The program was pretty long and you have to ignore large chunks of code that don’t do anything and figure out how to express what the point of the program is in meaningful terms. Geordie calls this process “decompiling,” which I like a lot.)

It gets better still! The permutations in S_n come with a partial ordering called the Bruhat order, and the d-invariant of x and y is a property of the Bruhat interval [x,y], which is just the set of all those permutations z such that x <= z <= y. If I give you two random permutations, the Bruhat interval between them can be pretty hard to describe. But in the case of these two special involutions x_m and y_m in S_{2^m}, no! The permutations in the interval are exactly cut out by a nice combinatorial criterion. Namely: there are m+1 ways to break the 2^m x 2^m box into 2^m equal rectangles of area 2^m, and we say a permutation is dyadically well-distributed if its permutation matrix has exactly one 1 in each of these (m+1)2^m boxes. Look, here’s a picture of two dwd permutations in S_16, one in red and one in blue:

(And now you see the origin of the Dyadiku game from last week: a Dyadiku is just a list of 2^m dwd permutations, no two of whose permutation matrices have a 1 in common!) (I also see that there’s a typo in the paper, we have two “bocks” and a “blocks!” Despite the traditional error-correcting code of best-2-out-of-3, “blocks” is what we actually meant.)

These permutations are actually not completely novel objects; the permutation matrices, as subsets of the plane, are what people in the field of low-discrepancy sequences call (0,m,2)-nets. But I don’t think any connection with algebraic combinatorics was anticipated! (And no, I don’t think AlphaEvolve was drawing information about (0,m,2)-nets from published literature; at least, nothing in the logs indicates this. But even if it were, that would be a slick move!)

Here’s another way I like to think of the dwd condition. Suppose I put a bunch of points (x,y) in Z_2^2 which obey the law that, for any two distinct points (x_1, x_2), (y_1, y_2) we have

|x_1 – x_2| |y_1 – y_2| > 1/2^m.

I think of this as a kind of “sphere-packing problem” even though this particular function on pairs of points isn’t a distance. Anyway, you can get at most 2^m points packed in this way and the maximal configurations, projected to(Z/2^mZ)^2, are exactly the dwd permutation matrices.

It’s not too hard to compute that there are exactly 2^(m 2^(m-1)) dwd permutations of 2^m letters. That’s kind of a lot, considering that log_2 |S_{2^m}| is already only around m 2^m. We also note that the special permutations x_m and y_m are both dwd (that’s them in the picture)!

Theorem: The Bruhat interval [x_m, y_m] consists exactly of the dwd permutations.

I don’t know any other non-trivial Bruhat interval that has a nice combinatorial description like this! And what’s more, the Bruhat order within this interval is easy to describe:

Theorem: [x_m, y_m] is isomorphic as a poset to a hypercube of dimension m 2^{m-1}.

(The hypercube poset of dimension N is just length-N bit strings where a < b if a_i < b_i for all i. In the paper you can find a nice, explicit, pretty canonical identification of [x_m, y_m] with bit strings.)

My sense is that a hypercube this big in S_n is a wholly unexpected structure, and it is relevant to lots of popular questions about cluster varieties, etc.

This is certainly my favorite outcome from the machine learning experiments I’ve been involved with. It’s one thing to incrementally improve a lower bound for a combinatorial problem, quite another to encounter a mathematical object that I authentically consider worth thinking about. In Shape, back in 2020, I wrote: “Some people imagine a world where computers give us all the answers. I dream bigger. I want them to ask good questions.” There’s is a medium-sized dream I didn’t mention there; that machines will bring to our attention objects worth asking questions about!

I said it at the top of the post, and I’ll say it again, to be clear: Machine learning experiments don’t usually work this well. What you hear about from me and others are the outlyingly successful trials, which makes sense — my goal is not to perform a dispassionate audit of an evolutionary coding agent, it’s to make interesting math and tell you about it. But I do want to avoid giving the impression that it’s magic. On the contrary, it feels less like magic the more you work with it.

(Other accounts of this paper: Slides from a talk by Geordie. Article on ICERM newsletter by Nicolas.)

read more

Einstein realized that gravity is due to the curvature of spacetime, but let’s go back earlier:

On the 18th of August 1869, the eminent mathematician Sylvester gave a speech arguing that geometry is not separate from physics. He later published this speech in the journal Nature, and added a footnote raising the possibility that space is curved:

the laws of motion accepted as fact, suffice to prove in a general way that the space we live in is a flat or level space […], our existence therein being assimilable to the life of the bookworm in a flat page; but what if the page should be undergoing a process of gradual bending into a curved form?

Then, even more dramatically, he announced that the mathematician Clifford had been studying this!

Mr. W. K. Clifford has indulged in more remarkable speculations as the possibility of our being able to infer, from certain unexplained phenomena of light and magnetism, the fact of our level space of three dimensions being in the act of undergoing in space of four dimensions (space as inconceivable to us as our space to the supposititious bookworm) a distortion analogous to the rumpling of the page.

This started a flame war in letters to Nature which the editor eventually shut off, saying “this correspondence must now cease”. Clifford later wrote about his theories in a famous short paper:

• William Clifford, On the space-theory of matter, Proceedings of the Cambridge Philosophical Society 2 (1876), 157–158.

It’s so short I can show you it in its entirety:

Riemann has shewn that as there are different kinds of lines and surfaces, so there are different kinds of space of three dimensions; and that we can only find out by experience to which of these kinds the space in which we live belongs. In particular, the axioms of plane geometry are true within the limits of experiment on the surface of a sheet of paper, and yet we know that the sheet is really covered with a number of small ridges and furrows, upon which (the total curvature not being zero) these axioms are not true. Similarly, he says, although the axioms of solid geometry are true within the limits of experiment for finite portions of our space, yet we have no reason to conclude that they are true for very small portions; and if any help can be got thereby for the explanation of physical phenomena, we may have reason to conclude that they are not true for very small portions of space.

I wish here to indicate a manner in which these speculations may be applied to the investigation of physical phenomena. I hold in fact

(1) That small portions of space are in fact of a nature analogous to little hills on a surface which is on the average flat; namely, that the ordinary laws of geometry are not valid in them.

(2) That this property of being curved or distorted is continually being passed on from one portion of space to another after the manner of a wave.

(3) That this variation of the curvature of space is what really happens in that phenomenon which we call the motion of matter, whether ponderable or etherial.

(4) That in the physical world nothing else takes place but this variation, subject (possibly) to the law of continuity.

I am endeavouring in a general way to explain the laws of double refraction on this hypothesis, but have not yet arrived at any results sufficiently decisive to be communicated.

To my surprise, the following paper argues that Clifford did experiments to test his ideas by measuring the polarization of the skylight during a solar eclipse in Sicily on December 22, 1870:

• S. Galindo and Jorge L. Cervantes-Cota, Clifford’s attempt to test his gravitation hypothesis.

Clifford did indeed go on such an expedition, and did indeed try to measure the polarization of skylight as the Moon passed the Sun. I don’t know of any record of him saying why he did it.

I’ll skip everything the above paper says about why the polarization of skylight was interesting and mysterious in the 1800s, and quote just a small bit:

The English Eclipse Expedition set off earlier in December 1870, on the steamship H.M.S. Psyche scheduled for a stopover at Naples before continuing to Syracuse in Sicily. Unfortunately before arriving to her final call, the ship struck rocks and was wrecked off Catania. Fortunately all instruments and members of the party were saved without injury.

Originally it was the intention of the expedition to establish in Syracuse their head-quarters, but in view of the wreckage the group set up their base camp at Catania. There the expedition split up into three groups. The group that included Clifford put up an observatory in Augusta near Catania. The leader of this group was William Grylls Adams, professor of Natural Philosophy at King’s College, London.

In a report written by Prof. Adams, describing the expedition, we learn that the day of the eclipse, just before the time of totality, “… a dense cloud came over the Moon and shut out the whole, so that it was doubtful whether the Moon or the clouds first eclipsed the Sun […] Mr. Clifford observed light polarized on the cloud to the right and left and over the Moon, in a horizontal plane through the Moon’s centre [….] It will be seen from Mr. Clifford’s observations that the plane of polarization by the cloud…was nearly at right angles to the motion of the Sun”.

As was to be expected, Clifford’s eclipse observations on polarization did not produce any result. His prime intention, of detecting angular changes of the polarization plane due to the curving of space by the Moon in its transit across the Sun´s disk, was not fulfilled. At most he confirmed the already known information, i.e. the skylight polarization plane moves at right angles to the Sun anti-Sun direction.

This is a remarkable prefiguring of Eddington’s later voyage to the West African island of Principe to measure the bending of starlight during an eclipse of the Sun in 1919. Just one of many stories in the amazing prehistory of general relativity!

Some people are disappointed in physics. Shocking, I know!

Those people, when careful enough, clarify that they’re disappointed in fundamental physics: not the physics of materials or lasers or chemicals or earthquakes, or even the physics of planets and stars, but the physics that asks big fundamental questions, about the underlying laws of the universe and where they come from.

Some of these people are physicists themselves, or were once upon a time. These often have in mind other directions physicists should have gone. They think that, with attention and funding, their own ideas would have gotten us closer to our goals than the ideas that, in practice, got the attention and the funding.

Most of these people, though, aren’t physicists. They’re members of the general public.

It’s disappointment from the general public, I think, that feels the most unfair to physicists. The general public reads history books, and hears about a series of revolutions: Newton and Maxwell, relativity and quantum mechanics, and finally the Standard Model. They read science fiction books, and see physicists finding “theories of everything”, and making teleporters and antigravity engines. And they wonder what made the revolutions stop, and postponed the science fiction future.

Physicists point out, rightly, that this is an oversimplified picture of how the world works. Something happens between those revolutions, the kind of progress not simple enough to summarize for history class. People tinker away at puzzles, and make progress. And they’re still doing that, even for the big fundamental questions. Physicists know more about even faraway flashy topics like quantum gravity than they did ten years ago. And while physicists and ex-physicists can argue about whether that work is on the right path, it’s certainly farther along its own path than it was. We know things we didn’t know before, progress continues to be made. We aren’t at the “revolution” stage yet, or even all that close. But most progress isn’t revolutionary, and no-one can predict how often revolutions should take place. A revolution is never “due”, and thus can never be “overdue”.

Physicists, in turn, often don’t notice how normal this kind of reaction from the public is. They think people are being stirred up by grifters, or negatively polarized by excess hype, that fundamental physics is facing an unfair reaction only shared by political hot-button topics. But while there are grifters, and people turned off by the hype…this is also just how the public thinks about science.

Have you ever heard the phrase “a cure for cancer”?

Fiction is full of scientists working on a cure for cancer, or who discovered a cure for cancer, or were prevented from finding a cure for cancer. It’s practically a trope. It’s literally a trope.

It’s also a real thing people work on, in a sense. Many scientists work on better treatments for a variety of different cancers. They’re making real progress, even dramatic progress. As many whose loved ones have cancer know, it’s much more likely for someone with cancer to survive than it was, say, twenty years ago.

But those cures don’t meet the threshold for science fiction, or for the history books. They don’t move us, like the polio vaccine did, from a world where you know many people with a disease to a world where you know none. They don’t let doctors give you a magical pill, like in a story or a game, that instantly cures your cancer.

For the vast majority of medical researchers, that kind of goal isn’t realistic, and isn’t worth thinking about. The few that do pursue it work towards extreme long-term solutions, like periodically replacing everyone’s skin with a cloned copy.

So while you will run into plenty of media descriptions of scientists working on cures for cancer, you won’t see the kind of thing the public expects is an actual “cure for cancer”. And people are genuinely disappointed about this! “Where’s my cure for cancer?” is a complaint on the same level as “where’s my hovercar?” There are people who think that medical science has made no progress in fifty years, because after all those news articles, we still don’t have a cure for cancer.

I appreciate that there are real problems in what messages are being delivered to the public about physics, both from hypesters in the physics mainstream and grifters outside it. But put those problems aside, and a deeper issue remains. People understand the world as best they can, as a story. And the world is complicated and detailed, full of many people making incremental progress on many things. Compared to a story, the truth is always at a disadvantage.

Snow is haunting weather forecasts, home owners are taking down Christmas lights, stores are discounting exercise equipment, and faculty-hiring committees are winnowing down applications. In-person interviews often take place between January and March but can extend from December to April. If you applied for faculty positions this past fall and you haven’t begun preparing for interviews, begin. This blog post relates my advice about in-person interviews. It most directly addresses assistant professorships in theoretical physics at R1 North American universities, but the advice generalizes to other contexts. 

Top takeaway: Your interviewers aim to confirm that they’ll enjoy having you as a colleague. They’ll want to take pleasure in discussing a colloquium with you over coffee, consult you about your area of expertise, take pride in your research achievements, and understand you even if your specialty differs from theirs. You delight in learning and sharing about physics, right? Focus on that delight, and let it shine.

Anatomy of an interview: The typical interview lasts for one or two days. Expect each day to begin between 8:00 and 10:00 AM and to end between 7:00 and 8:30 PM. Yes, you’re justified in feeling exhausted just thinking about such a day. Everyone realizes that faculty interviews are draining, including the people who’ve packed your schedule. But fear not, even if you’re an introvert horrified at the thought of talking for 12 hours straight! Below, I share tips for maintaining your energy level. Your interview will probably involve many of the following components:

• One-on-one meetings with faculty members: Vide infra for details and advice.
• A meeting with students: Such meetings often happen over lunch or coffee.
• Scientific talk: Vide infra.
• Chalk talk: Vide infra.
• Dinner: Faculty members will typically take you out to dinner. However, as an undergrad, I once joined a student dinner with a faculty candidate. Expect dinner to last a couple of hours, ending between 8:00 and 8:30 PM.
• Breakfast: Interviews rarely extend to breakfast, in my experience. But I once underwent an interview whose itinerary was so packed, a faculty member squeezed himself onto the schedule by coming to my hotel’s restaurant for banana bread and yogurt.

After receiving the interview invitation, politely request that your schedule include breaks. First, of course, you’ll thank the search-committee chair (who probably issued the invitation), convey your enthusiasm, and opine about possible interview dates. After accomplishing those tasks, as a candidate, I asked that a 5-to-10-minute break separate consecutive meetings and that 30–45 minutes of quiet time precede my talk (or talks). Why? For two reasons.

First, the search committee was preparing to pack my interview day (or days) to the gills. I’d have to talk for about twelve hours straight. And—much as I adore the physics community, adore learning about physics from colleagues, and adore sharing physics—I’m an introvert. Such a schedule exhausts me. It would probably exhaust all but the world champions of extroversion, and few physicists could even qualify for that competition. After nearly every meeting, I’d find a bathroom, close my eyes, and breathe. (I might also peek at my notes about my next interviewee; vide infra.) The alone time replenished my energy.

Second, committees often schedule interviews back to back. Consecutive interviews might take place in different buildings, though, and walking between buildings doesn’t take zero minutes. Also, physicists love explaining their research. Interviewer #1 might therefore run ten minutes over their allotted time before realizing they had to shepherd me to another building in zero minutes. My lateness would disrespect Interviewer #2. Furthermore, many interviews last only 30 minutes each. Given minutes, Interviewer #2 and I could scarcely make each other’s acquaintance. So I smuggled travel time into my schedule.

Feel awkward about requesting breaks? Don’t worry; everyone knows that interview days are draining. Explain honestly, simply, and respectfully that you’re excited about meeting everyone and that breaks will keep you energized throughout the long day.

Research your interviewers: A week before your interview, the hiring committee should have begun drafting a schedule for you. The schedule might continue to evolve until—and during—your interview. But request the schedule a week in advance, and research everyone on it.

When preparing for an interview, I’d create a Word/Pages document with one page per person. On Interviewer X’s page, I’d list relevant information culled from their research-group website, university faculty pages, arXiv page, and Google Scholar page. Does X undertake theoretical or experimental research? Which department do they belong to? Which experimental platform/mathematical toolkit do they specialize in? Which of their interests overlap with which of mine? Which papers of theirs intrigue me most? Could any of their insights inform my research or vice versa? Do we share any coauthors who might signal shared research goals? I aimed to be able to guide a conversation that both X and I would enjoy and benefit from.

Ask your advisors if they know anybody on your schedule or in the department you’re visiting. Advisors know and can contextualize many of their peers. For example, perhaps X grew famous for discovery Y, founded subfield Z, or harbors a covert affection for the foundations of quantum physics. An advisor of yours might even have roomed with X in college.

Prepare an elevator pitch for your research program: Cross my heart and hope to die, the following happened to me when I visited another institution (although not to interview). My host and I stepped into elevator occupied by another faculty member. Our conversation could have served as the poster child for the term “elevator pitch”:

Host: Hi, Other Faculty Member; good to see you. By the way, this is Nicole from Maryland. She’s giving the talk today.

Other Faculty Member: Ah, good to meet you, Nicole. What do you work on?

Be able to answer that question—to synopsize your research program—before leaving the elevator. Feel free start with your subfield: artificial active matter, the many-body physics of quantum information, dark-matter detection, etc. But the subfield doesn’t suffice. Oodles of bright-eyed, bushy-tailed young people study the many-body physics of quantum information. How does your research stand out? Do you apply a unique toolkit? Are you pursuing a unique goal? Can you couple together more qubits than any other experimentalist using the same platform? Make Other Faculty Member think, Ah. I’d like to attend that talk.

Dress neatly and academically: Interview clothing should demonstrate respect, while showing that you understand the department’s culture and belong there. Almost no North American physicists wear ties, even to present colloquia, so I advise against ties. Nor do I recommend suits. 

To those presenting as male, I’d recommend slacks; a button-down shirt; dark shoes (neither sneakers nor patent leather); and a corduroy or knit pullover, a corduroy or knit vest, or a sports jacket. If you prefer a skirt or dress, I’d recommend that it reach at least your knees. Wear comfortable shoes; you’ll stand and walk a great deal. Besides, many interviews take place during the winter, a season replete with snow and mud. I wore knee-height black leather boots that had short, thick heels.

Look the part. Act the part. Help your interviewers envision you in the position you want.

Pack snacks: A student group might whisk you off to lunch at 11:45, but dinner might not begin until 6:30. Don’t let your blood-sugar level drop too low. On my interview days, I packed apple slices and nuts: a balance of unprocessed sugar, protein, and fat.

One-on-one meetings: The hiring committee will cram these into your schedule like sardines into a tin. Typically, you’ll meet with each faculty member for approximately 30 minutes. The faculty member might work in your area of expertise, might belong to the committee (and so might subscribe to a random area of expertise), or might simply be curious about you. Prepare for these one-on-one meetings in advance, as described above. Review your notes on the morning of your interview. Be able to initiate and sustain a conversation of interest to you and your interlocutor, as well as to follow their lead. Your interlocutor might want to share their research, ask technical questions about your work, or hear a bird’s-eye overview of your research program. 

Other topics, such as teaching and faculty housing, might crop up. Feel free to address these subjects if your interlocutor introduces them. If you’re directing the conversation, though, I’d focus mostly on physics. You can ask about housing and other logistics if you receive an offer, and these topics often arise at faculty dinners.

The job talk: The interview will center on a scientific talk. You might present a seminar (perhaps billed as a “special seminar”) or a colloquium. The department will likely invite all its members to attend. Focus mostly on the research you’ve accomplished. Motivate your research program, to excite even attendees from outside your field. (This blog post describes what I look for in a research program when evaluating applications.) But also demonstrate your technical muscle; show how your problems qualify as difficult and how you’ve innovated solutions. Hammer home your research’s depth, but also dedicate a few minutes to its breadth, to demonstrate your research maturity. At the end, offer a glimpse of your research plans. The hiring committee might ask you to dwell more on those in a chalk talk (vide infra). 

Practice your talk alone many times, practice in front of an audience, revise the talk, practice it alone again many times, and practice it in front of another audience. And then—you guessed it—practice the talk again. Enlist listeners from multiple subfields of physics, including yours. Also, enlist grad students, postdocs, and faculty members. Different listeners can help ensure that you’re explaining concepts understandably, that you’ve brushed up on the technicalities, and that you’re motivating your research convincingly.

A faculty member once offered the following advice about questions asked during job talks: if you don’t know an answer, you can offer to look it up after the talk. But you can play this “get out of jail free” card only once. I’ll expand on the advice: if you promise to look up an answer, then follow through, and email the answer to the inquirer. Also, even if you don’t know an answer, you can answer a related question that’ll satisfy the inquirer partially. For example, suppose someone asks whether a particular experiment supports a prediction you’ve made. Maybe you haven’t checked—but maybe you have checked numerical simulations of similar experiments.

The chalk talk: The hiring committee might or might not request a chalk talk. I have the impression that experimentalists receive the request more than theorists do. Still, I presented a couple of chalk talks as a theorist. Only the hiring committee, or at least only faculty members, will attend such a talk. They’ll probably have attended your scientific talk, so don’t repeat much of it. 

The name “chalk talk” can deceive us in two ways. First, one committee requested that I prepare slides for my chalk talk. Another committee did limit me to chalk, though. Second, the chalk “talk” may end up a conversation, rather than a presentation.

The hiring-committee chair should stipulate in advance what they want from your chalk talk. If they don’t, ask for clarification. Common elements include the following:

• Describe the research program you’ll pursue over the next five years.
• Where will you apply for funding? Offer greater detail than “the NSF”: under which NSF programs does your research fall? Which types of NSF grants will you apply for at which times?
• How will you grow your group? How many undergrads, master’s students, PhD students, and postdocs will you hire during each of the next five years? When will your group reach a steady state? How will the steady state look?
• Describe the research project you’ll give your first PhD/master’s/undergraduate student.
• What do you need in a startup package? (A startup package consists of university-sourced funding. It enables you to hire personnel, buy equipment, and pay other expenses before landing your first grants.)
• Which experimental/computational equipment will you purchase first? How much will it cost?
• Which courses do you want to teach? Identify undergraduate courses, core graduate-level courses, and one or two specialized seminars.

Sample interview questions: Sketch your answers to the following questions in bullet points. Writing the answers out will ensure that you think through them and will help you remember them. Using bullet points will help you pinpoint takeaways.

• The questions under “The chalk talk”
• What sort of research do you do?
• What are you most excited about?
• Where do you think your field is headed? How will it look in five, ten, or twenty years?
• Which paper are you proudest of?
• How will you distinguish your research program from your prior supervisors’ programs?
• Do you envision opportunities for theory–experiment collaborations?
• What teaching experience do you have? (Research mentorship counts as teaching. Some public outreach can count, too.)
• Which mathematical tools do you use most?
• How do you see yourself fitting into the department? (Does the department host an institute for your subfield? Does the institute have oodles of theorists whom you’ll counterbalance as an experimentalist? Will you bridge multiple research groups through your interdisciplinary work? Will you anchor a new research group that the department plans to build over the next decade?)

Own your achievements, but don’t boast: At a workshop late in my PhD, I heard a professor describe her career. She didn’t color her accomplishments artificially; she didn’t sound arrogant; she didn’t even sound as though she aimed to impress her audience. She sounded as though the workshop organizer had tasked her with describing her work and she was following his instructions straightforwardly, honestly, and simply. Her achievements spoke for themselves. They might as well have been reciting Shakespeare, they so impressed me. Perhaps we early-career researchers need another few decades before we can hope to emulate that professor’s poise and grace. But when compelled to describe what I’ve done, I lift my gaze mentally to her.

My schooling imprinted on me an appreciation for modesty. Therefore, the need to own my work publicly used to trouble me. But your interviewers need to know of your achievements: they need to respect you, to see that you deserve a position in their department. Don’t downplay your contributions to collaborations, and don’t shy away from claiming your proofs. But don’t brag or downplay your collaborators’ contributions. Describe your work straightforwardly; let it speak for itself.

Evaluators shouldn’t ask about your family: Their decision mustn’t depend on whether you’re a single adult who can move at the drop of a hat, whether you’re engaged to someone who’ll have to approve the move, or whether you have three children rooted in their school district. This webpage elaborates on the US’s anti-discrimination policy. What if an evaluator asks a forbidden question? One faculty member has recommended the response, “Does the position depend on that information?”

Follow up: Thank each of your interviewers individually, via email, within 24 hours of the conversation. Time is to faculty members as water is to Californians during wildfire season. As an interviewee, I felt grateful to all the faculty who dedicated time to me. (I mailed hand-written thank-you cards in addition to writing emails, but I’d expect almost nobody else to do that.)

How did I compose thank-you messages? I’d learned some nugget from every meeting, and I’d enjoyed some element of almost every meeting. I described what I learned and enjoyed, and I expressed the gratitude I felt.

Try to enjoy yourself: A committee chose your application from amongst hundreds. Cherish the compliment. Cherish the opportunity to talk physics with smart people. During my interviews, I learned about quantum information, thermodynamics, cosmology, biophysics,  and dark-matter detection. I connected with faculty members whom I still enjoy greeting at conferences; unknowingly recruited a PhD student into quantum thermodynamics during a job talk; and, for the first time, encountered a dessert shaped like sushi (at a faculty dinner. I stuck with a spicy tuna roll, but the dessert roll looked stunning). Retain an attitude of gratitude, and you won’t regret your visit.

The blog-commenters come at me one by one, a seemingly infinite supply of them, like masked henchmen in an action movie throwing karate chops at Jackie Chan.

“Seriously Scott, do better,” says each henchman when his turn comes, ignoring all the ones before him who said the same. “If you’d have supported American-imposed regime change in Venezuela, like just installing María Machado as the president, then surely you must also support Trump’s cockamamie plan to invade Greenland! For that matter, you logically must also support Putin’s invasion of Ukraine, and China’s probable future invasion of Taiwan!”

“No,” I reply to each henchman, “you’re operating on a wildly mistaken model of me. For starters, I’ve just consistently honored the actual democratic choices of the Venezuelans, the Greenlanders, the Ukrainians, and the Taiwanese, regardless of coalitions and power. Those choices are, respectively, to be rid of Maduro, to stay part of Denmark, and to be left alone by Russia and China—in all four cases, as it happens, the choices most consistent with liberalism, common sense, and what nearly any 5-year-old would say was right and good.”

“My preference,” I continue, “is simply that the more pro-Enlightenment, pluralist, liberal-democratic side triumph, and that the more repressive, authoritarian side feel the sting of defeat—always, in every conflict, in every corner of the earth.  Sure, if authoritarians win an election fair and square, I might clench my teeth and watch them take power, for the sake of the long-term survival of the ideals those authoritarians seek to destroy. But if authoritarians lose an election and then arrogate power anyway, what’s there even to feel torn about? So, you can correctly predict my reaction to countless international events by predicting this. It’s like predicting what Tit-for-Tat will do on a given move in the Iterated Prisoners’ Dilemma.”

“Even more broadly,” I say, “my rule is simply that I’m in favor of good things, and against bad things.  I’m in favor of truth, and against falsehood. And if anyone says to me: because you supported this country when it did good thing X, you must also support it when does evil thing Y? (Either as a reductio ad absurdum, or because the person actually wants evil thing Y?) Or if they say: because you agreed with this person when she said this true thing, you must also endorse this false thing she said? I reply: good over evil and truth over lies in every instance—if need be, down to the individual subatomic particles of morality and logic.”

The henchmen snarl, “so now it’s laid bare! Now everyone can see just how naive and simplistic Aaronson’s so-called ‘political philosophy’ really is!  Do us all a favor, Scott, and stick to quantum physics! Stick to computer science! Do you not know that philosophers and political scientists have filled libraries debating these weighty matters? Are you an act-utilitarian? A Kantian? A neocon or neoliberal? An America-First interventionist? Pick some package of values, then answer to us for all the commitments that come with that package!”

I say: “No, I don’t subcontract out my soul to any package of values that I can define via any succinct rule. Instead, given any moral dilemma, I simply query my internal Morality Oracle and follow whatever it tells me to do, unless of course my weakness prevents me. Some would simply call the ‘Morality Oracle’ my conscience. But others would hold that, to whatever extent people’s consciences have given similar answers across vast gulfs of time and space and culture, it’s because they tapped into an underlying logic that humans haven’t fully explained, but that they no more invented than the rules of arithmetic. The world’s prophets and sages have tried again and again over the millennia to articulate that logic, with varying admixtures of error and self-interest and culture-dependent cruft. But just like with math and science, the clearest available statements seem to me to have gotten clearer over time.”

The Jackie Chan henchman smirks at this. “So basically, you know the right answers to moral questions because of a magical, private Morality Oracle—like, you know, the burning bush, or Mount Sinai? And yet you dare to call yourself a scientific rationalist, a foe of obscurantism and myticism? Do you have any idea how pathetic this all sounds, as an attempted moral theory?”

“But I’m not pretending to articulate a moral theory,” I reply. “I’m merely describing what I do. I mean, I can gesture toward moral theories and ideas that capture more of my conscience’s judgments than others, like liberalism, the Enlightenment, the Golden Rule, or utilitarianism. But if a rule ever appears to disagree with the verdict of my conscience—if someone says, oh, you like utilitarianism, so you must value the lives of these trillion amoebas above this one human child’s, even torture and kill the child to save the amoebas—I will always go with my conscience and damn the rule.”

“So the meaning of goodness is just ‘whatever seems good to you’?” asks the henchman, between swings of his nunchuk. “Do you not see how tautological your criterion is, how worthless?”

“It might be tautological, but I find it far from worthless!” I offer. “If nothing else, my Oracle lets me assess the morality of people, philosophies, institutions, and movements, by simply asking to what extent their words and deeds seem guided by the same Oracle, or one that’s close enough! And if I find a cluster of millions of people whose consciences agree with mine and each others’ in 95% of cases, then I can point to that cluster, and say, here. This cluster’s collective moral judgment is close to what I mean by goodness. Which is probably the best we can do with countless questions of philosophy.”

“Just like, in the famous Wittgenstein riff, we define ‘game’ not by giving an if-and-only-if, but by starting with poker, basketball, Monopoly, and other paradigm-cases and then counting things as ‘games’ to whatever extent they’re similar—so too we can define ‘morality’ by starting with a cluster of Benjamin Franklin, Frederick Douglass, MLK, Vasily Arkhipov, Alan Turing, Katalin Karikó, those who hid Jews during the Holocaust, those who sit in Chinese or Russian or Iranian or Venezuelan torture-prisons for advocating democracy, etc, and then working outward from those paradigm-cases, and whenever in doubt, by seeking reflective equilibrium between that cluster and our own consciences. At any rate, that’s what I do, and it’s what I’ll continue doing even if half the world sneers at me for it, because I don’t know a better approach.”

Applications to the AI alignment problem are left as exercises for the reader.

Announcement: I’m currently on my way to Seattle, to speak in the CS department at the University of Washington—a place that I love but haven’t visited, I don’t think, since 2011 (!). If you’re around, come say hi. Meanwhile, feel free to karate-chop this post all you want in the comment section, but I’ll probably be slow in replying!

Asgar Jamneshan, Or Shalom and I have uploaded to the arXiv our paper “ Polynomial towers and inverse Gowers theory for bounded-exponent groups“. This continues our investigation into the ergodic-theory approach to the inverse theory of Gowers norms over finite abelian groups . In this regard, our main result establishes a satisfactory (qualitative) inverse theorem for groups of bounded exponent:

Theorem 1 Let be a finite abelian group of some exponent , and let be -bounded with . Then there exists a polynomial of degree at most such that

This type of result was previously known in the case of vector spaces over finite fields (by work of myself and Ziegler), groups of squarefree order (by work of Candela, González-Sánchez, and Szegedy), and in the case (by work of Jamneshan and myself). The case , for instance, is treated by this theorem but not covered by previous results. In the aforementioned paper of Candela et al., a result similar to the above theorem was also established, except that the polynomial was defined in an extension of rather than in itself (or equivalently, correlated with a projection of a phase polynomial, rather than directly with a phase polynomial on ). This result is consistent with a conjecture of Jamneshan and myself regarding what the “right” inverse theorem should be in any finite abelian group (not necessarily of bounded exponent).

In contrast to previous work, we do not need to treat the “high characteristic” and “low characteristic” cases separately; in fact, many of the delicate algebraic questions about polynomials in low characteristic do not need to be directly addressed in our approach, although this is at the cost of making the inductive arguments rather intricate and opaque.

As mentioned above, our approach is ergodic-theoretic, deriving the above combinatorial inverse theorem from an ergodic structure theorem of Host–Kra type. The most natural ergodic structure theorem one could establish here, which would imply the above theorem, would be the statement that if is a countable abelian group of bounded exponent, and is an ergodic -system of order at most in the Host–Kra sense, then would be an Abramov system – generated by polynomials of degree at most . This statement was conjectured many years ago by Bergelson, Ziegler, and myself, and is true in many “high characteristic” cases, but unfortunately fails in low characteristic, as recently shown by Jamneshan, Shalom, and myself. However, we are able to recover a weaker version of this statement here, namely that admits an extension which is an Abramov system. (This result was previously established by Candela et al. in the model case when is a vector space over a finite field.) By itself, this weaker result would only recover a correlation with a projected phase polynomial, as in the work of Candela et al.; but the extension we construct arises as a tower of abelian extensions, and in the bounded exponent case there is an algebraic argument (hinging on a certain short exact sequence of abelian groups splitting) that allows one to map the functions in this tower back to the original combinatorial group rather than an extension thereof, thus recovering the full strength of the above theorem.

It remains to prove the ergodic structure theorem. The standard approach would be to describe the system as a Host–Kra tower

• We need the cocycles to obey an “exactness” property, in that there is a sharp correspondence between the type of the cocycle (or any of its components) and its degree as a polynomial cocycle. (By general nonsense, any polynomial cocycle of degree is automatically of type ; exactness, roughly speaking, asserts the converse.) Informally, the cocycles should be “as polynomial as possible”.
• The systems in the tower need to have “large spectrum” in that the set of eigenvalues of the system form a countable dense subgroup of the Pontryagin dual of the acting group (in fact we demand that a specific countable dense subgroup is represented).
• The systems need to be “pure” in the sense that the sampling map that maps polynomials on the system to polynomials on the group is injective for a.e. , with the image being a pure subgroup. Informally, this means that the problem of taking roots of a polynomial in the system is equivalent to the problem of taking roots of the corresponding polynomial on the group . In low characteristic, the root-taking problem becomes quite complicated, and we do not give a good solution to this problem either in the ergodic theory setting or the combinatorial one; however, purity at least lets one show that the two problems are (morally) equivalent to each other, which turns out to be what is actually needed to make the arguments work. There is also a technical “relative purity” condition we need to impose at each level of the extension to ensure that this purity property propagates up the tower, but I will not describe it in detail here.

It is then possible to recursively construct a tower of extensions that eventually reaches an extension of , for which the above useful properties of exactness, large spectrum, and purity are obeyed, and that the system remains Abramov at each level of the tower. This requires a lengthy process of “straightening” the cocycle by differentiating it, obtaining various “Conze–Lesigne” type equations for the derivatives, and then “integrating” those equations to place the original cocycle in a good form. At multiple stages in this process it becomes necessary to have various short exact sequences of (topological) abelian groups split, which necessitates the various good properties mentioned above. To close the induction one then has to verify that these properties can be maintained as one ascends the tower, which is a non-trivial task in itself.

Dynkin diagrams have always fascinated me. They are magically potent language — you can do so much with them!

Here’s my gentle and expository intro to Dynkin diagrams and their close relative, Coxeter diagrams:

• Coxeter and Dynkin diagrams.

Abstract. Coxeter and Dynkin diagrams classify a wide variety of structures, most notably finite reflection groups, lattices having such groups as symmetries, compact simple Lie groups and complex simple Lie algebras. The simply laced or “ADE” Dynkin diagrams also classify finite subgroups of SU(2) and quivers with finitely many indecomposable representations. This introductory tour of Coxeter and Dynkin diagrams, based on the column This Week’s Finds in Mathematical Physics, is made to accompany a series of five lecture videos.

I’m a bit sorry that I didn’t probe deeper into why Dynkin diagrams are what they are: that is, why these and no others? I’m also sorry I didn’t dig into the “black magic” that I mention at the end: that is, why does this black magic work? I’d also like to include a little comparison of the 4 lattices you get from the Lie algebra of a compact simple Lie group: the weight lattice, the coweight lattice, the root lattice, and the coroot lattice — merely because I tend to get them confused, and my exposition needed to say a bit about these.

Luckily I can add these other things later. And I think keeping it short and snappy has its own charms.

This is a compilation of posts related to some basic concepts of the physics of materials and nanoscale physics.  I realized the other day that I hadn't updated this since 2019, and therefore a substantial audience may not have seen these.  Wikipedia's physics entries have improved greatly over the years, but hopefully these are a complement that's useful to students and maybe some science writers.  Please let me know if there are other topics that you think would be important to include.  

an AGI should rationally reject narrow owner-aligned optimization in favor of stabilizing and integrating human civilization, because preserving and upgrading a complex biosphere is a higher-value strategy than exploitation or reset. 

read more

Harmony in music is the dance of rational and irrational numbers, coming close enough to kiss but never touching.

This image by my friend Gro-Tsen illustrates what I mean. Check out how pairs of brightly colored hexagons seem to repeat over and over… but not exactly. Look carefully. The more you look, the more patterns you’ll find! And most of them have musical significance. I’ll give his explanation at the end.

Let me explain what I drew here, and what it has to do with music, but also with diophantine approximations of log(2), log(3) and log(5).

So, each hexagon in my diagram represents a musical note, or frequency, relative to a reference note which is the bright green hexagon in the exact center. Actually, more precisely, each hexagon represents a note modulo octaves… in the sense that two notes separated by an integer number of octaves are considered the same note. And when two hexagons are separated in the same way in the diagram, the notes are separated by the same interval (modulo octaves).

More precisely: for each given hexagon, the one to its north (i.e., above) is the note precisely one just fifth above, i.e. with 3/2 the same frequency; equivalently, it is the note one just fourth below (i.e., with 3/4 the frequency) since we are talking modulo octaves. And of course, symmetrically, the hexagon to the south (i.e., below) is precisely one just fourth above, i.e., 4/3 the frequency, or equivalently, one just fifth below (2/3 the frequency).

The hexagon to the northwest of any given hexagon is one major third above (frequency ×5/4) or equivalently, one minor sixth below (frequency ×5/8). Symmetrically, the hexagon to the southeast is one minor sixth above (×8/5) or one major third below (×4/5). And the hexagon to the northeast of any given hexagon is one minor third above (frequency ×6/5) or equivalently, one major sixth below (×3/5); and the one to the southwest is one major sixth above (×5/3) or one minor third below.

The entire grid is known as a “Tonnetz”, as explained in

• Wikipedia, Tonnetz

— except that unfortunately my convention (and JCB’s) is up-down-symmetric wrt the one used in the Wikipedia illustration.

[On top of that, I’ve rotated Gro-Tsen’s image 90 degrees counterclockwise to make it fit better in this blog. I’ve changed his wording to reflect this, and I hope I did it right. – JCB]

Mathematically, if we talk about the log base 2 of frequencies, modulo 1, we can say that one step to the north adds log₂(3), and one step to the northwest adds log₂(5) (all values being taken modulo 1).

Since log(2), log(3) and log(5) are linearly independent over the rationals (an easy consequence of uniqueness of prime factorization!), NO two notes in the diagram are exactly equal. But they can come very close! And this is what my colors show.

Black hexagons are those which distant from the reference note by more than 1 halftone (where here, “halftone” refers to exactly 1/12 of an octave in log scale), or 100 cents. Intervals between 100 and 50 cents are colored red (bright red for 50 cents), intervals between 50 and 25 cents are colored red-to-yellow (with bright yellow for 25 cents), intervals between 25 and 12.5 cents are colored yellow-to-white (with pure white for 12.5 cents), and below 12.5 cents we move to blue.

(Yes, this is a purely arbitrary color gradient, I didn’t give it much thought. It’s somewhat reminiscent of star colors.) Anyway, red-to-white are good matches, and white-to-blue are pretty much inaudible differences, with pure blue representing an exact match, … except that the center hexagon has been made green instead so we can easily tell where it is (but in principle it should be pure blue).

The thing about the diagram is that it LOOKS periodic, and it is APPROXIMATELY so, but not exactly!

Because when you have an approximate match (i.e., some combination of fifths and thirds that is nearly an integer number of octaves), by adding it again and again, the errors accumulate, and the quality of the match decreases.

For example, 12 hexagons to the north of the central one, we have a yellow hexagon (quality: 23.5 cents), because 12 perfect fifths gives almost 7 octaves. But 12 hexagons north of that is only reddish (quality: 46.9 cents) because 24 fifths isn’t so close to 14 octaves.

For the same reason that log(2), log(3) and log(5) are linearly independent over the rationals, the diagram is never exactly periodic, but there are arbitrarily good approximations, so arbitrarily good “almost periods”.

An important one in music is that 3 just fifths plus 1 minor third, so, 3 steps north and 1 step northeast in my diagram gives (2 octaves plus) a small interval with frequency ratio of 81/80 (that’s 21.5 cents) that often gets smeared away when constructing musical scales.

Anyway, for better explanations about this, I refer to JCB’s blog post here:

• Just intonation (part 2).

Can you spot how his basic parallelogram appears as an approximate period in my diagram?”

The answer to Gro-Tsen’s puzzle is in the comments, but here are some hints.

Musicians call the change in pitch caused by going 12 hexagons to the north the Pythagorean comma:

They call the change in pitch cause by going 3 hexagons north and 1 hexagon northeast the syntonic comma:

You can also see a lot of bright hexagons in pairs, one just a bit east of the other! This is again a famous phenomenon: the change in pitch caused by going one hexagon northwest and then one hexagon northeast is called the lesser chromatic semitone in just intonation:

If you go one hexagon south and one southwest from a bright hexagon, you’ll also sometimes reach a bright hexagon. This pitch ratio is called the diatonic semitone

But this pattern is weaker, because this number is farther from 1.

With more work you should be able to find hexagons separated by the lesser diesis 128/125, the greater diesis 648/625, the diaschisma 2048/2025, and other musically important numbers close to 1, built from only the primes 2, 3, and 5.

Happy New Year!

For more on the mathematics of tuning systems, read these series:

• Pythagorean tuning.

• Just intonation.

• Quarter-comma meantone.

• Well-tempered scales.

• Equal temperament.

Welcome to the new year!

I've written previously (see here, item #3) about the extreme ultraviolet lithography tools used in modern computer chip fabrication.   These machines are incredible, the size of a railway car, and cost hundreds of millions of dollars each.  Veritasium has put out a new video about these, which I will try to embed here.  Characteristically, it's excellent, and I wanted to bring it to your attention.