My 5-minute quantum computing talk at the White House
(OK, technically it was in the Eisenhower Executive Office Building, which is not exactly the White House itself, but is adjacent to the West Wing in the White House complex. And President Obama wasn’t there—maybe, like Justin Trudeau, he already knows everything about quantum computing? But lots of people from the Office of Science and Technology Policy were! And some of us talked with Valerie Jarrett, Obama’s adviser, when she passed us on her way to the West Wing.
The occasion was a Quantum Information Science policy workshop that OSTP held, and which the White House explicitly gave us permission to discuss on social media. Indeed, John Preskill already tweeted photos from the event. Besides me and Preskill, others in attendance included Umesh Vazirani, Seth Lloyd, Yaoyun Shi, Rob Schoelkopf, Krysta Svore, Hartmut Neven, Stephen Jordan…
I don’t know whether this is the first time that the polynomial hierarchy, or the notion of variation distance, were ever invoked in a speech at the White House. But in any case, I was proud to receive a box of Hershey Kisses bearing the presidential seal. I thought of not eating them, but then I got hungry, and realized that I can simply refill the box later if desired.
For regular readers of Shtetl-Optimized, my talk won’t have all that much that’s new, but in any case it’s short.
Incidentally, during the workshop, a guy from OSTP told me that, when he and others at the White House were asked to prepare materials about quantum computing, posts on Shtetl-Optimized (such as Shor I’ll Do It) were a huge help. Honored though I was to have “served my country,” I winced, thinking about all the puerile doofosities I might’ve self-censored had I had any idea who might read them. I didn’t dare ask whether anyone at the White House also reads the comment sections!
Thanks so much to all the other participants and to the organizers for a great workshop. –SA)
Quantum Supremacy
by Scott Aaronson (UT Austin)
October 18, 2016
Thank you; it’s great to be here. There are lots of directions that excite me enormously right now in quantum computing theory, which is what I work on. For example, there’s the use of quantum computing to get new insight into classical computation, into condensed matter physics, and recently, even into the black hole information problem.
But since I have five minutes, I wanted to talk here about one particular direction—one that, like nothing else that I know of, bridges theory and experiment in the service of what we hope will be a spectacular result in the near future. This direction is what’s known as “Quantum Supremacy”—John [Preskill], did you help popularize that term? [John nods yes]—although some people have been backing away from the term recently, because of the campaign of one of the possible future occupants of this here complex.
But what quantum supremacy means to me, is demonstrating a quantum speedup for some task as confidently as possible. Notice that I didn’t say a useful task! I like to say that for me, the #1 application of quantum computing—more than codebreaking, machine learning, or even quantum simulation—is just disproving the people who say quantum computing is impossible! So, quantum supremacy targets that application.
What is important for quantum supremacy is that we solve a clearly defined problem, with some relationship between inputs and outputs that’s independent of whatever hardware we’re using to solve the problem. That’s part of why it doesn’t cut it to point to some complicated, hard-to-simulate molecule and say “aha! quantum supremacy!”
One discovery, which I and others stumbled on 7 or 8 years ago, is that quantum supremacy seems to become much easier to demonstrate if we switch from problems with a single valid output to sampling problems: that is, problems of sampling exactly or approximately from some specified probability distribution.
Doing this has two advantages. First, we no longer need a full, fault-tolerant quantum computer—in fact, very rudimentary types of quantum hardware appear to suffice. Second, we can design sampling problems for which we can arguably be more confident that they really are hard for a classical computer, than we are that (say) factoring is classically hard. I like to say that a fast classical factoring algorithm might collapse the world’s electronic commerce, but as far as we know, it wouldn’t collapse the polynomial hierarchy! But with sampling problems, at least with exact sampling, we can often show the latter implication, which is about the best evidence you can possibly get for such a problem being hard in the present state of mathematics.
One example of these sampling tasks that we think are classically hard is BosonSampling, which Alex Arkhipov and I proposed in 2011. BosonSampling uses a bunch of identical photons that are sent through a network of beamsplitters, then measured to count the number of photons in each output mode. Over the past few years, this proposal has been experimentally demonstrated by quantum optics groups around the world, with the current record being a 6-photon demonstration by the O’Brien group in Bristol, UK. A second example is the IQP (“Instantaneous Quantum Polynomial-Time”) or Commuting Hamiltonians model of Bremner, Jozsa, and Shepherd.
A third example—no doubt the simplest—is just to sample from the output distribution of a random quantum circuit, let’s say on a 2D square lattice of qubits with nearest-neighbor interactions. Notably, this last task is one that the Martinis group at Google is working toward achieving right now, with 40-50 qubits. They say that they’ll achieve it in as little as one or two years, which translated from experimental jargon, means maybe five years? But not infinity years.
The challenges on the experimental side are clear: get enough qubits with long enough coherence times to achieve this. But there are also some huge theoretical challenges remaining.
A first is, can we still solve classically hard sampling problems even in the presence of realistic experimental imperfections? Arkhipov and I already thought about that problem—in particular, about sampling from a distribution that’s merely close in variation distance to the BosonSampling one—and got results that admittedly weren’t as satisfactory as the results for exact sampling. But I’m delighted to say that, just within the last month or two, there have been some excellent new papers on the arXiv that tackle exactly this question, with both positive and negative results.
A second theoretical challenge is, how do we verify the results of a quantum supremacy experiment? Note that, as far as we know today, verification could itself require classical exponential time. But that’s not the showstopper that some people think, since we could target the “sweet spot” of 40-50 qubits, where classical verification is difficult (and in particular, clearly “costlier” than running the experiment itself), but also far from impossible with cluster computing resources.
If I have any policy advice, it’s this: recognize that a clear demonstration of quantum supremacy is at least as big a deal as (say) the discovery of the Higgs boson. After this scientific milestone is achieved, I predict that the whole discussion of commercial applications of quantum computing will shift to a new plane, much like the Manhattan Project shifted to a new plane after Fermi built his pile under the Chicago stadium in 1942. In other words: at this point, the most “applied” thing to do might be to set applications aside temporarily, and just achieve this quantum supremacy milestone—i.e., build the quantum computing Fermi pile—and thereby show the world that quantum computing speedups are a reality. Thank you.
Follow
Comment #1 October 25th, 2016 at 8:14 pm
I’m so excited this happened! Soon after you got your Waterman, perhaps by coincidence but I hope not , the Nat. Sci and Tech Council Committee on Science started an exploratory committee on Quantum Computing. I’m just sad it took this long to invite you to talk (I left NSF a year and a half ago and am now at NASA rockin’ Earth Observation instruments).
Comment #2 October 25th, 2016 at 8:38 pm
Wait, so what papers are these? I don’t recall you writing about these here!
Comment #3 October 25th, 2016 at 9:24 pm
I have a theory that, in Simon’s problem, the secret value’s ith bit is 1 if the blackbox function is lossy relative to that bit.
For example, if the secret value is 1001, then you cannot always recover the first and last input bits by inspecting the blackbox function’s output.
Given a blackbox 2-to-1 function, determine which of the function’s input bits are fully recoverable. I like this phrasing of Simon’s problem alot better – assuming it’s correct (i’m speculating, i have no proof). It actually seems fairly useful beyond demonstrating a quantum speedup.
Like, of practical use, along the lines of “does this piece of software leak the user’s credit card”? What do you think?
Comment #4 October 25th, 2016 at 10:32 pm
Since I still don’t see why simulating a molecule or material—a clearly defined task with different inputs (number and position of nuclei) and corresponding different outputs, and a task which is defined in a hardware independent way (you can look up the Hamiltonian in a textbook and take that as defining the problem; as a point of principle there are QED corrections which are complicated but which can be handled by an effective Hamiltonian in most applications), and a task where we have access to many instances of the same problem—doesn’t count as quantum supremacy, can you give a _formal_ definition of quantum supremacy which does not include such simulation?
Comment #5 October 25th, 2016 at 11:53 pm
@matt#4: Simulating molecules/materials could technically work as a quantum supremacy task, but it probably won’t be the *first* such task. Quantum supremacy is really about unequivocally demonstrating some task that a quantum computer can do that no classical computer can currently do (or can’t asymptotically do).
The technical machinery necessary to accurately simulate molecules far better than we can do classically is actually fairly complicated–you need a good basis set for your wavefunctions, you have to represent your wavefunctions as qubits, you have to apply many complicated unitaries to those qubits etc. etc. This sort of machinery will almost certainly appear soon after quantum supremacy is demonstrated (where ‘soon’ is like ~’decades’), but it makes for a poor first “killer app” for a quantum computer.
So sure, you might be able to demonstrate an ab initio algorithm on a quantum computer that scales asymptotically better than every known classical algorithm/gives better energies/treats larger systems/all of the above, but this won’t be around for a while. Quantum computers will be able to beat classical computers at a whole family of tasks long before those algorithms are actually implementable. Scott (and others) are looking for the first such problem in that family.
Comment #6 October 25th, 2016 at 11:54 pm
Sniffnoy #2: Sorry about that! I’ve now added hyperlinks throughout the talk. The mention of cool new papers on quantum supremacy goes to works by Fujii and Bremner et al..
Comment #7 October 25th, 2016 at 11:59 pm
Job #3: Yes, by definition, mapping x to x+s—i.e., flipping all the bits that are 1 in s—doesn’t change the value of f. But flipping a proper subset of those bits does change the value of f, so we can’t say that those bits “don’t matter”: there’s just a single bit about those bits that doesn’t matter. But when you say it like that, it’s just a restatement of the Simon promise!
Comment #8 October 26th, 2016 at 12:24 am
matt #4: I actually think that “simulating a molecule or material” could form the basis for a convincing quantum supremacy demonstration, but that more work would need to be done to make the case. Specifically, here’s what I’d want someone to do:
(1) Describe an infinite collection of instances, for which there’s a reasonably “uniform” hardware design that can in principle decide any instance in the collection. For example, “simulate the quantum dynamics of an arbitrary DNA strand” would be OK if you had a machine to synthesize any DNA strand up to (say) 1000 base pairs, and if you could make a case for why there’s no fundamental obstacle (short of cosmology) in extending to 2000 or any larger number of base pairs. But “simulate the quantum dynamics of an arbitrary molecule” wouldn’t work, unless you demonstrated that you could actually synthesize an arbitrary molecule of size n with poly(n) effort. And in such a case, I’d regard your synthesis machine, rather than the molecules themselves, as your “special-purpose quantum computer.”
(2) Whatever special (but theoretically infinite) class of molecules or materials you could synthesize, formalize the problem of simulating those molecules or materials in a completely self-contained way, and then give some theoretical argument for why the mathematical problem you’ve thereby defined is classically intractable. E.g., because it’s BQP-complete, or because a polynomial-time classical algorithm to sample the same distribution would imply a collapse of PH or some other consequence. But in any case, your argument can’t rely solely on the practical difficulties chemists and physicists have had in solving related problems, because that doesn’t sufficiently distinguish the asymptotic, complexity-theoretic kind of difficulty from other kinds (e.g., the kinds that arise even when simulating classical systems).
Comment #9 October 26th, 2016 at 2:23 am
If Supremacy doesn’t quite work anymore because of old Delirium Tremens, how about the other titles in the Jason Bourne series? The Quantum Identity? The Quantum Legacy? Ultimatum?
Comment #10 October 26th, 2016 at 3:41 am
Thanks for the kind mention of our work, Scott! I must confess that, when working out the details of Lemma 9 in Appendix B (etc.), the thought “Hmmm… I wonder if one day someone will discuss these results in the White House?” didn’t cross my mind…
Comment #11 October 26th, 2016 at 4:35 am
Scott #6: Thanks!
Comment #12 October 26th, 2016 at 8:10 am
They put you in a tough situation when they invited you but let you talk for only five minutes. You solved it great though, your talk is very informative.
When you talked about particular problems you recommend for demonstrating quantum supremacy, some of the details seemed new to me. I guess you probably said the same things in previous blog entries, I just forgot since.
I hope your speech and the other speeches at the same meeting will be effective, in the sense that the government people you targeted will remember it the right way.
Comment #13 October 26th, 2016 at 9:26 am
Mayra #1 and Jonas #12: Thanks!!!
Comment #14 October 26th, 2016 at 9:28 am
Daniel #5: No, I think Matt was thinking about the molecule itself as being the “computer.” In which case, see my response in #8.
Comment #15 October 26th, 2016 at 11:05 am
Yes, I was talking about the molecule being the computer. I think Scott’s answer is a fair answer. A related old and slightly imprecise question: http://web.math.princeton.edu/~aizenman/OpenProblems.iamp/9808.ImposThms.html
Comment #16 October 26th, 2016 at 12:56 pm
“because of the campaign of one of the possible future occupants of this here complex”
Texas is getting to you.
Comment #17 October 26th, 2016 at 3:03 pm
Is it known PP is contained in EXP?
Comment #18 October 26th, 2016 at 3:09 pm
Chris #16: Yee-haw!
Comment #19 October 26th, 2016 at 3:09 pm
AJ #17: Yup. As we say down in Texas, PP ⊆ P#P ⊆ PSPACE ⊆ EXP.
Comment #20 October 27th, 2016 at 5:23 am
Concerns regarding unwanted connotations of “supremacy” give added weight to John Preskill’s long-standing request (in his on-line essay “Supremacy Now”, see also Preskill’s arXiv:1203.5813, “Quantum computing and the entanglement frontier”):
Here are some resources and references that bear upon Preskill’s request for supremacy-alternatives.
Resources for sampling quantum ouliphany The free-as-in-freedom command-line phrase-sampler ouliphany — which is available as the shell-script “ouliphany.bash” — applies the methods of OuLiPo to sample hundreds of thousands of alternatives to “quantum supremacy”.
The results include some personal favorites:
• #5 quantum hilarity … in tribute to Baruch Spinoza
• #4 quantum comity … in tribute to Friends
• #3 quantum iatromechanics … in tribute to medicine
• #2 quantum querencity … in tribute to Jorge Luis Borges
• #1 quantum celerity … in tribute to the friendship of Stephen Maturin and Jack Aubrey
The five phrases each are grounded in a vast and beautiful literature … so vast indeed, that no mere blog-comment can survey it.
This comment’s limited objective, therefore, is to observe that the quest for quantum supremacy can be naturally regarded — with strengthened philosophical hilarity, social comity, medical practicality, and pedagogic querencity — as a quest for quantum celerity.
The postulate of quantum celerity Some physical processes can be simulated efficiently only by quantum computing resources
Here “quantum celerity” is suggested as a drop-in replacement for the phrase “quantum supremacy”, with no modification to John Preskill’s original conception required or imputed. In regard to the existing literature, the global replacement supremacy -> celerity generically “just works”; see for example Preskill’s arXiv:1203.5813 and Scott’s various on-line “Quantum Supremacy” talks (recently at Oxford, Redmond, Banff, and the White House).
The querencia of quantum iatromechanics How does the quest for quantum celerity illuminate the literature of Kalai-style quantum skepticism? In what sense(s) does quantum iatromechanics — here appreciated as the study of the quantum dynamical processes that are associated to biological processes and medical practice in particular — present a model for Kalai-style quantum skepticism? Can quantum iatromechanics provide young researchers with nurturing querencias (in the sense of Borges)?
In a nutshell, the querencia of quantum iatromechanics encompasses:
• shared resources like the (rapidly growing) bioRXiv preprint server
• articles like the bioRXiv preprints “Predicting binding free energies: Frontiers and benchmarks” (doi:10.1101/074625) and “Two-Dimensional NMR Lineshape Analysis” (doi:10.1101/039735)
• research collaborations like the Drug Design Data Resource (D3R)
• retrospectives and roadmaps like Cathy Peishoff’s “Computational chemistry looking forward: How can we as a community improve our field?” (2016)
When we read the above quantum iatromechanical works in parallel with quantum celerity works — in parallel with, for example, the Martinis Group’s preprint (which is wonderful as it seems to me) “Characterizing quantum supremacy in near-term devices” (arXiv:1608.00263v2) — the fundamental similarities are more striking (to me) than the fundamental differences.
On the other hand, “It is difference of opinion that makes horse races”, and perhaps the most pronounced contrast between the quantum celerity literature and the quantum iatromechanical literature is the role of noise.
In the quantum iatromechanical literature noise is no “Dreckeffect” in which “soll man nicht wühlen”” (after Wolfgang Pauli), but rather is “the ever flowing source of all that’s good and the cure of all ills” (after Karl Marlantes) … as far as efficient quantum simulation is concerned, anyway! 🙂
This contrasting view of noise can be summarized in two iatromechanical postulates (the first one weak and the second one stronger)
The weak postulate of quantum iatromechanics All naturally evolved biological processes can be simulated efficiently by classical computing resources
Here the feasibility of iatric simulational efficiency is computationally ascribed (consistent with quantum orthodoxy) to the noisy vacuum of a liquid-water environment.
The strong postulate of quantum iatromechanics All technologies that can be feasibly constructed by evolved biological organisms — as contrasted with hypothetical gedankentechnologies — can be simulated efficiently with classical computing resources
Here the feasibility of universal simulational efficiency is computationally ascribed (consistent with quantum orthodoxy) to the noisy vacuum of quantum electrodynamics; this strong postulate is simply the Extended Church-Turing Thesis (ECT), expressed in iatromechanical/Kalai-compatible terms.
Obviously, much more could be said — indeed many books can be and are being written — regarding the entangled relation of quantum celerity to quantum iatromechanics … and fortunately for young researchers especially, the entangled querencias of arXiv preprints and bioRXiv preprints are alive with people exploring and sharing these wonderful ideas! 🙂
Comment #21 October 27th, 2016 at 9:07 am
I’m wondering whether one can precisely define the parameters for a “fair” demonstration of quantum supremacy. It wouldn’t do to compare the quantum circuit to a simulation running on a laptop. It would also be unfair to pit the quantum circuit against the best supercomputer we have.
Maybe one could say that if the quantum circuit solves in 1 day a problem that takes 1 month to be solved in some dedicated classical hardware of comparable cost, quantum supremacy is convincingly demonstrated?
Comment #22 October 27th, 2016 at 9:18 am
For what it’s worth, I like “quantum celerity”. But maybe that something you should post on Preskill’s blog?
https://quantumfrontiers.com/author/preskill/
Comment #23 October 27th, 2016 at 3:07 pm
Jay, I have posted the suggestion supremacy->celerity to John Preskill’s Quantum Frontiers weblog, as a comment that concludes:
I’m posting this comment here, mainly because the Preskill/Kitaev course-notes are an excellent resource for students, but also because it’s not entirely clear (to me) whether Preskill’s 2012 “Supremacy Now” blog-essay is still accepting comments (the most recent previous comment dates back to 2012).
Comment #24 October 27th, 2016 at 4:57 pm
An experimental demonstration of what is infelicitously called quantum supremacy (I prefer “classical retardation”) would be way less earthshaking than the Higgs boson. It would be much more like the experimental demonstrations of Bell and CHSH violations: a validation of what we have every right to expect, based on the unblemished success of quantum theory so far. Discomfiting an annoying rear guard who feel, for no good reason they can name, that quantum computers gotta not work is less important than making a real scientific discovery like the Higgs. As I believe you have already emphasized, it is the opposite outcome—the discovery of some fundamental breakdown of quantum mechanics (e.g. by nonlinearity, physical collapse, etc) that prevents quantum computers from working as advertised—that would be earthshaking. And speaking of preventing something from working, I think that someone who uses language as carefully and effectively as you should eschew the biz-speak barbarism of using “showstopper” to mean an obstacle or roadblock, the opposite of its original theatrical meaning.
Comment #25 October 27th, 2016 at 5:28 pm
Charles #24: The trouble with that argument is that physicists also had every right to expect the Higgs to be there. Granted, they weren’t quite as certain of that as they are of QM, and there was one parameter (the mass) that was genuinely unknown. But finding the Higgs had a broadly similar character as experimental demonstrations of QM, in that anything other than the sought-after phenomenon would’ve been a tremendously greater scientific surprise than the phenomenon itself.
As for “showstopper,” Wiktionary gives me the following:
1. A performance or segment of a theatrical production that induces a positive audience reaction strong enough to pause the production.
2. Any impediment that prevents all further progress; especially a software bug that must be fixed before any further development is possible.
Usage notes
Ambiguous connotation, depending on context: very good or very bad.
Merriam-Webster also gives the sense that I used.
But, OK, I’ll duly note that even though I’ve got the dictionaries on my side, there are people who get annoyed by the use of “showstopper” to mean “obstacle” or “roadblock,” and I’ll substitute a different word whenever I remember to.
Comment #26 October 27th, 2016 at 11:45 pm
John Sidles #20: Being a language aficionado, I hope you won’t mind if I contact you for advice on some names I have coined (w.r.t. representation of uncertainty in data, propagation of uncertainty in calculations). Choosing names for new concepts is a tricky business.
Comment #27 October 28th, 2016 at 4:49 am
Hi Charles, everybody,
Greetings from Tel Aviv, it could be useful to give a brief account of my view on the matter (representing my work of the last decade or so).
A) Noisy quantum circuits with the standard modelling of noise and noisy BosonSampling represent a very low-level (or “retarded,” if you prefer) computational power.
B) In the small scale, this very low-level computational power cannot support quantum supremacy and cannot support quantum error-correction of the quality needed for quantum fault-tolerance.
C) This deems both quantum supremacy and quantum fault-tolerance impossible at all scales. It also leads to interesting consequences for modeling noisy quantum systems in the large scale.
You can read more about it in my Notices AMS paper “The quantum computer puzzle,” its expanded version on the arXive, and, regarding BosonSampling, my paper with Guy Kindler “Gaussian noise sensitivity and BosonSampling.” Item B) is coming now to test in the various experimental efforts to demonstrate “quantum supremacy” (that Scott talked about above) and efforts to demonstrate high quality encoded qubits.
In my view, a failure of “quantum supremacy” and “quantum fault-tolerance” is indeed an important possibility with important consequences! However, this failure does not account for some fundamental breakdown of quantum mechanics. Rather, “quantum supremacy” is an artifact of an incomplete account of the locality principle in the model of quantum circuits (and the other models Scott considered).
Of course, you need to account for locality because otherwise it is very easy to devise quantum evolutions (or even classical evolutions) that takes you directly from the question to the answer for computationally intractable problems. The standard noise model for quantum circuits does lead to an appropriate modeling of locality, but people overlooked the multi-scale analysis required for fully understanding this model.
Comment #28 November 1st, 2016 at 11:28 am
I am surprised that sampling has come this far indeed. I also don’t understand why people do not seem to invoke the approximate sampling -> BQP \subseteq AM result in the old paper of David and I. This result works for constant-depth circuits, IQP circuits or KLM/bosonsampling, as long as you know the probability for the output that you post-select on (which one knows in all these cases as one uses teleportation etc.). It is a more direct argument which may also be useful in showing how sampling is a sign-problem issue (so relate it to questions of StoqMA \subseteq AM and QMA).
Comment #29 November 1st, 2016 at 12:08 pm
Barbara #28: By coincidence, just yesterday I was finishing the introduction to a new paper on “complexity-theoretic foundations of quantum supremacy experiments” that a student and I are writing—and while writing that intro, I took pains to give you and David credit for having the first inkling of “the power of sampling-based quantum supremacy,” with your BQP⊆AM thing for constant-depth circuits in 2003. In retrospect, you should’ve gone just slightly further than you did, and said not only that you’d get BQP⊆AM (which, truthfully, we still don’t have any strong intuition for whether that’s likely or not in the unrelativized world), but that you’d even get PostBQP⊆BPPNP, which collapses PH! But the basic idea was totally there, and I’m sorry if I’ve forgotten to stress that in the past quite as much as I should have. Kudos.
Comment #30 November 1st, 2016 at 12:54 pm
i see 🙂 would be nice to see sampling being useful though.
Comment #31 November 1st, 2016 at 10:22 pm
Unless my study of history is completely wrong, Scott considers proving Gil Kalai’s view above wrong as probably the most important application of quantum supremacy.
Comment #32 November 2nd, 2016 at 10:47 am
For political reasons that are unnecessary to state, the phrase “Quantum Supremacy”, and especially the phrase “Quantum Supremacist” (of comment #11) have lost much of their lustre (for me anyway); moreover the countervailing phrases “Quantum Skepticism” and “Quantum Skeptic” now too seem unappealing and indescriptive.
In contrast, the uncapitalized phrases “quantum celerity” and (felicitously) the phrase “quantum celebrant” are (for me) gaining steadily in appeal, particularly in regard to teaching.
This is because all of us — Supremacists and Skeptics alike — are jointly cerebrating within a shared and wondrous world, in which “weak quantum celerity” is the postulate that classical computational resources suffice to solve efficiently an ever-broadening gyre of real-world quantum simulation / sampling / optimization problems; a gyre that encompasses in particular all of biology and all condensed matter technologies (as Quantum Skeptical arguments provide reason to hope).
“Strong quantum celerity” then is the postulate that quantum computational resources ingeniously solve at least some problems that are provably outside the widening gyre of weak qantum celerity (as the Quantum Supremacists thrillingly hope to demonstrate).
These conciliatory considerations are the motivating themes of a scary-story — just-now posted as a comment upon Gödel’s Lost Letter’s essay “Halloween Math Style” — which surveys some of the recent complexity-theory literature, with a view toward reminding students especially, that there’s nothing scary about algorithmic celerity, no matter whether that celerity is weak or strong, and no matter whether it is motivated by Supremacist versus Skeptical convictions, and no matter it us exhibited by classical versus quantum computational resources! 🙂
Comment #33 November 2nd, 2016 at 11:27 am
Scott:
“I like to say that for me, the #1 application of quantum computing is just disproving the people who say quantum computing is impossible”
.
Not sure why you say “just”, because “disproving the people who say…” is probably one of the hardest things to do in general! (e.g. climate change deniers).
The problem with “toy problems” is that there is usually no practical motivation/benefit for someone to try and optimize the corresponding classical approach (like for factorization)?
The ultimate proof is someone turning into a billionaire thanks to the supremacy of QC.
Comment #34 November 2nd, 2016 at 10:30 pm
A viable alternative strategy is to “convince the people who don’t say”, that is, people who are professionally secretive.
In this regard, the D-Wave Corporation has announced the formation of an independent Washington-based company called D-Wave Government Inc, whose governing board is entirely composed of “people who don’t say”. Specifically, the credentials of D-Wave Government’s directors have eminently qualify the board to receive Sensitive Compartmented Information (SCI) in the context of Special Access Programs (SAP), as follows:
• Assistant Secretary of Energy
• Assistant Secretary of the Air Force
• Assistant Secretary of the Navy
• Chair of the U.S. Geospatial Intelligence Foundation
• Deputy Director of the CIA for Science and Technology
• Deputy Under Secretary of Defense
for Science and Technology
• Director, Los Alamos National Laboratory
• Director, National Reconnaissance Office (#1: JK Harris)
• Director, National Reconnaissance Office (#2: DM Kerr)
• Executive Director of the National Security Agency
• Member, Defense Science Board
• President, Lockheed Martin Missiles and Space
• President, Lockheed Martin Special Programs
• Principal Deputy Director of National Intelligence
• Special Advisor to the U.S Strategic Command
• Vice Chair, MITRE Corporation Board of Trustees
Note that each of the D-Wave Government directors has filled multiple SCI/SAP-compatible management roles, and conversely, crucial SCI/SAP-compatible roles have been filled by multiple D-Wave Government directors.
What can the quantum information community infer from D-Wave’s roster? Not much … and that’s the point! 🙂
It is evident, however, that the cadre of researchers who are seeking to efficiently simulate the computational protocols of the Martinis Group’s “Characterizing quantum supremacy in near-term devices” (arXiv:1608.00263v2) — no matter whether their research allegiance is to weak or strong quantum celerity (per #32) — are investigating computational processes that the intelligence community cares deeply about, for reasons that may or may not be evident to the academic community.
Comment #35 November 5th, 2016 at 10:56 pm
Quantum celery is a much cruncher phrase than quantum celerity.
Comment #36 November 6th, 2016 at 1:25 am
Boaz Barak and Pablo Parrilo at Harvard, in parallel with David Steurer and Pravesh Kothari at Princeton, are giving a join seminar “Proofs, beliefs, and algorithms through the lens of sum-of-squares“. This seminar is based upon the work reported in the Barak/Steurer lecture “Sum-of-squares proofs and the quest toward optimal algorithms” (ICM, 2014).
Of general interest to Quantum Celebrants of all persuasions, and Shtetl Optimized readers in particular, was last Friday’s (March 4) lecture “Quantum entanglement, sum of squares, and the log rank conjecture”. Signing up via Piazza gives access to course notes like:
The above remarks can be appreciated in the broader context of the seminar, which is (from the ICM lecture, op cit):
Quantum Celebrators of both the weak and strong persuasions (per comment #32) will find plenty to celebrate in this fine seminar, for which this appreciation and thanks are extended to Boaz Barak, Pablo Parrilo, David Steurer and Pravesh Kothari, for their outstanding commitment of talent and effort, in generously sharing this work.