tag:blogger.com,1999:blog-3722233.post970586742716794287..comments2024-07-19T08:15:14.879-05:00Comments on Computational Complexity: Is Quantum the new Random ?Lance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger22125tag:blogger.com,1999:blog-3722233.post-42336668072850917402009-11-03T15:11:26.404-06:002009-11-03T15:11:26.404-06:00Drucker and de Wolf's survey "Quantum Pro...Drucker and de Wolf's survey "Quantum Proofs for Classical Theorems" has appeared on the arXiv.<br />http://xxx.lanl.gov/abs/0910.3376Eleanor Rieffelhttp://palblog.fxpal.com/?author=13noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-70399160561884780232009-08-14T09:33:28.502-05:002009-08-14T09:33:28.502-05:00What kinds of [quantum] questions would you expect...<i>What kinds of [quantum] questions would you expect [undergraduate] students to answer on an exam?</i><br /><br />The same questions that undergraduate [engineering] students would be expected to answer about <i>classical</i> systems---and that they could find jobs for knowing how to answer.<br /><br />"What varieties of quantum system can be optimally designed and efficiently simulated? Give practical examples."John Sidleshttp://www.mrfm.orgnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-16916626396016282582009-08-14T06:45:48.058-05:002009-08-14T06:45:48.058-05:00The Dasgupta-Papadimitriou-Vazirani textbook has a...The Dasgupta-Papadimitriou-Vazirani textbook has a chapter on quantum, but that doesn't mean anyone teaches it. Do you know of which schools teach quantum in their undergrad algorithms course? What kinds of questions would you expect students to answer on an exam?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-22396907037872196842009-08-14T04:51:16.281-05:002009-08-14T04:51:16.281-05:00I find it amusing that noone has mentioned the Das...I find it amusing that noone has mentioned the Dasgupta-Papadimitriou-Vazirani (undergraduate) textbook. It has a chapter on quantum algorithms, including a sketch of Shor's.<br /><br />So quantum techniques have been taught to undergraduates for a couple of years, at many places, without the need for special extra Math courses (see also Scott's version of intro quantum computation as negative probabilities, and Lance's paper on characterizing quantum complexity classes as complex number versions of "correct" counting classes.)<br /><br />As for when will we teach it in a Complexity course, the answer is "when we think it is more useful than some other topic currently being taught"--I guess, a very personal decision of what techniques are likely to lead to good new results.CSProfhttps://www.blogger.com/profile/07212822875614144307noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-25511010306216285962009-08-14T03:56:52.394-05:002009-08-14T03:56:52.394-05:00Give me a call, Gilbert, once you're in Seattl...Give me a call, Gilbert, once you're in Seattle -- we have twice-a-week QSE Group meetings at which everyone is welcome ... and these <a href="http://faculty.washington.edu/sidles/QSEPACK/Kavli/sidles_kavli_tutorial.pdf" rel="nofollow">Kavli tutorial notes</a> summarize our QSE Group's geometric framework for QIT/QIS analysis and simulation.John Sidleshttp://www.mrfm.orgnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-70331039232603767402009-08-13T23:17:52.952-05:002009-08-13T23:17:52.952-05:00Thanks John. I may just have to take you up on th...Thanks John. I may just have to take you up on that offer.Gilbert Bernsteinhttp://www.cs.utexas.edu/users/gilbonoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-9505852193575034562009-08-13T13:54:12.766-05:002009-08-13T13:54:12.766-05:00This term I took a course at Waterloo on "Qua...This term I took a course at Waterloo on "Quantum Applications of Classical Complexity".<br /><br />I found that Scott's PostBQP-based proof that PP is closed under intersection was very neat and good motivation to understand the basic formulation of quantum computing. My course project was to write this up, see http://en.wikipedia.org/wiki/PostBQP<br /><br />On the other hand, my own feeling was that this was sort of a unique example -- the other topics in the course felt to me like quantum topics with quantum results. (Just an opinion, I don't mean to debate it, and certainly I am interested to see the upcoming survey paper.)Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-52526644860182056282009-08-13T11:37:39.797-05:002009-08-13T11:37:39.797-05:00Quantum is much more compelling for its own sake t...Quantum is much more compelling for its own sake than for its classical applications. However, given that quantum computers can be built in principle, it would seem to be the correct model to study for lower bounds.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-33657622879393602272009-08-13T05:53:02.873-05:002009-08-13T05:53:02.873-05:00Counting generously, there are now about a dozen e...Counting generously, there are now about a dozen examples of applications of quantum computing techniques to non-quantum TCS/math. For those interested in the topic, Andy Drucker and I are writing a survey paper, which should be out in a month or two.<br /><br />-- Ronald de WolfUnknownhttps://www.blogger.com/profile/13688293834506843997noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-36998860182562462802009-08-13T04:09:03.580-05:002009-08-13T04:09:03.580-05:00Welcome to the UW Gilbert! If you walk across the...Welcome to the UW Gilbert! If you walk across the street from the CSE building, you'll be in the ME Building, and you are very welcome to visit our UW Quantum Systems Engineering (QSE) laboratory.<br /><br />Our QSE Group's interest in complexity theory resides mainly in model order reduction of quantum system dynamics, and our main tools for achieving this are Kählerian concentration theorems that derive from drift-and-diffusion descriptions of measurement-and-control processes.<br /><br />So we try to keep one foot in both worlds ... we prove theorems *and* we cut metal ... and yes, we most definitely use a *lot* of quantum mechanical analysis.John Sidleshttp://www.mrfm.orgnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-88511359648630174452009-08-13T02:34:30.216-05:002009-08-13T02:34:30.216-05:00Sorry if I'm off in left field here, but my im...Sorry if I'm off in left field here, but my impression was that most undergrads will have little to no use for most of complexity theory, seeing as how most of them will be taking jobs in industry. The major points that seem to require communicating are the halting problem and a clear understanding of P vs. NP, that is the notions that problems may be provably hard or insoluble.<br /><br />It seems to me that widely used linear to cubic time algorithms, ample applications of those algorithms, and techniques and principles for devising novel algorithms and applications are much more important for most students. Probability tends to show up as a pragmatic technique (e.g. quicksort pivots) in the undergraduate curriculum, not as a complexity theoretic topic or technique. I don't imagine quantum techniques will ever find their way into the undergraduate curriculum unless they can (a) be applied to real programs and (b) there is no way to explain the resulting application without appealing to a quantum explanation.Gilbert Bernsteinhttp://www.cs.utexas.edu/users/gilbo/Home.htmlnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-57680000803690390242009-08-13T00:26:53.394-05:002009-08-13T00:26:53.394-05:00Kurt asks: Will the typical undergrad taking an in...Kurt asks: <i>Will the typical undergrad taking an intro to computation class have the necessary math prerequisites to understand quantum techniques?</i><br /><br />Kurt, your question is excellent, and it holds with redoubled force if we replace "quantum" with "classical".<br /><br />The problem arises because incoming graduate students whose understanding of dynamical state-spaces (whether classical or quantum) is fundamentally Euclidian (whether Newtonian or Hilbert) have an immense amount of mathematics still to learn before they can be entrusted with even the simplest simulation codes.<br /><br />The point is that even when the state-space of nature is Euclidian/Hilbert (to a very good approximation) it still generically happens that working simulation state-apaces are nonlinear <i>prima facie</i> ... yet dynamical conservation laws and informatic/thermodynamic principles must be strictly respected ... and undergraduate curricula leave many (most?) entering graduate students mathematically unprepared to deal with this.<br /><br />How many undergraduates have acquired the ever-elusive mathematical maturity needed to learn classical mathematics from (say) Arnol'd?<br /><br />At last month's FOMMS Conference this problem was widely acknowledged as being so severe, that it had its own short-hand name: "The Education Problem."John Sidleshttp://www.mrfm.orgnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-71716949158807886412009-08-12T22:04:41.231-05:002009-08-12T22:04:41.231-05:00Will the typical undergrad taking an intro to comp...Will the typical undergrad taking an intro to computation class have the necessary math prerequisites to understand quantum techniques? Or will the math instruction also need to be extended?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-66612239292064045152009-08-12T20:39:08.857-05:002009-08-12T20:39:08.857-05:00Oh yeah ... when the above is cast GASARCHian math...Oh yeah ... when the above is cast GASARCHian mathematical form it becomes the following advice to students: "Even if all you care about is complex structure, then you still need to know about symplectic and Riemmanian structure."<br /><br />In fact, an even stronger statement follows: "<i>All</i> you need to know about is symplectic and Riemmanian structure, because then the complex structure comes <a href="http://en.wikipedia.org/wiki/Almost_complex_manifold#Compatible_triples" rel="nofollow">for free</a>."John Sidleshttp://www.mrfm.orgnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-43346112107443373232009-08-12T20:29:22.419-05:002009-08-12T20:29:22.419-05:00Many practical computational problems are problems...Many practical computational problems are problems about simulation (there is even a point of view in which all computations are simulations). <br /><br />And obviously, a pretty big subset of practical simulations are performed upon state-spaces that are small-dimension encodings of the large-dimension space that nature specifies.<br /><br />The great advantage of learning quantum techniques comes when we ask questions like "Why does concentration work so well in real-world problems?" "What generic mechanism acts to algorithmically concentrate simulation trajectories?" For quantum systems this question can be phrased in Scott's language as "What physical mechanism accomplishes sure/Shor separations in real-world quantum systems?" <br /><br />A good reason to learn quantum simulation is that (AFAICT) it is <i>only</i> for quantum systems that a reasonably generic mechanism (and mathematically well-posed) for algorithmic concentration known --- it is the physical mechanism that Zurek calls "einselection".<br /><br />Now, if we ask, what mathematical aspects of quantum mechanics are necessary for einselection, then the mathematically natural answer is "the compatible triple of symplectic, Riemannian, and complex structure ... and as for the linear structure ... well ... that is merely a 'technical convenience' (according to the point of view of Ashtekar and Schilling)."<br /><br />The resulting prediction is clear ... furture textbooks on quantum complexity will cover compatible triples first ... <i>then</i> cover linear structure. :)<br /><br />The advantage of this approach is that complexity students end up speaking pretty much the same symplectic simulation language that biologists use ... and as simulation becomes more central to research at every scale of biology, this mathematical link-up increasingly benefits both disciplines.John Sidleshttp://www.mrfm.orgnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-901564584945363952009-08-12T19:22:01.029-05:002009-08-12T19:22:01.029-05:00It depends what you want to do with it. I think ev...It depends what you want to do with it. I think even your second statement is controversial: you <em>can</em> teach undergraduate algorithms/complexity without mentioning randomization. Would I feel that something was missing from such a course? Yes, but adding one thing means removing something else. The point is that there is plenty to learn without it. <br /><br />The same goes for quantum, only more so. =)<br /><br /><em>When will we be teaching Quantum techniques in the standard Grad Complexity Course?</em><br /><br />As soon as a good textbook on the subject becomes available. (Or a good chapter in a general complexity textbook -- Arora-Barak may qualify; I haven't checked yet.)<br /><br /><em>When will we be teaching Quantum techniques in the standard Undergrad Complexity Course?</em><br /><br /><em>What</em> standard undergrad complexity course? Or maybe you mean "when will Sipser's book include a section on quantum"? Unfortunately, I have not yet seen an introduction to quantum computing that would work in an undergrad class.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-77516308351353243002009-08-12T18:58:01.372-05:002009-08-12T18:58:01.372-05:00To anon #1: I think this is a reference to the exp...To anon #1: I think this is a reference to the explicit formula for the roots of a cubic, which can require calculation with complex numbers even to get real roots.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-63048783448894530052009-08-12T18:21:30.949-05:002009-08-12T18:21:30.949-05:00To Anonymous number 2: What is wrong with using St...To Anonymous number 2: What is wrong with using Sturm sequences to determine the number of roots in any interval?<br /><br />Anyhow, everyone wants to know what the "next big thing" is. What experience has taught us is that we are very bad at this guessing game. I have no idea whether we will care about Quantum Computers in 20 years. I don't even want to guess.Daniel Lemirehttps://www.blogger.com/profile/01566622051558391310noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-61779890309913792842009-08-12T18:03:56.769-05:002009-08-12T18:03:56.769-05:00The papers of Gentry and Peikert used quantum tech...<i>The papers of Gentry and Peikert used quantum techniques in Crypto. </i><br /><br />This is a bit misleading. Peikert's paper is about *removing* quantumness from an earlier reduction of Oded Regev. Gentry's reduction, though, is quantum much the same way that Regev's reduction is.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-13018883160281162752009-08-12T17:52:02.413-05:002009-08-12T17:52:02.413-05:00When viable quantum computers exist.When viable quantum computers exist.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-63036093757220136822009-08-12T17:47:19.873-05:002009-08-12T17:47:19.873-05:00to anon@1, how do you know that you have exhausted...to anon@1, how do you know that you have exhausted all the real roots?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-42089509718279476872009-08-12T16:10:47.285-05:002009-08-12T16:10:47.285-05:00"Even if all you care about is finding real r..."Even if all you care about is finding real roots of polynomials over the reals then you still need to know about complex numbers."<br /><br />I do not agree with this statement at all.<br />Why does one need to discuss complex numbers in order to talk about real roots of a real polynomial ? Every theorem (that I know of) about real roots of real polynomials can be proved without referring to complex numbers.Anonymousnoreply@blogger.com