The Gift of Nonconstructivity

Can we quantify “nonconstructive advantage”?

Japan Times source

Péter Frankl has been in the news again this year. The news is substantial partial progress on his famous conjecture that for any finite family of nonempty sets that is closed under union, some element must belong to at least half of the sets. The progress shows that some must belong to at least of the sets, but does not tell you how to find .

Today, amid twelve days of gift-giving, we wonder why nonconstructive proofs are often easier than constructive ones—and by how much?

Fusion Breakthrough or Increment?

And could a barrier be lurking?

Her DoE page

Jennifer Granholm is the U.S. Secretary of Energy in President Joe Biden’s cabinet.

Last week, she said at a press conference:

A Mutation Carol 2

Ghosts of creations past and citations not present

Domenico Amalfitano, Ana Paiva, Alexis Inquel, Luis Pinto, Anna Rita Fasolino, and René Just are the authors of an article in this month’s Communications of the ACM. Their article is on the program testing method called mutation.

Today we discuss how far back citations should go.

Thanks

Thanks to you all. I must explain why I have not been active in the last six months. I have had several illnesses. I had a broken hip that needed surgery

I also had several COVID related illnesses, and some terrible GI issues. I am trying to get better. Thanks to my dear wife Kathryn Farley I have finally started to get better. I cannot ever thank her enough. Kenneth Regan and Rich DeMillo and many others have also helped me. Thanks to you all.

Quantum Circuits in the New York Times

Can quantum circuits have something to do with wormholes?

Wikipedia src

Maria Spiropulu, a physicist at the California Institute of Technology, is featured in an article in last week’s Tuesday Science section of the New York Times about teleporting qubits through what might be described as a wormhole. The article says that physicists such as she

like to compare the teleportation process to two cups of tea. Drop a cube of sugar into one teacup, and it promptly dissolves—then, after a tick of the quantum clock, the cube reappears intact in the other teacup.

Today (yesterday? tomorrow? years ago?—with a quantum clock, does it matter?) we ask what the paper referenced in the NYT story might really be about. This is after trying to work through a lot of hype and pushback.

The first trouble is that we cannot tick a real quantum clock quite yet. But Spiropulu and her group were able to simulate a quantum clock via using a quantum computer. The group comprises: first author Daniel Jafferis, then Alexander Zlokapa, Joseph Lykken, David Kolchmeyer, Samantha Davis, Nikolai Lauk, Hartmut Neven, and then Spiropulu. Their paper was just reported in Nature. The whole buzz makes us recall an exchange that never took place:

Albert Einstein: “Reality is merely an illusion, albeit a persistent one.”

Woody Allen: “[If] everything is an illusion and nothing exists, [then] I definitely overpaid for my carpet.”

The Quantum Experiment

Spiropulu’s group could not build a quantum experiment to directly test this kind of teleportation. At least it seemed like that would be impossible. But they cleverly used the Sycamore chip developed by Google in 2019. It uses a type of quantum computing called superconducting qubits, which send electric currents flowing through superconducting materials to store and process information. Google created the chip to study “quantum supremacy” as we covered three years ago. A wonderful article on Medium by Jonathan Hui runs helpful commentary around circuit diagrams of the processor from the Google team’s original paper. Hui says:

Regardless of other claims, Google’s processor is a significant milestone because it demonstrates a problem with some real value. Whether classical computers will take 100,000 years or 2.5 days for the pseudo-random generator, this kind of speed improvement is rarely or never demonstrated with a general-purpose quantum computer.

What we find significant is that Google’s processor is not limited to the pseudo-randomness application to demonstrate what we’ll call advantage. It has plug-and-play capabilities. Google may not have created Sycamore to study quantum teleportation. But it was possible to exploit its quantum ability to demonstrate teleportation. See their Nature paper for how.

Wormholes and Their Duals

The NYT story and an article by Natalie Wolchover in Quanta have some pithy quotes from people well-known to us:

• John Preskill, about ‘the evolving system of qubits in the Sycamore chip’: “[It] has this really cool alternative description. You can think of the system in a very different language as being gravitational.”

• Leonard Susskind: “The really interesting thing here is the possibility of analyzing purely quantum phenomena using general relativity, and who knows where that’s going to go.”

• Scott Aaronson: “If this experiment has brought a wormhole into actual physical existence, then a strong case could be made that you, too, bring a wormhole into actual physical existence every time you sketch one with pen and paper.” (See also Scott’s post here.)

These quotes allude to a duality, both ends of which connect Einstein and the Israeli-American physicist Nathan Rosen. Their 1935 paper, abbreviated ER, showed how a wormhole could arise in the specific form of an Einstein-Rosen bridge according to the equations of general relativity. They were joined that same year by Boris Podolsky in a paper that described quantum entanglement via the so-called EPR paradox. In 2013, Juan Maldacena wrote a paper with Susskind claiming a correspondence between them. This was expanded by Alexei Kitaev following work by Subir Sachdev and Jinwu Ye. All this draws on Maldacena’s work in the 1990s showing a duality between two cosmic models that have different dimensionalities, in the manner of a hologram. Maldacena and Susskind’s claim is pithily expressed as the title of section 3 of their paper:

Equality is enticing because this could effect the communion of relativity and quantum mechanics. This matter found its way into another New York Times story in October, where Susskind is quoted as saying in 2017:

“It may be too strong to say that gravity and quantum mechanics are exactly the same thing. But those of us who are paying attention may already sense that the two are inseparable, and that neither makes sense without the other.”

That story centered the duality on black holes, but Will Kinney, a colleague of Ken’s at Buffalo, observed that Maldacena and Susskind “conjectured that ANY entangled particle pair is dual to a wormhole solution.” Kinney also quoted Quanta editor Thomas Lin as saying,

“In the context of the article, it should be clear that a quantum system was created that was dual to a holographic wormhole.”

What fascinates us is that the quantum system had the form of direct simulation of quantum circuitry. In fact, Spiropulu’s team used only 9 of 72 available qubits on a Sycamore chip. The NYT article has a big graphic on the role of ordinary quantum circuits, from which we snip this detail:

This leads us to some speculations of our own.

Dualling Quantum Circuits?

Setting aside the question of wormholes or their duals, Spiropulu’s team did observe behavior that could be forecasted only after running an exhaustive classical simulation tied to the Sachdev-Ye-Kitaev model on the 9-qubit scale. This is described in a video by Quanta about their work, starting about 11:00. As Wolchover summarizes:

“[A]n ineffable quantum phenomenon—information teleporting between particles—has a tangible interpretation as a particle receiving a kick of energy and moving at a calculable speed from A to B.”

Maybe there is no actual burst of energy, as Mateus Araújo underscored while criticizing this segment of the video. But is the physical process in the circuit nevertheless subject to instability and noise? We reiterate a question that we posed a year ago after describing how small quantum circuits can embody quantum walks that are chaotic:

When a quantum circuit simulates an unstable physical process with full quantum advantage, what is the boundary between the simulation and the behavior being simulated? Is potential bridging of this boundary a stumbling block to maintaining coherent operation while scaling up quantum hardware?

In the context of the November 2021 post, we noted that when one simulates chaotic physical systems in, say, FORTRAN or C++ or Python on a classical computer, one would not say the physical classical chips are themselves behaving chaotically. In the quantum case, we note Peter Shor’s response to Wolchover’s referencing a 2017 lecture video on simulating physical systems. Shor retorts that a quantum computer simulating fusion doesn’t shine like the sun, nor can quantum circuits both using and simulating superconductivity power the nation’s electric grid. But our instances of chaotic quantum walks, and now possibly wormhole duality, strike us as more closely attached to the relation of physical behavior to computation.

The new question we have is even more speculative, but may work as a counterpoint to the current discussion of the new paper. If ER=EPR is correct, then ordinary entanglements are dual to wormholes. That maximal entanglements are binary-only may correspond to the simplest wormholes going only from a point A to a point B. Entanglements are bread-and-butter to quantum circuits, so if this duality has any force, it should extend to the circuits themselves:

If the team could possibly create a theoretical dual to a wormhole in a quantum circuit, then does the correspondence in the other direction yield duals to quantum circuits that could house wormholes? Might the notion of such a circuit dual, expressed within general relativity, furnish an organizing principle about how the universe processes information to build structures on cosmic scales?

A 2018 paper by Tadashi Takayanagi titled “Holographic Spacetimes as Quantum Circuits of Path-Integrations” seems to open at least one direction of a cosmos-to-quantum-circuits correspondence. A very recent paper by Scott with Jason Pollack, on how Maldacena’s correspondence treats quantum states, draws on earlier work by Takayanagi, but seems to stop short of such duality.

Open Problems

What do you think of the questions raised by the new paper? As we highlighted at the start, it is couched in down-to-earth terms of quantum circuits. Setting aside the rampant controversy on the physics side—there are more links collected by Peter Woit besides those we’ve used—what does this say about realizing the quantum circuit model?

[some slight word changes]

The Gerrymanders Have It

The real winner of the 2022 midterms in the House

David Wasserman is an elections analyst for the Cook Political Report. He is known for forecasting the results of elections after people have voted. His words “I’ve seen enough” to declare an outcome are taken as seriously as any network election call.

This week, with nine US House races uncalled and control of the chamber still unknown, he is working overtime.

Cheating at Chess—Not Again

Play the opening like a book, the middle game like a magician, and the end game like a machine — Rudolf Spielmann

Kenneth Regan is my dear friend and co-writer of this blog. He obtained his doctorate—technically D.Phil not PhD—in 1986 for a thesis titled On the Separation of Complexity Classes from the University of Oxford under Dominic Welsh. He has, however, been enmeshed this month in a story quite separate from complexity classes.

It was Ken’s birthday just last week and we wish him many more.

Legal Complexity

Formal logical methods may be needed to represent the Donald Trump documents case

her page

Monica Palmirani is a Professor of Computer Science and Law at the University of Bologna in Italy. She is one of the Program Chairs of the 2021-2022 AICOL conference: Artificial Intelligence Approaches to the Complexity of Legal Systems.

Today Ken and I discuss how logical methods may be used to model complex legal cases.

A Theoretical Question About UAPs

What should be the Bayesian prior for a new NASA study?

Crop from ‘Interstellar’ discussion

David Spergel is a physics professor emeritus of Princeton University who now heads the James Simons Foundation. He shared the 2010 Shaw Prize and 2018 Breakthrough Prize with Charles Bennett of Johns Hopkins and others of the team on the Wilkinson Microwave Anisotropy Probe (WMAP), whose mapping of fluctuations in the cosmic microwave background has channeled numerous physical theories. He has recently been appointed to lead a new NASA study on unidentified aerial phenomena (UAPs, previously called UFOs).

Today we wish him auguri on the project and pose a theoretical question on what its baseline should be.

Juris Hartmanis 1928–2022

A sure foundation for Computational Complexity

source—wonderful 2015 CACM interview

Juris Hartmanis passed away this morning. He was a professor in Cornell’s computer science department since 1965. He won the 1993 Turing Award with Richard Stearns for their 1963–1965 paper “On the Computational Complexity of Algorithms.”

Today, Dick and I express our condolences and also appreciation for a long life and career shaping our field of computational complexity theory.