The Blog of Scott Aaronson If you take just one piece of information from this blog: Quantum computers would not solve hard search problems instantaneously by simply trying all the possible solutions at once.
This entry was posted
on Wednesday, November 5th, 2008 at 12:52 am and is filed under The Fate of Humanity.
You can follow any responses to this entry through the RSS 2.0 feed.
Both comments and pings are currently closed.
48 Responses to “The unfamiliar burden of victory”
Rahul: Personally I’m watching Franken vs. Coleman in Minnesota and gays vs. pitchfork-mob in California, the former of which is still up in the air (even with 96% of precincts reporting!) and the latter of which is not looking good. At issue is whether every silver lining has a cloud…
Great day for America and the world. Usually I hate listening to politicians talk (even those I agree with), but I listened to both end of game speeches. Two of the best political statements I have ever heard.
Although he “I approved” some cheep shot ads, I basically like McCain. He is from the “not crazy” branch of the Republican party. Palin appears to be somewhat like Geo. W.; personable, not too bright, jumping at the opportunity to be the front person for the nutcake branch of the RP.
TJIC: Well, it’s the first time in my life that the mood of the country has been this Democratic. Clinton won in ’92 with just 43% of the vote, and was hobbled by Congress in a way that seems harder to imagine now. More to the point, the last eight years feel like 800.
As long as this diagram of yours doesn’t represent a Ponzi scheme cooked up by derivative divers on Wall Street, then I’m looking forward to having four years of Obama and his team of advisers in the White House.;~)
Anon Says: What’s with the Iwo Jima shot? You know it was actually the second flag and a staged shot, right?
I am grateful to Scott for including that shot, which perhaps better than any other shot he selected, illustrates the complexity of human affairs and the human heart. And as the father of a Marine preparing for his fourth deployment, it had special meaning for me, as no photograph is more iconic for the Marines.
The Wikipedia page on the flag-raising is excellent. The 1950 John Wayne movie and Clint Eastwood’s two 2006 movies on Iwo Jima all are good (and no two describe the same story). First-person accounts are available and (as usual in human affairs) these accounts are more richly textured than the movies.
In my database of quotes is a little-known account of the Iwo Jima flag raising that is of personal interest to me as a medical researcher specializing in regenerative medicine (for me, quantum information science is a challenging mathematical tool for achieved even more challenging medical ends).
Here is the account of trauma surgeon George M. Boswell. Dr. Boswell served also as ship’s photography officer and developed the picture:
When [photographer Joe Rosenthal] returned to the ship with his shots of the flag raising on Mt. Suribachi, I had to go into the darkroom with him. As ships photographer he couldn’t get there without me!
As the wet print came up in the tray neither of us thought it was anything great. The controversy of staging or not staging the shot is ridiculous. He was an AP photographer and as always, wanted as many people in shots as possible in order to reach more hometown names back in the States.
He simply had to shoot and reshoot to get as many Marines as possible.
When it came up he said, “Well it’s not great but it’s the best I got so here it goes.”
I have often wished I had made him pull one more print for me.
Many a famous mathematical and scientific enterprise has had similarly humble beginnings, under similarly difficult and unexpected circumstances.
Georgia, Oregon, Minnesota, and Alaska(!!!) all seem to still not be officially over.
While I rather like Gordon Smith, and can understand why voters might be skeptical of putting Al Franken into national office, is the population of Alaska really stupid enough to re-elect a convicted felon?
In unrelated news, Michael Crichton, whose scifi-tinged books convinced thousands to pursue careers in the hard sciences, thousands more that DNA could clone dinosaurs and that quantum computers could transport you through time, and G.W. Bush that global warming was a massive conspiracy designed to give fruit-fly researchers in Paris more funding, has passed away.
Thanks Scott for the “reverse Kvell” of the previous post, and thanks Ronald (and others) for your good wishes. We Obama volunteers here in Florida are so happy that the state turned blue this time around. I am also very relieved to read that 78% of Jewish voters supported Obama , similar to the 2004 support for Kerry . This is clear rejection of the lies (Obama is a terrorist,) and smears (Obama is like Hitler) blanketing the Jewish community recently by the Republican Jewish Coalition.
Today the AP writes: “Barack Obama’s election as America’s first black president unleashed a renewed love for the United States after years of dwindling goodwill…”
This is good news indeed. One problem with the Republican party is that some of its members are too jingoistic and mistake that for patriotism. I hope the President-Elect will realize the gravity of his global peacemaker position and learn to govern from the middle. May he continue to keep us safe.
TI: Sorry about that! Sometimes totally innocuous comments get held up by the filter for whatever reason. If that happens, you can either (1) email me or (2) just sit tight; I usually check the moderation queue a couple times a day.
Ian: Obama went on record opposing bubblesort as the fastest way to sort a million 32-bit integers. I’m not aware of any other candidates taking stands on complexity issues (e.g. I’d love to know whether Palin believes the Unique Games Conjecture, and if so with what parameters), but maybe I just didn’t look hard enough.
I am very glad Obama will be in charge now. Although I live outside the US,I watched closely this election. Obama has totally won our trust and support and I hope he will dare to reform the entire system.
Scott,great story about Obama in GooglePlex! I think we have a new algorithm here which I publicly propose we name it “Obama Sort”. It is summarized in “anything but bubble sort”!
“Scott,great story about Obama in GooglePlex! I think we have a new algorithm here which I publicly propose we name it “Obama Sort”. It is summarized in “anything but bubble sort”!”
Ok, let’s not get carried away: (1) – While it was funny, it was ultimately a non-answer. (2) – Isn’t it true he knew about the question beforehand and that it had stumped McCain? Also, on that note, he was a lecturer, not a professor at U. Chicago. There’s a big difference.
I think it’s a good idea to keep in mind that Obama is first and foremost a politician. It’s going to be very important for him to put together a balanced non-partisan group of advisers. To his credit, it seems like he might actually be doing that.
Scott says – “I completely agree: he’s not the messiah, just a politician who doesn’t suck. It was Bush’s achievement to make the two seem indistinguishable.”
And I completely agree with you. I just have some philosophical differences with him – I’m not questioning his competency as a leader anymore (not since the end of the Democratic primaries).
I suppose my point was that, like any other president, he’s going to have to depend heavily on his advisers to deal with scientific/technological/environmental issues. So, similar to what happened in the Clinton administration, he needs to surround himself with smart people (I don’t doubt this will happen), and importantly, maintain some degree of ideologically balance while doing so. He doesn’t have to be balanced with his actions, I just want to make sure he’s hearing (informed) dissenting viewpoints on issues like alternative energy, nuclear energy, carbon credits, etc.
Not: “Global warming is liberal propaganda!”
But rather: “Let’s seriously consider and invest in breeder reactor technology, let’s reconsider the merits of this international agreement on carbon taxation, corn ethanol is a bad idea, and so forth.”
* Ok, let’s not get carried away. * I completely agree
Despite heavy criticism, I still believe ObamaSort is fast and can be faster(Yes it can) Wikipedia says that in a series with a min a, a max b and a median Ma, it runs in O(b+a)/Ma in a modest platform!!
Panos says – “Despite heavy criticism, I still believe ObamaSort is fast and can be faster(Yes it can)…”
Remember that it goes in both ways! Considering that the House is still working hard to make our nation’s problem N.P. complete, I just hope your algorithm (and the new administration) doesn’t collapse to a CarterSort.
there is no way I would be offended by insightful comments. If my English failed me, what I meant with my previous comment on CarterSort is that as a foreigner I didn’t know that Carter Admin sucked so much.
This is the 365th post on Scott’s blog. Barack Obama won the election with 365 electoral votes.
Scott, did you set this up?
From the very beginning. (And it wasn’t easy: I had to pad things out by writing a lot of entries that would seem embarrassing or stupid if you didn’t know they were in the service of a numerical coincidence.)
If they’re able to succeed then that what does that say about the capability of the average mammalian brain to make use of quantum effects for computational purposes (which i believe i’ve seen mentioned occasionally and which i don’t find very realistic)? Since simulating a QC is in BQP, Blue Gene must fail (by which i mean produce a simulation that doesn’t correspond to whatever observations they’ve made) if the mammalian brain commonly makes use of any quantum-computed results in conscious action. Or am i mistaken?
Job comments: “Since simulating a QC is in BQP, Blue Gene must fail.”
Yikes! Perhaps this is a good time to point out that comments like this benefit greatly from a careful description of context.
Quantum chemists are of course well-accustomed to thinking of biological mechanisms at the quantum level; physicists and biologists less so. It seems to our QSE Group that the quantum chemists mainly have the right of it, in the sense that any accurate ab initio simulation of atomic-level biological processes must be quantum mechanical.
Of course, it then follows that technologies for atomic-resolution observation of biological processes similarly require a quantum mechanical description; this is especially true if we require that the observation process be non-destructive (as in spin imaging, for example).
Our QSE Group’s working rule-of-thumb is that the minimal state-space dimensionality required for the quantum-level simulation and observation of atomic-scale biological systems is about 10^3 × larger than the corresponding classical state-space.
The working quantum dimensionality is “only” 10^3 × larger because biological systems are hot and noisy … hence (exponentially many) higher-order correlations can be quenched (via the usual quantum informatic unraveling tricks) without compromising the fidelity of the simulations.
Hey … if quantum simulations require 10^3 × more resources than classical simulations … and Blue Gene has 10^3 × more processors … that’s a good match!
That’s why we are presently studying the feasibility/desirability of migrating our QSE Group’s open-source fast simulation algorithms onto computers of Blue Gene’s class and architecture … our (GPL’d) algorithms are in fact optimized to ease this transition. And it should be noted that many other quantum simulation research groups are following a similar path.
Of course, it might be true that within our hot, wet, and noisy mammalian brains, computation is taking place within a quantum subspace, having exponentially large dimension, that is protected from decoherence by some (presently unknown) mechanism. But at the present time, there is very little theoretical or experimental evidence to suggest that this is the case.
Job’s comment relates to an intriguing question that Jon Jacky raised at a recent UW QSE Group meeting: “What quantum elements are present in every household?” To which our collective answer was: (1) the computers, and (2) the biology of the inhabitants. Both are very complicated, but it seems (to us) that neither is BQP-hard to observe or simulate.
The above is, of course, only an opinion … in the next 10-20 years we will surely discover much more about the quantum-level “observability and learnability” of biological systems.
John, thanks for that (extremely long) reply. It makes sense that we shouldn’t expect all simulation of quantum processes to be in BQP, especially because these are only instances of the more general problem.
But i’ve read some reference to (i wish i could point it out) the possibility of the human brain having a small black box which can solve problems in BQP (of course it sounds ridiculous when i say it, but keep in mind i don’t endorse this idea). If this were the case then Blue Gene would have to fail since it can’t simulate that black box(?).
Job, although it may not be exactly what you are looking for, there is a recent preprint by Aharonov, Ben-Or, and Eban, titled Interactive proofs for quantum computations that seems to suggest an interesting algorithmic approach to experimentally testing this class of ideas.
I won’t pretend to have actually understood this preprint’s ideas … still it was a mighty interesting approach.
John Sidles’s post is extremely interesting to me. I have submitted some papers on the computational problems in Biology (dominated by networks, chaos, vast ranges of scale in time and space) and what consensus if any exists on how to meet the computational challenges.
Our civilization DOES now, finally, have the computational capability to fully model a single living cell, and many labs in many nations are competing to climb this Everest.
Needless to say, it is at least 10^11 times harder to model the cellular systems of an entire living human brain, which is why nobody is going to be “uploaded” into software any time soon, however Transhumanists and science fiction authors may extol the virtues of that distant goal.
My PhD research 1973-1977 and many subsequent refereed publications includes the questions of how to simulate in arbitrary precision the dynamics of a single living cell, with its tens of thousands of different proteins, and metabolic network evolved to be (I argued before the terms existed) “at the edge of chaos.”
The nonlinear system of Michaelis-Menten kinetics used since the 1930s to model the metabolism have no classical solution, but my simulations and simulated evolution allowed me to discover the perturbation expansion and convolution integral solutions in the neighborhood of steady state, thus determining a priori the velicity of “enzyme waves” in living systems, as later rediscovered in part by Prigogine et al.
The problem is, from an interdisciplinary perspective, that the tremendous knowledge of the Computer Science community, Physics Community, Biochemistry Community is poorly transmitted across disciplinary boundaries.
Hence the “tue believers” in nanotechnology-based Sinbgularity Real Soon now are either unintentionally or intentionally exploiting the shallowness of biological and chemical prerequisites among the Silicon Valley community, and can confuse even brilliant scientists such as (in my opinion) Prof. Scott Aaronson. Scott has had the intellectual honesty and clarity to openly state that he is weak in Chem and Bio, and has measured skepticism about The Singularity as a result. MIT happens to be one of the best places in the world for Scott to learn more. I have great faith in the power of his mind, and his curiosity, and his communications skills to see that happen.
Slightly off-topic, except for the Venn diagram intersection of Singularitarians and Bayesians, I am much more a believer in Minimum Description Length models than Bayesian models, in part because of the influence of Kolmogrov, Chaitin, and CS experts on the paradigm.
So my real question: what is the connection between Quantum Computing and Minimum Description Length? What is the QC equivalent of Occam’s Razor?