{\huge Interstellar Quantum Computation}
Proof from the Chelyabinsk bolide fragment \vspace{.2in}
\includegraphics[width=2in]{GrokhovskyHands.png}
source
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 propsects 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.
\includegraphics[width=3.5in]{ChebarkulHole.jpg}
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 three-part review of the arguments and contributions by others, including updates.
Consultations with nanocrystallographers on our faculties helped identify the pivotal class of computations as $latex {\mathsf{AC^1}}&fg=000000$, vis-à-vis quantum-$latex {\mathsf{AC^1}}&fg=000000$. Here $latex {\mathsf{AC^1}}&fg=000000$ 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 $latex {\mathsf{AC^1}}&fg=000000$? 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 $latex {\mathsf{AC^1}}&fg=000000$ iteration. Quantum $latex {\mathsf{AC^1}}&fg=000000$, however, would imply a different pattern---and of course, quantum $latex {\mathsf{AC^1}}&fg=000000$ (indeed quantum logspace) includes Peter Shor's famous factoring algorithm. By March 15th we were able to offer precise templates for experimental comparisons.
\includegraphics[width=3.5in]{CircuitPlusMeteorite.png}
Photo source, right side.
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-$latex {\mathsf{AC^1}}&fg=000000$ 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?
