Homepage RC
Invited Talks

Invited Talks

Relating the Limits of Computational Reversibility to Emergence

Dr. Kalyan S. Perumalla

Oak Ridge National Laboratory, Tennessee, USA

Abstract: An interesting aspect of reversible computation is that analyses of the theoretical limits of reversibility can touch metaphysical aspects. An objective treatment in reversible computation has given us the understanding that any expressed finite computation (for example, a Turing program) is effectively reversible by design or by transformation. However, a subjective treatment of reversibility regarding the purpose or meaning of a computation can lead to metaphysical considerations. A stark way this notion arises is in the concept of "emergence." Informally, emergence involves the phenomenon of something (new) arising or coming into view (for example, a leader emerging in a democracy of equals, or new particles spontaneously emerging from sub-atomic particle collisions). We argue that the concept of emergence and the concept of reversibility are disjunctive in any objective treatment. If something emerges (subjective view), it can never be reversed (objective view). If something can be reversed, it cannot have emerged. If the arguments hold, they lead to a strange equivalence class of terms that equates the following words to mean essentially the same thing (or lose meaning together): new, random, (dis)orderly, (in)elegant, (un)interesting, first, spontaneous, abrupt, (un)expected, and so on. When the computation of physics and the physics of computation meet in their limits, the conflu- ence of subjective and objective views with respect to their reversibility opens the counter-intuitive implications of the aforementioned equiva- lence class. We relax the concept of emergence into three types, the first encompassing the fully reversible objective view, the second capturing the fundamentally irreversible subjective view, and the third bridging the two ends by partial reversibility and proxy randomization.



Kalyan Perumalla, Ph.D., is a Distinguished R&D staff member and manager at the Oak Ridge National Laboratory. He is the founding Group Leader of the Discrete Computing Systems Group in the Computational Sciences and Engineering Division. He also serves as an Adjunct professor in the School of Computational Sciences and Engineering at the Georgia Institute of Technology.

He has published his research and delivered invited lectures and tutorials on topics spanning high performance computing and simulation. His recent book Introduction to Reversible Computing is among the first few in its area. He co-authored another monograph, three book chapters, and over 100 articles in peer-reviewed conferences and journals. Five of his co-authored papers received the best paper awards, in 1999, 2002, 2005, 2008 and 2014. His research prototypes in parallel and distributed computing have been disseminated to research institutions worldwide. He earned his Ph.D. in computer science from the Georgia Institute of Technology in 1999.

Dr. Perumalla is a winner of the US Department of Energy Early Career Award in Advanced Scientific Computing Research, 2010-2015, providing $2.5 million for basic research dedicated to reversible computing solutions at Exascale. In 2015, he was selected as a Fellow of the Institute of Advanced Study at the Durham University, UK. He has been nominated to serve on the National Academy of Sciences’ Technical Advisory Board on Information Science at the US Army Research Laboratory, 2015-2017. Dr. Perumalla serves as program committee member, editorial board member, and reviewer for multiple international conferences and journals in computing. He has performed over the past 15 years as principal investigator and co-principal investigator on research and development projects sponsored by the Department of Energy, Department of Homeland Security, DARPA, Army Research Laboratory, National Science Foundation, and industry.

Tools for quantum and reversible circuit compilation

Dr. Martin Roetteler

Senior Researcher, Microsoft Research Redmond, USA

Abstract: I will present tools for resource-aware compilation of higher-level, irreversible programs into lower-level, reversible circuits. Our main focus is on optimizing the memory footprint of the resulting reversible networks.

We discuss a number of examples to illustrate our compilation strategy for problems at scale, including a reversible implementation of hash functions such as SHA-256, automatic generation of reversible integer arithmetic from irreversible descriptions, as well as a test-bench of Boolean circuits that is used by the classical Circuits and Systems community. Our main findings are that, when compared with Bennett's original ``compute-copy-uncompute'', it is possible to reduce the space complexity by 75 percent or more, at the price of having an only moderate increase in circuit size as well as in compilation time.

Based in part on work with Matt Amy, Alex Parent, and Krysta M. Svore:
http://arxiv.org/abs/1510.00377
http://arxiv.org/abs/1603.01635



Martin Roetteler received a Ph.D. in computer science from the University of Karlsruhe, Germany, in 2001. Subsequently, from 2003-2004 he held a post-doc position at the Institute for Quantum Computing from at U Waterloo. From 2005 onward he was a Research Staff Member at NEC Laboratories America and from 2007-2013 he was the leader of NEC's Quantum IT group in Princeton. In 2013, Martin joined Microsoft Research in Redmond as a Senior Researcher. He worked on projects funded by ARO, NSA, the European Union, and the German DFG. He was the PI of the IARPA QCS project TORQUE, a joint effort between Raytheon/BBN Technologies, NEC Labs America, U Waterloo, and U Melbourne. Martin's research focuses on quantum algorithms, quantum programming languages, and quantum error-correction.

Personal website: http://research.microsoft.com/en-us/people/martinro/










info@reversible-computation.org