These days, any quantum computing post I write ought to begin with the disclaimer that the armies of Sauron are triumphing around the globe, this is the darkest time for humanity most of us have ever known, and nothing else matters by comparison. Certainly not quantum computing. Nevertheless stuff happens in quantum computing and it often brings me happiness to blog about it—certainly more happiness than doomscrolling or political arguments.<\/p>\n\n\n\n
So then: today JP Morgan Chase announced that, together with Quantinuum and DoE labs, they’ve experimentally demonstrated the protocol I proposed in 2018, and further developed in a STOC’2023 paper with Shih-Han Hung<\/a>, for using current quantum supremacy experiments to generate certifiable random bits for use in cryptographic applications. See here for our paper in Nature<\/em><\/a>—the JPMC team was gracious enough to include me and Shih-Han as coauthors.<\/p>\n\n\n\n Mirroring a conceptual split in the protocol itself, Quantinuum handled the quantum hardware part of my protocol, while JPMC handled the rest: modification of the protocol to make it suitable for trapped ions, as well as software to generate pseudorandom challenge circuits to send to the quantum computer over the Internet, then to verify the correctness of the quantum computer’s outputs (thereby ensuring, under reasonable complexity assumptions, that the outputs contained at least a certain amount of entropy), and finally to extract nearly uniform random bits from the outputs. The experiment used Quantinuum’s 56-qubit trapped-ion quantum computer, which was given and took a couple seconds to respond to each challenge. Verification of the outputs was done using the Frontier and Summit supercomputers. The team estimates that about 70,000 certified random bits were generated over 18 hours, in such a way that, using the best currently-known attack, you’d need at least<\/em> about four Frontier supercomputers working continuously to spoof the quantum computer’s outputs, and get the verifier to accept non-random bits.<\/p>\n\n\n\n We should be clear that this gap, though impressive from the standpoint of demonstrating quantum supremacy with trapped ions, is not yet good enough for high-stakes cryptographic applications (more about that later). Another important caveat is that the parameters of the experiment aren’t yet good enough for my and Shih-Han’s formal security reduction to give assurances: instead, for the moment one only has “practical security,” or security against a class of simplified yet realistic attackers. I hope that future experiments will build on the JPMC\/Quantinuum achievement and remedy these issues.<\/p>\n\n\n\n The story of this certified randomness protocol starts seven years ago, when I had lunch with Or Sattath<\/a> at a Japanese restaurant in Tel Aviv. Or told me that I needed to pay more attention to the then-recent Quantum Lightning<\/a> paper by Mark Zhandry. I already know that paper is great, I said. You don’t know the half of it, Or replied. As one byproduct of what he’s doing, for example, Mark gives a way to measure quantum money states in order to get certified random bits—bits whose genuine randomness (not<\/em> pseudorandomness) is certified by computational intractability, something that wouldn’t have been possible in a classical world.<\/p>\n\n\n\n Well, why do you even need quantum money states for that? I asked. Why not just use, say, a quantum supremacy experiment based on Random Circuit Sampling, like the one Google is now planning to do (i.e., the experiment Google would<\/em> do<\/a>, a year later after this conversation)? Then, the more I thought about that question, the more I liked the idea that these “useless” Random Circuit Sampling experiments would do something potentially useful despite themselves<\/em>, generating certified entropy as just an inevitable byproduct of passing our benchmarks for sampling from certain classically-hard probability distributions. Over the next couple weeks, I worked out some of the technical details of the security analysis (though not all! it was a big job, and one that only got finished years later, when I brought Shih-Han to UT Austin as a postdoc and worked with him on it for a year).<\/p>\n\n\n\n I emailed the Google team about the idea; they responded enthusiastically. I also got in touch with UT Austin’s intellectual property office to file a provisional patent, the only time I’ve done that my career. UT and I successfully licensed the patent to Google, though the license lapsed when Google’s priorities changed. Meantime, a couple years ago, when I visited Quantinuum’s lab in Broomfield, Colorado, I learned that a JPMC-led collaboration toward an experimental demonstration of the protocol was then underway. The protocol was well-suited to Quantinuum’s devices, particularly given their ability to apply two-qubit gates with all-to-all connectivity and fidelity approaching 99.9%.<\/p>\n\n\n\n I should mention that, in the intervening years, others had also<\/em> studied the use of quantum computers to generate cryptographically certified randomness; indeed it became a whole subarea of quantum computing. See especially the seminal work<\/a> of Brakerski, Christiano, Mahadev, Vazirani, and Vidick, which gave a certified randomness protocol that (unlike mine) relies only on standard cryptographic assumptions and allows verification in classical polynomial time. The “only” downside is that implementing their protocol securely seems to require a full fault-tolerant quantum computer (capable of things like Shor’s algorithm), rather than current noisy devices with 50-100 qubits.<\/p>\n\n\n\n For the rest of this post, I’ll share a little FAQ, adapted from my answers to a journalist’s questions. Happy to answer additional questions in the comments. <\/p>\n\n\n\n Well, it\u2019s the first experimental demonstration of a protocol to generate cryptographically certified random bits with the use of a quantum computer.<\/p>\n\n\n\n To remove any misunderstanding: if you\u2019re just talking about the use of quantum phenomena to generate\u00a0random\u00a0bits, without certifying<\/em> the randomness of those bits to a faraway skeptic, then that\u2019s been easy to do for generations (just stick a Geiger counter next to some radioactive material!). The new part, the part that requires a quantum computer, is all about the certification.<\/p>\n\n\n\n Also: if you\u2019re talking about the use of separated, entangled parties to generate certified\u00a0random\u00a0bits by violating the Bell inequality (see eg here<\/a>) \u2014 that approach does give certification, but the downside is that you need to believe that the two parties really are unable to communicate with each other, something that you couldn\u2019t certify in practice over the Internet.\u00a0 A quantum-computer-based protocol like mine, by contrast, requires just a single quantum device.<\/p>\n\n\n\n In any cryptographic application where you need to distribute random bits over the Internet, the fundamental question is, why should everyone trust that these bits are truly random, rather than being backdoored by an adversary?<\/p>\n\n\n\n This isn\u2019t so easy to solve. If you consider any classical method for generating random bits, an adversary could substitute a cryptographic pseudorandom generator without anyone being the wiser.<\/p>\n\n\n\n The key insight behind the quantum protocol is that a quantum computer can solve certain problems efficiently, but only<\/em> (it\u2019s conjectured, and proven under plausible assumptions) by sampling an answer randomly \u2014 thereby giving you certified\u00a0randomness, once you verify that the quantum computer really has solved the problem in question.\u00a0 Unlike with a classical computer, there\u2019s no way to substitute a pseudorandom generator, since\u00a0randomness\u00a0is just an inherent part of a quantum computer\u2019s operation \u2014 specifically, when the entangled superposition state randomly collapses on measurement.<\/p>\n\n\n\n One potential application is to proof-of-stake cryptocurrencies, like Ethereum. These cryptocurrencies are vastly more energy-efficient than \u201cproof-of-work\u201d cryptocurrencies (like Bitcoin), but they require lotteries to be run constantly to decide which currency holder gets to add the next block to the blockchain (and get paid for it). Billions of dollars are riding on these lotteries being fair.<\/p>\n\n\n\n
\n\n\n\n
\n\n\n\n\n
\n
\n
\n
\n
\n