Published In
Facta Universitatis, Series: Electronics and Energetics
Document Type
Article
Publication Date
2020
Subjects
Cellular automata, Logic circuits -- Design and construction, Quantum Algorithm, Automata Encoding
Abstract
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.
Locate the Document
DOI
10.2298/FUEE2002169T
Persistent Identifier
https://archives.pdx.edu/ds/psu/32664
Citation Details
Tsai, E., & Perkowski, M. (2020). A QUANTUM AlgoRIThM FoR AUToMATA ENCodINg. Facta Universitatis, Series: Electronics and Energetics, 33(2), 169-215.
Description
© 2020 by the authors. Facta Universitatis.This article is an open access article distributed under the terms and conditions of the Creative Commons Attribution (CC BY) license (http://creativecommons.org/licenses/by/4.0/).