Journal of Physical Studies 15(3), Article 3001 [6 pages] (2011) DOI: https://doi.org/10.30970/jps.15.3001 QUANTUM ALGORITHM OF EVOLUTIONARY ANALYSIS OF ONE DIMENSIONAL CELLULAR AUTOMATA B. Pavlyshenko Ivan Franko National University of Lviv, Faculty of Electronics, 50, Drahomanov St., Lviv, 79005 Ukraine e-mail: pavlsh@yahoo.com

It is shown that irreversible classical cellular automata can be performed by quantum algorithm using additional ancilla registers. An algorithm for cellular automata states analysis has been proposed. This algorithm is based on the elements of Grover's algorithm -- the inversion of amplitude of searched states and unitary transform of inversion about the average. The inversion of searched states amplitudes can be performed by the quantum Toffoli gate.

PACS number(s): 03.67.Lx, 03.67.-a

pdf