%0 Book Section %1 langdon:2003:normal %A Langdon, W. B. %B Genetic Programming Theory and Practise %D 2003 %E Riolo, Rick L. %E Worzel, Bill %I Kluwer %K CCNOT, Toffoli, algorithms, computation, computing, consumption evolutionary fitness genetic landscape, low power programming, quantum %P 173--188 %T The distribution of Reversible Functions is Normal %U http://www.cs.ucl.ac.uk/staff/W.Langdon/ftp/papers/wbl_reversible.ps.gz %X 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. %& 11 %@ 1-4020-7581-2

@incollection{langdon:2003:normal, abstract = {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.}, added-at = {2008-06-19T17:35:00.000+0200}, author = {Langdon, W. B.}, biburl = {https://www.bibsonomy.org/bibtex/2b9a19d9daa49e245603864ec6c0b1ad4/brazovayeye}, booktitle = {Genetic Programming Theory and Practise}, chapter = 11, editor = {Riolo, Rick L. and Worzel, Bill}, interhash = {13dec47da0463e70529a55cb9ddf6a6d}, intrahash = {b9a19d9daa49e245603864ec6c0b1ad4}, isbn = {1-4020-7581-2}, keywords = {CCNOT, Toffoli, algorithms, computation, computing, consumption evolutionary fitness genetic landscape, low power programming, quantum}, notes = {Extension of work presented at Dagstuhl See page 11 of \cite{beyer_et_al:DSP:2006:498}}, pages = {173--188}, publisher = {Kluwer}, size = {16 pages}, timestamp = {2008-06-19T17:45:01.000+0200}, title = {The distribution of Reversible Functions is {Normal}}, url = {http://www.cs.ucl.ac.uk/staff/W.Langdon/ftp/papers/wbl_reversible.ps.gz}, year = 2003 }