Archive for the ‘Speaking Truth to Parallelism’ Category

Slowly emerging from blog-hibervacation

Wednesday, July 21st, 2021

Alright everyone:

  1. Victor Galitski has an impassioned rant against out-of-control quantum computing hype, which I enjoyed and enthusiastically recommend, although I wished Galitski had engaged a bit more with the strongest arguments for optimism (e.g., the recent sampling-based supremacy experiments, the extrapolations that show gate fidelities crossing the fault-tolerance threshold within the next decade). Even if I’ve been saying similar things on this blog for 15 years, I clearly haven’t been doing so in a style that works for everyone. Quantum information needs as many people as possible who will tell the truth as best they see it, unencumbered by any competing interests, and has nothing legitimate to fear from that. The modern intersection of quantum theory and computer science has raised profound scientific questions that will be with us for decades to come. It’s a lily that need not be gilded with hype.
  2. Last month Limaye, Srinivasan, and Tavenas posted an exciting preprint to ECCC, which apparently proves the first (slightly) superpolynomial lower bound on the size of constant-depth arithmetic circuits, over fields of characteristic 0. Assuming it’s correct, this is another small victory in the generations-long war against the P vs. NP problem.
  3. I’m grateful to the Texas Democratic legislators who fled the state to prevent the legislature, a couple miles from my house, having a quorum to enact new voting restrictions, and who thereby drew national attention to the enormity of what’s at stake. It should go without saying that, if a minority gets to rule indefinitely by forcing through laws to suppress the votes of a majority that would otherwise unseat it, thereby giving itself the power to force through more such laws, etc., then we no longer live in a democracy but in a banana republic. And there’s no symmetry to the situation: no matter how terrified you (or I) might feel about wokeists and their denunciation campaigns, the Democrats have no comparable effort to suppress Republican votes. Alas, I don’t know of any solutions beyond the obvious one, of trying to deal the conspiracy-addled grievance party crushing defeats in 2022 and 2024.
  4. Added: Here’s the video of my recent Astral Codex Ten ask-me-anything session.

QC ethics and hype: the call is coming from inside the house

Saturday, March 20th, 2021

For years, I’d sometimes hear discussions about the ethics of quantum computing research. Quantum ethics!

When the debates weren’t purely semantic, over the propriety of terms like “quantum supremacy” or “ancilla qubit,” they were always about chin-strokers like “but what if cracking RSA encryption gives governments more power to surveil their citizens? or what if only a few big countries or companies get quantum computers, thereby widening the divide between haves and have-nots?” Which, OK, conceivably these will someday be issues. But, besides barely depending on any specific facts about quantum computing, these debates always struck me as oddly safe, because the moral dilemmas were so hypothetical and far removed from us in time.

I confess I may have even occasionally poked fun when asked to expound on quantum ethics. I may have commented that quantum computers probably won’t kill anyone unless a dilution refrigerator tips over onto their head. I may have asked forgiveness for feeding custom-designed oracles to BQP and QMA, without first consulting an ethics committee about the long-term effects on those complexity classes.

Now fate has punished me for my flippancy. These days, I really do feel like quantum computing research has become an ethical minefield—but not for any of the reasons mentioned previously. What’s new is that millions of dollars are now potentially available to quantum computing researchers, along with equity, stock options, and whatever else causes “ka-ching” sound effects and bulging eyes with dollar signs. And in many cases, to have a shot at such riches, all an expert needs to do is profess optimism that quantum computing will have revolutionary, world-changing applications and have them soon. Or at least, not object too strongly when others say that.

Some of today’s rhetoric will of course remind people of the D-Wave saga, which first brought this blog to prominence when it began in earnest in 2007. Quantum computers, we hear now as then, will soon leave the Earth’s fastest supercomputers in the dust. They’re going to harness superposition to try all the exponentially many possible solutions at once. They’ll crack the Traveling Salesman Problem, and will transform machine learning and AI beyond recognition. Meanwhile, simulations of quantum systems will be key to solving global warming and cancer.

Despite the parallels, though, this new gold rush doesn’t feel to me like the D-Wave one, which seems in retrospect like just a little dry run. If I had to articulate what’s new in one sentence, it’s that this time “the call is coming from inside the house.” Many of the companies making wildly overhyped claims are recognized leaders of the field. They have brilliant quantum computing theorists and experimentalists on their staff with impeccable research records. Some of those researchers are among my best friends. And even when I wince at the claims of near-term applications, in many cases (especially with quantum simulation) the claims aren’t obviously false—we won’t know for certain until we try it and see! It’s genuinely gotten harder to draw the line between defensible optimism and exaggerations verging on fraud.

Indeed, this time around virtually everyone in QC is “complicit” to a greater or lesser degree. I, too, have accepted compensation to consult on quantum computing topics, to give talks at hedge funds, and in a few cases to serve as a scientific adviser to quantum computing startups. I tell myself that, by 2021 standards, this stuff is all trivial chump change—a few thousands of dollars here or there, to expound on the same themes that I already discuss free of charge on this blog. I actually get paid to dispel hype, rather than propagate it! I tell myself that I’ve turned my back on the orders of magnitude more money available to those willing to hitch their scientific reputations to the aspirations of this or that specific QC company. (Yes, this blog, and my desire to preserve its intellectual independence and credibility, might well be costing me millions!)

But, OK, some would argue that accepting any money from QC companies or QC investors just puts you at the top of a slope with unabashed snake-oil salesmen at the bottom. With the commercialization of our field that started around 2015, there’s no bright line anymore marking the boundary between pure scientific curiosity and the pursuit of filthy lucre; it’s all just points along a continuum. I’m not sure that these people are wrong.

As some of you might’ve seen already, IonQ, the trapped-ion QC startup that originated from the University of Maryland, is poised to have the first-ever quantum computing IPO—a so-called “SPAC IPO,” which while I’m a financial ignoramus, apparently involves merging with a shell company and thereby bypassing the SEC’s normal IPO rules. Supposedly they’re seeking $650 million in new funding and a $2 billion market cap. If you want to see what IonQ is saying about QC to prospective investors, click here. Lacking any choice in the matter, I’ll probably say more about these developments in a future post.

Meanwhile, PsiQuantum, the Palo-Alto-based optical QC startup, has said that it’s soon going to leave “stealth mode.” And Amazon, Microsoft, Google, IBM, Honeywell, and other big players continue making large investments in QC—treating it, at least rhetorically, not at all like blue-sky basic research, but like a central part of their future business plans.

All of these companies have produced or funded excellent QC research. And of course, they’re all heterogeneous, composed of individuals who might vehemently disagree with each other about the near- or long-term prospects of QC. And yet all of them have, at various times, inspired reflections in me like the ones in this post.

I regret that this post has no clear conclusion. I’m still hashing things out, solicing thoughts from my readers and friends. Speaking of which: this coming Monday, March 22, at 8-10pm US Eastern time, I’ve decided to hold a discussion around these issues on Clubhouse—my “grand debut” on that app, and an opportunity to see whether I like it or not! My friend Adam Brown will moderate the discussion; other likely participants will be John Horgan, George Musser, Michael Nielsen, and Matjaž Leonardis. If you’re on Clubhouse, I hope to see you there!

Update (March 22): Read this comment by “FB” if you’d like to understand how we got to this point.

Sufficiently amusing that I had no choice

Thursday, January 21st, 2021

From quantum supremacy to classical fallacy

Wednesday, October 2nd, 2019

Retrospective Comment (Dec. 26, 2019): While I basically stand by what I wrote in this post, I wanted to call attention to the fact that, in its aftermath, one of the authors of the p-bit paper—Kerem Camsari—displayed a striking degree of intellectual courage and honesty. He showed up in the comments section to defend the motivation for the p-bit model, but also to concede the points I’d raised about scaling. Notably, on some matters, he explicitly broke with his own coauthors. He treated having his paper harshly criticized on Shtetl-Optimized not as a personal attack, but as an opportunity to learn and grow. I’m not sure that I would’ve been able to do the same in his shoes, and I regard it as one of the happier outcomes in this blog’s history. –SA

Maybe I should hope that people never learn to distinguish for themselves which claimed breakthroughs in building new forms of computation are obviously serious, and which ones are obviously silly. For as long as they don’t, this blog will always serve at least one purpose. People will cite it, tweet it, invoke its “authority,” even while from my point of view, I’m offering nothing more intellectually special than my toddler does when he calls out “moo-moo cow! baa-baa sheep!” as we pass them on the road.

But that’s too pessimistic. Sure, most readers must more-or-less already know what I’ll say about each thing: that Google’s quantum supremacy claim is serious, that memcomputing to solve NP-complete problems is not, etc. Even so, I’ve heard from many readers that this blog was at least helpful for double-checking their initial impressions, and for making common knowledge what before had merely been known to many. I’m fine for it to continue serving those roles.

Last week, even as I dealt with fallout from Google’s quantum supremacy leak, I also got several people asking me to comment on a Nature paper entitled Integer factorization using stochastic magnetic tunnel junctions (warning: paywalled). See also here for a university press release.

The authors report building a new kind of computer based on asynchronously updated “p-bits” (probabilistic bits). A p-bit is “a robust, classical entity fluctuating in time between 0 and 1, which interacts with other p-bits … using principles inspired by neural networks.” They build a device with 8 p-bits, and use it to factor integers up to 945. They present this as another “unconventional computation scheme” alongside quantum computing, and as a “potentially scalable hardware approach to the difficult problems of optimization and sampling.”

A commentary accompanying the Nature paper goes much further still—claiming that the new factoring approach, “if improved, could threaten data encryption,” and that resources should now be diverted from quantum computing to this promising new idea, one with the advantages of requiring no refrigeration or maintenance of delicate entangled states. (It should’ve added: and how big a number has Shor’s algorithm factored anyway, 21? Compared to 945, that’s peanuts!)

Since I couldn’t figure out a gentler way to say this, here goes: it’s astounding that this paper and commentary made it into Nature in the form that they did. Juxtaposing Google’s sampling achievement with p-bits, as several of my Facebook friends did last week, is juxtaposing the Wright brothers with some guy bouncing around on a pogo stick.

If you were looking forward to watching me dismantle the p-bit claims, I’m afraid you might be disappointed: the task is over almost the moment it begins. “p-bit” devices can’t scalably outperform classical computers, for the simple reason that they are classical computers. A little unusual in their architecture, but still well-covered by the classical Extended Church-Turing Thesis. Just like with the quantum adiabatic algorithm, an energy penalty is applied to coax the p-bits into running a local optimization algorithm: that is, making random local moves that preferentially decrease the number of violated constraints. Except here, because the whole evolution is classical, there doesn’t seem to be even the pretense that anything is happening that a laptop with a random-number generator couldn’t straightforwardly simulate.

Even so, I wouldn’t be writing this post if you opened the paper and it immediately said, in effect, “look, we know. You’re thinking that this is just yet another stochastic local optimization method, which could clearly be simulated efficiently on a conventional computer, thereby putting it into a different conceptual universe from quantum computing. You’re thinking that factoring an n-bit integer will self-evidently take exp(n) time by this method, as compared to exp(n1/3) for the Number Field Sieve, and that no crypto is in even remote danger from this. But here’s why you should still be interested in our p-bit model: because of other advantages X, Y, and Z.” Alas, in vain one searches the whole paper, and the lengthy supplementary material, and the commentary, for any acknowledgment of the pachyderm in the pagoda. Not an asymptotic runtime scaling in sight. Quantum computing is there, but stripped of the theoretical framework that gives it its purpose.

That silence, in the pages of Naturethat’s the part that convinced me that, while on the negative side this blog seems to have accomplished nothing for the world in 14 years of existence, on the positive side it will likely have a role for decades to come.

Update: See a response in the comments, which I appreciated, from Kerem Cansari (one of the authors of the paper), and my response to the response.

(Partly) Unrelated Announcement #1: My new postdoc, Andrea Rocchetto, had the neat idea of compiling a Quantum Computing Fact Sheet: a quick “Cliffs Notes” for journalists, policymakers, and others looking to get the basics right. The fact sheet might grow in the future, but in the meantime, check it out! Or at a more popular level, try the Quantum Atlas made by folks at the University of Maryland.

Unrelated Announcement #2: Daniel Wichs asked me to give a shout-out to a new Conference on Information-Theoretic Cryptography, to be held June 17-19 in Boston.

Third Announcement: Several friends asked me to share that Prof. Peter Wittek, quantum computing researcher at the University of Toronto, has gone missing in the Himalayas. Needless to say we hope for his safe return.

Just says in P

Wednesday, April 17th, 2019

Recently a Twitter account started called justsaysinmice. The only thing this account does, is to repost breathless news articles about medical research breakthroughs that fail to mention that the effect in question was only observed in mice, and then add the words “IN MICE” to them. Simple concept, but it already seems to be changing the conversation about science reporting.

It occurred to me that we could do something analogous for quantum computing. While my own deep-seated aversion to Twitter prevents me from doing it myself, which of my readers is up for starting an account that just reposts one overhyped QC article after another, while appending the words “A CLASSICAL COMPUTER COULD ALSO DO THIS” to each one?

Quantum computing for policymakers and philosopher-novelists

Wednesday, June 6th, 2018

Last week Rebecca Newberger Goldstein, the great philosopher and novelist who I’m privileged to call a friend, wrote to ask me whether I “see any particular political and security problems that are raised by quantum computing,” to help her prepare for a conference she’d be attending in which that question would be discussed.  So I sent her the response below, and then decided that it might be of broader interest.

Shtetl-Optimized regulars and QC aficionados will find absolutely nothing new here—move right along, you’ve been warned.  But I decided to post my (slightly edited) response to Rebecca anyway, for two reasons.  First, so I have something to send anyone who asks me the same question in the future—something that, moreover, as Feynman said about the Feynman Lectures on Physics, contains views “not far from my own.”  And second, because, while of course I’ve written many other popular-level quantum computing essays, with basically all of them, my goal was to get the reader to hear the music, so to speak.  On reflection, though, I think there might also be some value in a piece for business and policy people (not to mention humanist intellectuals) that sets aside the harmony of the interfering amplitudes, and just tries to convey some of the words to the song without egregious howlers—which is what Rebecca’s question about “political and security problems” forced me to do.  This being quantum computing, of course, much of what one finds in the press doesn’t even get the lyrics right!  So without further ado:


Dear Rebecca,

If you want something serious and thoughtful about your question, you probably won’t do much better than the recent essay “The Potential Impact of Quantum Computers on Society,” by my longtime friend and colleague Ronald de Wolf.

To elaborate my own thoughts, though: I feel like the political and security problems raised by quantum computing are mostly the usual ones raised by any new technology (national prestige competitions, haves vs have-nots, etc)—but with one added twist, coming from quantum computers’ famous ability to break our current methods for public-key cryptography.

As Ronald writes, you should think of a quantum computer as a specialized device, which is unlikely to improve all or even most of what we do with today’s computers, but which could give dramatic speedups for a few specific problems.  There are three most important types of applications that we know about today:

(1) Simulation of quantum physics and chemistry. This was Richard Feynman’s original application when he proposed quantum computing in 1981, and I think it’s still the most important one economically.  Having a fast, general-purpose quantum simulator could help a lot in designing new drugs, materials, solar cells, high-temperature superconductors, chemical reactions for making fertilizer, etc.  Obviously, these are not applications like web browsing or email that will directly affect the everyday computer user.  But they’re areas where you’d only need a few high-profile successes to generate billions of dollars of value.

(2) Breaking existing public-key cryptography.  This is the most direct political and security implication.  Every time you visit a website that begins with “https,” the authentication and encryption—including, e.g., protecting your credit card number—happen using a cryptosystem based on factoring integers or discrete logarithms or a few other related problems in number theory.  A full, universal quantum computer, if built, is known to be able to break all of this.

Having said that, we all know today that hackers, and intelligence agencies, can compromise people’s data in hundreds of more prosaic ways than by building a quantum computer!  Usually they don’t even bother trying to break the encryption, relying instead on poor implementations and human error.

And it’s also important to understand that a quantum computer wouldn’t mean the end of online security.  There are public-key cryptosystems currently under development—most notably, those based on lattices—that are believed to resist attack even by quantum computers; NIST is planning to establish standards for these systems over the next few years.  Switching to these “post-quantum” systems would be a significant burden, much like fixing the Y2K bug (and they’re also somewhat slower than our current systems), but hopefully it would only need to happen once.

As you might imagine, there’s some interest in switching to post-quantum cryptosystems even now—for example, if you wanted to encrypt messages today with some confidence they won’t be decrypted even 30 years from now.  Google did a trial of a post-quantum cryptosystem two years ago.  On the other hand, given that a large fraction of web servers still use 512-bit “export grade” cryptography that was already breakable in the 1990s (good news: commenter Viktor Dukhovni tells me that this has now been mostly fixed, since security experts, including my childhood friend Alex Halderman, raised a stink about it a few years ago), it’s a safe bet that getting everyone to upgrade would take quite a long time, even if the experts agreed (which they don’t yet) which of the various post-quantum cryptosystems should become the new standard.  And since, as I said, most attacks target mistakes in implementation rather than the underlying cryptography, we should expect any switch to post-quantum cryptography to make security worse rather than better in the short run.

As a radical alternative to post-quantum crypto, there’s also (ironically enough) quantum cryptography, which doesn’t work over the existing Internet—it requires setting up new communications infrastructure—but which has already been deployed in a tiny number of places, and which promises security based only on quantum physics (and, of course, on the proper construction of the hardware), as opposed to mathematical problems that a quantum computer or any other kind of computer could potentially solve.  According to a long-running joke (or not-quite-joke) in our field, one of the central applications of quantum computing will be to create demand for quantum cryptography!

Finally, there’s private-key cryptography—i.e., the traditional kind, where the sender and recipient meet in secret to agree on a key in advance—which is hardly threatened by quantum computing at all: you can achieve the same level of security as before, we think, by simply doubling the key lengths.  If there’s no constraint on key length, then the ultimate here is the one-time pad, which when used correctly, is theoretically unbreakable by anything short of actual physical access to the sender or recipient (e.g., hacking their computers, or beating down their doors with an ax).  But while private-key crypto might be fine for spy agencies, it’s impractical for widespread deployment on the Internet, unless we also have a secure way to distribute the keys.  This is precisely where public-key crypto typically gets used today, and where quantum crypto could in principle be used in the future: to exchange private keys that are then used to encrypt and decrypt the actual data.

I should also mention that, because it breaks elliptic-curve-based signature schemes, a quantum computer might let a thief steal billions of dollars’ worth of Bitcoin.  Again, this could in principle be fixed by migrating Bitcoin (and other cryptocurrencies) to quantum-resistant cryptographic problems, but that hasn’t been done yet.

(3) Optimization and machine learning.  These are obviously huge application areas for industry, defense, and pretty much anything else.  The main issue is just that we don’t know how to get as large a speedup from a quantum computer as we’d like for these applications.  A quantum computer, we think, will often be able to solve optimization and machine learning problems in something like the square root of the number of steps that would be needed classically, using variants of what’s called Grover’s algorithm.  So, that’s significant, but it’s not the exponential speedup and complete game-changer that we’d have for quantum simulation or for breaking public-key cryptography.  Most likely, a quantum computer will be able to achieve exponential speedups for these sorts of problems only in special cases, and no one knows yet how important those special cases will be in practice.  This is a still-developing research area—there might be further theoretical breakthroughs (in inventing new quantum algorithms, analyzing old algorithms, matching the performance of the quantum algorithms by classical algorithms, etc.), but it’s also possible that we won’t really understand the potential of quantum computers for these sorts of problems until we have the actual devices and can test them out.

 

As for how far away all this is: given the spectacular progress by Google and others over the last few years, my guess is that we’re at most a decade away from some small, special-purpose quantum computers (with ~50-200 qubits) that could be useful for quantum simulation.  These are what the physicist John Preskill called “Noisy Intermediate Scale Quantum” (NISQ) computers in his excellent recent essay.

However, my guess is also that it will take longer than that to get the full, error-corrected, universal quantum computers that would be needed for optimization and (most relevant to your question) for breaking public-key cryptography.  Currently, the engineering requirements for a “full, universal” quantum computer look downright scary—so we’re waiting either for further breakthroughs that would cut the costs by a few more orders of magnitude (which, by their very nature, can’t be predicted), or for some modern-day General Groves and Oppenheimer who’d be licensed to spend however many hundreds of billions of dollars it would take to make it happen sooner.

The race to build “NISQ” devices has been heating up, with a shift from pure academic research to venture capitalists and industrial efforts just within the last 4-5 years, noticeably changing the character of our field.

In this particular race, I think that the US is the clear world leader right now—specifically, Google, IBM, Intel, Microsoft, University of Maryland / NIST, and various startups—followed by Europe (with serious experimental efforts in the Netherlands, Austria, and the UK among other places).  Here I should mention that the EU has a new 1-billion-Euro initiative in quantum information.  Other countries that have made or are now making significant investments include Canada, Australia, China, and Israel.  Surprisingly, there’s been very little investment in Russia in this area, and less than I would’ve expected in Japan.

China is a very interesting case.  They’ve chosen to focus less on quantum computing than on the related areas of quantum communication and cryptography, where they’ve become the world leader.  Last summer, in a big upset, China launched the first satellite (“Micius”) specifically for quantum communications, and were able to use it to do quantum cryptography and to distribute entanglement over thousands of miles (from one end of China to the other), the previous record being maybe 100 miles.  If the US has anything comparable to this, it isn’t publicly known (my guess is that we don’t).

This past year, there were hearings in Congress about the need for the US to invest more in quantum information, for example to keep up with China, and it looks likely to happen.  As indifferent or hostile as the current administration has been toward science more generally, the government and defense people I’ve met are very much on board with quantum information—often more so than I am!  I’ve even heard China’s Micius satellite referred to as the “quantum Sputnik,” the thing that will spur the US and others to spend much more to keep up.

As you’d imagine, part of me is delighted that something so abstruse, and interesting for fundamental science, and close to my heart, is now getting attention and funding at this level.  But part of me is worried by how much of the current boom I know to be fueled by misconceptions, among policymakers and journalists and the general public, about what quantum computers will be able to do for us once we have them.  Basically, people think they’ll be magic oracles that will solve all problems faster, rather than just special classes of problems like the ones I enumerated above—and that they’ll simply allow the continuation of the Moore’s Law that we know and love, rather than being something fundamentally different.  I’ve been trying to correct these misconceptions, on my blog and elsewhere, to anyone who will listen, for all the good that’s done!  In any case, the history of AI reminds us that a crash could easily follow the current boom-time, if the results of quantum computing research don’t live up to people’s expectations.

I guess there’s one final thing I’ll say.  Quantum computers are sometimes analogized to nuclear weapons, as a disruptive technology with implications for global security that scientists theorized about decades before it became technically feasible.  But there are some fundamental differences.  Most obviously: the deterrent value of a nuclear weapon comes if everyone knows you have it but you never need to use it, whereas the intelligence value of a quantum computer comes if you use it but no one knows you have it.

(Which is related to how the Manhattan Project entered the world’s consciousness in August 1945, whereas Bletchley Park—which was much more important to the actual winning of WWII—remained secret until the 1970s.)

As I said before, once your adversaries realized that you had a universal quantum computer, or might have one soon, they could switch to quantum-resistant forms of encryption, at least for their most sensitive secrets—in which case, as far as encryption was concerned, everyone would be more-or-less back where they started.  Such a switch would be onerous, cost billions of dollars, and (in practice) probably open up its own security holes unrelated to quantum computing.  But we think we already basically understand how to do it.

This is one reason why, even in a hypothetical future where hostile powers got access to quantum computers (and despite the past two years, I still don’t think of the US as a “hostile power”—I mean, like, North Korea or ISIS or something…!)—even in that future, I’d still be much less concerned about the hostile powers having this brand-new technology, than I’d be about their having the generations-old technology of fission and fusion bombs.

Best,
Scott


Unrelated Update (June 8): Ian Tierney asked me to advertise a Kickstarter for a short film that he’s planning to make about Richard Feynman, and a letter that he wrote to his first wife Arlene after she died.

Review of Vivek Wadhwa’s Washington Post column on quantum computing

Tuesday, February 13th, 2018

Various people pointed me to a Washington Post piece by Vivek Wadhwa, entitled “Quantum computers may be more of an immiment threat than AI.”  I know I’m late to the party, but in the spirit of Pete Wells’ famous New York Times “review” of Guy Fieri’s now-closed Times Square restaurant, I have a few questions that have been gnawing at me:

Mr. Wadhwa, when you decided to use the Traveling Salesman Problem as your go-to example of a problem that quantum computers can solve quickly, did the thought ever cross your mind that maybe you should look this stuff up first—let’s say, on Wikipedia?  Or that you should email one person—just one, anywhere on the planet—who works in quantum algorithms?

When you wrote of the Traveling Salesman Problem that “[i]t would take a laptop computer 1,000 years to compute the most efficient route between 22 cities”—how confident are you about that?  Willing to bet your house?  Your car?  How much would it blow your mind if I told you that a standard laptop, running a halfway decent algorithm, could handle 22 cities in a fraction of a second?

When you explained that quantum computing is “equivalent to opening a combination lock by trying every possible number and sequence simultaneously,” where did this knowledge come from?  Did it come from the same source you consulted before you pronounced the death of Bitcoin … in January 2016?

Had you wanted to consult someone who knew the first thing about quantum computing, the subject of your column, would you have been able to use a search engine to find one?  Or would you have simply found another “expert,” in the consulting or think-tank worlds, who “knew” the same things about quantum computing that you do?

Incidentally, when you wrote that quantum computing “could pose a greater burden on businesses than the Y2K computer bug did toward the end of the ’90s,” were you trying to communicate how large the burden might be?

And when you wrote that

[T]here is substantial progress in the development of algorithms that are “quantum safe.” One promising field is matrix multiplication, which takes advantage of the techniques that allow quantum computers to be able to analyze so much information.

—were you generating random text using one of those Markov chain programs?  If not, then what were you referring to?

Would you agree that the Washington Post has been a leader in investigative journalism exposing Trump’s malfeasance?  Do you, like me, consider them one of the most important venues on earth for people to be able to trust right now?  How does it happen that the Washington Post publishes a quantum computing piece filled with errors that would embarrass a high-school student doing a term project (and we won’t even count the reference to Stephen “Hawkings”—that’s a freebie)?

Were the fact-checkers home with the flu?  Did they give your column a pass simply because it was “perspective” rather than news?  Or did they trust you as a widely-published technology expert?  How does one become such an expert, anyway?

Thanks!


Update (Feb. 21): For casual readers, Vivek Wadhwa quickly came into the comments section to try to defend himself—before leaving in a huff as a chorus of commenters tried to explain why he was wrong. As far as I know, he has not posted any corrections to his Washington Post piece. Wadhwa’s central defense was that he was simply repeating what Michelle Simmons, a noted quantum computing experimentalist in Australia, said in various talks in YouTube—which turns out to be largely true (though Wadhwa said explicitly that quantum computers could efficiently solve TSP, while Simmons mostly left this as an unstated implication). As a result, while Wadhwa should obviously have followed the journalistic practice of checking incredible-sounding claims—on Wikipedia if nowhere else!—before repeating them in the Washington Post, I now feel that Simmons shares in the responsibility for this. As John Preskill tweeted, an excellent lesson to draw from this affair is that everyone in our field needs to be careful to say things that are true when speaking to the public.

Practicing the modus ponens of Twitter

Monday, January 29th, 2018

I saw today that Ryan Lackey generously praised my and Zach Weinersmith’s quantum computing SMBC comic on Twitter:

Somehow this SMBC comic is the best explanation of quantum computing for non-professionals that I’ve ever found

To which the venture capitalist Matthew Ocko replied, in another tweet:

Except Scott Aaronson is a surly little troll who has literally never built anything at all of meaning. He’s a professional critic of braver people.  So, no, this is not a good explanation – anymore than Jeremy Rifkin on CRISPR would be… ????

Now, I don’t mind if Ocko hates me, and also hates my and Zach’s comic.  What’s been bothering me is just the logic of his tweet.  Like: what did he have in his head when he wrote the word “So”?  Let’s suppose for the sake of argument that I’m a “surly little troll,” and an ax murderer besides.  How does it follow that my explanation of quantum computing wasn’t good?  To reach that stop in proposition-space, wouldn’t one still need to point to something wrong with the explanation?

But I’m certain that my inability to understand this is just another of my many failings.  In a world where Trump is president, bitcoin is valued at $11,000 when I last checked, and the attack-tweet has fully replaced the argument, it’s obvious that those of us who see a word like “so” or “because,” and start looking for the inferential step, are merely insufficiently brave.  For godsakes, I’m not even on Twitter!  I’m a sclerotic dinosaur who needs to get with the times.

But maybe I, too, could learn the art of the naked ad-hominem.  Let me try: from a Google search, we learn that Ocko is an enthusiastic investor in D-Wave.  Is it possible he’s simply upset that there’s so much excitement right now in experimental quantum computing—including “things of meaning” being built by brave people, at Google and IBM and Rigetti and IonQ and elsewhere—but that virtually none of this involves D-Wave, whose devices remain interesting from various physics and engineering standpoints, but still fail to achieve any clear quantum speedups, just as the professional critics predicted?  Is he upset that the brave system-builders who are racing finally to achieve quantum computational supremacy over the next year, are the ones who actually interacted with academic researchers (sorry: surly little trolls), and listened to what they said?  Who understood, for example, why scaling up to 50+ qubits only made a lot of sense once you had one or two qubits that at least behaved well enough in isolation—which, after years of heroic effort, many of these system-builders now do?

How’d I do?  Was there still too much argument there for the world of 2018?

Insert D-Wave Post Here

Thursday, March 16th, 2017

In the two months since I last blogged, the US has continued its descent into madness.  Yet even while so many certainties have proven ephemeral as the morning dew—the US’s autonomy from Russia, the sanity of our nuclear chain of command, the outcome of our Civil War, the constraints on rulers that supposedly set us apart from the world’s dictator-run hellholes—I’ve learned that certain facts of life remain constant.

The moon still waxes and wanes.  Electrons remain bound to their nuclei.  P≠NP proofs still fill my inbox.  Squirrels still gather acorns.  And—of course!—people continue to claim big quantum speedups using D-Wave devices, and those claims still require careful scrutiny.

With that preamble, I hereby offer you eight quantum computing news items.


Cathy McGeoch Episode II: The Selby Comparison

On January 17, a group from D-Wave—including Cathy McGeoch, who now works directly for D-Wave—put out a preprint claiming a factor-of-2500 speedup for the D-Wave machine (the new, 2000-qubit one) compared to the best classical algorithms.  Notably, they wrote that the speedup persisted when they compared against simulated annealing, quantum Monte Carlo, and even the so-called Hamze-de Freitas-Selby (HFS) algorithm, which was often the classical victor in previous performance comparisons against the D-Wave machine.

Reading this, I was happy to see how far the discussion has advanced since 2013, when McGeoch and Cong Wang reported a factor-of-3600 speedup for the D-Wave machine, but then it turned out that they’d compared only against classical exact solvers rather than heuristics—a choice for which they were heavily criticized on this blog and elsewhere.  (And indeed, that particular speedup disappeared once the classical computer’s shackles were removed.)

So, when people asked me this January about the new speedup claim—the one even against the HFS algorithm—I replied that, even though we’ve by now been around this carousel several times, I felt like the ball was now firmly in the D-Wave skeptics’ court, to reproduce the observed performance classically.  And if, after a year or so, no one could, that would be a good time to start taking seriously that a D-Wave speedup might finally be here to stay—and to move on to the next question, of whether this speedup had anything to do with quantum computation, or only with the building of a piece of special-purpose optimization hardware.


A&M: Annealing and Matching

As it happened, it only took one month.  On March 2, Salvatore Mandrà, Helmut Katzgraber, and Creighton Thomas put up a response preprint, pointing out that the instances studied by the D-Wave group in their most recent comparison are actually reducible to the minimum-weight perfect matching problem—and for that reason, are solvable in polynomial time on a classical computer.   Much of Mandrà et al.’s paper just consists of graphs, wherein they plot the running times of the D-Wave machine and of a classical heuristic on the relevant instances—clearly all different flavors of exponential—and then Edmonds’ matching algorithm from the 1960s, which breaks away from the pack into polynomiality.

But let me bend over backwards to tell you the full story.  Last week, I had the privilege of visiting Texas A&M to give a talk.  While there, I got to meet Helmut Katzgraber, a condensed-matter physicist who’s one of the world experts on quantum annealing experiments, to talk to him about their new response paper.  Helmut was clear in his prediction that, with only small modifications to the instances considered, one could see similar performance by the D-Wave machine while avoiding the reduction to perfect matching.  With those future modifications, it’s possible that one really might see a D-Wave speedup that survived serious attempts by skeptics to make it go away.

But Helmut was equally clear in saying that, even in such a case, he sees no evidence at present that the speedup would be asymptotic or quantum-computational in nature.  In other words, he thinks the existing data is well explained by the observation that we’re comparing D-Wave against classical algorithms for Ising spin minimization problems on Chimera graphs, and D-Wave has heroically engineered an expensive piece of hardware specifically for Ising spin minimization problems on Chimera graphs and basically nothing else.  If so, then the prediction would be that such speedups as can be found are unlikely to extend either to more “practical” optimization problems—which need to be embedded into the Chimera graph with considerable losses—or to better scaling behavior on large instances.  (As usual, as long as the comparison is against the best classical algorithms, and as long as we grant the classical algorithm the same non-quantum advantages that the D-Wave machine enjoys, such as classical parallelism—as Rønnow et al advocated.)

Incidentally, my visit to Texas A&M was partly an “apology tour.”  When I announced on this blog that I was moving from MIT to UT Austin, I talked about the challenge and excitement of setting up a quantum computing research center in a place that currently had little quantum computing for hundreds of miles around.  This thoughtless remark inexcusably left out not only my friends at Louisiana State (like Jon Dowling and Mark Wilde), but even closer to home, Katzgraber and the others at Texas A&M.  I felt terrible about this for months.  So it gives me special satisfaction to have the opportunity to call out Katzgraber’s new work in this post.  In football, UT and A&M were longtime arch-rivals, but when it comes to the appropriate level of skepticism to apply to quantum supremacy claims, the Texas Republic seems remarkably unified.


When 15 MilliKelvin is Toasty

In other D-Wave-related scientific news, on Monday night Tameem Albash, Victor Martin-Mayer, and Itay Hen put out a preprint arguing that, in order for quantum annealing to have any real chance of yielding a speedup over classical optimization methods, the temperature of the annealer should decrease at least like 1/log(n), where n is the instance size, and more likely like 1/nβ (i.e., as an inverse power law).

If this is correct, then cold as the D-Wave machine is, at 0.015 degrees or whatever above absolute zero, it still wouldn’t be cold enough to see a scalable speedup, at least not without quantum fault-tolerance, something that D-Wave has so far eschewed.  With no error-correction, any constant temperature that’s above zero would cause dangerous level-crossings up to excited states when the instances get large enough.  Only a temperature that actually converged to zero as the problems got larger would suffice.

Over the last few years, I’ve heard many experts make this exact same point in conversation, but this is the first time I’ve seen the argument spelled out in a paper, with explicit calculations (modulo assumptions) of the rate at which the temperature would need to go to zero for uncorrected quantum annealing to be a viable path to a speedup.  I lack the expertise to evaluate the calculations myself, but any experts who’d like to share their insight in the comments section are “warmly” (har har) invited.


“Their Current Numbers Are Still To Be Checked”

As some of you will have seen, The Economist now has a sprawling 10-page cover story about quantum computing and other quantum technologies.  I had some contact with the author while the story was in the works.

The piece covers a lot of ground and contains many true statements.  It could be much worse.

But I take issue with two things.

First, The Economist claims: “What is notable about the effort [to build scalable QCs] now is that the challenges are no longer scientific but have become matters of engineering.”  As John Preskill and others pointed out, this is pretty far from true, at least if we interpret the claim in the way most engineers and businesspeople would.

Yes, we know the rules of quantum mechanics, and the theory of quantum fault-tolerance, and a few promising applications; and the basic building blocks of QC have already been demonstrated in several platforms.  But if (let’s say) someone were to pony up $100 billion, asking only for a universal quantum computer as soon as possible, I think the rational thing to do would be to spend initially on a frenzy of basic research: should we bet on superconducting qubits, trapped ions, nonabelian anyons, photonics, a combination thereof, or something else?  (Even that is far from settled.)  Can we invent better error-correcting codes and magic state distillation schemes, in order to push the resource requirements for universal QC down by three or four orders of magnitude?  Which decoherence mechanisms will be relevant when we try to do this stuff at scale?  And of course, which new quantum algorithms can we discover, and which new cryptographic codes resistant to quantum attack?

The second statement I take issue with is this:

“For years experts questioned whether the [D-Wave] devices were actually exploiting quantum mechanics and whether they worked better than traditional computers.  Those questions have since been conclusively answered—yes, and sometimes”

I would instead say that the answers are:

  1. depends on what you mean by “exploit” (yes, there are quantum tunneling effects, but do they help you solve problems faster?), and
  2. no, the evidence remains weak to nonexistent that the D-Wave machine solves anything faster than a traditional computer—certainly if, by “traditional computer,” we mean a device that gets all the advantages of the D-Wave machine (e.g., classical parallelism, hardware heroically specialized to the one type of problem we’re testing on), but no quantum effects.

Shortly afterward, when discussing the race to achieve “quantum supremacy” (i.e., a clear quantum computing speedup for some task, not necessarily a useful one), the Economist piece hedges: “D-Wave has hinted it has already [achieved quantum supremacy], but has made similar claims in the past; their current numbers are still to be checked.”

To me, “their current numbers are still to be checked” deserves its place alongside “mistakes were made” among the great understatements of the English language—perhaps a fitting honor for The Economist.


Defeat Device

Some of you might also have seen that D-Wave announced a deal with Volkswagen, to use D-Wave machines for traffic flow.  I had some advance warning of this deal, when reporters called asking me to comment on it.  At least in the materials I saw, no evidence is discussed that the D-Wave machine actually solves whatever problem VW is interested in faster than it could be solved with a classical computer.  Indeed, in a pattern we’ve seen repeatedly for the past decade, the question of such evidence is never even directly confronted or acknowledged.

So I guess I’ll say the same thing here that I said to the journalists.  Namely, until there’s a paper or some other technical information, obviously there’s not much I can say about this D-Wave/Volkswagen collaboration.  But it would be astonishing if quantum supremacy were to be achieved on an application problem of interest to a carmaker, even as scientists struggle to achieve that milestone on contrived and artificial benchmarks, even as the milestone seems repeatedly to elude D-Wave itself on contrived and artificial benchmarks.  In the previous such partnerships—such as that with Lockheed Martin—we can reasonably guess that no convincing evidence for quantum supremacy was found, because if it had been, it would’ve been trumpeted from the rooftops.

Anyway, I confess that I couldn’t resist adding a tiny snark—something about how, if these claims of amazing performance were found not to withstand an examination of the details, it would not be the first time in Volkswagen’s recent history.


Farewell to a Visionary Leader—One Who Was Trash-Talking Critics on Social Media A Decade Before President Trump

This isn’t really news, but since it happened since my last D-Wave post, I figured I should share.  Apparently D-Wave’s outspoken and inimitable founder, Geordie Rose, left D-Wave to form a machine-learning startup (see D-Wave’s leadership page, where Rose is absent).  I wish Geordie the best with his new venture.


Martinis Visits UT Austin

On Feb. 22, we were privileged to have John Martinis of Google visit UT Austin for a day and give the physics colloquium.  Martinis concentrated on the quest to achieve quantum supremacy, in the near future, using sampling problems inspired by theoretical proposals such as BosonSampling and IQP, but tailored to Google’s architecture.  He elaborated on Google’s plan to build a 49-qubit device within the next few years: basically, a 7×7 square array of superconducting qubits with controllable nearest-neighbor couplings.  To a layperson, 49 qubits might sound unimpressive compared to D-Wave’s 2000—but the point is that these qubits will hopefully maintain coherence times thousands of times longer than the D-Wave qubits, and will also support arbitrary quantum computations (rather than only annealing).  Obviously I don’t know whether Google will succeed in its announced plan, but if it does, I’m very optimistic about a convincing quantum supremacy demonstration being possible with this sort of device.

Perhaps most memorably, Martinis unveiled some spectacular data, which showed near-perfect agreement between Google’s earlier 9-qubit quantum computer and the theoretical predictions for a simulation of the Hofstadter butterfly (incidentally invented by Douglas Hofstadter, of Gödel, Escher, Bach fame, when he was still a physics graduate student).  My colleague Andrew Potter explained to me that the Hofstadter butterfly can’t be used to show quantum supremacy, because it’s mathematically equivalent to a system of non-interacting fermions, and can therefore be simulated in classical polynomial time.  But it’s certainly an impressive calibration test for Google’s device.


2000 Qubits Are Easy, 50 Qubits Are Hard

Just like the Google group, IBM has also publicly set itself the ambitious goal of building a 50-qubit superconducting quantum computer in the near future (i.e., the next few years).  Here in Austin, IBM held a quantum computing session at South by Southwest, so I went—my first exposure of any kind to SXSW.  There were 10 or 15 people in the audience; the purpose of the presentation was to walk through the use of the IBM Quantum Experience in designing 5-qubit quantum circuits and submitting them first to a simulator and then to IBM’s actual superconducting device.  (To the end user, of course, the real machine differs from the simulation only in that with the former, you can see the exact effects of decoherence.)  Afterward, I chatted with the presenters, who were extremely friendly and knowledgeable, and relieved (they said) that I found nothing substantial to criticize in their summary of quantum computing.

Hope everyone had a great Pi Day and Ides of March.

“THE TALK”: My quantum computing cartoon with Zach Weinersmith

Wednesday, December 14th, 2016

OK, here’s the big entrée that I promised you yesterday:

“THE TALK”: My joint cartoon about quantum comgputing with Zach Weinersmith of SMBC Comics.

Just to whet your appetite:

In case you’re wondering how this came about: after our mutual friend Sean Carroll introduced me and Zach for a different reason, the idea of a joint quantum computing comic just seemed too good to pass up.  The basic premise—“The Talk”—was all Zach.  I dutifully drafted some dialogue for him, which he then improved and illustrated.  I.e., he did almost all the work (despite having a newborn competing for his attention!).  Still, it was an honor for me to collaborate with one of the great visual artists of our time, and I hope you like the result.  Beyond that, I’ll let the work speak for itself.