Bennett, Toffoli and reversible computation
In 1973, Charles Bennett showed that universal computation can be done reversibly, and Tommaso Toffoli later invented the Toffoli gate, a controlled-controlled-NOT gate that takes three inputs and produces three outputs. Because every set of outputs maps back to exactly one set of inputs, no information is lost and the operation can always be run in reverse. This matters because the Toffoli gate is universal: any other logic gate can be built from it, giving reversible computation the same power as conventional computing. Paul Benioff at Argonne National Laboratory then extended this further by constructing a quantum-mechanical version of Turing machine state transitions, laying the groundwork for the idea that quantum systems could run real algorithms.
- The contrast with a conventional AND gate makes the reversibility point concrete: an AND gate maps two inputs to one output, so three of its four input combinations are unrecoverable from the output alone.
- The Toffoli gate is widely referenced in quantum computing literature, and the hosts note that learners at any level will encounter it by name when studying the field.
- Charles Bennett was also involved in early quantum cryptography through a connection with his undergraduate friend Stephen Wiesner at Columbia, though that thread is picked up in the following chapter.
Transcript
This chapter, from the episode video's captions · 467 words
32:08we're used to and gates and or those are those are and and we got algorithms galore for days for that kind of stuff right um 1973 Charles Bennett demonstrates that you can actually use universal reversible computation um and along with him Edward Fredkin and Tomaso Tofouli who's over here Tomaso Tofo invents something called a tofully gate which is a controlled controlled notgate okay I don't want to get into all of that but it's effectively a logic gate that is reversible meaning I can always go backwards the the logic the truth table is is unique because my three inputs give me three
32:49outputs so from those three outputs I can always reconstruct my three inputs >> but crucially this gate is something that I can use for universal computation I can build any other gate from these gates okay so now >> it's possible there's a chance >> this this makes sense It's unlike our previous uh and ANDgate where three out of the four outputs you could not go back from >> because it went two to one right so it's like yeah you lost some here it's three to three >> three to three so you basically retain all the degrees of information necessary to go backwards um and that's a fundamental building block to now be able to potentially do the type of computation that you would you have uh
33:31the an enabling layer to potentially now think about the idea of quantum computing. >> Yes. >> Yes. You've got like a substrate that I can start building a algorithm. Maybe >> maybe and tofully um for for those that are like well-versed in quantum computing or are like just starting to learn about it, you'll hear a lot about tofully gates. That's where the that's who it's named after, right? And it's because it's this like first idea of like a a a gate that can make up universal um logic in some sense. So following this, Paul Beni off at the Argon National Lab, he creates a quantum mechanics version of the state transitions in touring machines. Alan Turing and um Church who we talked about
34:13um again on our America 250. I keep pitching this thing, but um they demonstrated at Princeton that you know um any computable algorithm can be computed on a touring machine using these like straight state transitions and very simple logic. He showed that, you know, there there's a version of that that I can do in quantum mechanics. Okay, side note, um Charles Bennett, who's the guy who um demonstrated that first reversible computation, um he was involved in the early days of quantum cryptography. So his undergrad friend Stephven Wizzner at um at Colombia, they had an idea to use
From How Quantum Computing Actually Works (Part 1)
Part I of our quantum computing deep dive traces the field from Bell and Feynman to Deutsch and Shor—and explains what quantum computers actually do differently from classical machines.