Reversible and Quantum Computing


For a computer scientist, the interest in reversible and quantum computing can be summarized in the following thesis:
The discipline of computer science is founded on the "wrong worldview," a worldview that is fundamentally at odds with physical reality.
More than thirty years ago, Toffoli (1980) stated the following:
Mathematical models of computation are abstract constructions, by their nature unfettered by physical laws. However, if these models are to give indications that are relevant to concrete computing, they must somehow capture, albeit in a selective and stylized way, certain general physical restrictions to which all concrete computing processes are subjected.
More recently, Girard (2007) states:
In other terms, what is so good in logic that quantum physics should obey? Can't we imagine that our conceptions about logic are wrong, so wrong that they are unable to cope with the quantum miracle? ... Instead of teaching logic to nature, it is more reasonable to learn from her. Instead of interpreting quantum into logic, we shall interpret logic into quantum.

There is a growing research programme that accepts the quantum reality as foundational and investigates its consequences. This class is an introduction to this growing and exciting research area.

Office hours

Amr: 9am-12pm Wednesdays and by appointment.

Schedule of Talks

Feb. 3: Rebecca: Functional Quantum Programming (Mu and Bird)

Feb. 8: Adam: Shor in Haskell: the Quantum IO Monad (Alexander S. Green and Thorsten Altenkirch)

Feb. 10: Mike: Thermodynamics (Maxwell, Landauer, Bennett)

Feb. 15: Devarshi: Linear Logic (Wadler)

Mar 1: Hongyan: An injective language for reversible computation (Shin-Cheng Mu, Zhenjiang Hu, and Masato Takeichi)

Mar 3: JP: Hilbert spaces

Mar 8: Eran: Time and space complexity

Mar 10: Will: Reversible Logic (Toffoli)

Eric: Categorical Quantum Mechanics (Abramsky and Coecke)

Jason: Quantum Lambda Calculus (Selinger and Valiron)

Josh: Linear Logic (Girard)

Background Reading

Advanced Material

Optional Material

Amr Sabry