Bennett and Brassard Win the Turing Award

Gilles Brassard and Charlie Bennett

Charlie Bennett and Gilles Brassard will receive the 2025 ACM Turing Award for their work on the foundations of quantum information science, the first Turing award for quantum. Read all about it in The New York Times, Science and Quanta.

Bennett and Brassard famously met in the water off a beach during the 1979 FOCS conference in Puerto Rico. That led to years of collaboration, most notably for their quantum secure key distribution protocol. The basic idea is pretty simple and does not require quantum entanglement. Alice sends a series of random bits, either straightforward or rotated 45 degrees. Bob measures each of these bits in randomly chosen bases. They discard the bits where they used different bases and use some of the remaining bits to check for eavesdropping, which would collapse the state, and others to set the key.

Bennett and Brassard and four other authors showed how to teleport a quantum bit using entanglement and two classical bits. Bennett with Stephen Wiesner gave the dual superdense coding protocol of sending two classical bits using a single quantum bit. 

Bennett and Brassard, with Ethan Bernstein and Umesh Vazirani, showed that in black-box setting, quantum computers would require \(\Omega(\sqrt{n})\) queries to search \(n\) entries, matching Grover's algorithm. For some reason, the popular press rarely covers these results that limit the power of quantum computing. 

I've had the pleasure of knowing both Bennett and Brassard since the 1980s, both just full of enthusiasm and wonderful ideas. 

Let me end by saying I don't see this as a Turing award for quantum computing. Once (if?) we get large scale machines, we'll certainly see Turing awards, if not Nobel Prizes, for Peter Shor, Umesh Vazirani and others.

The Importance of Networking

People skip conferences because of the coronavirus or for global warming or just because conferences are too expensive and time consuming. I'm certainly no fan of the current conference structure but I would never want to virtualize all of them. Even if we could completely recreate the conference experience in virtual reality, people would not hang out in the halls without the commitment of having made the physical trip. I made this point in a tweet with a depressing response.

At least in CS theory, I don't see any crucial importance. These days it's easy to follow the latest developments online. If you're interested in someone's work, you just email them and start a collaboration. Sooner or later networking in hallways may become a thing of the past.

— Mahdi Cheraghchi (@cheraghchi) March 6, 2020

I don't disagree with anything Mahdi says except for the "crucial importance". Great ideas come from chance encounters and random conversations. Many of my research papers would never have happened if not for a conversation had at a conference or on the plane or train rides that took me there. Harken Gilles Brassard's origin story of quantum cryptography.

One fine afternoon in late October 1979, I was swimming at the beach of a posh hotel in San Juan, Puerto Rico. Imagine my surprise when this complete stranger swims up to me and starts telling me, without apparent provocation on my part, about Wiesner’s quantum banknotes! This was probably the most bizarre, and certainly the most magical, moment in my professional life⁶. Within hours, we had found ways to mesh Wiesner’s coding scheme with some of the then-new concepts of public-key cryptography.... The ideas that Bennett and I tossed around on the beach that day resulted in the first paper ever published on quantum cryptography, indeed the paper in which the term “Quantum Cryptography” was coined. 

And Footnote 6 read as follows.

At the risk of taking some of the magic away, I must confess that it was not by accident that Bennett and I were swimming at the same beach in Puerto Rico. We were both there for the 20th Annual IEEE Symposium on the Foundations of Computer Science. Bennett approached me because I was scheduled to give a talk on relativized cryptography on the last day of the Symposium and he thought I might be interested in Wiesner’s ideas. By an amazing coincidence, on my way to San Juan, I had read Martin Gardner’s account of Bennett’s report on Chaitin’s Omega, which had just appeared in the November 1979 “Mathematical Games” column of Scientific American—so, I knew the name but I could not recognize Bennett in that swimmer because I did not know what he looked like.

After we see a slate of conferences held virtually due to the virus, networking may indeed become a thing of the past. But we'll never know the research not done because of people who never connected.

Computability in Europe

Bill and I are both in Europe this week. I'm in Milan at Computability in Europe and Bill is 500 miles away in Budapest for the Paul Erdős Centenary. The US 4th of July holiday doesn't seem to sway the the Europeans from holding workshops. Bill will report on the star-studded Erdős celebration when he gets back.

So what is "Computability in Europe"? Don't the Europeans use the same Turing machines that we do? Wasn't Turing European?

Or course computation is the same, whether we do it in the US or Europe, Japan or Jupiter, but the emphasis is different. In the US we typically deal with traditional models of computers and see how much time and memory we need to solve various problems. The theme of this year's CiE is "The Nature of Computing" with "nature" being the key word. The conference is co-located with the Unconventional Computation and Natural Computation conference that focuses on different models of computing, especially those that rise from nature like biological computing. The two tutorials this week come from Grzegorz Rozenberg, talking on computing modes based on living cells and Gilles Brassard (whom I didn't recognize without his trademark beard) on quantum models.

Me, I like my computation served straight up on Turing machines, thank you very much.

My Quantum Summer

Rendering of PsiQuantum's facility in Chicago

I wasn't looking for quantum this summer but it found me. At various events I ran into some of the most recognized names in quantum computing: Peter Shor, Charlie Bennett, Gilles Brassard and Scott Aaronson (twice), Harry Buhrman and Ronald de Wolf.

I was invited to Amsterdam for a goodbye event for Harry Buhrman. Harry co-founded and co-led the CWI quantum center QuSoft and has now moved to London to join Quantinuum as chief scientist and I was invited to give a talk on Harry's classical complexity work before he joined the dark side. Ronald and Gilles gave talks after mine. 

On the way to Amsterdam I spent a few days visiting Rahul Santhanam in Oxford. Scott Aaronson and Dana Moshkovitz showed up with kids in tow. Scott gave a talk on AI not quantum in Oxford. I would see Scott again at the Complexity conference in Michigan.

Peter Shor and Charlie Bennett both attended the Levin Event I mentioned last week.

I talked to all of them about the future of quantum computing. Even though I'm the quantum skeptic in the crowd, we don't have that much disagreement. Everyone agreed we haven't yet achieved practical applications of quantum computing and that the power of quantum computing is often overstated, especially in what it can achieve for general search and optimization problems. There is some disagreement on when we'll get large scale quantum computers, say enough to factor large numbers. Scott and Harry would say growth will come quickly like we've seen in AI, others thought it would be more gradual. Meanwhile, machine learning continues to solve problems we were waiting for quantum machines to attack. 

My city of Chicago had a big quantum announcement, the Illinois Quantum and Microelectronics Park built on an old steel works site on the Southeast Side of the city built with federal, state and local funds as well as a big investment from PsiQuantum. I have my doubts as to whether this will lead to a practical quantum machine but no doubt having all this investment in quantum will bring more money and talent to the area, and we'll get a much better scientific and technological understanding of quantum. 

PsiQuantum's website claims they are "Building the world's first useful quantum computer". PsiQuantum is using photonic qubits, based on particles of light. Harry's company Quantinuum is using trapped ions. IBM and Google are trying superconducting qubits. Microsoft is using topological qubits and Intel with Silicon qubits (naturally). Who will succeed? They all might. None of them? Time will tell, though it might be a lot of time.

On NP in BQP

In the wake of a misleading Economist article on the D-Wave quantum computer, Scott argues why he believes quantum computers cannot efficiently solve NP-complete problems, i.e., that the complexity class BQP does not contain NP. Let's look at that question purely from a computational complexity viewpoint.

Ideally we would like a mathematical proof that NP ⊄ BQP. But any such proof would imply P≠NP, one of the great open problems in mathematics.

Moving on, complexity theorists give evidence that a statement Q is false by a "Pigs Can Fly" argument, by showing that Q implies something else we don't believe. For example

• If there are sparse NP-complete sets then P=NP.
• If NP has efficient probabilistic algorithms (NP⊆BPP), then the polynomial-time hierarchy collapses.
• If good pseudorandom generators don't exist then exponential time has small circuits.

But we don't have any known consequences of NP⊆BQP.

What we do have is the result of Bennett, Bernstein, Brassard, Vazirani that BQP can't solve black-box NP problems, a relativized separation of NP from BQP. Relativized results like this don't tell us whether or not a statement is true, just that any proof that NP in BQP would require nonrelativizing techniques. So the sentence from the Economist article

In principle, by putting a set of entangled qubits into a suitably tuned magnetic field, the optimal solution to a given NP-complete problem can be found in one shot.

does not reflect current knowledge.

Can one have a nonrelativizing proof that NP is in BQP? We do have precedent. My very first theorem gave a relativized world where co-NP does not have interactive proof systems. We published the result in a 1988 paper Are there interactive protocols for co-NP languages? and we conjectured the answer was no. We were wrong.

But so far interactive proof and related systems have been the only source of reasonable nonrelativized proof techniques that we have seen in computational complexity and we haven't had any success using this algebraic structure of arithmetized satisfiability to make efficient quantum algorithms for NP problems.

I do conjecture that NP ⊄ BQP and most computational complexity theorists would agree with me. But until we see some negative consequences of NP in BQP, computational complexity theory has so far failed to give any real evidence that NP ⊄ BQP. We believe that NP ⊄ BQP for the same reason we believe that there are no probabilistic polynomial-time algorithms for Factoring—despite considerable effort, failure to find any algorithmic techniques that might solve the problem.

A Classical World

We need to rewrite the traffic laws in this country because they don't handle flying cars. We don't have flying cars, you say. We might have flying cars in the next couple of decades so the current traffic laws no longer apply.

Keep that argument in mind as you read the following paragraph from David Bacon.

If today someone was to prove that P does not equal NP for a classical computer, would we be satisfied? Well certainly we would be very excited and this would be the breakthrough of the century in computation, but because the universe is fundamentally quantum mechanical, would we really be satisfied that the intractability of NP-complete problems had been shown? Quantum computers open up an entire bag of worrying about the foundations of computational complexity. It is dangerous to say this, of course: if this view is correct, then the hard work of classical computational theory might have been in vain. But if this is the correct view, then we need to begin weaning ourselves off of the classical model of computation.

Dangerous indeed. Bacon is not the first one to make such statements, Gilles Brassard made much stronger pronouncements as far back as 1990.

Did the theory of relativity mean the hard work of classical mechanics was in vain? Of course not. When we drive a car we don't need to worry about relativistic effects, they simply don't amount to much at that level.

We don't know how quantum mechanics will actually play out in a computer that would require the entanglement and manipulation of tens of thousands of quantum bits. Maybe we can harness the full power of quantum computation, maybe we can't. At this point we simply don't know.

I support research in quantum complexity, as long as quantum computing remains a possibility we should try and understand its computational power. But not until we all have fast quantum computers on our desks should we even think of abandoning classical complexity. And in our current state of affairs, where creating a quantum computer that factors faster than my daughter is a pipe dream, classical computational complexity serves us very well indeed.

Surprising Results

Guest Post by Bill Gasarch with help from Harry Lewis and Richard Ladner.

What are the surprising results in theory? By surprising we DO NOT mean surprising that they were PROVEN (e.g., PRIMES in P) but surprising that they were TRUE. Some results are surprising since people thought the opposite is true, but some results are surprising because people didn't even think in those terms. The latter we call BIG surprises. I will note which ones are BIG. Here is a list of results that were surprising on some level.

While compiling this list and talking to people one (obvious) thing really struck me: what people consider surprising is very much a function of WHEN they were in graduate school. For example, Median Finding in Linear time was a big surprise at the time, but we now teach it to undergrads who are not impressed. And neither are we.

1. Gödel's Inc. Theorem. (1931) REALLY surprised Hilbert and others. BIG Original Version Modern Version
2. HALT is undecidable. (1931–though in a different form). BIG
3. Multiplication in subquadratic time (Toom-1963, Cook-1966). Later improved to n log n loglog n (Schonhage-Strassen 1971) People did it in O(n²) for so long! BIG
4. Matching in Polynomial Time. (Edmonds 1965, Canadian Journal of Mathematics) Poly time seen as important. BIG.
5. Matrix Multiplication in O(n^2.87) time (less than n³ !!) (Strassen 1969).
6. The Speed Up Theorem–There are decidable sets that cannot be assigned a complexity intelligently. (M. Blum STOC69, JACM71)
7. Savitch's Theorem (JCSS 1970): NSPACE(T(n)) ⊆ DSPACE(T²(n)).
8. Cook's Theorem. (1971 STOC) EVERY NP-problem is reducible to SAT! (Cook also had CLIQUE–so I've left off Karp's 22 problems). BIG.
9. Equivalence problem for Regular Expressions with Squaring is EXP-SPACE complete (Meyer, Stockmeyer FOCS72). A `natural' problem proven to NOT be in P!
10. Median in Linear time (Blum,Floyd,Pratt,Rivest,Tarjan STOC72, JCSS73).
11. Super-Exponential Complexity of Presburger Arithmetic (Fischer-Rabin, 1974). A new way of looking at Hilbert's program and its difficulties.
12. Amortized Union-Find in Θ(nINVACK(n)). (Tarjan- 1975). Inverse Ackerman comes up naturally! First time?
13. P vs NP cannot be solved by techniques that relatives (Baker, Gill, Solovay 1975). BIG
14. Public Key Crypto (Diffie Helman, 1976, IEEE Trans Inform Theory, Rivest-Shamir-Adleman, 1978). Establishing shared key without meeting. In retrospect solved 2000 year old problem. BIG.
15. Permanent is #P complete. (Valiant 1979) BIG–Introduced #P.
16. Linear Programming in P. (Khachiyan 1979).
17. Integer Programming with fixed number of variables in P (H.W. Lenstra 1983) Note that the range of the variables is unbounded.
18. Shortest Path problem on planar graphs BETTER THAN O(n log n) (Fredersickson, 1983, FOCS). You don't need to sort!
19. Bit commitment⇒SAT in Zero Knowledge (Brassard,Crepeau FOCS86, Goldreich,Micali,Wigderson CRYPTO86, JACM91) if φ in SAT, can convince you that φ in SAT without giving you a clue on how to satisfy it. Result did not relativize.
20. NSPACE(n) = coNSPACE(n). (1987-Szelepcsenyi-BEATCS, Immerman-1988-IEEECCC, SICOMP).
21. Fixed Parameter Tractability material—Hard to pin down ONE result. I was surprised at Vertex cover for fixed k in O(f(k)n³) via Graph Minor Theorem. Other candidates are solid evidence that Dominating Set and Clique are NOT Fixed Point Tractable. More progress on Vertex Cover (down to something like n+(1.34)^k + O(1)) and Subgraph Homeomorphism for fixed graphs in O(n³) (Robertson and Seymour).
22. Under assumptions, P=BPP (Nisan, Wigderson FOCS 1988, JCSS 1994). People had thought P ≠ BPP. BIG.
23. PH in P^#P. (Toda FOCS89, SICOMP91) PH is the Poly Hierarchy. #P REALLY powerful!
24. IP=PSPACE (Lund-Fortnow-Karloff-Nisan, Shamir FOCS90 JACM 92). Bonus: Proof did not relativize. BIG.
25. Connection between PCP and Approximation. (Feige,Goldwasser,Lovasz,Safra,Szegedy FOCS91, JACM96). BIG.
26. Factoring is in QUANTUM P (Shor 1994 FOCS). Natural candidate for QP-P ! BIG.
27. Limits on what we can prove about circuits (Razborov and Rudich STOC94, JCSS97).
28. Randomized approx algorithms for MAX CUT which are .87856.. OPT (Goemans, Williamson, 1995).
29. Grover's Quantum O(n^0.5) search algorithm (STOC 1996, Phy Review Letters 1997)
30. HALT is truth-table reducible to RAND, where RAND is Kolmogorov rand strings (Kummer STACS 96). All the people working on this problem (granted, not many) thought it was false.
31. Planar TSP has a PTAS. (Arora FOCS97, JACM98). Most people thought false.
32. Assuming Unique Game Conjecture Max Cut algorithm of GW is optimal unless P=NP (Mossel, O'Donnell, Oleskiewicz 2005FOCS)

Theory for Dentists

Thanks to Rahul Santhanam for covering for me last week. If you are looking for a smart hard-working postdoc in complexity take a look at Rahul.

On the plane last week the passenger sitting next to me, a dentist from Vancouver, was reading a Scientific American article on quantum cryptography. Quantum cryptography got its start from people in the theoretical computer science field like Charlie Bennett and Gilles Brassard. For our field to flourish we must produce research of interest to others and to see outsiders reading about the fruits of our labor just for fun is a good sign.