Facta Universitatis, Series: Electronics and Energetics
Cellular automata, Logic circuits -- Design and construction, Quantum Algorithm, Automata Encoding
Encoding of ﬁnite 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 ﬁnd 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 ﬁnd optimal encodings for ﬁnite 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.
Locate the Document
Tsai, E., & Perkowski, M. (2020). A QUANTUM AlgoRIThM FoR AUToMATA ENCodINg. Facta Universitatis, Series: Electronics and Energetics, 33(2), 169-215.