Quantum Unproving

Quantum Tarot source

Dr. Lofa Polir is a research associate at UCLQ. This is the new University College London Quantum Institute. We have previously noted her move to England after working at the LIGO lab in Shreveport, Louisiana.

Today we describe her recent disturbing discovery—or rather, “undiscovery.”

It began with an unsettling experience last Wednesday after an exciting all-day lab session that re-created Alain Aspect’s Nobel Prize-winning experiment with heavy particles rather than photons. She is teaching an evening course on classical versus quantum complexity. It was her lecture on , and she intended to finish by showing the proof of Len Adleman’s famous theorem that every problem in has polynomial-sized circuits. But she couldn’t get the proof to work. Long day, working from sketch notes—it happens to all of us. She promised to post a fixed proof on the course forum.

Back in her apartment, however, she really could not get the proof to work. It would work if she could suppose that every language in polynomial space has nondeterministic polynomial-sized circuits, but is an unrealistically strong assumption. Thursday with a long sleep and a clear mind, she couldn’t get it to work either. So she reached out to us for help. After a weekend’s delving, we found a new paper and a book that combine for an astounding answer.

The Paper

We have been intending to post about the ITCS conference—Innovations in Theoretical Computer Science for 2024—which was held earlier this year. One of the accepted papers that really caught our eye was this by Scott Aaronson (UT Austin/OpenAI), Harry Buhrman (QuSoft/CWI/University of Amsterdam) and William Kretschmer (Simons Institute/UC Berkeley). It is titled:

“A Qubit, a Coin, and an Advice String Walk Into a Relational Problem”

In order to treat this subject with the appropriate degree of gravity for our readers, we need to begin with a technical exposition of the title. The key concept is that of a bar:

Bar Jokes source

The bar acts as a functor mapping into the fractal set of jokes. Elements of this set are funny, whereas unfunny jokes fall outside the set and hence are not jokes in reality. Here are some instances of this mapping:

• A neutron walks into a bar and orders a drink. When the neutron gets his drink, he asks, “Bartender, how much do I owe you?” The bartender replies, “For you, neutron, no charge.”

• A horse walks into a bar. The shocked bartender points a finger his way in alarm and yells, “Hey!” The horse says, “You read my mind, buddy.”

• A rabbi, a priest, and a Lutheran minister walk into a bar. The bartender looks up and says, “Is this some kind of joke?”

• A grasshopper hops into a bar. The bartender says, “You’re quite a celebrity around here. We’ve even got a drink named after you.” The grasshopper says, “You’ve got a drink named Steve?”

The usual cardinality of people entering a bar is 3. Here are the three authors of the paper:

Basic Idea

Let’s look at their paper a bit more. The central problem with complexity theory is that we cannot actually solve almost any open problem that concerns the power of nontrivial complexity classes. The point of their paper is that changing from standard classes can make things provable today. This is quite cool.

Here is a basic and under appreciated fact: there are computational problems—not distributed or cryptographic tasks, but just pure computational problems—that provably admit only randomized solutions. One simple example is: “output an -bit Kolmogorov-random string.” Another example is: “given as input a halting Turing machine , output any string other than what outputs when run on its own description.”

Relational problems (those with many possible valid outputs) are different from decision problems, but it is easy to forget just how different. This paper initiates the study of , the class of relational problems solvable in quantum polynomial-time with the help of polynomial-sized quantum advice, along with its analogues for deterministic and randomized computation.

Their second main result, however, does not involve quantum at all. Here again, the initial in their notation refers to relational problems, which are the same was what Alan Selman and his co-workers called multi-valued functions.

Our second result is that —that is, Adleman’s Theorem fails for relational problems—unless . Our proof uses and time-bounded Kolmogorov complexity.

But Lofa Polir was not lecturing on relational problems, just good old language-based . How did this paper’s theorems get mixed into her world? Here is where the climate modeler and quantum researcher Tim Palmer of Oxford comes in.

The Book and the Answer

The final third of Palmer’s book The Primacy of Doubt includes a popular exposition of his Invariant Set Hypothesis. This says that instead of the unfettered multiverse of the quantum Many Worlds Hypothesis, the possible states of the cosmos are limited to an invariant set of fractal dimension.

When coupled with superdeterminism, Palmer’s hypothesis has this ramification: What we think of as is in reality a class we can call and define as follows:

Definition 1 A language belongs to if there are polynomial-time decidable predicates and such that for all there is a unique such that , and:

To explain: We may think we are doing the “” analysis on random strings given . But the “” part of the random string is determined, because the other “random” possibilities for it fall outside Palmer’s fractal set. (Or it may be “few-limited” in the sense of .)

Moreover, there is really no “” part. We can still incorporate into the randomized analysis used in the standard proof of Adleman’s theorem. But now it works only if can be incorporated into the definition of the polynomial-sized circuits. For reasons similar to being unknown (and disbelieved on account of factoring), but higher up in the complexity-class food chain, we don’t know how to do this. And since is a projected case of Scott et al.’s , their theorem shows this can’t always be possible uniformly.

So what happened to Lofa is that her Aspect experiment knocked her world into a different one of Palmer’s states, with a different mapping. That may be one where Adleman’s theorem fails, or at least is difficult to prove. Luckily that didn’t happen to all of us—so far. It would be terrible if quantum fluctuations on the scale of the universe can unprove theorems in our textbooks.

Open Problems

As mathematical Platonists, we hold that true theorems in the abstract are true in all possible worlds. But we also regard practical proofs of important theorems as primarily social constructs. Is it possible that the way we frame our theorem statements is similarly contingent, such that in one of Palmer’s alternate configurations for the world, we would perceive their truth values changing between worlds? If no, we say: April Fool. But if yes…?