BQPOTUS (or, the Big-O)
Disclaimer: The White House Office of Science and Technology Policy has asked me to clarify that, although this post will contain a photograph of me standing near the President of the United States, nothing in the post, or in Shtetl-Optimized more generally, is endorsed in any way by the White House or the President. You know, just in case you were wondering.
It’s a good thing that I chose a career in science rather than in public relations.
Within one century, government-sponsored scientific research radically changed the ways that human beings exist on this planet. Electronics are possible because of the quantum revolution of the 1920s, a revolution that many of us are still trying to understand the full implications of. While it benefited from a government monopoly, Bell Labs was able to invent and/or commercialize the transistor, the laser, the fiber-optic cable, and the communications satellite. (As soon as Congress opened the telecom market to competitors, Bell Labs’ capacity to innovate was permanently crippled.) Computers, the Internet, cell phones, nuclear energy, DNA testing, and widespread vaccination are a reality today largely because of a partnership between academic scientists and their governments, in the US and elsewhere, that started in earnest during World War II and has continued to the present.
I sort of imagined that, if you were reading this blog, then you knew all of that, and also knew that I knew it. But I was mistaken. In writing about what seemed to me like a slam-dunk issue for any thinking person—namely, protecting the 0.18% of the United States federal budget that goes to the National Science Foundation—I somehow managed to make enemies not only of the NSF’s opponents, who skewered me as an ivory-tower elitist, but also of many of its supporters, who either didn’t understand or didn’t appreciate my attempts at gallows humor.
Fortunately, today I have a happy story involving the NSF. As Lance Fortnow kindly mentioned a month ago, I had the honor of being included in this year’s PECASE (Presidential Early Career Award for Scientists and Engineers) class. Here I followed in the footsteps of Adam Smith and Sean Hallgren, two theoretical computer scientists from Penn State (and very nice people) who won last year. The PECASE is given for a combination of research and outreach, so there’s little doubt this blog played a role, in addition (I hope!) to the research and teaching that I sometimes do in my spare time. There’s no money in the PECASE, just a fun trip to DC for ceremonies and a photo-op with the President.
The day (last Monday) started with a ceremony in the Department of Agriculture building. There was a Color Guard, then a beautiful live performance of the national anthem, then short speeches, then a presentation of awards that resembled a high-school graduation, then a reception where they served these really nice smoked-salmon wraps, as well as chocolate truffles that were on sticks like lollipops. The awardees’ families were all there with us, but unfortunately, only the awardees themselves were cleared to enter the White House complex for the presidential photo-op. There was no Air Force One pickup to get to the White House: we took the Metro. We arrived at the Eisenhower Executive Office Building, which is to the left of the White House, adjacent to the West Wing. There were Christmas decorations all around.
After going through a security check, we were ushered into a room that seemed specially designed for presidential photo-ops. It had staggered platforms for standing on, with curtains in the background.
I was allowed to bring my cellphone, but it didn’t work inside the White House. There was a strict no-photography rule.
We were called to pose for the photo in order of height: people over 6ft in the back row, then people over 5ft 10in in the next two rows, etc. I was lucky to be short enough to land a spot in the second-to-front row. We stood there for about fifteen minutes while waiting for the President to arrive.
The organizer from the Office of Science and Technology Policy warned the women in the front row that last year, the President put his arm around them for the photo—so they should be prepared!
At 1:55pm, we received word that the President would arrive at 2:05pm, and at 2pm, we received word that he was on his way over. Finally, at 2:05 on the dot, he bounded into the room and the PECASE awardees erupted into applause. My MIT colleague Manolis Kellis bellowed “Mr. President!”, which made the President laugh.
The President looked and sounded pretty much the same as on TV. I was happy to see that his lip looked fine. He shook hands with everyone in the front row, assuring everyone else that they’d get a chance to shake his hand later as well.
(I’m the one wearing a tie with a little drawing of the MIT Stata Center on the bottom.)
The President spoke for about five minutes, while Secret Service agents stood unobtrusively in the corners of the room. Here were his main points, as I remember them:
- He couldn’t be more proud of us.
- Science and technology are extremely important for the nation’s future.
- He’s been fighting for more science funding. (At this, the PECASE awardees burst into applause again.)
- Science will be a highlight of his next State of the Union address. (Hey, you read it here first.)
- He understands that the PECASE award is not just for research but also for outreach and education, which is great.
- As someone with two daughters, he’s especially happy to see so many female PECASE winners.
- He feels so honored to be able to pose for a photo with us. (At this, everyone laughed.)
- He made a reference to “young people, which most of you still qualify as” (causing more laughter), and said he’s expecting us to “produce” and win some Nobel prizes.
As the rows cleared out, the President shook hands with everyone in turn. A few people said Merry Christmas. I just said “thank you,” and he said “thank you” back. Then I quickly moved away, since I had a cold and was worried about giving it to him. (Also, my hand was sweating for some reason—maybe because I was wearing a suit, which was definitely one of the more unusual aspects of the day for me!)
Immediately after the photo, we were escorted out of the Eisenhower Building. (Apparently the PECASE awardees in some previous years got a tour of the White House, but we didn’t.)
Later in the afternoon, there was a reception at NSF headquarters for the 19 PECASE winners whose research was sponsored by NSF (the remaining 66 were sponsored by the National Institutes of Health, the Department of Energy, the Defense Department, NASA, or other agencies). After opening remarks by Subra Suresh, the new NSF director and previously Dean of Engineering at MIT, each of the awardees gave a 3-minute speech about his or her work. I really enjoyed listening to the other 18 talks (as for my own, I spoke too fast and probably lost people).
At the risk of annoying earnestness, I’d like to thank:
- My NSF program officer (and all-around favorite government official), Dmitri Maslov.
- Every reader of this blog who ever said anything positive (or at least non-negative) about it.
- The Office of Science and Technology Policy, for putting together an awesome day (and inducing me to wear a tie even though no one was being married, buried, or bar-mitzvahed).
- President Obama, for supporting science and education even in the face of determined opposition.
- My fellow American taxpayers, for bankrolling the NSF. May all who receive grants strive to be worthy of them.
- My family.
Follow
Comment #1 December 19th, 2010 at 7:17 pm
Congrats again! Time to get to work on “producing” that CS Nobel Prize lol
Comment #2 December 19th, 2010 at 7:23 pm
Great to read this happy story, Scott. Your award is of course richly deserved. I also strongly second your point “May all who receive grants strive to be worthy of them”.
Happy holidays!
Comment #3 December 19th, 2010 at 7:42 pm
Congrats! I think your best shot is for the Nobel in Literature, although they’re giving out the Peace prize pretty randomly these days.
Comment #4 December 19th, 2010 at 7:49 pm
Thanks so much, everyone!
And Sean, I always thought of economics as the “easiest Nobel,” but you’re right that I wasn’t thinking far enough outside the box. To win the Peace Prize, it suffices to kill a lot of people, then publicly announce that you’ll stop doing so.
Comment #5 December 19th, 2010 at 8:11 pm
Congrats on meeting the big man! I hope you can get get back into doing some great science research, because your econ isn’t nearly as solid 🙂
Comment #6 December 19th, 2010 at 8:23 pm
Congratulations. Green with envy here 😀
Comment #7 December 19th, 2010 at 9:12 pm
Congratulations Scott, on a very well deserved award.
Comment #8 December 20th, 2010 at 2:39 am
Congratulations! I think a Nevalinna in ’14 or ’18 would be in the spirit of the presidential injunction.
Comment #9 December 20th, 2010 at 4:21 am
Congrats!
Comment #10 December 20th, 2010 at 9:06 am
Congratulations! Gotta say I’m slightly surpriced how excited you seem to be. I kinda thought you’d be somehowe “beyond this” :-).
Comment #11 December 20th, 2010 at 9:23 am
Łukasz: Nope. 🙂 It was absolutely fascinating for me to learn firsthand about the low-priority activities of the Executive Branch.
Comment #12 December 20th, 2010 at 6:03 pm
Congrats, Scott! A well-deserved honor for doing God’s work in promoting complexity.
Comment #13 December 21st, 2010 at 12:40 am
Happy happy happy!
Congratulations Scott! You were looking good in the suit!
Comment #14 December 21st, 2010 at 3:25 am
‘I always thought of economics as the “easiest Nobel’
Well I thought it was medical science where apparent you can publish trapezoid rule a seminal insight and get 75 citations for it.
Comment #15 December 21st, 2010 at 4:44 am
Hi Scott,
I think I have said both positive and negative things about this blog and you. Congras to you! I hope you can write more good articles to the laymen of computational complexity in the future.
MI
Comment #16 December 21st, 2010 at 9:20 am
Hi Scott,
It was such an honor to shake your hand. I read your blog on Saturdays before Sasha and Malia awake and when Michelle is out running. It is such a relief to have some time to myself and spend it thinking about the troubles with the breakdown of the polynomial hierarchy. I once explained the definition of the zig zag product to Putin, but he got really mad and said that I should never ever do such a thing again or he will bring it up at the security council meetings. I also have some ideas for a new definition of NP, but the only person willing to listen is dear ol’ Gordon. He thinks I should include it in my next State of the Union and see if I get a response from somebody in the 300 mills of my peeps. I don’t know … if I write to you, will you respond? I have also written to Nick, but my French isn’t good enough to nail the definition I have in mind. It basically passes through a dynamical system of a type I call piecewise affine linear and then goes on to show how some of its properties could be characterized as complete for NP. I think this is promising, but even Manmohan wasn’t ready to listen. It’s lonely at the top, you know. It took a lot of effort to keep myself from inviting you into my chamber the other day. People are watching and I don’t want to upset the repubs and give them another reason to boo me. Anyway, work beckons, back to real world PPAD-complete problems. Sigh.
Comment #17 December 21st, 2010 at 12:51 pm
The pastiche posted by “The President” will be familiar to many … the prior version by The Onion is astoundingly true-to-fact.
My congratulations go to Scott and to all the PECASE recipients; my thanks go to the NSF and the American public for supporting these young scholars; and my appreciation goes to the President for recognizing them.
May all of you succeed in living up to the Principles of the Harvard Society of Fellows:
Comment #18 December 22nd, 2010 at 4:28 am
where is the like button on your blog?
Comment #19 December 23rd, 2010 at 1:37 am
where is the like button on your blog?
Nowhere. Think about it.
Comment #20 December 23rd, 2010 at 1:47 am
BTW, it’s great that Obama takes the time to show up at these events. IMO this type of involvement is what leadership is about.
You know, i’ve never really won anything. You’re probably shocked to hear that, but it’s true.
Comment #21 December 23rd, 2010 at 7:27 am
So… any thoughts on whether the bailout hierarchy will eventually collapse?
Comment #22 December 23rd, 2010 at 2:03 pm
Econo-depressive asks: Any thoughts on whether the bailout hierarchy will eventually collapse?
—————————
[NASA Director] Chris Kraft: This could be the worst disaster NASA’s ever faced.
[Apollo 13 Flight Directory] Gene Kranz: With all due respect, sir, I believe this is gonna be our finest hour.
Comment #23 December 23rd, 2010 at 8:24 pm
To play devil’s advocate to your case for the triumph of scientce, allow me to quote Edward Teller: “I do not want a hydrogen bomb because it would kill more people. I wanted a hydrogen bomb because it was new. Because it was something we did not know and could know. I am afraid of ignorance.”
For all you ignorance-fearing scientists who are busy pursuing “the new”, I would simply ask: Is there a point at which we must stop seeking knowledge or risk extinction? What is that point? Are we already there?
Comment #24 December 23rd, 2010 at 10:38 pm
Don’t we risk extinction either way? Knowledge and ignorance are equally deadly, but one provides for interesting conversation.
Comment #25 December 23rd, 2010 at 10:49 pm
Is there a point at which we must stop seeking knowledge or risk extinction?
Sean, your question contains an unstated presupposition that that’s indeed the choice. I think that at least as often the choice is, seek knowledge or risk extinction! To give one example, if Teller and Ulam hadn’t developed the hydrogen bomb, the Soviet Union still would have done so, with terrible consequences for the balance of power. It’s hubris to think that you can prevent something from being invented by not inventing it yourself. The best one can hope for, in general, is that the (relatively) good guys stay a few steps ahead of the bad guys technologically.
But beyond that, I’d submit that the pursuit of science for its own sake is slightly “biased in the right direction”: that is, it’s slightly more likely to benefit the forces of good than the forces of evil. My reason is that the forces of good tend (by definition) to be more tolerant and accommodating towards nerds.
Comment #26 December 24th, 2010 at 8:08 am
Sean Strange asks: Is there a point at which we must stop seeking knowledge or risk extinction?
Sean, your question (obviously) has been asked, and answered, many times over the centuries. Right?
So it’s very interesting to inquire how mathematicians and scientists have asked, and answered, this question in previous decades—because this history conveys important information regarding our own century’s ability to ask and answer this questions.
In this regard, a classic analysis by von Neumann is his 1955 essay Can we survive technology?—you can find it on Google books—in which von Neumann anticipates many of the themes and conclusions of Jared DIamond’s 2004 book Collapse: How Societies Choose to Fail or Succeed.
Hmmmm … a fun exercise is to search Google’s “ngrams.googlelabs.com” for von Neumann’s phrase “survive technology” … and similar phrases like “survival of the human species” … “planetary health” … it’s apparent that planetary survival has become a serious concern of humans only since … well … since von Neumann’s 1955 essay. He was the first! 🙂
These earlier writings are largely consonant with the thrust of Scott’s comment #25 … except that it would be contrary-to-fact—and in the long run, immensely harmful to human society and to our planet—if math, science, and engineering were to become identified in the public mind as practiced exclusively by “nerds” (in Scott’s phrase).
In his recent obituary of Vladimir Arnold, Samson Kutateladze wrote:
Kutateladze’s essay reminds of history’s sobering lesson, that for 21st century humanity to “survive technology”—in the phrase that von Neumann’s essay coined—the embrace of breadth is going to have to be broadly practiced throughout the STEM enterprise … and specifically in its core disciplines of CT/QIT/QSE.
Comment #27 December 27th, 2010 at 11:55 am
Scott says: It’s a good thing that I chose a career in science rather than in public relations.
Scott, it’s interesting that you self-describe your professional objectives as “science”, as contrasted with “mathematics” or “engineering.”
Given the impressively large number (seventy-two in the latest version) of propositions, definitions, theorems, and lemmas in your recent Computational Complexity of Linear Optics manuscript, an objective observer might have guessed “mathematics.” Moreover, your faculty appointment is in MIT’s School of Engineering … thus, like increasingly many STEM researchers, your academic credentials certify your membership in all three tribes.
Now, in this regard there’s a terrific interview by Mikhail Gelfand of Yuri Manin, in Notices of the AMS (2009), titled We do not choose mathematics as our profession, it chooses us. In it, Manin remarks:
Hmmm … that’s a daunting observation … were it not that nowadays, young researchers have a terrific advantage over von Neumann. Namely, to stay abreast of the entirety of the pre-WWII literature on quantum measurement (for example), von Neumann had to read about one or two articles per month (a number that I’ve checked personally) … whereas nowadays, one has/gets to read approximately that many articles per waking hour.
These are thought-provoking numbers, both for good and for ill … do we all have to start taking Adderall to keep up, for example?
A welcome Shtetl Optimized post—of substantial interest to many, I am sure—would be a serious discussion of the emerging challenges and opportunities of 21st century “triple-threat” careers, both broadly in the global STEM enterprise, and specifically in North American CT/QIT/QSE.
It seems (to me) that there is plenty of good news for young researchers … but it is mixed with plenty of sobering challenges too. So why not try for some New Year’s cheer! 🙂
Comment #28 December 29th, 2010 at 10:03 am
Hmmm … no Shtetl Optimized posts in two days … well … to help sustain a dialog among engineers, scientist, and mathematicians, here’s our QSE Litotica Seminar’s reading of an updated version of Scott and Alex Arkhipov’s Computational Complexity of Linear Optics (CCOCL, as kindly made available by Scott at his website).
From a mathematical point-of-view we think the updated CCOCL manuscript is terrific; from a scientific point-of-view CCOCL raises the intriguing question “What exactly is the extended Church-Turing Thesis?”, and from an engineering point-of-view CCOCL raises deep issues relating to the fundamental limits to scalability in large-n linear optics experiments, as assessed via cavity QED formalisms.
In summary, for us engineers, the CCOCL work is an outstanding example of the broad and fundamental relevance that CT/QIT research has for the entire STEM enterprise. Thus CCOCL is not the last word, but rather the first word, of what promises to be a fundamentally important line of research.
Comment #29 December 30th, 2010 at 8:12 am
Sean asked: Is there a point at which we must stop seeking knowledge or risk extinction?
Chinese philosopher Lao Zi said 2500 years ago that we should not seek knowledge because life is limited but knowledge is infinite and it will be dangerous to pursue infinite knowledge with our limited lives. He also said use of intelligence is against Tao which is what governs the operation of our universe.
http://en.wikipedia.org/wiki/Laozi
Comment #30 December 31st, 2010 at 12:45 pm
@math idiot #29
I think that is a terrible oversimplification and misrepresentation of Taoist philosophy, though I’m sure you’re not the first to come up with that interpretation.
I think the more useful Taoist lesson to draw for science is something more like this:
Having enough knowledge to understand the system is not the same thing as having enough knowledge to beat the system.
Comment #31 January 2nd, 2011 at 6:40 am
Congratulations! Is there a way to look for the 10 breakthrough algorithms from TCS that were discovered in the last decade and that is useful in any current day products or that will be possibly used in the next 10 years?
Comment #32 January 2nd, 2011 at 11:11 am
LifeIsChill asks: Is there a way to look for the 10 breakthrough algorithms from TCS that were discovered in the last decade
LifeIsChill, the short answer to your question is “no,” and to appreciate why, let’s review some literature.
In Redner’s Citation statistics from more than a century of Physical Review (2004) we find abundant evidence that “breakthrough algorithms” often require much more than a decade to be recognized.
Consider as a paradigmatic example the most-cited article in the literature of physics and chemistry: Kohn and Sham’s Self-consistent equations including exchange and correlation effects (1965). As Redner’s review establishes, only sparse references to the Kohn-Sham article appeared during its first decade … yet nowadays the frequency of references to this work is still accelerating (forty-six years later).
To appreciate the roots of the Kohn-Sham algorithm in complexity theory and quantum information theory, a recommended starting reference is Kohn’s Nobel lecture Electronic structure of matter-wave functions and density functionals (1999), and in particular two short articles referenced therein: van Vleck’s Nonorthogonality and ferromagnetism (1936) and Kohn’s own Density functional and density matrix method scaling linearly with the number of atoms (1996).
All of these articles—extending back seventy-five year—bear directly upon a subject of central interest to Shtetl Optimized readers, namely, the feasibility and scalability of experimentally preparing and/or computationally simulating highly entangled quantum states, both as inputs to and outputs from quantum computing devices. These are matters regarding which, even today, our mathematical and physical understanding is uncertain and unsatisfactory, and our engineering ability to produce and/or measure these states is deplorably limited.
The preceding examples apply mainly to quantum aspects of theoretical computer science, but similar considerations apply broadly to all aspects of computational math, science, and engineering … Robert Bixby’s Solving real-world linear programs: a decade and more of progress (2002) is a terrific example.
The overall point, LifeIsChill, is that we are still today in the process of appreciating the informatic and computational significance of articles that were written many decades ago; thus a short-sighted focus on “breakthroughs in TCS in the last decade” is more likely to impair one’s overall understanding, than to help it.
In the end, there’s no substitute for reading and reflecting upon the literature oneself … because a strictly uniform consensus as to what work(s) qualify as “TCS breakthroughs” is neither desirable nor feasible at the present time.
Comment #33 January 2nd, 2011 at 8:40 pm
ic…. but ultimately in the world we live in we measure progress as $/bit-processed or $/joule for every bit processed or joule/bit-processed for a vast majority of ‘progresses’.
If I understand your viewpoint: we are beginning to scratch the surface of interaction between what mother nature + TCS.
But if one considers only ‘blind math’ based TCS research, apart from the question of infeasible practical computations(NP problems), for purposes of practical utility, is it safe to say that the stage of research in ‘blind math’ approach to TCS is probably close to saturation just as some topics in pure Mathematics are close to complete and satisfactory results and essentially fully classified? By that I mean the amount of investment that could be made to get even lower $/bit or $/joule or joule/bit is probably not worth it just as for practical communications systems the limits of efficient compression and communication in the Shannon sense is for all sane reasons of engineering essentially achieved.
Comment #34 January 2nd, 2011 at 9:58 pm
LifeIsChill asks: Is it safe to say that the stage of research in ‘blind math’ approach to TCS is probably close to saturation?
Your question is a good excuse to search my quotation database …
In the ACM’s Interview with Vladimir Arnol’d we read:
What we really want in complexity theory is (of course) the best of both worlds: clear ideas accompanied by rigorous proofs … we are at present quite far from that ideal (obviously) … but (IMHO) there is no reason to be downcast about the rate of progress overall.
LifeIsChill, perhaps what you have in mind to ask is more aligned with Jeannette Wing’s concluding question in her recent Five deep questions in computing (2008):
My own opinion (or rather, hope) is that at least one key element of Wing’s envisioned theory already exists in embryonic form … it is Lindblad theory.
Comment #35 January 3rd, 2011 at 9:20 pm
I will look in Lindbald theory.
Prof Aaronson: I think this kind of gets what I am asking from a practical perspective. May be this is what I should have asked. Whether any ‘classical TCS Moore’ law still holds?
http://agtb.wordpress.com/2010/12/23/progress-in-algorithms-beats-moore%E2%80%99s-law/
Comment #36 January 4th, 2011 at 11:48 am
LifeIsChill Says: I will look in Lindbald theory.
LifeIsChill, learning Lindblad theory—or more broadly, learning the theory of open dynamical systems—is pretty much guaranteed to be enjoyable adventure, provided that one begins with realistic expectations regarding the immense size of the territory to be explored.
One good entry point is a thorough familiarity with Chapters 2 and 8 of Nielsen and Chuang’s Quantum Computation and Quantum Information, augmented by Carlton Caves’ Quantum error correction and reversible operations (1998) and by Caves’ excellent on-line notes Completely positive maps, positive maps, and the Lindblad form (2000, revised 2002 and 2008).
At this point it will be evident that the simplest generator of Lindbladian dynamics is simply the Hamiltonian itself; thus a reasonable course of study is to review what is known about Hamiltonian dynamics from an algebraic, informatic, and geometric point-of-view.
For algebraic dynamics see Dirac’s Principles of Quantum Mechanics (1930). For informatic dynamics see Nielsen and Chuang (op cit). For geometric dynamics—which has by far the largest and most diverse literature—a solid foundation is supplied by Jack Lee’s Introduction to Smooth Manifolds (2003), augmented by Arnold’s Mathematical Methods of Classical Mechanics (1978) and by Mac Lane’s Chauvenet Lecture Hamiltonian mechanics and geometry (1970).
At this point you will be prepared to read, with good understanding and enjoyment, Ashtekar and Schilling’s classic Geometrical formulation of quantum mechanics (1999, arXiv:gr-qc/9706069), and in particular, you will be able to translate freely between algebraic, informatic, and geometric descriptions of dynamical systems. For example, simple answers will be evident to questions that are not commonly discussed in quantum mechanical textbooks, like “Why does Bloch dynamics (and Landau-Lifshitz-Gilbert dynamics too) have a natural Hamiltonian description, but not a natural Lagrangian description?”
At this point you will have achieved only the barest beginning of an integrated mathematical understanding of Kraus/Lindblad dynamics … in the sense that you will not yet be able to fluently translate between algebraic, informatic, and geometric descriptions of open system dynamics … but since nobody at present knows how to do this … why … that’s why they call it “research”! 🙂
For sure, though, you will have read a lot of great articles and books, and you will have acquired in integrated mathematical toolset that will serve you well in analyzing pretty much any dynamical system, whether classical or quantum, that naturally ariss in any branch of mathematics, science, or engineering.
So enjoy the great STEM adventure that awaits you! 🙂
Comment #37 January 5th, 2011 at 1:47 am
John,
Thanks for the tip, I will try to catch up on Lindbald theory when I have get a couple free hours!
More seriously, it was good to hear about the views of Arnol’d and Kolmogorov. I have studied 2.5 of Arnol’d’s books, and 0.10 of Kolmogorov’s.
Long ago, I was working on a Ph.D. in math, and despised the Bourbaki-ization of math then going on. It caused me to switch to physics, and then applied math. I wound up in CS. Funny how those things go.
Of course, everything is nonlinear. I highly recommend “Foundations of Modern Analysis” by Dieudonne, who is perhaps the best known member of Bourbaki. As I recall, this book starts with some wisecracks about how things have changed since a book of the same title by Whittaker and Watson was published. Both of these books are excellent expositions of huge parts of math, with zero intersection.
Comment #38 January 5th, 2011 at 4:32 am
Glad you enjoyed the references, Raoul. Near the end of this dynamical road—an end that needless to say, we are far from reaching—we find mathematical ideas like those summarized in Terry Tao’s recent column The Euler-Arnold Equation.
These various mathematical writings reflect a shared theme that is familiar from complexity theory. As Scott’s writings often emphasize, in complexity theory one has a formal tool, namely reduction theory, that is so broadly effective and elegant relative to all other tools, that by its mere existence it largely determined the course of 20th century research.
Similarly, in the theory of dynamical systems we have a formal tool, namely group theory, that is so broadly effective and elegant relative to all other tools, that by its mere existence it largely determined the course of 20th century research.
The great promise of Lindblad theory as a formal tool for 21st century CS/CT/QIT/QSE is that it is comparably effective and elegant to group theory in reducing the effective dimensionality of dynamical state-spaces, thus rendering them amenable to analysis and simulation.
Moreover, from a purely practical point-of-view, it is “a truth universally acknowledged” that computationally reducible systems are ubiquitous … and symmetric systems are ubiquitous … and that noisy, thermalized, open dynamical systems are ubiquitous too.
Thus we see the outlines of a partial answer to Jeannette Wing’s concluding question in her Five deep questions in computing (2008):
That answer is along the lines of “A great many computations are associated to dynamical systems that are computationally reducible and/or symmetric and/or open, and generically these systems can be simulated efficiently.”
How efficiently? By what algorithms? By what hardware? By what software? As described in what texts? Enabling what great enterprises? These are key questions for 21st century CS/CT/QIT/QSE.
Comment #39 January 9th, 2011 at 11:35 pm
Dick Lipton is featuring an essay, Dangers of proof by contradiction (advice for amateurs or beginners), from Henry Cohn’s Random Mathematical Thoughts website.
Actually, *all* the essays on Cohn’s website are well worth reading, and I wish to specially recommend the essay Why symplectic geometry is the natural setting for classical mechanics.
Cohn’s essay can be translated into a parallel essay Why symplectic geometry is the natural setting for quantum mechanics pretty much automatically … it is only necessary to replace the natural almost complex structure that is associated to cotangent bundles manifolds with the natural complex structure that is associated to Kähler manifolds.
We then appreciate why (as mentioned above) the Bloch equation dynamics are a Hamiltonian flow, yet the Bloch equations cannot be derived via a Langrangian variation (try it!) … it’s because the Riemann sphere has the wrong topology to be a tangent bundle manifold.
There’s one minor glitch in Henry’s essay … it incorrectly asserts that the “laws of physics” require that the alternating forms of Hamiltonian mechanics be closed. This is not the case … rattleblocks and Chaplygin sleighs are two well-known examples of classical dynamical systems whose dynamical flow is governed by alternating forms that are not closed.
It’s true, though, that rattleblocks and Chaplygin sleighs violate the Second Law … and there is a considerable literature on the remarkable consequences of this fact.