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.

I think Zurek is 60, like me. Was the cake good? I can’t tell from the picture whether the display is edible.

Like or Dislike: 0 0

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.

Like or Dislike: 0 0

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.

Like or Dislike: 0 0

By itself the Toffoli gate cannot create any superpositions. Only together with (say) single-qubit gates, like Hadamard, is it universal.

Like or Dislike: 0 0

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.

Like or Dislike: 0 0

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.

Like or Dislike: 0 0

Maybe the moral is that in quantum mechanics “The Third Man” can be virtual because of entanglement

Like or Dislike: 0 0