ترغب بنشر مسار تعليمي؟ اضغط هنا

The Distribution of Reversible Functions is Normal

61   0   0.0 ( 0 )
 نشر من قبل W B Langdon
 تاريخ النشر 2018
  مجال البحث الهندسة المعلوماتية
والبحث باللغة English
 تأليف W. B. Langdon




اسأل ChatGPT حول البحث

The distribution of reversible programs tends to a limit as their size increases. For problems with a Hamming distance fitness function the limiting distribution is binomial with an exponentially small chance (but non~zero) chance of perfect solution. Sufficiently good reversible circuits are more common. Expected RMS error is also calculated. Random unitary matrices may suggest possible extension to quantum computing. Using the genetic programming (GP) benchmark, the six multiplexor, circuits of Toffoli gates are shown to give a fitness landscape amenable to evolutionary search. Minimal CCNOT solutions to the six multiplexer are found but larger circuits are more evolvable.



قيم البحث

اقرأ أيضاً

An analog computer makes use of continuously changeable quantities of a system, such as its electrical, mechanical, or hydraulic properties, to solve a given problem. While these devices are usually computationally more powerful than their digital co unterparts, they suffer from analog noise which does not allow for error control. We will focus on analog computers based on active electrical networks comprised of resistors, capacitors, and operational amplifiers which are capable of simulating any linear ordinary differential equation. However, the class of nonlinear dynamics they can solve is limited. In this work, by adding memristors to the electrical network, we show that the analog computer can simulate a large variety of linear and nonlinear integro-differential equations by carefully choosing the conductance and the dynamics of the memristor state variable. To the best of our knowledge, this is the first time that circuits based on memristors are proposed for simulations. We study the performance of these analog computers by simulating integro-differential models related to fluid dynamics, nonlinear Volterra equations for population growth, and quantum models describing non-Markovian memory effects, among others. Finally, we perform stability tests by considering imperfect analog components, obtaining robust solutions with up to $13%$ relative error for relevant timescales.
135 - Michael P. Frank 2018
Landauers Principle that information loss from a computation implies entropy increase can be rigorously proved from mathematical physics. However, carefully examining its detailed formulation reveals that the traditional identification of logically r eversible computational operations with bijective transformations of the full digital state space is actually not the correct logical-level characterization of the full set of classical computational operations that can be carried out physically with asymptotically zero energy dissipation. To find the correct logical conditions for physical reversibility, we must account for initial-state probabilities when applying the Principle. The minimal logical-level requirement for the physical reversibility of deterministic computational operations is that the subset of initial states that exhibit nonzero probability in a given statistical operating context must be transformed one-to-one into final states. Thus, any computational operation is conditionally reversible relative to any sufficiently-restrictive precondition on its initial state, and the minimum dissipation required for any deterministic operation by Landauers Principle asymptotically approaches 0 when the probability of meeting any preselected one of its suitable preconditions approaches 1. This realization facilitates simpler designs for asymptotically thermodynamically reversible computational hardware, compared to designs that are restricted to using only fully-bijective operations such as Toffoli type operations. Thus, this more general framework for reversible computing provides a more effective theoretical foundation to use for the design of practical reversible computers than does the more restrictive traditional model of reversible logic. In this paper, we formally develop the theoretical foundations of the generalized model, and briefly survey some of its applications.
We investigate the subclass of reversible functions that are self-inverse and relate them to reversible circuits that are equal to their reverse circuit, which are called palindromic circuits. We precisely determine which self-inverse functions can b e realized as a palindromic circuit. For those functions that cannot be realized as a palindromic circuit, we find alternative palindromic representations that require an extra circuit line or quantum gates in their construction. Our analyses make use of involutions in the symmetric group $S_{2^n}$ which are isomorphic to self-inverse reversible function on $n$ variables.
The paper studies the main aspects of the realization of 2 x 2 ternary reversible circuits based on cycles, considering the results of the realization of all 362,880 2 x 2 ternary reversible functions. It has been shown that in most cases, realizatio ns obtained with the MMD+ algorithm have a lower complexity (in terms of cost) than realizations based on cycles. In the paper it is shown under which conditions realizations based on transpositions may have a higher or a lower cost than realizations using larger cycles. Finally it is shown that there are a few special cases where realizations based on transpositions have the same cost or possibly lower cost than the MMD+ based realizations. Aspects of scaleability are considered in terms of 2 x 2-based n x n reversible circuits.
التعليقات
جاري جلب التعليقات جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
mircosoft-partner

هل ترغب بارسال اشعارات عن اخر التحديثات في شمرا-اكاديميا