Edison Tsai, Marek Perkowski

DOI Number
First page
Last page


Encoding of finite automata or state machines is critical to modern digital logic design methods for sequential circuits. Encoding is the process of assigning to every state, input value, and output value of a state machine a binary string, which is used to represent that state, input value, or output value in digital logic. Usually, one wishes to choose an encoding that, when the state machine is implemented as a digital logic circuit, will optimize some aspect of that circuit. For instance, one might wish to encode in such a way as to minimize power dissipation or silicon area. For most such optimization objectives, no method to find the exact solution, other than a straightforward exhaustive search, is known.
Recent progress towards producing a quantum computer of large enough scale to surpass modern supercomputers has made it increasingly relevant to consider how quantum computers may be used to solve problems of practical interest. A quantum computer using Grover’s well-known search algorithm can perform exhaustive searches that would be impractical on a classical computer, due to the speedup provided by Grover’s algorithm. Therefore, we propose to use Grover’s algorithm to find optimal encodings for finite state machines via exhaustive search. We demonstrate the design of quantum circuits that allow Grover’s algorithm to be used for this purpose. The quantum circuit design methods that we introduce are potentially applicable to other problems as well.


Quantum Algorithm, Automata Encoding, Finete State Machines

Full Text:



J. M. Gambetta, J. M. Chow, and M. Steffen, “Building logical qubits in a superconducting quantum computing system,” npj Quantum Information, vol. 3, p. 2, Jan. 2017.

L. K. Grover, “A fast quantum mechanical algorithm for database search,” in Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing, pp. 212–219, May 1996.

L. K. Grover, “Quantum mechanics helps in searching for a needle in a haystack,” Phys. Rev. Lett., vol. 79, pp. 325–328, Jul 1997.

L. K. Grover, “A framework for fast quantum mechanical algorithms,” in Proceedings of the Thirtieth Annual ACM Symposium on Theory of Computing, STOC ’98, (New York, NY, USA), pp. 53–62, ACM, 1998.

G. Wendin, “Quantum information processing with superconducting circuits: a review,” Reports on Progress in Physics, vol. 80, no. 10, p. 106001, 2017.

J. Hartmanis, “On the state assignment problem for sequential machines. I,” IRE Transactions on Electronic Computers, vol. EC-10, pp. 157–165, June 1961.

R. E. Stearns and J. Hartmanis, “On the state assignment problem for sequential machines. II,” IRE Transactions on Electronic Computers, vol. EC-10, pp. 593–603, Dec. 1961.

L. Benini and G. D. Micheli, “State assignment for low power dissipation,” IEEE Journal of Solid-State Circuits, vol. 30, pp. 258–268, Mar. 1995.

G. D. Hachtel, M. Hermida, A. Pardo, M. Poncino, and F. Somenzi, “Re-encoding sequential circuits to reduce power dissipation,” in Proceedings of the 1994 IEEE/ACM International Conference on Computer-aided Design, ICCAD ’94, (Los Alamitos, CA, USA), pp. 70–73, IEEE Computer Society Press, 1994.

G. D. Micheli, R. K. Brayton, and A. Sangiovanni-Vincentelli, “Optimal state assignment for finite state machines,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 4, pp. 269–285, July 1985.

T. Villa and A. Sangiovanni-Vincentelli, “NOVA: state assignment of finite state machines for optimal two-level logic implementation,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 9, pp. 905–924, Sept. 1990.

S. Devadas and A. R. Newton, “Exact algorithms for output encoding, state assignment and four-level boolean minimization,” in System Sciences, 1990., Proceedings of the Twenty-Third Annual Hawaii International Conference on, vol. 1, pp. 387–396, IEEE, 1990.

E. F. Moore, “Gedanken Experiments on Sequential Machines,” in Automata Studies, pp. 129–153, Princeton U., 1956.

J. Hartmanis, “Loop-free structure of sequential machines,” Information and Control, vol. 5, no. 1, pp. 25–43, 1962.

G. H. Mealy, “A method for synthesizing sequential circuits,” Bell System Technical Journal, vol. 34, no. 5, pp. 1045–1079, 1955.

M. A. Nielsen and I. L. Chuang, Quantum Computation and Quantum Information. Cambridge University Press, 10th anniversary ed., 2010.

M. Boyer, G. Brassard, P. Høyer, and A. Tapp, “Tight bounds on quantum searching,” Fortschritte der Physik, vol. 46, no. 4-5, pp. 493–505, 1998.

G. Brassard, P. Høyer, and A. Tapp, “Quantum counting,” in Automata, Languages and Programming, pp. 820–831, Springer Berlin Heidelberg, 1998.

D. Maslov and G. Dueck, “Improved quantum cost for n-bit toffoli gates,” Electronics Letters, vol. 39, pp. 1790–1791, December 2003.

A. Barenco, C. H. Bennett, R. Cleve, D. P. DiVincenzo, N. Margolus, P. Shor, T. Sleator, J. A. Smolin, and H. Weinfurter, “Elementary gates for quantum computation,” Phys. Rev. A, vol. 52, pp. 3457– 3467, Nov 1995.


  • There are currently no refbacks.

ISSN: 0353-3670 (Print)

ISSN: 2217-5997 (Online)

COBISS.SR-ID 12826626