Tommaso Toffoli’s 3-input 3-output logic gate, central to the theory of reversible and quantum computing, recently featured on a custom cake made for his 70’th birthday.
Nowadays scientists’ birthday celebrations often take the form of informal mini-conferences, festschrifts without the schrift. I have had the honor of attending several this year, including ones for John Preskill’s and Wojciech Zurek’s 60’th birthdays and a joint 80’th birthday conference for Myriam Sarachik and Daniel Greenberger, both physics professors at City College of New York. At that party I learned that Greenberger and Sarachick have known each other since high school. Neither has any immediate plans for retirement.
O brave new quantum world!
I think Zurek is 60, like me. Was the cake good? I can’t tell from the picture whether the display is edible.
Thanks for the correction–I’ve updated the text. I got Zurek mixed up with me. He’s 60 and I’m 70. The interior of the cake was quite good–a carrot cake.
Yeah, I’m struggling to understand why the Toffoli gate is universal in classical computing but not in quantum computing. I can’t make sense of this.
By itself the Toffoli gate cannot create any superpositions. Only together with (say) single-qubit gates, like Hadamard, is it universal.
Ok but I’m still not sure what it means. Given enough power and memory a classical computer can simulate a quantum computer. That means it can solve any problem a quantum computer can. Isn’t that what we mean by “universal”?
Are we using an extended definition of universal to fit the extended Church-Turing thesis?
This is just a hobby for me so forgive the ignorance.
Dear PPLN,
In classical reversible Boolean logic, the set of reversible one- and two-bit Boolean gates is so limited (comprising the identity, NOT, XOR, trivial variations of XOR with some negated inputs or outputs) that it cannot generate all reversible logic functions. Adding a 3-bit reversible gate, such as the Toffoli gate, makes the set universal. This requirement for 3-input gates for classical reversible logic is in contrast both with classical irreversible Boolean logic (where the one-input NOT and two-input AND suffice for universality), and with reversible quantum logic (where the two-input XOR together almost any one-qubit gate suffice for universality). Deutsch’s first proposal for quantum gate logic was a direct generalization of classical reversible Boolean logic, and used quantum Toffoli gates. Later Barenco et al showed that these could be constructed from two-qubit XORs and one-qubit unitary operations. These constructions do not carry over to a construction of classical Toffolis from classical one and two-bit gates, because they depend on one-qubit gates that are unitary but not Boolean.
Maybe the moral is that in quantum mechanics “The Third Man” can be virtual because of entanglement