Shtetl-Optimized

Here it is, recorded last week at Y Combinator’s office in San Francisco.  For regular readers of this blog, there will be a few things that are new—research projects I’ve been working on this year—and many things that are old.  Hope you enjoy it!  Thanks so much to Craig Cannon of Y Combinator for inviting me.

Associated with the podcast, Hacker News will be doing an AMA with me later today.  I’ll post a link to that when it’s available.  Update: here it is.

I’m at STOC’2018 TheoryFest in Los Angeles right now, where theoretical computer scientists celebrated the 50th anniversary of the conference that in some sense was the birthplace of the P vs. NP problem.  (Two participants in the very first STOC in 1969, Richard Karp and Allan Borodin, were on a panel to share their memories, along with Ronitt Rubinfeld and Avrim Blum, who joined the action in the 1980s.)  There’s been a great program this year—if you’d like to ask me about it, maybe do so in the comments of this post rather than in the AMA.

Follow

Reader Lewikee asked when I’d do another “Ask Me Anything.”  So fine, let’s do one now (and for the next 24 hours or so, or until I get too fatigued).  The rules:

• This time around, only questions that ask me to render a moral judgment on some issue, which could be personal, political, or both (I answer plenty of quantum and complexity questions in the comments sections of other posts…)
• One question per person total; no multipart questions or questions that require me to watch a video or read a linked document
• Anything nasty, sneering, or non-genuine will be left in the moderation queue at my discretion

Let me get things started with the following judgment:

It is morally wrong to lie to parents that you’re taking their children away from them for 20 minutes to give them a bath, but then instead separate the children from their parents indefinitely, imprison the parents, and confine the children in giant holding facilities where they can no longer be contacted, as United States border agents are apparently now doing.  And yes, I know that people sometimes make such proclamations not out of genuine moral concern, but simply to virtue-signal for their chosen tribe and attack a rival tribe.  However, as someone who’s angered and offended nearly every tribe on his blog, I hope I might be taken at face value if I simply say: this is wrong.

Update (June 18): OK, thanks to everyone who participated! I’ll circle back to the few questions I haven’t yet gotten to, but no new questions please.

Follow

1. For the next two weeks, I’m in Berkeley for the Simons program “Challenges in Quantum Computation” (awesome program, by the way).  If you’re in the Bay Area and wanted to meet, feel free to shoot me an email (easiest for me if you come to Berkeley, though I do have a couple planned trips to SF).  If enough people wanted, we could even do a first-ever dedicated Shtetl-Optimized meetup.
2. More broadly: I’m finally finished my yearlong sabbatical in Israel.  At some point I’ll do a post with my reflections on the experience.  I’ll now be traveling around North America all summer, then returning to UT Austin in the fall.
3. Longtime friend-of-the-blog Boaz Barak, from a university in Cambridge, MA known as Harvard, asks me to invite readers to check out his new free draft textbook Introduction to Theoretical Computer Science, and to post comments about “typos, bugs, confusing explanations and such” in the book’s GitHub repository.  It looks great!
4. This is already almost a month old, but if you enjoy the quantum computing content on this blog and wish to see related content from our carefully selected partners, check out John Preskill’s Y Combinator interview.
5. Here’s the text of Senator Kamala Harris’s bill, currently working its way through the Senate, to create a US Quantum Computing Research Consortium.  Apparently there’s now also a second, competing quantum computing bill (!)—has anyone seen the text of that one?

Update (June 16): Even though I said there wouldn’t be a meetup, enough people eventually emailed wanting to have coffee that we did do the first-ever dedicated Shtetl-Optimized meetup after all—appropriately, given the title of the blog, at Saul’s Delicatessen in Berkeley. It was awesome. I met people working on fascinating and important things, from cheap nuclear energy to data analytics for downballot Democrats, and who I felt very proud to count as readers. Thanks so much to everyone who came; we’ll have to do another one sometime!

Follow

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.

Follow

Update (June 4): OK, I think the blog formatting issues are fixed now—thanks so much to Jesse Kipp for his help!

True story.  A couple nights ago, I was sitting in the Knesset, Israel’s parliament building, watching Gilles Brassard and Charles Bennett receive the Wolf Prize in Physics for their foundational contributions to quantum computing and information.  (The other laureates included, among others, Beilinson and Drinfeld in mathematics; the American honeybee researcher Gene Robinson; and Sir Paul McCartney, who did not show up for the ceremony.)

Along with the BB84 quantum cryptography scheme, the discovery of quantum teleportation, and much else, Bennett and Brassard’s seminal work included some of the first quantum oracle results, such as the BBBV Theorem (Bennett, Bernstein, Brassard, Vazirani), which proved the optimality of Grover’s search algorithm, and thus the inability of quantum computers to solve NP-complete problems in polynomial time in the black-box setting.  It thereby set the stage for much of my own career.  Of course, the early giants were nice enough to bequeath to us a few problems they weren’t able to solve, such as: is there an oracle relative to which quantum computers can solve some problem outside the entire polynomial hierarchy (PH)?  That particular problem, in fact, had been open from 1993 all the way to the present, resisting sporadic attacks by me and others.

As I sat through the Wolf Prize ceremony — the speeches in Hebrew that I only 20% understood (though with these sorts of speeches, you can sort of fill in the inspirational sayings for yourself); the applause as one laureate after another announced that they were donating their winnings to charity; the ironic spectacle of far-right, ultranationalist Israeli politicians having to sit through a beautiful (and uncensored) choral rendition of John Lennon’s “Imagine” — I got an email from my friend and colleague Avishay Tal.  Avishay wrote that he and Ran Raz had just posted a paper online giving an oracle separation between BQP and PH, thereby putting to rest that quarter-century-old problem.  So I was faced with a dilemma: do I look up, at the distinguished people from the US, Canada, Japan, and elsewhere winning medals in Israel, or down at my phone, at the bombshell paper by two Israelis now living in the US?

For those tuning in from home, BQP, or Bounded-Error Quantum Polynomial Time, is the class of decision problems efficiently solvable by a quantum computer.  PH, or the Polynomial Hierarchy, is a generalization of NP to allow multiple quantifiers (e.g., does there exist a setting of these variables such that for every setting of those variables, this Boolean formula is satisfied?).  These are two of the most fundamental complexity classes, which is all the motivation one should need for wondering whether the former is contained in the latter.  If additional motivation is needed, though, we’re effectively asking: could quantum computers still solve problems that were classically hard, even in a hypothetical world where P=NP (and hence P=PH also)?  If so, the problems in question could not be any of the famous ones like factoring or discrete logarithms; they’d need to be stranger problems, for which a classical computer couldn’t even recognize a solution efficiently, let alone finding it.

And just so we’re on the same page: if BQP ⊆ PH, then one could hope for a straight-up proof of the containment, but if BQP ⊄ PH, then there’s no way to prove such a thing unconditionally, without also proving (at a minimum) that P ≠ PSPACE.  In the latter case, the best we can hope is to provide evidence for a non-containment—for example, by showing that BQP ⊄ PH relative to a suitable oracle.  What’s noteworthy here is that even the latter, limited goal remained elusive for decades.

In 1993, Bernstein and Vazirani defined an oracle problem called Recursive Fourier Sampling (RFS), and proved it was in BQP but not in BPP (Bounded-Error Probabilistic Polynomial-Time).  One can also show without too much trouble that RFS is not in NP or MA, though one gets stuck trying to put it outside AM.  Bernstein and Vazirani conjectured—at least verbally, I don’t think in writing—that RFS wasn’t even in the polynomial hierarchy.  In 2003, I did some work on Recursive Fourier Sampling, but was unable to find a version that I could prove was outside PH.

Maybe this is a good place to explain that, by a fundamental connection made in the 1980s, proving that oracle problems are outside the polynomial hierarchy is equivalent to proving lower bounds on the sizes of AC⁰ circuits—or more precisely, constant-depth Boolean circuits with unbounded fan-in and a quasipolynomial number of AND, OR, and NOT gates.  And proving lower bounds on the sizes of AC⁰ circuits is (just) within complexity theory’s existing abilities—that’s how, for example, Furst-Saxe-Sipser, Ajtai, and Yao managed to show that PH ≠ PSPACE relative to a suitable oracle (indeed, even a random oracle with probability 1).  Alas, from a lower bounds standpoint, Recursive Fourier Sampling is a horrendously complicated problem, and none of the existing techniques seemed to work for it.  And that wasn’t even the only problem: even if one somehow succeeded, the separation that one could hope for from RFS was only quasipolynomial (n versus n^{log n}), rather than exponential.

Ten years ago, as I floated in a swimming pool in Cambridge, MA, it occurred to me that RFS was probably the wrong way to go.  If you just wanted an oracle separation between BQP and PH, you should focus on a different kind of problem—something like what I’d later call Forrelation.  The Forrelation problem asks: given black-box access to two Boolean functions f,g:{0,1}ⁿ→{0,1}, are f and g random and independent, or are they random individually but with each one close to the Boolean Fourier transform of the other one?  It’s easy to give a quantum algorithm to solve Forrelation, even with only 1 query.  But the quantum algorithm really seems to require querying all the f- and g-inputs in superposition, to produce an amplitude that’s a global sum of f(x)g(y) terms with massive cancellations in it.  It’s not clear how we’d reproduce this behavior even with the full power of the polynomial hierarchy.  To be clear: to answer the question, it would suffice to show that no AC⁰ circuit with exp(poly(n)) gates could distinguish a “Forrelated” distribution over (f,g) pairs from the uniform distribution.

Using a related problem, I managed to show that, relative to a suitable oracle—in fact, even a random oracle—the relational version of BQP (that is, the version where we allow problems with many valid outputs) is not contained in the relational version of PH.  I also showed that a lower bound for Forrelation itself, and hence an oracle separation between the “original,” decision versions of BQP and PH, would follow from something that I called the “Generalized Linial-Nisan Conjecture.”  This conjecture talked about the inability of AC⁰ circuits to distinguish the uniform distribution from distributions that “looked close to uniform locally.”  My banging the drum about this, I’m happy to say, initiated a sequence of events that culminated in Mark Braverman’s breakthrough proof of the original Linial-Nisan Conjecture.  But alas, I later discovered that my generalized version is false.  This meant that different circuit lower bound techniques, ones more tailored to problems like Forrelation, would be needed to go the distance.

I never reached the promised land.  But my consolation prize is that Avishay and Ran have now done so, by taking Forrelation as their jumping-off point but then going in directions that I’d never considered.

As a first step, Avishay and Ran modify the Forrelation problem so that, in the “yes” case, the correlation between f and the Fourier transform of g is much weaker (though still detectable using a quantum algorithm that makes n^O(1) queries to f and g).  This seems like an inconsequential change—sure, you can do that, but what does it buy you?—but it turns out to be crucial for their analysis.  Ultimately, this change lets them show that, when we write down a polynomial that expresses an AC⁰ circuit’s bias in detecting the forrelation between f and g, all the “higher-order contributions”—those involving a product of k terms of the form f(x) or g(y), for some k>2—get exponentially damped as a function of k, so that only the k=2 contributions still matter.

There are a few additional ideas that Raz and Tal need to finish the job.  First, they relax the Boolean functions f and g to real-valued, Gaussian-distributed functions—very similar to what Andris Ambainis and I did when we proved a nearly-tight randomized lower bound for Forrelation, except that they also need to truncate f and g so they take values in [-1,1]; they then prove that a multilinear polynomial has no way to distinguish their real-valued functions from the original Boolean ones.  Second, they exploit recent results of Tal about the Fourier spectra of AC⁰ functions.  Third, they exploit recent work of Chattopadhyay et al. on pseudorandom generators from random walks (Chattopadhyay, incidentally, recently finished his PhD at UT Austin).  A crucial idea turns out to be to think of the values of f(x) and g(y), in a real-valued Forrelation instance, as sums of huge numbers of independent random contributions.  Formally, this changes nothing: you end up with exactly the same Gaussian distributions that you had before.  Conceptually, though, you can look at how each tiny contribution changes the distinguishing bias, conditioned on the sum of all the previous contributions; and this leads to the suppression of higher-order terms that we talked about before, with the higher-order terms going to zero as the step size does.

Stepping back from the details, though, let me talk about a central conceptual barrier—one that I know from an email exchange with Avishay was on his and Ran’s minds, even though they never discuss it explicitly in their paper.  In my 2009 paper, I identified what I argued was the main reason why no existing technique was able to prove an oracle separation between BQP and PH.  The reason was this: the existing techniques, based on the Switching Lemma and so forth, involved arguing (often implicitly) that

1. any AC⁰ circuit can be approximated by a low-degree real polynomial, but
2. the function that we’re trying to compute can’t be approximated by a low-degree real polynomial.

Follow