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,
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:
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/