Proof from the Chelyabinsk bolide fragment

Viktor Grokhovsky is a member of the Russian Academy of Science’s Committee on Meteorites. He is on the faculty of Ural Federal University, and specializes in metallurgy. He has been coordinating the recovery of fragments of the bolide that blazed and exploded over the skies of Chelyabinsk in southern Russia on the morning of February 15th. The largest known piece fell into icy Chebarkul Lake about forty miles southwest of the city.

Today we are delighted to convey findings from metallic crystallographic analysis of the interior of the fragment, and discuss their significance for the reality and prospects of scalable quantum computation.

Part reason we are able to do so is that the analysis was co-funded by a grant by the Royal Swedish Academy of Sciences to Lund University for interstellar biology, specifically spectral analysis of the many recently discovered exoplanets to determine whether they are capable of supporting life. The leader of this grant, PI Lars Olof, is first author of the 2009 paper, “Detectability of life and photosynthesis on exoplanets.” There has been much recent controversy about evidence of life from meteorites, some of which are known to originate from the second closest extra-terrestrial planet, Mars. Olof is a relation of Faadosly Polir, whom we have featured before.

The Chelyabinsk event appears to be the largest recorded meteor strike since the 1908 Tunguska explosion, which occurred much further east in Siberia. The latter was far stronger but killed only one person, while over 1,200 people were injured in Chelyabinsk and environs, some seriously. One shudders to wonder how bad a larger meteor would have been there. With that acknowledged, it is fortunate for science that the meteor’s core was sizable, and after being shielded from the thermal combustion of its covering, was instantly cooled by the lake.

## Misplaced Emphasis on Life

Whether life exists outside Earth is one of humanity’s oldest and most hopeful questions. We feel, however, that it is subsumed by a better question. Advances in life sciences have been propelled by information theory enough to reward the view that life is a computational process. Accordingly, this is our preferred question:

Is there evidence of computational processes outside of Earth?

Seth Lloyd of MIT, besides his many papers on quantum computing and information physics, wrote the book Programming the Universe to advocate a yes answer, but until now we have not had the kind of evidence that can be held in one’s hand. Lloyd also wrote an article titled “A bit of quantum hanky-panky” reviewing studies linking biological processes to quantum random walks. He and others were also referenced in a feature in the journal Nature titled “Physics of Life: the dawn of quantum biology.”

The New Year brought more onto our radar than the chess cheating case in Zadar, Croatia. A meteorite said to have fallen December 29th in Polonnaruwa, Sri Lanka, was recovered and analyzed by a team led by physicist Chandra Wickramasinghe, a long-term proponent of extraterrestrial life. Claims quickly followed of fossilized life forms called diatoms being found in the preserved core of the rock, similar to but larger than the fossilized bacteria alleged in the meteorite Allan Hills 84001 which was found in 1984. These claims have since been rebutted, amid further controversy over (lack of) peer review. For us, however, there seemed to be a simple syllogism:

If there is evidence of quantum computing in single-cell life, and evidence of single-cell life in space rocks, then there ought at least to be evidence of quantum computing in space rocks.

And the last kind of evidence ought to be easier to come by, since the messy and humanly freighted subject of life can be snipped neatly from the equation. Hence when the Chelyabinsk meteor happened, we followed the recovery news and tried opening some channels of inquiry.

## Quantum or Classical Hanky Panky?

Our syllogism also works without the word “quantum.” Indeed DNA computing, which Dick has long been associated with, is classical in conception, and researchers such as Ehud Shapiro and his co-workers at the Weizmann Institute have drawn numerous connections to Turing machine-type computations. It has even become possible to store an MP3 audioclip of Martin Luther King’s “I Have a Dream” speech into DNA strands. This led to the further thought:

If evidence of computation is found in interstellar matter, then whether that computation is quantum or classical could indicate an answer to whether quantum or classical is the supreme computing paradigm of the universe.

We have invested much effort in the latter question, in our year-long debate between Aram Harrow and Gil Kalai. Indeed, our own intended pair of posts reviewing this debate and giving our take have been delayed by the above events and others, while Gil has recently posted his own colorful threepart review of the arguments and contributions by others, including updates.

Consultations with nanocrystallographers on our faculties helped identify the pivotal class of computations as ${\mathsf{AC^1}}$, vis-à-vis quantum-${\mathsf{AC^1}}$. Here ${\mathsf{AC^1}}$ is not defined passively as a class of languages decided within certain asymptotic bounds that may have arbitrarily large constants, but actively by an algebra of computational primitives one can compose and iterate to concretely small extents.

Why ${\mathsf{AC^1}}$? It is the smallest bound that allows logarithmic iteration of unbounded fan-in gates. To aid the crystallographers, my student Robert Surówka prepared a very large diagram of this kind of ${\mathsf{AC^1}}$ iteration. Quantum ${\mathsf{AC^1}}$, however, would imply a different pattern—and of course, quantum ${\mathsf{AC^1}}$ (indeed quantum logspace) includes Peter Shor’s famous factoring algorithm. By March 15th we were able to offer precise templates for experimental comparisons.

 source for right-side photo

## Connections and Results

There remained the question of how to convey the implementation. We considered going through Lloyd via Aram at MIT, but wished not to incur appearance of partiality. Ditto Gil, even though Israel would be a longer first hop. We were intending to approach the people at Lund, but my old chess connections came through first. From tournaments years ago I have a friend in Minsk, who has a friend in Pinsk, whose friend in Omsk has friends in Tomsk with friends in Chelyabinsk. Their friends in Alexandrovsk knew labs in Petropavlovsk, with friends somehow to analyze now the rock in Dnepropetrovsk.

And when the work was done, ha-ha began the fun: from Dnepropetrovsk to Petropavlovsk, by way of Iliysk and Novorossiysk, to Alexandrovsk and Chelyabinsk, through Tomsk and Omsk to Pinsk and Minsk to me the news did run. Yes, to me the news did run—but once I translated it from Russian I was able to convey it to Dick as well. It boiled down to two words:

Quantum Wins.

Taking care of our own first, we must congratulate Aram for emerging as the clear winner of the debate, and thank Gil for his incredible efforts holding up the other side. We will of course continue with this line of inquiry, as unfolding the ramifications of this verdict of Nature will occupy research for decades at least. The nanocrystalline core harnesses entanglement in the manner of Oxford’s diamonds, as described by geometric quantum computation.

Even more fundamentally, we can say: Computation Wins. Most in particular, the discovery is a major step in the plausibility of building a Dyson sphere. The asteroid belt can provide the extreme computational resources needed for operation on this scale, with space automatically providing the cooling mechanisms we strain to achieve on Earth.

Unfortunately we are not able to exhibit the blueprints of quantum-${\mathsf{AC^1}}$ by which the structures inside the meteorite were recognized. They were furnished not via diagrams—of course not because that would subsume Shor’s algorithm—but rather via the polynomial method we outlined last July, together with partial versions of matrix computations still in process. On the Russian side, nano-images of the meteorite core have been classified, again for the obvious factoring-related reason. However, some findings will likely be presented at a workshop on “Algorithms and Complexity,” June 29–July 1 (reg. by April 10, led by Konstantyn Makarychev, Alexander Shen, Mario Szegedy, and Ryan Williams), in Yekaterinburg, Russia, which is 120 miles north of Chelyabinsk.

## Open Problems

What other evidence of extraterrestrial computation is out there? Are they out there?

While on the subject of “fools”, I have made updates noting possible overreach statements in the posts “Logic in Action” and “Benford’s Law and Baseball.”

15 Comments leave one →
1. April 1, 2013 9:38 am

What, no mention of Poisson this April?

April 1, 2013 2:02 pm

Good pun Jon – even if it works only in French…!

2. April 1, 2013 10:41 am

it all sounds quite plausible to me especially on a day like today. it seems possibly closely related to quantum phenomena in photosynthesis which has now been proven. an investigation of the possibility of quantum computing precursors in plants and their apparent ability to overcome quantum noise limits should be immediately commenced. I nominate Zeilberger & you as the lead researchers. from Zeilbergers ref, think that somehow automated theorem proving is applicable & should be cited also.

3. April 1, 2013 11:24 am

Leibniz was right all along … the Universe is a Hologrammautomaton …

4. April 2, 2013 7:42 am

Why the Leprechaun King argues that Gil Kalai is right
An open letter from the Leprechaun King to a candid world

Scott Aaronson opines [in regard to Senator Tom Coburn’s recent criticism of the NSF]: “For me, the real point has always been to understand the ultimate limits on what’s knowable and computable in the physical universe …”

For institutions like NSF — and the STEM community whose research effort the NSF helps to support — one natural question is the degree of consonance that pure-science/pure-math objectives — which many academic researchers embrace — shares with the NSF’s mandate from Congress:

The NSF Mission  To promote the progress of science; to advance the national health, prosperity, and welfare; [and] to secure the national defense …

Definition  We call Leprechaun utopia any world that realizes the explicit elements of an utopian vision, yet does not not realize other elements that commonly are regarded as implicit concomitants. The etymology is that wish-granting leprechauns notoriously are tricksters in regard to realizing utopian wishes!

Inspired by the Five Worlds that are set forth in Russell Impagliazzo’s (justly!) celebrated personal view of average-case complexity, we can envision two possible leprechaun utopias of (say) 2050:

• Synoptica  P ≠ NP is proved by 2050 (and the Clay Millenium Prize is awarded for its proof) and moreover QIT dynamics is demonstrated to be correct (specifically, arbitrary unitary evolution on Hilbert state-manifolds of exponentially-scalable dimension is experimentally demonstrated). On the other hand, the scaling coefficients associated to QIT physics are found to be sufficiently adverse that quantum computers are not used to solve practical problems. And at the national level (that is the US/NSF’s main concern) the secular decline in per-capita physical science graduate enrollment that began circa 1980 continues through 2050 and beyond, accompanied by erosion of US health, prosperity, welfare, and security.

• Pragmatica  P ≠ NP is proved to be undecidable by 2050 (and so the Clay Millenium Prize is withdrawn) and moreover QIT dynamics is shown to be unachievable (specifically, arbitrary unitary evolution on Hilbert state-manifolds of exponentially-scalable dimension is demonstrated to be incompatible with the locally relativistic gauge field theories that Nature provides). On the other hand, the scaling coefficients associated to dynamical simulation of thermodynamical systems are demonstrated to be sufficiently favorable that classical computers suffice to simulate most physical systems of practical economic consequence. At the national level (that is the US/NSF’s main concern) the associated enterprise-driven secular increases in physical science enrollment result by 2050 in sustained generation-upon-generation increases in US health, prosperity, welfare, and security.

Remarks  By construction, Synoptica is the QIT community’s leprechaun utopia, while Pragmatica is the NSF’s leprechaun utopia.

Conclusion  For young STEM researchers — whose professional aspirations require that family-supporting jobs be created in large numbers at a rapid pace — the world of Synoptica is a dismal dystopia, whereas Pragmatica is a mathematically, physically, and economically credible approximation to an utopia.

Question  Is the QIT community fully appreciative that both the NSF/Congress and young STEM researchers would cheerfully and rationally choose to live in the world of Pragmatica in preference to the world of Synoptica?

• John Sidles permalink
April 2, 2013 1:03 pm

Please let me say that the Leprechaun King’s conception of the world Pragmatica — in particular, the conception of Pragmatica as a world that efficiently simulates thermodynamical systems (i.e., systems governed by the 0th, 1st, 2nd,  and 3rd, Laws) — draws substantially from a recent preprint by Brandao and Horodecki, titled “Exponential decay of correlations implies area law” (arXiv:1206.2947).

In essence, Pragmatica is a world in which by 2050 (or sooner) Brandao and Horodecki’s concluding list of QIT Open Problems are solved. So perhaps the Leprechaun King’s synoptical and pragmatical utopias are not associated to magical and/or oracular capabilities, but instead arise naturally, from muggle-style consideration of the QIT literature!

• April 3, 2013 12:46 pm

In regard to $\text{P}\overset{?}{=}\text{NP}$, Leprechaun King’s conception of the world Pragmatica — in particular, the conception of Pragmatica (2050) as a world in which the Clay Institute’s statement of the $\text{P}\overset{?}{=}\text{NP}$ problem is revised from its present form — draws substantially from the ideas of Juris Hartmanis and Gregory Chaitin in postulating a world in which theorems along the following lines are proved:

Definition A language in $\text{P}$ is called constructible iff it is accepted by an efficient universal Turing machine (TM) whose specification-tape has a length $\text{L}$ that is a time-constructible function of that TM’s runtime exponent, and moreover WLOG this function is entirely determined by the axioms of the proof-system and hence exists as a universal function (in Chaitin’s complexity-theoretic sense).

Theorem  Neither ZFC, nor any finite extension of ZFC, can decide whether a specified listing of constructable languages is strongly ordered by runtime exponent.

In essence, Pragmatica (2050) is a world whose appreciation of the subtleties of the complexity class $\text{P}$ has grown sufficiently that the 20th century Clay Millennium Prize statement of the $\text{P}\overset{?}{=}\text{NP}$ problem requires substantial revision.

Summary  With regard to 21st century conceptions of complexity theory (CT), similarly as with regard to 21st century conceptions of quantum information theory (QIT), the Leprechaun King’s synoptical and pragmatical utopias are not necessarily associated to magical and/or oracular capabilities, but plausibly arise naturally from muggle-style consideration of the 20th century literature.

• Javaid Aslam permalink
April 5, 2013 1:15 pm

John,
This was the perhaps most incomprehensible letter/comment I ever came across on this blog.

• April 7, 2013 10:16 am

Javaid, the TCS StackExchange community wiki “Does P contain languages whose existence is independent of PA or ZFC?” provides further discussion (and references) relating to these tough questions.

The wiki concludes with Lance Fortnow’s remark:

“None of us truly understands the P versus NP problem, we have only begun to peel the layers around this increasingly complex question.”

Lance’s remark is (as it seems to me) a safe assertion. Hopefully by the end of the 21st century, these issues will seem simple and be easy to explain … but that time is not yet.

For young CT/QIT researchers, this is a happy situation!

• April 7, 2013 3:14 pm

I have simple question, if anyone know relevant reference, please answer. Do solution set of NP complete problems form the group? or it is different structure. The origin of the question is in the definition of the group in terms of generators (here variables) and their relations (here x_i^2=1 and the equation encoding the problem, e.g. 3-SAT clauses). Thanks.

• April 3, 2013 4:10 pm
5. April 5, 2013 2:07 pm

test

6. April 6, 2013 2:57 pm

Amazing!! Quite ironically my grandmother Polla was born in Dnepropetrovsk