Halting Is Poly-Time Quantum Provable

How does this intersect David Deutsch’s thoughts in 1985?

Composite crop from homepages

Zhengfeng Ji, Anand Natarajan, Thomas Vidick, John Wright, and Henry Yuen (JNVWY) have just posted a paper titled . The title means that multiple provers sharing quantum entanglement, given any Turing machine and string accepted by , can convince a polynomial-time bounded verifier with high probability that . The time is polynomial in regardless of how long takes to halt on .

Today we applaud this work and try to convey some short way of apprehending it.

Yoking a classic undecidable problem to a polynomial-time task is not the only surprise. The proof refutes a conjecture in classical functional analysis that had apparently been widely believed. Thus this story continues the theme of surprises and possibly working the wrong way on conjectures, as we also just mentioned in our previous post. The new work subsumes a major paper last year showing that contains nondeterministic double exponential time (), which proves it different from its classical counterpart , which László Babai, Lance Fortnow, and Carsten Lund proved equal to .

The developments have been covered by Scott Aaronson here, Lance here, Boaz Barak here, and in a personal way by Vidick here. The new paper weights in at 165 pages. We will give our own snap-summary and try to add a little from the side.

A Halting Attempt to Explain

The refuted conjecture was made by the Fields Medalist Alain Connes in a context having no overt involvement of quantum mechanics. In these 2013 eight–lecture course notes on the conjecture, the word “quantum” appears only once, to say on page 2 of lecture 1:

Other very recent discoveries include the fact that Connes’ embedding conjecture is related to an important problem in Quantum Information Theory, the so-called Tsirelson’s problem…

The problem of Boris Tsirelson ultimately harks back to the theorem of John Bell about correlations that are physically realizable using quantum entanglement but not by any classical physical system. In the CHSH game form of Bell’s theorem, our old friends Alice and Bob can win the game over 85% of the time using quantum, only 75% otherwise. They can get this with just one pair of entangled qubits per trial. Tsirelson proved that the 85% (to wit, ) is optimal. In extensions of these games to larger-size cases, the question becomes: what are the gaps between quantum and classical?

Whether there is a gap of more than a fixed then feeds into interactive protocols. We can have parties trying to prove these gaps using their own entanglement. Where it gets tricky is when you allow Alice and Bob to use larger and larger quantum states and ask, can they achieve the gap with some large enough state? The limiting behavior of the gaps is complex. What JNVWY proved is that this becomes like a halting problem. Not just a halting problem, the Halting Problem. Yet two quantum provers, working for a given gap that is achievable, can prove this to a polynomial-time classical verifier. This is the magic of the theorem.

The reduction from halting to the problem about limits and gaps comes before introducing two-prover systems, as is reflected by JNVWY and also in the wonderful introduction of a 2017 paper by William Slofstra which they reference. In advance of saying more about it, we’ll remark that the new work may provide a new dictionary for translating between (i) issues of finite/infinite precision and other continuous matters, and (ii) possible evolutions of a system of finite size in discrete steps of time and size, where both are unbounded but (in positive cases) finite.

A Flashback?

The results strikes Dick and me as shedding new light on a principle stated by David Deutsch in a 1985 paper:

Every finitely realisable physical system can be perfectly simulated by a universal model computing machine operating by finite means.

I was a student at Oxford alongside Deutsch in 1984–1985, and I remember more going on than the searchable record seems to reflect. Deutsch believed that his model of a quantum computer could solve the Halting problem in finite time. He gave at least one talk at the Oxford Mathematical Institute on that claim. As far as I know the claim stayed local to Oxford and generated intense discussion led by Robin Gandy, Roger Penrose, and (if I recall) Angus Macintyre and at least one other person who was versed in random physical processes.

My recollection is that the nub of the technical argument turned on a property of infinite random sequences that, when hashed out, made some associated predicates decidable, so that Deutsch’s functions were classically total computable after all. Thus the hypercomputation claim was withdrawn.

Now, however, I wonder whether the two-prover system constitutes the kind of “machine” that Deutsch was intuitively thinking of. As I recall, his claim was not deemed wrong from first principles but from how theorems about random sequences interacted with machine model definitions. The theory of interactive provers as computational systems was then in its infancy. Could Deutsch have had some inkling of it?

Open Problems

Again we congratulate JNVWY on this achievement of a long-term research goal. Looking at the past, does it relate to the discussion of hypercomputation stemming from the 1980s? We mean a stronger connection than treated here or in this 2018 paper. Is it much different from ones where “the mystery … vanishes when the level of precision is explicitly taken into account” (quoting this). Looking ahead, are there any connection to the physical issues of infinity in finite time that we recently discussed here?

Updates 1/17: Gil Kalai has a post with background on further conjectures impacted by (the failure of) Connes’s conjecture and on quantum prover systems, plus a plethora of links.

A new article in Nature includes the following quotations:

• Alain Connes, after saying he was not (yet) able to digest all the material involved in the proof: “It is amazing that the [embedding] problem went so deep and I never foresaw that!”

• Tony Cubitt, University College of London: “What’s amazing is that quantum complexity theory has been the key to the proof.”

• Joseph Fitzsimons, Horizon Quantum Computing: “I thought it would turn out to be one of those complexity-theory questions that might take 100 years to answer.”

The article and comments on Scott’s blog include interpretations that seem to oppose rather than support Deutsch’s principle on the finiteness of nature. The tandem of two unlimited provers may not qualify as a “finite machine.”

There are comments below querying whether the theorem is in first-order arithmetic or how strong a choice axiom it may need.

[added to first paragraph in second section, added updates]

Our Thoughts on P=NP

The Clay prize anniversary is soon.

SME keynote lecture source

Evelyn Lamb is a mathematician who is also a journalist. She has a blog called Roots of Unity on the Scientific American blog network. Also impressive is that she designed the AMS Page-a-Day Calendar on behalf of the American Mathematical Society. It is available from the AMS with member discounts and is filled with wonderful tidbits on math.

The other day she interviewed Ken and me on P=NP.

No Password Encryption

Who can remember passwords anyway?

Real Bernie Sanders reaction source

Larry David is an American comedian. He was the lead writer and producer of the Seinfeld TV series. During the previous and current election cycles he has played Presidential candidate Bernie Sanders in skits on Saturday Night Live. His “Bernie” rails about issues with passwords.

Today I want to talk about reducing our dependence on passwords.

Servant: The TV Show

Using logic to try and understand the show Servant

[ M. Night ]

M. Night Shyamalan is the creator of many wonderful horror movies, including The Village and The Sixth Sense. His films often have a twist ending.

Today I thought I would try to apply math and logic to his latest creation, the TV show called Servant.

Resolutions For 2020

Some fun about resolutions.

source

Ben Orlin is a funny mathematician. His book title Change Is the Only Constant was selected by the blog Math-Frolic as the best mathematics book of 2019.

Today Ken and I want to try to get you to at least smile, if not laugh.

Orlin is a funny chap—okay I just got back from London—so forgive me for using “chap”. Check Orlin’s site out for proof that he is funny. Here are some of his examples of math types rewriting famous opening lines from books. We will make this into a kind of quiz. You must guess the book title from the modified quote:

1. The times had high variance.

2. Up to isomorphism there is one happy family.

3. It was a bright cold day, and the clocks were not mod 12.

4. All this happened, but not with equality.

5. was spiteful, full of a baby’s venom.

6. It was zero at the leading ordinal of viewing.

The third is the first hard one—I did not get it. The last one (of three from Ken not Ben) is probably unfair. All six of them, however, are on the “First Lines Literature Coffee Mug” which Ken received a year ago as a Christmas present from his sister. I did not know this when I chose the first three.

Orlin’s Resolutions

Many of us make resolutions for the new year. Here are some examples from Orlin:

Be better at explaining what I do to family and friends. I, Dick, have trouble with this one.

Not to prove by contradiction what can be proved directly. Assume that and

Stop using the word “obviously.” Here at GLL we try to avoid this, at least when it is not obvious. We posted about phrases to avoid a year ago.

Our Resolutions

Here are some of ours:

Stop doubting quantum computer claims. Unless, adds Ken, you have a possible concrete way of challenging them…

Start trying to apply AI methods to complexity theory. Could there be a new learning approach to 3-SAT? Note that PAC learning kind-of came from there. See for instance the end of this.

Stop trying to understand proofs that Peano arithmetic is inconsistent. I still do not understand what logic they use to prove that Peano is inconsistent. What if that logic is inconsistent?

Start up some fundamental research ideas and attempts on hard problems again.

And try to make GLL better, including making it appeal to a wider community.

Open Problems

The answers are:

1. A Tale of Two Cities by Charles Dickens: “It was the best of times, it was the worst of times.”

2. Anna Karenina by Leo Tolstoy: “Happy families are alike; every unhappy family is unlike in its own way.”

3. 1984 by George Orwell: “It was a bright cold day, and the clocks were striking thirteen.”

4. Slaughterhouse-Five by Kurt Vonnegut: “All this happened, more or less.”

5. Beloved by Toni Morrison, who died this year: “124 was spiteful, full of a baby’s venom.” This explanation of the line continues: “We know all about numbers being spiteful. We took high school algebra. We’ve experienced the pain. But in this instance, the quote isn’t actually referring to a number. There’s not some mysterious mathematical entity that’s come to wreak havoc on the characters in our story. Here, ‘124’ refers to…”

6. Lolita by Vladimir Nabokov: “It was love at first sight…” But wait—this is not the first line of the novel. The first line is maybe not suitable for a coffee mug or family-friendly blog. Instead it is the first line of chapter 29 of part II. We did say it was unfair. Update: Oops—as noted here, it is the first line of Catch-22 by Joseph Heller. Maybe Ken’s Google engine shares his tendency toward chess-playing authors…

Have a happy new year, and make some fun resolutions. Please let us know some of them, or ideas for ours.

[added Update fixing last first-line answer.]

A Math Gift For All

Happy holidays to all.

Kathryn Farley is my dear wife. We just celebrated Christmas together and then went off to London for a holiday.

Today I thought I would share a gift with you.

Predicting When P=NP is Resolved

Has it outlasted the ability to estimate when?

Composite of src1, src2

Ryohei Hisano and Didier Sornette wrote in 2012 a paper titled, “On the distribution of time-to-proof of mathematical conjectures.”

Today Ken and I discuss predicting the end to mathematical conjectures. This is apart from considering odds on which way they will go, which we also talk about.