A Quantum Algorithm for Automata Encoding Edison Tsai and Marek Perkowski Department of Electrical and Computer Engineering Portland State University Abstract Encoding of finite automata or state machines is critical to modern digital logic design methods for sequential circuits. Encoding is the pro- cess 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 prob- lems of practical interest. A quantum computer using Grover’s well-known search algorithm can perform exhaustive searches that would be imprac- tical on a classical computer, due to the speedup provided by Grover’s al- gorithm. 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. 1 Introduction Although the concept of quantum computing has existed for decades, only recently has it appeared that quantum computers of sufficient scale to solve realistic problems may become available in the near future.1 The development of such quantum computers is of great interest because they are capable of solving certain classes of problems with a time complex- ity better than the best achievable with a classical computer. Grover’s 1See [1], Introduction, paragraph 6: “A physical quantum computer. . . is still an outstand- ing challenge. However, in recent work, physical qubits. . . have reached the point where errors are at or below the threshold, and networks of 4–9 superconducting qubits with individual control and readout have been used to show concepts of error correction. Over the next few years, the field will be in a stage of building interesting quantum devices with a complexity that could never be emulated in full generality on a classical computer (∼50 or more qubits).” 1 A Quantum Algorithm for Automata Encoding Edison Tsai and Marek Perkowski Department of Electrical and Computer Engineering Portland State University Abstract Encoding of finite automata or state machines is critical to modern digital logic design methods for sequential circuits. Encoding is the pro- cess 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 prob- lems of practical interest. A quantum computer using Grover’s well-known search algorithm can perform exhaustive searches that would be imprac- tical on a classical computer, due to the speedup provided by Grover’s al- gorithm. 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. 1 Introduction Although the concept of quantum computing has existed for decades, only recently has it appeared that quantum computers of sufficient scale to solve realistic problems may become available in the near future.1 The development of such quantum computers is of great interest because they are capable of solving certain classes of problems with a time complex- ity better than the best achievable with a classical computer. Grover’s 1See [1], Introduction, paragraph 6: “A physical quantum computer. . . is still an outstand- ing challenge. However, in recent work, physical qubits. . . have reached the point where errors are at or below the threshold, and networks of 4–9 superconducting qubits with individual control and readout have been used to show concepts of error correction. Over the next few years, the field will be in a stage of building interesting quantum devices with a complexity that could never be emulated in full generality on a classical computer (∼50 or more qubits).” 1 FACTA UNIVERSITATIS Series: Electronics and Energetics Vol. 33, No 2, June 2020, pp. 169 - 215 https://doi.org/10.2298/FUEE2002169T Edison Tsai, Marek Perkowski Received September 7, 2017; received in revised form January 28, 2020 Corresponding author: Marek Perkowski Department of Electrical and Computer Engineering, Portland State University, USA (E-mail: mperkows@ee.pdx.edu) FACTA UNIVERSITATIS Series: Electronics and Energetics Vol. 28, No 4, December 2015, pp. 507 - 525 DOI: 10.2298/FUEE1504507S hoRIZoNTAl CURRENT BIPolAR TRANSISToR (hCBT) – A loW-CoST, hIgh-PERFoRMANCE FlEXIBlE BICMoS TEChNologY FoR RF CoMMUNICATIoN APPlICATIoNS Tomislav Suligoj1, Marko Koričić1, Josip Žilak1, hidenori Mochizuki2, So-ichi Morita2, Katsumi Shinomura2, hisaya Imai2 1University of Zagreb, Faculty of Electrical Engineering and Computing, Department of Electronics, Micro- and Nano-electronics Laboratory, Croatia 2Asahi Kasei Microdevices Co. 5-4960, Nobeoka, Miyazaki, 882-0031, Japan Abstract. In an overview of Horizontal Current Bipolar Transistor (HCBT) technology, the state-of-the-art integrated silicon bipolar transistors are described which exhibit fT and fmax of 51 GHz and 61 GHz and fTBVCEO product of 173 GHzV that are among the highest-performance implanted-base, silicon bipolar transistors. HBCT is integrated with CMOS in a considerably lower-cost fabrication sequence as compared to standard vertical-current bipolar transistors with only 2 or 3 additional masks and fewer process steps. Due to its specific structure, the charge sharing effect can be employed to increase BVCEO without sacrificing fT and fmax. Moreover, the electric field can be engineered just by manipulating the lithography masks achieving the high-voltage HCBTs with breakdowns up to 36 V integrated in the same process flow with high-speed devices, i.e. at zero additional costs. Double-balanced active mixer circuit is designed and fabricated in HCBT technology. The maximum IIP3 of 17.7 dBm at mixer current of 9.2 mA and conversion gain of -5 dB are achieved. Key words: BiCMOS technology, Bipolar transistors, Horizontal Current Bipolar Transistor, Radio frequency integrated circuits, Mixer, High-voltage bipolar transistors. 1. INTRODUCTION In the highly competitive wireless communication markets, the RF circuits and systems are fabricated in the technologies that are very cost-sensitive. In order to minimize the fabrication costs, the sub-10 GHz applications can be processed by using the high-volume silicon technologies. It has been identified that the optimum solution might Received March 9, 2015 Corresponding author: Tomislav Suligoj University of Zagreb, Faculty of Electrical Engineering and Computing, Department of Electronics, Micro- and Nano-electronics Laboratory, Croatia (e-mail: tom@zemris.fer.hr) A QUANTUM AlgoRIThM FoR AUToMATA ENCodINg Department of Electrical and Computer Engineering, Portland State University, USA 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. Key words: Quantum Algorithm, Automata Encoding, Finete State Machines. © 2020 by University of Niš, Serbia | Creative Commons License: CC BY-NC-ND well-known search algorithm [2, 3, 4] provides a commonly cited example of such a class of problems. However, despite the theoretical capabili- ties of quantum computing, virtually no work has been published that demonstrates a specific, concrete example of Grover’s algorithm (or an- other quantum algorithm) applied to solve a problem of practical interest. This gap in the literature has become increasingly relevant as large-scale quantum computers move ever closer to reality.2 To fill this gap, we demonstrate in this work how Grover’s algorithm can be applied to the problem of state encoding for finite state machines (FSMs). A well-known problem in digital logic design, which has been rec- ognized for over 50 years [6, 7] and today remains important and relevant to the design of virtually all very-large-scale integrated (VLSI) circuits and systems including microprocessors, state encoding (a.k.a. state as- signment) is the assignment of binary states in a digital logic circuit to represent the internal states of an FSM. Distinct encodings for the same FSM produce distinct implementations in digital logic, which may differ considerably in complexity [6]. Usually, one wishes to find a state encod- ing which is minimal with respect to some metric, e.g., power [8, 9] or silicon area [10, 11] of the resulting digital circuit. Our goal is to find the exact minimum (with respect to one particular metric) solution for state and input encoding of finite state machines. So far, only one previous work [12] has attempted to find exact minimum solutions to this problem. Furthermore, the methods in [12] find solutions for only state and not input encoding. There is currently no published result that finds the exact minimum solution for concurrent state and input assignment. The methods in [12] rely on finding prime implicants and solving a covering problem on the set of all prime implicants. This would be difficult to implement using Grover’s algorithm on a quantum computer because at least one qubit would be required for each prime im- plicant and the total number of prime implicants can be extremely large. Therefore, we do not attempt to directly adapt the approach presented in [12] for a quantum computer. Instead, we use a simplified cost met- ric from [6, 7], in which the cost of an encoding is defined as the total number of dependencies of the next-state functions on current state and input variables. The use of this metric makes it easier to construct the quantum circuits necessary to use Grover’s algorithm to search for encod- ings. Since Grover’s algorithm effectively performs an exhaustive search, our method is always able to find an encoding with exact minimum cost. The techniques that we use to adapt Grover’s algorithm for the purpose of encoding finite state machines may prove useful for other purposes as well. 2See above; see also [5], Abstract: “Advanced quantum simulation experiments have been shown with up to nine qubits, while a demonstration of quantum supremacy with fifty qubits is anticipated in just a few years. Quantum supremacy means that the quantum system can no longer be simulated by the most powerful classical supercomputers.” 2 2 Finite State Machines and State En- codings 2.1 Review of Finite State Machines We assume that the reader is familiar with the concept of finite state machines (FSMs) and how they are realized using digital logic, as well as with the state encoding (a.k.a. state assignment or secondary state assignment) problem. For the sake of self-containment we briefly review these subjects here. An FSM consists of a set of internal states (call it S) together with sets of inputs and outputs (call them I and O, respectively); at all times, it maintains a single internal state which is an element of S, is presented with an input value which is an element of I, and produces an output value which is an element of O. The machine’s operation is idealized as a discrete-time process; with each successive unit of time, it updates its internal state and output in a deterministic fashion based on its current internal state and the input value that is being presented. Thus, the internal state of the machine at time t + 1 is a function of the internal state at time t and the input at time t: St+1 = δ(St, It), where St ∈ S is the internal state at time t, It ∈ I is the input value at time t, and St+1 ∈ S is the internal state at time t + 1. We refer to the function δ as the transition function for the FSM. This function is also commonly called the excitation function or next-state function. The output of an FSM can either directly depend on only its internal state, or it can directly depend on both the internal state and the input. The former scenario corresponds to a so-called Moore machine [13, 14] whereas the latter corresponds to a so-called Mealy machine [15, 14]. Here, as will be discussed in more detail below, we only consider the problem of encoding internal states; thus, the type of the machine is irrelevant and our work is equally applicable to both. From now on, for the sake of brevity, we will simply use “states” to refer to the internal states of an FSM. The phrase “internal states” avoids confusion with other objects also referred to as “states”, in particular the input and output values which are sometimes called input and output states, respectively. We will always use the phrases “input (output)” or “input (output) values” here, so that there is no risk of confusion in using simply “states” to refer to internal states. FSMs are commonly implemented using digital logic circuits consisting of an array of flip-flops, which stores the current state, together with com- binational logic (often referred to as the next-state logic), which computes the next state from the current state and current input. To design this combinational logic, one must select a state encoding, a mapping which associates each state of the FSM with a state of the flip-flop array. More precisely, since the state of a flip-flop array is simply a binary string, a state encoding is a function cS : S → {0, 1}n that maps each state of the FSM to a vector of flip-flop states that represents the FSM state in a digital logic circuit. Here, n denotes the number of flip-flops in the circuit. 3 170 E. TSAI, M. PERKOWSKI A Quantum Algorithm for Automata Encoding 171 well-known search algorithm [2, 3, 4] provides a commonly cited example of such a class of problems. However, despite the theoretical capabili- ties of quantum computing, virtually no work has been published that demonstrates a specific, concrete example of Grover’s algorithm (or an- other quantum algorithm) applied to solve a problem of practical interest. This gap in the literature has become increasingly relevant as large-scale quantum computers move ever closer to reality.2 To fill this gap, we demonstrate in this work how Grover’s algorithm can be applied to the problem of state encoding for finite state machines (FSMs). A well-known problem in digital logic design, which has been rec- ognized for over 50 years [6, 7] and today remains important and relevant to the design of virtually all very-large-scale integrated (VLSI) circuits and systems including microprocessors, state encoding (a.k.a. state as- signment) is the assignment of binary states in a digital logic circuit to represent the internal states of an FSM. Distinct encodings for the same FSM produce distinct implementations in digital logic, which may differ considerably in complexity [6]. Usually, one wishes to find a state encod- ing which is minimal with respect to some metric, e.g., power [8, 9] or silicon area [10, 11] of the resulting digital circuit. Our goal is to find the exact minimum (with respect to one particular metric) solution for state and input encoding of finite state machines. So far, only one previous work [12] has attempted to find exact minimum solutions to this problem. Furthermore, the methods in [12] find solutions for only state and not input encoding. There is currently no published result that finds the exact minimum solution for concurrent state and input assignment. The methods in [12] rely on finding prime implicants and solving a covering problem on the set of all prime implicants. This would be difficult to implement using Grover’s algorithm on a quantum computer because at least one qubit would be required for each prime im- plicant and the total number of prime implicants can be extremely large. Therefore, we do not attempt to directly adapt the approach presented in [12] for a quantum computer. Instead, we use a simplified cost met- ric from [6, 7], in which the cost of an encoding is defined as the total number of dependencies of the next-state functions on current state and input variables. The use of this metric makes it easier to construct the quantum circuits necessary to use Grover’s algorithm to search for encod- ings. Since Grover’s algorithm effectively performs an exhaustive search, our method is always able to find an encoding with exact minimum cost. The techniques that we use to adapt Grover’s algorithm for the purpose of encoding finite state machines may prove useful for other purposes as well. 2See above; see also [5], Abstract: “Advanced quantum simulation experiments have been shown with up to nine qubits, while a demonstration of quantum supremacy with fifty qubits is anticipated in just a few years. Quantum supremacy means that the quantum system can no longer be simulated by the most powerful classical supercomputers.” 2 2 Finite State Machines and State En- codings 2.1 Review of Finite State Machines We assume that the reader is familiar with the concept of finite state machines (FSMs) and how they are realized using digital logic, as well as with the state encoding (a.k.a. state assignment or secondary state assignment) problem. For the sake of self-containment we briefly review these subjects here. An FSM consists of a set of internal states (call it S) together with sets of inputs and outputs (call them I and O, respectively); at all times, it maintains a single internal state which is an element of S, is presented with an input value which is an element of I, and produces an output value which is an element of O. The machine’s operation is idealized as a discrete-time process; with each successive unit of time, it updates its internal state and output in a deterministic fashion based on its current internal state and the input value that is being presented. Thus, the internal state of the machine at time t + 1 is a function of the internal state at time t and the input at time t: St+1 = δ(St, It), where St ∈ S is the internal state at time t, It ∈ I is the input value at time t, and St+1 ∈ S is the internal state at time t + 1. We refer to the function δ as the transition function for the FSM. This function is also commonly called the excitation function or next-state function. The output of an FSM can either directly depend on only its internal state, or it can directly depend on both the internal state and the input. The former scenario corresponds to a so-called Moore machine [13, 14] whereas the latter corresponds to a so-called Mealy machine [15, 14]. Here, as will be discussed in more detail below, we only consider the problem of encoding internal states; thus, the type of the machine is irrelevant and our work is equally applicable to both. From now on, for the sake of brevity, we will simply use “states” to refer to the internal states of an FSM. The phrase “internal states” avoids confusion with other objects also referred to as “states”, in particular the input and output values which are sometimes called input and output states, respectively. We will always use the phrases “input (output)” or “input (output) values” here, so that there is no risk of confusion in using simply “states” to refer to internal states. FSMs are commonly implemented using digital logic circuits consisting of an array of flip-flops, which stores the current state, together with com- binational logic (often referred to as the next-state logic), which computes the next state from the current state and current input. To design this combinational logic, one must select a state encoding, a mapping which associates each state of the FSM with a state of the flip-flop array. More precisely, since the state of a flip-flop array is simply a binary string, a state encoding is a function cS : S → {0, 1}n that maps each state of the FSM to a vector of flip-flop states that represents the FSM state in a digital logic circuit. Here, n denotes the number of flip-flops in the circuit. 3 170 E. TSAI, M. PERKOWSKI A Quantum Algorithm for Automata Encoding 171 Similarly, in order to implement an FSM with a digital logic circuit, one must also select an input encoding, which maps each input value of the FSM to an array of Boolean values, where each Boolean value represents the value supplied on an input wire to the digital logic circuit. In other words, an input encoding is a function cI : I → {0, 1}m where m is the number of input wires. Finally, in addition to the state and input encoding, one must select an output encoding to fully implement an FSM with digital logic. However, we do not consider the problem of encoding outputs in this paper and consequently, we will ignore the outputs of an FSM from now on. We will use “encoding” without further qualification to mean the combination of a state and input encoding. We may also use the phrase “encoding of [a state or input value]” to mean the combination of state or input variable values corresponding to that state or input value under a given encoding. In other words, given a state encoding as a function cS as described above, the encoding of a state S is simply cS(S); the situation is analogous for inputs. Finally, we also use “encoding” as a verb to mean the process of selecting or generating an encoding. Thus, we describe the main objective of this paper as solving an FSM encoding problem. From now on, when considering a digital logic circuit implementation of an FSM, we will follow the common convention of using Qi to denote the state of the ith flip-flop at a given point in time. We will also use xj to represent the value on the jth input wire at a given point in time. We refer to the variables Q1 through Qn as state variables and the variables x1 through xm as input variables. Figure 1 illustrates this notation in the context of a digital logic circuit that implements an FSM. We distinguish carefully between input values, which are the symbolic inputs of an FSM and elements of the set I, and input variables, which are the Boolean variables x1 through xm used in a digital logic circuit to represent input values. Similarly, we also distinguish between states and state variables—states are the symbolic internal states of an FSM and elements of the set S, while state variables are the variables Q1 through Qn that correspond to the states of individual flip-flops and together rep- resent the symbolic state. To help avoid confusion, we will always follow a consistent notational convention where, in addition to using Qi and xj for states and input values respectively, we also use S or S1, S2, etc. to repre- sent states and I, I1, I2, etc. to represent input values. In the context of an FSM, the word “input” without further qualification will always refer to an input value and not an input variable. A state encoding may be bijective, that is, each flip-flop array state represents exactly one FSM state, or it may not. Non-bijective encodings might arise (for instance) if the number of possible flip-flop array states is greater than the number of FSM states, in which case some of the possible flip-flop states will not represent any FSM state at all. Similarly, input encodings may also be bijective, or not. For a bijective input encoding, each possible combination of assignments to input variables corresponds to exactly one input value. We say that an encoding (the combination of both state and input encodings) is bijective if both the state and input encodings are bijective. If an encoding is bijective, then any combination of assignments to the 4 D1 Q1 D2 Q2 Dn Qn δ1(Q1, . . . , Qn, x1, . . . , xm) δ2(Q1, . . . , Qn, x1, . . . , xm) δn(Q1, . . . , Qn, x1, . . . , xm) x1 xm Figure 1: General structure of an FSM implemented as a digital logic circuit; output logic not shown. 5 172 E. TSAI, M. PERKOWSKI A Quantum Algorithm for Automata Encoding 173 Similarly, in order to implement an FSM with a digital logic circuit, one must also select an input encoding, which maps each input value of the FSM to an array of Boolean values, where each Boolean value represents the value supplied on an input wire to the digital logic circuit. In other words, an input encoding is a function cI : I → {0, 1}m where m is the number of input wires. Finally, in addition to the state and input encoding, one must select an output encoding to fully implement an FSM with digital logic. However, we do not consider the problem of encoding outputs in this paper and consequently, we will ignore the outputs of an FSM from now on. We will use “encoding” without further qualification to mean the combination of a state and input encoding. We may also use the phrase “encoding of [a state or input value]” to mean the combination of state or input variable values corresponding to that state or input value under a given encoding. In other words, given a state encoding as a function cS as described above, the encoding of a state S is simply cS(S); the situation is analogous for inputs. Finally, we also use “encoding” as a verb to mean the process of selecting or generating an encoding. Thus, we describe the main objective of this paper as solving an FSM encoding problem. From now on, when considering a digital logic circuit implementation of an FSM, we will follow the common convention of using Qi to denote the state of the ith flip-flop at a given point in time. We will also use xj to represent the value on the jth input wire at a given point in time. We refer to the variables Q1 through Qn as state variables and the variables x1 through xm as input variables. Figure 1 illustrates this notation in the context of a digital logic circuit that implements an FSM. We distinguish carefully between input values, which are the symbolic inputs of an FSM and elements of the set I, and input variables, which are the Boolean variables x1 through xm used in a digital logic circuit to represent input values. Similarly, we also distinguish between states and state variables—states are the symbolic internal states of an FSM and elements of the set S, while state variables are the variables Q1 through Qn that correspond to the states of individual flip-flops and together rep- resent the symbolic state. To help avoid confusion, we will always follow a consistent notational convention where, in addition to using Qi and xj for states and input values respectively, we also use S or S1, S2, etc. to repre- sent states and I, I1, I2, etc. to represent input values. In the context of an FSM, the word “input” without further qualification will always refer to an input value and not an input variable. A state encoding may be bijective, that is, each flip-flop array state represents exactly one FSM state, or it may not. Non-bijective encodings might arise (for instance) if the number of possible flip-flop array states is greater than the number of FSM states, in which case some of the possible flip-flop states will not represent any FSM state at all. Similarly, input encodings may also be bijective, or not. For a bijective input encoding, each possible combination of assignments to input variables corresponds to exactly one input value. We say that an encoding (the combination of both state and input encodings) is bijective if both the state and input encodings are bijective. If an encoding is bijective, then any combination of assignments to the 4 D1 Q1 D2 Q2 Dn Qn δ1(Q1, . . . , Qn, x1, . . . , xm) δ2(Q1, . . . , Qn, x1, . . . , xm) δn(Q1, . . . , Qn, x1, . . . , xm) x1 xm Figure 1: General structure of an FSM implemented as a digital logic circuit; output logic not shown. 5 172 E. TSAI, M. PERKOWSKI A Quantum Algorithm for Automata Encoding 173 variables Q1 through Qn and x1 through xm corresponds to a unique state and input value of the FSM. Therefore, the next state is also uniquely de- termined by the transition function δ. In this case, we define a collection of encoded transition functions δ1 through δn, where δi represents the next state of the ith flip-flop in terms of the variables Q1 through Qn and x1 through xm. In other words, the values of Q1 through Qn and x1 through xm uniquely determine a state S and input value I. If these are the current state of and input to the FSM, then the next state of the FSM will be δ(S, I) and the encoding of this next state is cS(δ(S, I)) where cS is the functional representation of a state encoding as previ- ously described. We then define δi(Q1, . . . , Qn, x1, . . . , xm) to be the i th component of cS(δ(S, I)). Encoded transition functions represent the computations to be per- formed by the next-state logic in a digital logic circuit implementation of an FSM. In other words, given a particular state encoding for an FSM, each encoded transition function gives the next state of a single flip-flop in terms of the current states of all flip-flops and the current input. Thus, digital logic design for an FSM involves realizing the encoded transition functions as digital logic circuits. Figure 1 graphically demonstrates this relationship between encoded transition functions and the digital logic implementation of an FSM. In the remainder of this paper, we will con- centrate on evaluating the cost of realizing encoded transition functions and how this cost can be minimized. If a state encoding is not bijective, one can still define a set of en- coded transition functions using the same concept—each encoded transi- tion function represents the next state of a single flip-flop in terms of the current states of all flip-flops and the current values of all input variables. However, the encoded transition “functions” defined in this way are no longer functions in the mathematical sense; they are relations instead. If the flip-flops’ current state does not correspond to any FSM state or the input variables’ values do not correspond to any FSM input value, then the next state is indeterminate (a.k.a. a “don’t-care”). In practice, digital logic design for FSMs commonly involves non-bijective encodings. Nevertheless, for reasons to be discussed later, we will only consider bi- jective encodings, for which all encoded transition functions are actual functions in the mathematical sense. Observe that this restriction implies that we are only considering FSMs where the number of states is a power of two, since no bijective encodings exist otherwise. It also implies the assumption that the machine is state-minimized, meaning that there are no equivalent states in the machine, so that no two distinct states may have the same encoding. It is common to use the notation Q+i to represent the next state of the ith flip-flop, where Q1 through Qn represent the current states of all flip-flops. In other words, Q+i = δi(Q1, . . . , Qn, x1, . . . , xm) for all i. This means that Q+i is simply a more compact notation for the function δi that can be used when it is not necessary to explicitly show that δi is a function of Q1 through Qn and x1 through xm. From now on, we will use both the Q+i and δi notations interchangeably, with the choice of notation being simply a matter of convenience. 6 2.2 Metric for Evaluating Cost of State Encod- ings The reader may observe that, by considering the implementation of FSMs using digital logic circuits, we have created a distinction between a sym- bolic FSM itself and its implementation using flip-flops and combinational logic. The former is simply an abstract mathematical concept, while the latter is a physical realization of that abstract concept. From now on, when the meaning is clear from the context, we will use “finite state machine” to refer to both an FSM in the abstract conceptual sense and physical implementations of that FSM. When the need to avoid confusion arises, we will use “FSM specification” to refer specifically to the abstract mathematical concept of an FSM. There always exist many possible implementations of any single FSM specification, since an implementation of an FSM is always associated with some encoding and there are many possible encodings for any given set of states or inputs. The differences between implementations obtained with different encodings are of great interest to the digital logic designer. In particular, the combinational circuit complexity (as measured, for in- stance, by the number of logic gates or the maximum delay) of imple- mentations may greatly vary for different encodings. Consider the FSM whose transition function is as given in Figure 2(a). Figure 2(b) depicts a possible encoding for the FSM where the four possible two-bit strings are simply allocated in the usual base-two counting order (00 first, then 01, 10, and 11). Figure 2(c) then shows the resulting encoded transition functions. These functions may be represented by the following logical expressions: Q + 1 = (Q1 ∧ x2) ∨ (Q1 ∧ ¬Q2 ∧ x1) ∨ (¬Q1 ∧ Q2 ∧ x1) ∨ (Q2 ∧ ¬x1 ∧ ¬x2) ∨ (x1 ∧ x2), Q + 2 = (Q1 ∧ Q2 ∧ ¬x1) ∨ (Q1 ∧ Q2 ∧ ¬x2) ∨ (¬Q1 ∧ ¬Q2 ∧ ¬x1) ∨(¬Q1 ∧ ¬Q2 ∧ ¬x2) ∨ (¬x1 ∧ ¬x2), which show that both Q+1 and Q + 2 depend on all four state/input variables (Q1, Q2, x1, and x2). In comparison, if the encoding shown in Figure 2(d) is used instead, then the encoded transition functions are as shown in Figure 2(e) and may be represented by the expressions Q + 1 = Q2 ∨ ¬x1, Q + 2 = (Q1 ∧ ¬x1) ∨ (Q1 ∧ x2) ∨ (¬x1 ∧ ¬x2), where we observe that Q+1 depends on only two variables (Q2 and x1) and Q+2 depends on three (Q1, x1, and x2). We therefore see that between these two encodings, the encoding from Figure 2(d) results in encoded transition functions that depend on less variables. If we make the reasonable assumption that the complexity of a digital logic circuit is correlated with its number of inputs, then we would expect the encoding from Figure 2(d) to ultimately result in a 7 174 E. TSAI, M. PERKOWSKI A Quantum Algorithm for Automata Encoding 175 variables Q1 through Qn and x1 through xm corresponds to a unique state and input value of the FSM. Therefore, the next state is also uniquely de- termined by the transition function δ. In this case, we define a collection of encoded transition functions δ1 through δn, where δi represents the next state of the ith flip-flop in terms of the variables Q1 through Qn and x1 through xm. In other words, the values of Q1 through Qn and x1 through xm uniquely determine a state S and input value I. If these are the current state of and input to the FSM, then the next state of the FSM will be δ(S, I) and the encoding of this next state is cS(δ(S, I)) where cS is the functional representation of a state encoding as previ- ously described. We then define δi(Q1, . . . , Qn, x1, . . . , xm) to be the i th component of cS(δ(S, I)). Encoded transition functions represent the computations to be per- formed by the next-state logic in a digital logic circuit implementation of an FSM. In other words, given a particular state encoding for an FSM, each encoded transition function gives the next state of a single flip-flop in terms of the current states of all flip-flops and the current input. Thus, digital logic design for an FSM involves realizing the encoded transition functions as digital logic circuits. Figure 1 graphically demonstrates this relationship between encoded transition functions and the digital logic implementation of an FSM. In the remainder of this paper, we will con- centrate on evaluating the cost of realizing encoded transition functions and how this cost can be minimized. If a state encoding is not bijective, one can still define a set of en- coded transition functions using the same concept—each encoded transi- tion function represents the next state of a single flip-flop in terms of the current states of all flip-flops and the current values of all input variables. However, the encoded transition “functions” defined in this way are no longer functions in the mathematical sense; they are relations instead. If the flip-flops’ current state does not correspond to any FSM state or the input variables’ values do not correspond to any FSM input value, then the next state is indeterminate (a.k.a. a “don’t-care”). In practice, digital logic design for FSMs commonly involves non-bijective encodings. Nevertheless, for reasons to be discussed later, we will only consider bi- jective encodings, for which all encoded transition functions are actual functions in the mathematical sense. Observe that this restriction implies that we are only considering FSMs where the number of states is a power of two, since no bijective encodings exist otherwise. It also implies the assumption that the machine is state-minimized, meaning that there are no equivalent states in the machine, so that no two distinct states may have the same encoding. It is common to use the notation Q+i to represent the next state of the ith flip-flop, where Q1 through Qn represent the current states of all flip-flops. In other words, Q+i = δi(Q1, . . . , Qn, x1, . . . , xm) for all i. This means that Q+i is simply a more compact notation for the function δi that can be used when it is not necessary to explicitly show that δi is a function of Q1 through Qn and x1 through xm. From now on, we will use both the Q+i and δi notations interchangeably, with the choice of notation being simply a matter of convenience. 6 2.2 Metric for Evaluating Cost of State Encod- ings The reader may observe that, by considering the implementation of FSMs using digital logic circuits, we have created a distinction between a sym- bolic FSM itself and its implementation using flip-flops and combinational logic. The former is simply an abstract mathematical concept, while the latter is a physical realization of that abstract concept. From now on, when the meaning is clear from the context, we will use “finite state machine” to refer to both an FSM in the abstract conceptual sense and physical implementations of that FSM. When the need to avoid confusion arises, we will use “FSM specification” to refer specifically to the abstract mathematical concept of an FSM. There always exist many possible implementations of any single FSM specification, since an implementation of an FSM is always associated with some encoding and there are many possible encodings for any given set of states or inputs. The differences between implementations obtained with different encodings are of great interest to the digital logic designer. In particular, the combinational circuit complexity (as measured, for in- stance, by the number of logic gates or the maximum delay) of imple- mentations may greatly vary for different encodings. Consider the FSM whose transition function is as given in Figure 2(a). Figure 2(b) depicts a possible encoding for the FSM where the four possible two-bit strings are simply allocated in the usual base-two counting order (00 first, then 01, 10, and 11). Figure 2(c) then shows the resulting encoded transition functions. These functions may be represented by the following logical expressions: Q + 1 = (Q1 ∧ x2) ∨ (Q1 ∧ ¬Q2 ∧ x1) ∨ (¬Q1 ∧ Q2 ∧ x1) ∨ (Q2 ∧ ¬x1 ∧ ¬x2) ∨ (x1 ∧ x2), Q + 2 = (Q1 ∧ Q2 ∧ ¬x1) ∨ (Q1 ∧ Q2 ∧ ¬x2) ∨ (¬Q1 ∧ ¬Q2 ∧ ¬x1) ∨(¬Q1 ∧ ¬Q2 ∧ ¬x2) ∨ (¬x1 ∧ ¬x2), which show that both Q+1 and Q + 2 depend on all four state/input variables (Q1, Q2, x1, and x2). In comparison, if the encoding shown in Figure 2(d) is used instead, then the encoded transition functions are as shown in Figure 2(e) and may be represented by the expressions Q + 1 = Q2 ∨ ¬x1, Q + 2 = (Q1 ∧ ¬x1) ∨ (Q1 ∧ x2) ∨ (¬x1 ∧ ¬x2), where we observe that Q+1 depends on only two variables (Q2 and x1) and Q+2 depends on three (Q1, x1, and x2). We therefore see that between these two encodings, the encoding from Figure 2(d) results in encoded transition functions that depend on less variables. If we make the reasonable assumption that the complexity of a digital logic circuit is correlated with its number of inputs, then we would expect the encoding from Figure 2(d) to ultimately result in a 7 174 E. TSAI, M. PERKOWSKI A Quantum Algorithm for Automata Encoding 175 I1 I2 I3 I4 S1 S2 S3 S4 S2 S2 S2 S3 S4 S1 S3 S3 S2 S3 S3 S3 S4 S4 S2 S3 (a) Q1Q2S S1 0 0 S2 0 1 S3 1 0 S4 1 1 x1 x2I I1 0 0 I2 0 1 I3 1 0 I4 1 1 (b) 00 01 11 10 00 01 11 10 0 0 1 0 1 0 1 1 1 1 1 0 0 1 1 1 Q1Q2 x1x2 Q+1 00 01 11 10 00 01 11 10 1 1 0 1 1 0 0 0 1 1 0 1 1 0 0 0 Q1Q2 x1x2 Q+2 (c) Q1Q2S S1 0 1 S2 1 0 S3 1 1 S4 0 0 x1 x2I I1 1 0 I2 1 1 I3 0 1 I4 0 0 (d) 00 01 11 10 00 01 11 10 1 1 0 0 1 1 1 1 1 1 1 1 1 1 0 0 Q1Q2 x1x2 Q+1 00 01 11 10 00 01 11 10 1 0 0 0 1 0 0 0 1 1 1 0 1 1 1 0 Q1Q2 x1x2 Q+2 (e) Figure 2: (a) Transition table for an FSM; (b) an encoding for that FSM; (c) resulting encoded transition functions from that encoding; (d) another encoding for the same FSM; (e) resulting encoded transition functions. 8 less complex digital logic circuit, since the next-state logic for both flip- flops would involve fewer variables. Of course, this correlation between complexity and number of inputs depends on the precise definition of complexity used, and is not perfect in any case. There is no guarantee that the encoding from Figure 2(d) would actually produce a digital logic circuit that better suits the design goals (whatever they may be) of a digital logic designer. Nevertheless, in the remainder of this paper we will use the simple metric of defining cost as the total number of variables on which a Boolean function depends, for two reasons. First, this cost metric simplifies the problem of finding the optimal encoding for an FSM enough that we can always find the exact minimum solution. The only published work so far that achieves exact minimum results for FSM encoding is [12]. However, the authors in [12] use a different cost metric, which is based on the number of product terms when digital logic is implemented using a programmable logic array (PLA). This brings us to our second reason for using a cost metric based on number of dependencies: minimizing the number of product terms in a PLA has little to no relevance if an FSM is not implemented using PLAs, as they are not (for instance) in most modern VLSI chips. Minimizing the number of variable dependencies of a Boolean function, on the other hand, is a reasonable goal for virtually any digital logic technology, and will likely remain reasonable even for future technologies. Based on the preceding discussion, we therefore formulate as follows the problem to be solved in the remainder of this paper—given an FSM that satisfies the following conditions: • the number of states in the machine is a power of 2; • the number of possible input values to the machine is a power of 2; • the machine is state-minimal, meaning that no two distinct states are equivalent and therefore no two distinct states may be assigned the same encoding; • no two input values are equivalent and therefore no two distinct input values may be assigned the same encoding; find an encoding for the FSM with the lowest possible cost, where the cost of an encoding is defined as the sum of the costs of the encoded transition functions resulting from that encoding, and the cost of a single function is the number of variables on which the function depends. A function is considered to depend on a variable if and only if the function cannot be computed without knowledge of the value of that variable. Our cost model thus defined is the same as that used in [6] and [7]. 3 Grover’s Search Algorithm 3.1 Operation of Grover’s Algorithm In this section we briefly review Grover’s algorithm and its relevance to the state encoding problem. We assume the reader’s familiarity with quantum computing in general, and in particular with qubits, quantum states, circuits, gates, and the matrix-vector representations thereof. For 9 176 E. TSAI, M. PERKOWSKI A Quantum Algorithm for Automata Encoding 177 I1 I2 I3 I4 S1 S2 S3 S4 S2 S2 S2 S3 S4 S1 S3 S3 S2 S3 S3 S3 S4 S4 S2 S3 (a) Q1Q2S S1 0 0 S2 0 1 S3 1 0 S4 1 1 x1 x2I I1 0 0 I2 0 1 I3 1 0 I4 1 1 (b) 00 01 11 10 00 01 11 10 0 0 1 0 1 0 1 1 1 1 1 0 0 1 1 1 Q1Q2 x1x2 Q+1 00 01 11 10 00 01 11 10 1 1 0 1 1 0 0 0 1 1 0 1 1 0 0 0 Q1Q2 x1x2 Q+2 (c) Q1Q2S S1 0 1 S2 1 0 S3 1 1 S4 0 0 x1 x2I I1 1 0 I2 1 1 I3 0 1 I4 0 0 (d) 00 01 11 10 00 01 11 10 1 1 0 0 1 1 1 1 1 1 1 1 1 1 0 0 Q1Q2 x1x2 Q+1 00 01 11 10 00 01 11 10 1 0 0 0 1 0 0 0 1 1 1 0 1 1 1 0 Q1Q2 x1x2 Q+2 (e) Figure 2: (a) Transition table for an FSM; (b) an encoding for that FSM; (c) resulting encoded transition functions from that encoding; (d) another encoding for the same FSM; (e) resulting encoded transition functions. 8 less complex digital logic circuit, since the next-state logic for both flip- flops would involve fewer variables. Of course, this correlation between complexity and number of inputs depends on the precise definition of complexity used, and is not perfect in any case. There is no guarantee that the encoding from Figure 2(d) would actually produce a digital logic circuit that better suits the design goals (whatever they may be) of a digital logic designer. Nevertheless, in the remainder of this paper we will use the simple metric of defining cost as the total number of variables on which a Boolean function depends, for two reasons. First, this cost metric simplifies the problem of finding the optimal encoding for an FSM enough that we can always find the exact minimum solution. The only published work so far that achieves exact minimum results for FSM encoding is [12]. However, the authors in [12] use a different cost metric, which is based on the number of product terms when digital logic is implemented using a programmable logic array (PLA). This brings us to our second reason for using a cost metric based on number of dependencies: minimizing the number of product terms in a PLA has little to no relevance if an FSM is not implemented using PLAs, as they are not (for instance) in most modern VLSI chips. Minimizing the number of variable dependencies of a Boolean function, on the other hand, is a reasonable goal for virtually any digital logic technology, and will likely remain reasonable even for future technologies. Based on the preceding discussion, we therefore formulate as follows the problem to be solved in the remainder of this paper—given an FSM that satisfies the following conditions: • the number of states in the machine is a power of 2; • the number of possible input values to the machine is a power of 2; • the machine is state-minimal, meaning that no two distinct states are equivalent and therefore no two distinct states may be assigned the same encoding; • no two input values are equivalent and therefore no two distinct input values may be assigned the same encoding; find an encoding for the FSM with the lowest possible cost, where the cost of an encoding is defined as the sum of the costs of the encoded transition functions resulting from that encoding, and the cost of a single function is the number of variables on which the function depends. A function is considered to depend on a variable if and only if the function cannot be computed without knowledge of the value of that variable. Our cost model thus defined is the same as that used in [6] and [7]. 3 Grover’s Search Algorithm 3.1 Operation of Grover’s Algorithm In this section we briefly review Grover’s algorithm and its relevance to the state encoding problem. We assume the reader’s familiarity with quantum computing in general, and in particular with qubits, quantum states, circuits, gates, and the matrix-vector representations thereof. For 9 176 E. TSAI, M. PERKOWSKI A Quantum Algorithm for Automata Encoding 177 |0〉 |0〉 |0〉 |0〉 |1〉 H H H H H G G G Figure 3: A high-level schematic for Grover’s algorithm. a detailed treatment of the preceding concepts, we refer the reader to [16]. We concentrate on reviewing the conceptual aspects of Grover’s algorithm rather than proving that the algorithm functions as claimed. Full proofs of the validity of Grover’s algorithm are well known and may be found, for instance, in [3, 16]. Grover’s algorithm [2, 3, 4] is a well-known quantum algorithm and one of the first to demonstrate how quantum computers are in a sense more powerful than classical computers. Specifically, Grover’s algorithm solves the problem of satisfying a Boolean function; that is, given a func- tion f : {0, 1}n → {0, 1}, find x1 through xn such that3 f(x1, . . . , xn) = 1. This type of problem is commonly known as a satisfaction or decision prob- lem. Classically, assuming no additional information is known regarding the function f, one can on average solve this problem no faster than by exhaustive search. Such a search requires time O(N) where N = 2n, the total number of possible assignments of values {0, 1} to the variables x1 through xn. If a quantum computer is available, however, Grover’s algo- rithm provides a method to solve the same problem in O( √ N) time, a quadratic speedup. We first describe Grover’s algorithm with the assumption that exactly one solution exists; that is, there is exactly one assignment of the values {0, 1} to x1 through xn such that f(x1, . . . , xn) = 1. This is the original scenario considered by Grover. Later, we will relax this assumption and describe how the algorithm can be extended to cases where there is more than one solution, or no solution at all. Figure 3 shows a high-level schematic of a quantum circuit implement- ing Grover’s algorithm. We see that the algorithm consists of an initializa- tion step involving Hadamard gates, followed by repeated applications of an operation G (the Grover iterate), and then a measurement at the end. First, we examine the Grover iterate, which is the most important step. The Grover iterate accomplishes the task of amplitude amplification, the central concept underlying Grover’s algorithm. Amplitude amplification is the process of selectively increasing the amplitude of a certain compo- nent state of a superposition, while decreasing the amplitudes of all other 3The variables x1 through xn in this case are simply inputs to the function f and are unrelated to the input variables of an FSM. 10 O H H H H H H H H Z Figure 4: Structure of the Grover iterate G from Figure 3 with quantum oracle O and zero-state phase shift Z. component states. In Grover’s algorithm, the component state whose am- plitude is increased corresponds to the variable assignment satisfying the function f. By applying the Grover iterate enough times to a superpo- sition, one obtains a quantum state where the component corresponding to the satisfactory variable assignment has an amplitude near 1; all other components have zero or negligibly small amplitudes. A measurement then gives (with probability near 1) a variable assignment satisfying f. Figure 4 depicts a schematic of the Grover iterate, showing that it consists of a quantum oracle O, followed by the zero-state phase shift Z surrounded by arrays of Hadamard gates. The quantum oracle is a quantum circuit implementation of the function f to be satisfied. More specifically, the oracle acts as a “controlled inverter” controlled by f. That is, the quantum oracle acts on qubits x1 through xn together with an additional output qubit, and, for each possible basis state of x1 through xn, the oracle inverts the output qubit if and only if f(x1, . . . , xn) = 1. Figure 5 depicts an alternative schematic symbol for the oracle that graphically suggests this “controlled” nature. The quantum oracle essentially defines the search criteria for Grover’s algorithm and is the only part of Grover’s algorithm whose precise details depend on the nature of the function f. Therefore, a quantum computer cannot execute Grover’s algorithm for a given function f unless a quantum oracle for f is available. For some—if not the majority of—satisfaction problems arising from practical scenarios, the function f is not given ex- plicitly as a formula, but is instead only defined indirectly through a set of conditions or constraints. In such a case, designing a quantum oracle is far from trivial. In the subsequent sections of this paper, we will concen- trate on how to design a quantum oracle that can, when used in Grover’s algorithm, help find the optimal state encoding for an FSM. For now, we examine the quantum oracle’s role in Grover’s algorithm without concern for the details of its implementation. In Grover’s algorithm, the quantum oracle performs a phase flip, es- sentially “marking” the component of a superposition that corresponds to the variable assignment satisfying the function f—from now on, we will 11 178 E. TSAI, M. PERKOWSKI A Quantum Algorithm for Automata Encoding 179 |0〉 |0〉 |0〉 |0〉 |1〉 H H H H H G G G Figure 3: A high-level schematic for Grover’s algorithm. a detailed treatment of the preceding concepts, we refer the reader to [16]. We concentrate on reviewing the conceptual aspects of Grover’s algorithm rather than proving that the algorithm functions as claimed. Full proofs of the validity of Grover’s algorithm are well known and may be found, for instance, in [3, 16]. Grover’s algorithm [2, 3, 4] is a well-known quantum algorithm and one of the first to demonstrate how quantum computers are in a sense more powerful than classical computers. Specifically, Grover’s algorithm solves the problem of satisfying a Boolean function; that is, given a func- tion f : {0, 1}n → {0, 1}, find x1 through xn such that3 f(x1, . . . , xn) = 1. This type of problem is commonly known as a satisfaction or decision prob- lem. Classically, assuming no additional information is known regarding the function f, one can on average solve this problem no faster than by exhaustive search. Such a search requires time O(N) where N = 2n, the total number of possible assignments of values {0, 1} to the variables x1 through xn. If a quantum computer is available, however, Grover’s algo- rithm provides a method to solve the same problem in O( √ N) time, a quadratic speedup. We first describe Grover’s algorithm with the assumption that exactly one solution exists; that is, there is exactly one assignment of the values {0, 1} to x1 through xn such that f(x1, . . . , xn) = 1. This is the original scenario considered by Grover. Later, we will relax this assumption and describe how the algorithm can be extended to cases where there is more than one solution, or no solution at all. Figure 3 shows a high-level schematic of a quantum circuit implement- ing Grover’s algorithm. We see that the algorithm consists of an initializa- tion step involving Hadamard gates, followed by repeated applications of an operation G (the Grover iterate), and then a measurement at the end. First, we examine the Grover iterate, which is the most important step. The Grover iterate accomplishes the task of amplitude amplification, the central concept underlying Grover’s algorithm. Amplitude amplification is the process of selectively increasing the amplitude of a certain compo- nent state of a superposition, while decreasing the amplitudes of all other 3The variables x1 through xn in this case are simply inputs to the function f and are unrelated to the input variables of an FSM. 10 O H H H H H H H H Z Figure 4: Structure of the Grover iterate G from Figure 3 with quantum oracle O and zero-state phase shift Z. component states. In Grover’s algorithm, the component state whose am- plitude is increased corresponds to the variable assignment satisfying the function f. By applying the Grover iterate enough times to a superpo- sition, one obtains a quantum state where the component corresponding to the satisfactory variable assignment has an amplitude near 1; all other components have zero or negligibly small amplitudes. A measurement then gives (with probability near 1) a variable assignment satisfying f. Figure 4 depicts a schematic of the Grover iterate, showing that it consists of a quantum oracle O, followed by the zero-state phase shift Z surrounded by arrays of Hadamard gates. The quantum oracle is a quantum circuit implementation of the function f to be satisfied. More specifically, the oracle acts as a “controlled inverter” controlled by f. That is, the quantum oracle acts on qubits x1 through xn together with an additional output qubit, and, for each possible basis state of x1 through xn, the oracle inverts the output qubit if and only if f(x1, . . . , xn) = 1. Figure 5 depicts an alternative schematic symbol for the oracle that graphically suggests this “controlled” nature. The quantum oracle essentially defines the search criteria for Grover’s algorithm and is the only part of Grover’s algorithm whose precise details depend on the nature of the function f. Therefore, a quantum computer cannot execute Grover’s algorithm for a given function f unless a quantum oracle for f is available. For some—if not the majority of—satisfaction problems arising from practical scenarios, the function f is not given ex- plicitly as a formula, but is instead only defined indirectly through a set of conditions or constraints. In such a case, designing a quantum oracle is far from trivial. In the subsequent sections of this paper, we will concen- trate on how to design a quantum oracle that can, when used in Grover’s algorithm, help find the optimal state encoding for an FSM. For now, we examine the quantum oracle’s role in Grover’s algorithm without concern for the details of its implementation. In Grover’s algorithm, the quantum oracle performs a phase flip, es- sentially “marking” the component of a superposition that corresponds to the variable assignment satisfying the function f—from now on, we will 11 178 E. TSAI, M. PERKOWSKI A Quantum Algorithm for Automata Encoding 179 xn x3 x2 x1 y f Figure 5: Controlled inverter representation of a quantum oracle. |ψ〉 |ψ′〉 1√ 2 (|0〉 − |1〉) f (a) |ψ〉 |ψ′〉 (b) Figure 6: (a) Quantum oracle set up to perform a phase flip; (b) amplitude- graph visualization of the phase flip. refer to this component as the “solution” component since it represents the solution to the satisfaction problem. Specifically, one can prove that if one supplies the state 1√ 2 (|0〉 − |1〉) on the oracle’s output qubit (y in Figure 5) and supplies any state |ψ〉 on the input qubits, then the oracle inverts the phase of the solution component of |ψ〉. Figure 6(a) illustrates the quantum circuit diagram for an oracle set up to perform the phase in- version, showing the output qubit initialized to 1√ 2 (|0〉 − |1〉). Figure 6(b) then visualizes the initial and final states, |ψ〉 and |ψ′〉, of the oracle’s in- put qubits by plotting their component amplitudes. In other words, given the state |ψ〉 (or |ψ′〉) expressed as a sum of components, |ψ〉 = N−1∑ i=0 ai|i〉, the graphs plot ai against i. Comparison between |ψ〉 and |ψ′〉 shows that the phase of a single component (the solution component) has been inverted. We observe that the phase inversion can be interpreted to mean that the oracle in a sense evaluates the function f simultaneously for all pos- sible inputs and finds the solution immediately. Unfortunately, the so- 12 H H H H H H H H Z|ψ〉 |ψ′〉 (a) |ψ〉 µ |ψ′〉 µ (b) Figure 7: (a) Circuit to perform inversion about the mean; (b) amplitude-graph visualization. lution is encoded as a phase variation which is not directly observable. This problem is solved by the second part of Grover’s algorithm—the am- plitude amplification procedure, which converts this phase difference into a measurable amplitude difference. This procedure is seen on the right- hand side of Figure 4 and involves the Hadamard gates together with the zero-state phase shift Z. The zero-state phase shift is defined to invert the phase of the |0〉 component of any quantum state on which it acts. One can prove that when Hadamard gates are applied before and after a zero-state phase shift as shown in Figure 4, the result is an inversion about the mean, defined as follows: if µ denotes the mean amplitude of the components of a quantum state, then under an inversion about the mean, each component’s amplitude becomes 2µ − a where a is the component’s prior amplitude. This transformation is mathematically represented by the following equation: HZH ( N−1∑ i=0 ai|i〉 ) = N−1∑ i=0 (2µ − ai)|i〉, where HZH denotes the aforementioned combination of Hadamard gates and the zero-state phase shift. Figure 7 depicts the effect of inversion about the mean when applied immediately following the quantum oracle. Figure 7(a) shows the portion of the Grover iterate G (from Figures 3 and 4) that performs inversion about the mean. Figure 7(b) then visualizes the initial and final quantum states in the same manner as Figure 6. We see that following inversion about the mean, the amplitudes of the solution component has increased while those of all other components have decreased. Successive application of the Grover iterate similarly increases the amplitude of the solution component further. After enough iterations, the superposition consists entirely or nearly entirely of only the solution component. Specifically, one can prove that the number of iterations required is on the order of√ N, where N is the total number of components (i.e., the number of possible assignments of values to variables). Then, a measurement gives (with near certainty) a variable assignment satisfying the function f. Since we assume that nothing is known in advance about the function f, the just-described amplitude amplification procedure should begin with a superposition of all possible variable assignments, as any of them could 13 180 E. TSAI, M. PERKOWSKI A Quantum Algorithm for Automata Encoding 181 xn x3 x2 x1 y f Figure 5: Controlled inverter representation of a quantum oracle. |ψ〉 |ψ′〉 1√ 2 (|0〉 − |1〉) f (a) |ψ〉 |ψ′〉 (b) Figure 6: (a) Quantum oracle set up to perform a phase flip; (b) amplitude- graph visualization of the phase flip. refer to this component as the “solution” component since it represents the solution to the satisfaction problem. Specifically, one can prove that if one supplies the state 1√ 2 (|0〉 − |1〉) on the oracle’s output qubit (y in Figure 5) and supplies any state |ψ〉 on the input qubits, then the oracle inverts the phase of the solution component of |ψ〉. Figure 6(a) illustrates the quantum circuit diagram for an oracle set up to perform the phase in- version, showing the output qubit initialized to 1√ 2 (|0〉 − |1〉). Figure 6(b) then visualizes the initial and final states, |ψ〉 and |ψ′〉, of the oracle’s in- put qubits by plotting their component amplitudes. In other words, given the state |ψ〉 (or |ψ′〉) expressed as a sum of components, |ψ〉 = N−1∑ i=0 ai|i〉, the graphs plot ai against i. Comparison between |ψ〉 and |ψ′〉 shows that the phase of a single component (the solution component) has been inverted. We observe that the phase inversion can be interpreted to mean that the oracle in a sense evaluates the function f simultaneously for all pos- sible inputs and finds the solution immediately. Unfortunately, the so- 12 H H H H H H H H Z|ψ〉 |ψ′〉 (a) |ψ〉 µ |ψ′〉 µ (b) Figure 7: (a) Circuit to perform inversion about the mean; (b) amplitude-graph visualization. lution is encoded as a phase variation which is not directly observable. This problem is solved by the second part of Grover’s algorithm—the am- plitude amplification procedure, which converts this phase difference into a measurable amplitude difference. This procedure is seen on the right- hand side of Figure 4 and involves the Hadamard gates together with the zero-state phase shift Z. The zero-state phase shift is defined to invert the phase of the |0〉 component of any quantum state on which it acts. One can prove that when Hadamard gates are applied before and after a zero-state phase shift as shown in Figure 4, the result is an inversion about the mean, defined as follows: if µ denotes the mean amplitude of the components of a quantum state, then under an inversion about the mean, each component’s amplitude becomes 2µ − a where a is the component’s prior amplitude. This transformation is mathematically represented by the following equation: HZH ( N−1∑ i=0 ai|i〉 ) = N−1∑ i=0 (2µ − ai)|i〉, where HZH denotes the aforementioned combination of Hadamard gates and the zero-state phase shift. Figure 7 depicts the effect of inversion about the mean when applied immediately following the quantum oracle. Figure 7(a) shows the portion of the Grover iterate G (from Figures 3 and 4) that performs inversion about the mean. Figure 7(b) then visualizes the initial and final quantum states in the same manner as Figure 6. We see that following inversion about the mean, the amplitudes of the solution component has increased while those of all other components have decreased. Successive application of the Grover iterate similarly increases the amplitude of the solution component further. After enough iterations, the superposition consists entirely or nearly entirely of only the solution component. Specifically, one can prove that the number of iterations required is on the order of√ N, where N is the total number of components (i.e., the number of possible assignments of values to variables). Then, a measurement gives (with near certainty) a variable assignment satisfying the function f. Since we assume that nothing is known in advance about the function f, the just-described amplitude amplification procedure should begin with a superposition of all possible variable assignments, as any of them could 13 180 E. TSAI, M. PERKOWSKI A Quantum Algorithm for Automata Encoding 181 potentially satisfy f. Therefore, before performing the amplitude ampli- fication procedure, Grover’s algorithm first initializes the qubits that will serve as inputs to the quantum oracle, x1 through xn, to a superposition of all possible states. Conventionally, this is accomplished by initializing each input qubit (x1 through xn) to |0〉 and then applying a Hadamard gate to each input qubit, as shown in Figure 3. Similarly, the quantum or- acle’s output qubit is initialized to 1√ 2 (|0〉 − |1〉) by applying a Hadamard gate to an initial state of |1〉, also shown in Figure 3. Following comple- tion of the amplitude amplification procedure, the qubits x1 through xn are measured to obtain the final output of Grover’s algorithm; Figure 3 indicates this measurement on the right-hand side using the standard left- pointing triangular symbol. We therefore see that the complete Grover’s algorithm consists of the following steps: 1. Begin with n input qubits and one output qubit, initialized as de- scribed in the preceding paragraph. 2. Perform the amplitude amplification procedure by applying the Grover iterate √ N times as previously described. 3. Measure the input qubits; the result of measurement forms the out- put of Grover’s algorithm. Since the initialization and measurement steps in Grover’s algorithm are proportional to the number of qubits used, which is on the order of n = log2 N, the number of variables of f, the O( √ N) time required for the amplitude amplification procedure forms the dominant contribution to the overall runtime of Grover’s algorithm. Therefore, Grover’s algorithm requires a time complexity of O( √ N). Equipped with an understanding of Grover’s original algorithm, which assumes that exactly one solution exists, we now consider how the algo- rithm can be modified if more than one solution exists, or if there are no solutions at all. There are several possible variations of this scenario, depending on one’s assumptions and objectives: • One may or may not know the number of solutions beforehand. • If at least one solution exists, one may wish to find just a single solution, or all possible solutions. • One may or may not know beforehand whether at least one solution exists. • If the existence of at least one solution is not guaranteed, one may be interested only in determining the existence or non-existence of a solution, and not in actually finding that solution. For our purposes, we will need to assume that we do not have prior knowl- edge of the existence and number of solutions. We will be interested in first determining whether any solutions exist, and then finding just a sin- gle solution if at least one exists. In Section 3.2, we will demonstrate that satisfying this requirement suffices to solve the state encoding problem using a quantum computer. Fortunately, for the assumptions stated above, one can extend Grover’s algorithm to the case of an unknown number of solutions while maintain- ing an O( √ N) run time complexity. In [17], the authors show that if 14 one has foreknowledge of the exact number of solutions, Grover’s original algorithm as previously described (which assumes the existence of exactly one solution) can still be used with one modification: instead of O( √ N) iterations, one now requires O( √ N/k) iterations, where k is the number of solutions. Furthermore, the authors in [17] also demonstrate a method by which one can find a solution in O( √ N/k) expected time even if the number of solutions is unknown. This same method is additionally capa- ble of detecting the non-existence of a solution in O( √ N) time with an arbitrarily high level of certainty. Alternatively, Brassard et al. [18] have described a quantum counting algorithm, with which one may obtain an estimate of the number of solutions. One could use this quantum counting algorithm together with the previously-mentioned extended Grover’s al- gorithm for a known number of solutions (in [17]) to find a single solution, if it exists.4 Using the above approaches, one can satisfy the previously stated requirement—determine whether any solutions exist, and find one if it does—with the same O( √ N) time complexity as Grover’s original algo- rithm. For the sake of brevity, we will from now on use “Grover’s algo- rithm” to refer to all of these approaches collectively. In other words, when we say we are “using Grover’s algorithm” to solve a satisfaction problem, we mean that we are using any of the above approaches to determine if a solution to the problem exists, and then find one if it does. There is one more aspect of Grover’s algorithm that we have not yet mentioned—the use of ancillary (“ancilla”) qubits in the quantum oracle. Strictly speaking, ancilla qubits are an aspect of quantum oracle design and not of Grover’s algorithm itself. We discuss them here nevertheless, since we will concentrate on designing a quantum oracle to solve the FSM state encoding problem in the remainder of this paper. Ancilla qubits are extra qubits that are used by a quantum oracle to store intermediate results while it is performing its computations. They are initialized to a value of the quantum circuit designer’s choice. A quantum oracle only uses ancilla qubits internally; externally, it should appear as if ancilla qubits simply “pass through” the oracle with no change. In other words, ancilla qubits do not externally appear to participate in the oracle’s operation at all; they participate internally and only for the purpose of acting as temporary storage. Ancilla qubits are usually employed to reduce the quantum circuit cost of a quantum oracle. A quantum circuit using ancilla qubits often has lower quantum cost than an equivalent circuit without ancilla qubits. For instance, Figure 8 shows a quantum oracle for the function f = (x1 + x2)(x3 + x4) using two ancilla qubits. It is possible to design a quantum oracle for this function without ancilla qubits, but the 4Strictly speaking, the viability of this second method is actually not absolutely clear, although it should likely work. The difficulty is that the quantum counting algorithm in [18] only provides an approximate estimate of the number of solutions, while [17] assumes knowledge of the exact number of solutions. A brief consideration of the mathematical analysis used in [17] suggests that the method will still succeed with high probability with only an estimate of the number of solutions, as long as this estimate is reasonably accurate. However, the authors in [17] do not rigorously prove this assertion. In any case, the validity of our present work is unaffected since [17] also give a method for finding one of an unknown number of solutions, as mentioned in the main text. 15 182 E. TSAI, M. PERKOWSKI A Quantum Algorithm for Automata Encoding 183 potentially satisfy f. Therefore, before performing the amplitude ampli- fication procedure, Grover’s algorithm first initializes the qubits that will serve as inputs to the quantum oracle, x1 through xn, to a superposition of all possible states. Conventionally, this is accomplished by initializing each input qubit (x1 through xn) to |0〉 and then applying a Hadamard gate to each input qubit, as shown in Figure 3. Similarly, the quantum or- acle’s output qubit is initialized to 1√ 2 (|0〉 − |1〉) by applying a Hadamard gate to an initial state of |1〉, also shown in Figure 3. Following comple- tion of the amplitude amplification procedure, the qubits x1 through xn are measured to obtain the final output of Grover’s algorithm; Figure 3 indicates this measurement on the right-hand side using the standard left- pointing triangular symbol. We therefore see that the complete Grover’s algorithm consists of the following steps: 1. Begin with n input qubits and one output qubit, initialized as de- scribed in the preceding paragraph. 2. Perform the amplitude amplification procedure by applying the Grover iterate √ N times as previously described. 3. Measure the input qubits; the result of measurement forms the out- put of Grover’s algorithm. Since the initialization and measurement steps in Grover’s algorithm are proportional to the number of qubits used, which is on the order of n = log2 N, the number of variables of f, the O( √ N) time required for the amplitude amplification procedure forms the dominant contribution to the overall runtime of Grover’s algorithm. Therefore, Grover’s algorithm requires a time complexity of O( √ N). Equipped with an understanding of Grover’s original algorithm, which assumes that exactly one solution exists, we now consider how the algo- rithm can be modified if more than one solution exists, or if there are no solutions at all. There are several possible variations of this scenario, depending on one’s assumptions and objectives: • One may or may not know the number of solutions beforehand. • If at least one solution exists, one may wish to find just a single solution, or all possible solutions. • One may or may not know beforehand whether at least one solution exists. • If the existence of at least one solution is not guaranteed, one may be interested only in determining the existence or non-existence of a solution, and not in actually finding that solution. For our purposes, we will need to assume that we do not have prior knowl- edge of the existence and number of solutions. We will be interested in first determining whether any solutions exist, and then finding just a sin- gle solution if at least one exists. In Section 3.2, we will demonstrate that satisfying this requirement suffices to solve the state encoding problem using a quantum computer. Fortunately, for the assumptions stated above, one can extend Grover’s algorithm to the case of an unknown number of solutions while maintain- ing an O( √ N) run time complexity. In [17], the authors show that if 14 one has foreknowledge of the exact number of solutions, Grover’s original algorithm as previously described (which assumes the existence of exactly one solution) can still be used with one modification: instead of O( √ N) iterations, one now requires O( √ N/k) iterations, where k is the number of solutions. Furthermore, the authors in [17] also demonstrate a method by which one can find a solution in O( √ N/k) expected time even if the number of solutions is unknown. This same method is additionally capa- ble of detecting the non-existence of a solution in O( √ N) time with an arbitrarily high level of certainty. Alternatively, Brassard et al. [18] have described a quantum counting algorithm, with which one may obtain an estimate of the number of solutions. One could use this quantum counting algorithm together with the previously-mentioned extended Grover’s al- gorithm for a known number of solutions (in [17]) to find a single solution, if it exists.4 Using the above approaches, one can satisfy the previously stated requirement—determine whether any solutions exist, and find one if it does—with the same O( √ N) time complexity as Grover’s original algo- rithm. For the sake of brevity, we will from now on use “Grover’s algo- rithm” to refer to all of these approaches collectively. In other words, when we say we are “using Grover’s algorithm” to solve a satisfaction problem, we mean that we are using any of the above approaches to determine if a solution to the problem exists, and then find one if it does. There is one more aspect of Grover’s algorithm that we have not yet mentioned—the use of ancillary (“ancilla”) qubits in the quantum oracle. Strictly speaking, ancilla qubits are an aspect of quantum oracle design and not of Grover’s algorithm itself. We discuss them here nevertheless, since we will concentrate on designing a quantum oracle to solve the FSM state encoding problem in the remainder of this paper. Ancilla qubits are extra qubits that are used by a quantum oracle to store intermediate results while it is performing its computations. They are initialized to a value of the quantum circuit designer’s choice. A quantum oracle only uses ancilla qubits internally; externally, it should appear as if ancilla qubits simply “pass through” the oracle with no change. In other words, ancilla qubits do not externally appear to participate in the oracle’s operation at all; they participate internally and only for the purpose of acting as temporary storage. Ancilla qubits are usually employed to reduce the quantum circuit cost of a quantum oracle. A quantum circuit using ancilla qubits often has lower quantum cost than an equivalent circuit without ancilla qubits. For instance, Figure 8 shows a quantum oracle for the function f = (x1 + x2)(x3 + x4) using two ancilla qubits. It is possible to design a quantum oracle for this function without ancilla qubits, but the 4Strictly speaking, the viability of this second method is actually not absolutely clear, although it should likely work. The difficulty is that the quantum counting algorithm in [18] only provides an approximate estimate of the number of solutions, while [17] assumes knowledge of the exact number of solutions. A brief consideration of the mathematical analysis used in [17] suggests that the method will still succeed with high probability with only an estimate of the number of solutions, as long as this estimate is reasonably accurate. However, the authors in [17] do not rigorously prove this assertion. In any case, the validity of our present work is unaffected since [17] also give a method for finding one of an unknown number of solutions, as mentioned in the main text. 15 182 E. TSAI, M. PERKOWSKI A Quantum Algorithm for Automata Encoding 183 |1〉 |1〉 |1〉 |1〉 x4 x4 x3 x3 x2 x2 x1 x1 y y ⊕ (x1 + x2)(x3 + x4) Figure 8: A quantum oracle using ancilla qubits. quantum circuit cost of such an oracle would be higher than the cost of the oracle in Figure 8. In many cases, creating a quantum oracle without using ancilla qubits is in fact completely impractical. Although the judicious employment of ancilla qubits can greatly re- duce quantum circuit costs, one must also keep in mind that ancilla qubits themselves are a limited resource—in any real quantum computer, only a finite number of qubits will be available. Consequently, quantum oracles using excessive quantities of ancilla qubits are unrealistic in the sense that no quantum computer will be able to execute them. The process of de- signing a quantum oracle (indeed, designing any quantum circuit) nearly always involves a trade-off between its quantum cost and the number of ancilla qubits it uses. 3.2 Use of Grover’s Algorithm to Solve Optimiza- tion Problems At this point, before turning to the design of a quantum oracle to solve the state encoding problem, we first consider an interesting issue regard- ing the usage of Grover’s algorithm for this problem, as it will affect the design of the quantum oracle. Specifically, some difficulty arises from the fact that, while state encoding cost minimization is an optimization prob- lem, Grover’s algorithm directly solves only satisfaction problems (a.k.a. decision problems). In other words, we wish to find the minimum value of a certain function (the cost function) while Grover’s algorithm can only find a point at which a function evaluates to 1. In order to use Grover’s al- gorithm for optimization, we reformulate optimization problems in terms of a sequence of satisfaction problems of the form: “find a point at which the value of the function f is less than r”, where r is an arbitrary thresh- old. By executing Grover’s algorithm for different values of the threshold r, one can conduct a search to find the minimum value of f. For example, such a search might proceed according to the following procedure: 1. Choose an initial value for the threshold a. Ideally, this initial value should be close to the minimum value of f, if an estimate of the minimum is available; if not, the search procedure will still function correctly with any initial value. 16 2. Execute Grover’s algorithm for the chosen threshold as previously described. 3. If Grover’s algorithm finds a solution, proceed to step 4. Otherwise, double the threshold a and repeat from step 2. 4. The preceding steps give a lower and upper bound for the minimum of f. In other words, one obtains threshold values amin and amax such that the function f never takes on any value less than amin (as determined using Grover’s algorithm) but takes on a value less than amax at one or more points. 5. Execute Grover’s algorithm for a threshold value of (amin +amax)/2. 6. If Grover’s algorithm finds a solution, then (amin + amax)/2 gives a new upper bound for the minimum of f; otherwise, it gives a new lower bound. Repeat from step 4 until the minimum value of f is determined. The final output of Grover’s algorithm gives the input to f at which the minimum occurs. The above sequence of steps essentially describes the well-known bi- nary search strategy. We give this strategy merely as an example showing that such a search is indeed possible. In particular, we do not claim that this strategy is optimal with respect to expected runtime or any other measure. The question of evaluating different search strategies, as well as what standard should be used to evaluate them in the first place, falls outside the scope of this paper. We leave this avenue of exploration open for future work. We make the crucial observation that the above procedure involves executing Grover’s algorithm using not a single, static quantum oracle, but a sequence of quantum oracles that are dynamically created on-the- fly for different thresholds. In particular, the threshold value r is not itself an input to the oracle, meaning that Grover’s algorithm does not directly search for the threshold. Grover’s algorithm is in fact incapable of directly searching for the threshold since, as previously discussed, that constitutes an optimization, not satisfaction, problem. Instead, the threshold value is built into the oracle, meaning that a different oracle is created for each threshold value. Consequently, to successfully use the above procedure, one requires not just a single quantum oracle but a method for generating quantum oracles for arbitrary threshold values. We additionally observe that repeated execution of Grover’s algorithm using a sequence of dynamically generated quantum oracles makes use of the freely reconfigurable nature of quantum circuits. More specifically, a quantum circuit is not a hardware circuit in the same sense as a classical digital logic circuit—in a quantum circuit, information is not transmit- ted through physical wires from gate to gate. Instead, the “wires” in a quantum circuit represent individual qubits that are stored on some phys- ical medium, and the gates are not physical components but rather are manipulations performed on the physical medium using implementation- dependent hardware (e.g., lasers, electromagnets, superconducting cir- cuits). This means that a quantum “circuit” is in fact a sequence of soft- ware operations stored on a classical computer that controls the quantum hardware, and this sequence of operations can easily be modified at will. 17 184 E. TSAI, M. PERKOWSKI A Quantum Algorithm for Automata Encoding 185 |1〉 |1〉 |1〉 |1〉 x4 x4 x3 x3 x2 x2 x1 x1 y y ⊕ (x1 + x2)(x3 + x4) Figure 8: A quantum oracle using ancilla qubits. quantum circuit cost of such an oracle would be higher than the cost of the oracle in Figure 8. In many cases, creating a quantum oracle without using ancilla qubits is in fact completely impractical. Although the judicious employment of ancilla qubits can greatly re- duce quantum circuit costs, one must also keep in mind that ancilla qubits themselves are a limited resource—in any real quantum computer, only a finite number of qubits will be available. Consequently, quantum oracles using excessive quantities of ancilla qubits are unrealistic in the sense that no quantum computer will be able to execute them. The process of de- signing a quantum oracle (indeed, designing any quantum circuit) nearly always involves a trade-off between its quantum cost and the number of ancilla qubits it uses. 3.2 Use of Grover’s Algorithm to Solve Optimiza- tion Problems At this point, before turning to the design of a quantum oracle to solve the state encoding problem, we first consider an interesting issue regard- ing the usage of Grover’s algorithm for this problem, as it will affect the design of the quantum oracle. Specifically, some difficulty arises from the fact that, while state encoding cost minimization is an optimization prob- lem, Grover’s algorithm directly solves only satisfaction problems (a.k.a. decision problems). In other words, we wish to find the minimum value of a certain function (the cost function) while Grover’s algorithm can only find a point at which a function evaluates to 1. In order to use Grover’s al- gorithm for optimization, we reformulate optimization problems in terms of a sequence of satisfaction problems of the form: “find a point at which the value of the function f is less than r”, where r is an arbitrary thresh- old. By executing Grover’s algorithm for different values of the threshold r, one can conduct a search to find the minimum value of f. For example, such a search might proceed according to the following procedure: 1. Choose an initial value for the threshold a. Ideally, this initial value should be close to the minimum value of f, if an estimate of the minimum is available; if not, the search procedure will still function correctly with any initial value. 16 2. Execute Grover’s algorithm for the chosen threshold as previously described. 3. If Grover’s algorithm finds a solution, proceed to step 4. Otherwise, double the threshold a and repeat from step 2. 4. The preceding steps give a lower and upper bound for the minimum of f. In other words, one obtains threshold values amin and amax such that the function f never takes on any value less than amin (as determined using Grover’s algorithm) but takes on a value less than amax at one or more points. 5. Execute Grover’s algorithm for a threshold value of (amin +amax)/2. 6. If Grover’s algorithm finds a solution, then (amin + amax)/2 gives a new upper bound for the minimum of f; otherwise, it gives a new lower bound. Repeat from step 4 until the minimum value of f is determined. The final output of Grover’s algorithm gives the input to f at which the minimum occurs. The above sequence of steps essentially describes the well-known bi- nary search strategy. We give this strategy merely as an example showing that such a search is indeed possible. In particular, we do not claim that this strategy is optimal with respect to expected runtime or any other measure. The question of evaluating different search strategies, as well as what standard should be used to evaluate them in the first place, falls outside the scope of this paper. We leave this avenue of exploration open for future work. We make the crucial observation that the above procedure involves executing Grover’s algorithm using not a single, static quantum oracle, but a sequence of quantum oracles that are dynamically created on-the- fly for different thresholds. In particular, the threshold value r is not itself an input to the oracle, meaning that Grover’s algorithm does not directly search for the threshold. Grover’s algorithm is in fact incapable of directly searching for the threshold since, as previously discussed, that constitutes an optimization, not satisfaction, problem. Instead, the threshold value is built into the oracle, meaning that a different oracle is created for each threshold value. Consequently, to successfully use the above procedure, one requires not just a single quantum oracle but a method for generating quantum oracles for arbitrary threshold values. We additionally observe that repeated execution of Grover’s algorithm using a sequence of dynamically generated quantum oracles makes use of the freely reconfigurable nature of quantum circuits. More specifically, a quantum circuit is not a hardware circuit in the same sense as a classical digital logic circuit—in a quantum circuit, information is not transmit- ted through physical wires from gate to gate. Instead, the “wires” in a quantum circuit represent individual qubits that are stored on some phys- ical medium, and the gates are not physical components but rather are manipulations performed on the physical medium using implementation- dependent hardware (e.g., lasers, electromagnets, superconducting cir- cuits). This means that a quantum “circuit” is in fact a sequence of soft- ware operations stored on a classical computer that controls the quantum hardware, and this sequence of operations can easily be modified at will. 17 184 E. TSAI, M. PERKOWSKI A Quantum Algorithm for Automata Encoding 185 Thus, executing Grover’s algorithm using a newly-generated quantum ora- cle simply involves having the classical computer perform the appropriate, newly-generated sequence of operations on the quantum hardware. Based on the preceding observations, we introduce a distinction be- tween compile time and run time for quantum circuits. In classical com- puting, compile time is the time at which instructions for the computer are generated, while run time is the time at which those instructions are actually executed. By analogy, compile time of a quantum circuit will refer to the generation process of the quantum circuit (which, as previ- ously noted, takes place on a classical computer). Run time of a quantum circuit, in contrast, will refer to the process of actually executing the quantum circuit on quantum hardware (which, as also noted, involves a classical computer controlling the quantum hardware with an appropriate sequence of commands). Therefore, our objective in the subsequent sections of this paper be- comes: given an FSM specification, demonstrate a procedure that can generate a quantum oracle for an arbitrary threshold value r, where the quantum oracle accepts as input an encoding for the FSM and answers the question “is the cost of the encoding (as defined in Section 2.2) less than r?” The process described in this section then constitutes a complete algorithm for finding an encoding for the given FSM with exact minimum cost. 4 Procedure to Calculate the Cost of a Given Encoding 4.1 Computing Cost by Considering Pairs of States We now consider a systematic procedure for computing the cost, as de- fined in Section 2.2, of a given encoding for a given FSM. This procedure will form the basis for the design of a quantum oracle that determines whether the cost of a given encoding is less than a predetermined thresh- old, therefore allowing the use of Grover’s algorithm to find the exact minimum-cost encoding for an FSM. To calculate the cost of a given encoding, we require a method to determine whether the value of a given state variable, say Qi, at time t + 1 depends on the value of any (possibly the same or different) state variable, say Qj, at time t. By definition, the value of Qi at time t + 1 is given by the function δi; thus, Q + i = δi(Q1, . . . , Qn, x1, . . . , xm) where n and m are the number of state and input variables, respectively. Now, Q+i only depends on Qj if, in at least one case, a change in Qj and in no other variables causes a change in Q+i . In other words, if there exist distinct states S, S′ and an input value I such that Qj is the only state variable assigned different values for S and S′, and Qi is assigned different values for δ(S, I) and δ(S′, I), then Q+i depends on Qj. 18 As an example, consider the state machine from Figure 2 and the encoding in Figure 2(b). The encoded transition function Q+1 = δ1(Q1, Q2, x1, x2) resulting from this encoding, shown in Figure 2(c), de- pends on all four variables. The dependency on Q1 can be seen from the fact that δ1(0, 0, 0, 1) = 0 but δ1(1, 0, 0, 1) = 1; i.e., a change in only Q1 causes a change in δ1. In terms of states and input values, Q1Q2 = 00 corresponds to a current state of S1 and Q1Q2 = 10 corresponds to S3. We then see that given the pair of states (S1, S3), whose encodings differ only in Q1, for at least one input value—in this case, I2, which corresponds to x1x2 = 01—the corresponding pair of next states, (S2, S3), is such that the value of Q1 differs between the two states in the pair. The result of the preceding discussion may be more formally expressed as follows. For any two distinct states S and S′, let Dj(S, S ′) mean “the encodings of S and S′ differ only in the value of Qj” and let Ai(S, S ′) mean “the encodings of S and S′ agree in the value of Qi”. Then, check whether Dj(S, S ′ ) ⇒ ∀I ∈ I Ai(δ(S, I), δ(S′, I)) (1) for all pairs of distinct states (S, S′). If so, then Q+i does not depend on Qj; otherwise, it does. We determine the dependency of a given Q+i on an input variable xj in a similar manner. Specifically, Q+i depends on xj if and only if, in at least one case, a change in xj and in no other state or input variables causes a change in Q+i . Therefore, we consider all pairs of distinct input values and determine whether, for those pairs whose encodings differ only in xj, the encodings of the corresponding pair of next states can ever differ in Qi. In other words, for any two distinct input values I and I ′, let Dj(I, I ′) mean “the encodings of I and I′ differ only in the value of xj”, and for any two states S and S′, let Ai(S, S ′) mean (as before) “the encodings of S and S′ agree in the value of Qi”. Then, we wish to check whether the condition Dj(I, I ′ ) ⇒ ∀S ∈ S Ai(δ(S, I), δ(S, I′)) (2) holds for every pair of distinct input values (I, I′). If so, Q+i does not depend on xj; otherwise, it does. Equipped with a procedure to determine the dependency of a given Q+i on any single state or input variable, it is now straightforward to compute the total cost of an encoding. We calculate the cost of each Q+i in accordance with our cost model—the total number of state and input variables on which Q+i depends gives the cost of Q + i . Then, the sum of costs of Q+i for 1 ≤ i ≤ n gives the total cost of a given encoding. 4.2 Necessity for Transition Functions to be Completely Specified The just-described procedure only gives the correct cost if the encoding is bijective. If this condition is not satisfied, problems can arise from the fact that the “functions” δi are no longer functions in the mathematical sense, but rather relations or so-called incompletely specified functions. In general, when δi is incompletely specified, the question of whether or 19 186 E. TSAI, M. PERKOWSKI A Quantum Algorithm for Automata Encoding 187 Thus, executing Grover’s algorithm using a newly-generated quantum ora- cle simply involves having the classical computer perform the appropriate, newly-generated sequence of operations on the quantum hardware. Based on the preceding observations, we introduce a distinction be- tween compile time and run time for quantum circuits. In classical com- puting, compile time is the time at which instructions for the computer are generated, while run time is the time at which those instructions are actually executed. By analogy, compile time of a quantum circuit will refer to the generation process of the quantum circuit (which, as previ- ously noted, takes place on a classical computer). Run time of a quantum circuit, in contrast, will refer to the process of actually executing the quantum circuit on quantum hardware (which, as also noted, involves a classical computer controlling the quantum hardware with an appropriate sequence of commands). Therefore, our objective in the subsequent sections of this paper be- comes: given an FSM specification, demonstrate a procedure that can generate a quantum oracle for an arbitrary threshold value r, where the quantum oracle accepts as input an encoding for the FSM and answers the question “is the cost of the encoding (as defined in Section 2.2) less than r?” The process described in this section then constitutes a complete algorithm for finding an encoding for the given FSM with exact minimum cost. 4 Procedure to Calculate the Cost of a Given Encoding 4.1 Computing Cost by Considering Pairs of States We now consider a systematic procedure for computing the cost, as de- fined in Section 2.2, of a given encoding for a given FSM. This procedure will form the basis for the design of a quantum oracle that determines whether the cost of a given encoding is less than a predetermined thresh- old, therefore allowing the use of Grover’s algorithm to find the exact minimum-cost encoding for an FSM. To calculate the cost of a given encoding, we require a method to determine whether the value of a given state variable, say Qi, at time t + 1 depends on the value of any (possibly the same or different) state variable, say Qj, at time t. By definition, the value of Qi at time t + 1 is given by the function δi; thus, Q + i = δi(Q1, . . . , Qn, x1, . . . , xm) where n and m are the number of state and input variables, respectively. Now, Q+i only depends on Qj if, in at least one case, a change in Qj and in no other variables causes a change in Q+i . In other words, if there exist distinct states S, S′ and an input value I such that Qj is the only state variable assigned different values for S and S′, and Qi is assigned different values for δ(S, I) and δ(S′, I), then Q+i depends on Qj. 18 As an example, consider the state machine from Figure 2 and the encoding in Figure 2(b). The encoded transition function Q+1 = δ1(Q1, Q2, x1, x2) resulting from this encoding, shown in Figure 2(c), de- pends on all four variables. The dependency on Q1 can be seen from the fact that δ1(0, 0, 0, 1) = 0 but δ1(1, 0, 0, 1) = 1; i.e., a change in only Q1 causes a change in δ1. In terms of states and input values, Q1Q2 = 00 corresponds to a current state of S1 and Q1Q2 = 10 corresponds to S3. We then see that given the pair of states (S1, S3), whose encodings differ only in Q1, for at least one input value—in this case, I2, which corresponds to x1x2 = 01—the corresponding pair of next states, (S2, S3), is such that the value of Q1 differs between the two states in the pair. The result of the preceding discussion may be more formally expressed as follows. For any two distinct states S and S′, let Dj(S, S ′) mean “the encodings of S and S′ differ only in the value of Qj” and let Ai(S, S ′) mean “the encodings of S and S′ agree in the value of Qi”. Then, check whether Dj(S, S ′ ) ⇒ ∀I ∈ I Ai(δ(S, I), δ(S′, I)) (1) for all pairs of distinct states (S, S′). If so, then Q+i does not depend on Qj; otherwise, it does. We determine the dependency of a given Q+i on an input variable xj in a similar manner. Specifically, Q+i depends on xj if and only if, in at least one case, a change in xj and in no other state or input variables causes a change in Q+i . Therefore, we consider all pairs of distinct input values and determine whether, for those pairs whose encodings differ only in xj, the encodings of the corresponding pair of next states can ever differ in Qi. In other words, for any two distinct input values I and I ′, let Dj(I, I ′) mean “the encodings of I and I′ differ only in the value of xj”, and for any two states S and S′, let Ai(S, S ′) mean (as before) “the encodings of S and S′ agree in the value of Qi”. Then, we wish to check whether the condition Dj(I, I ′ ) ⇒ ∀S ∈ S Ai(δ(S, I), δ(S, I′)) (2) holds for every pair of distinct input values (I, I′). If so, Q+i does not depend on xj; otherwise, it does. Equipped with a procedure to determine the dependency of a given Q+i on any single state or input variable, it is now straightforward to compute the total cost of an encoding. We calculate the cost of each Q+i in accordance with our cost model—the total number of state and input variables on which Q+i depends gives the cost of Q + i . Then, the sum of costs of Q+i for 1 ≤ i ≤ n gives the total cost of a given encoding. 4.2 Necessity for Transition Functions to be Completely Specified The just-described procedure only gives the correct cost if the encoding is bijective. If this condition is not satisfied, problems can arise from the fact that the “functions” δi are no longer functions in the mathematical sense, but rather relations or so-called incompletely specified functions. In general, when δi is incompletely specified, the question of whether or 19 186 E. TSAI, M. PERKOWSKI A Quantum Algorithm for Automata Encoding 187 I1 I2 I3 S1 S2 S3 S4 S5 S2 S4 S5 S1 S1 S1 S3 S3 S1 S3 S3 S3 S1 S3 S1 (a) Q1Q2Q3S S1 0 0 0 S2 0 1 1 S3 1 0 1 S4 1 1 0 S5 1 1 1 x1 x2I I1 0 0 I2 0 1 I3 1 0 (b) 1 − − − 0 0 0 0 1 − − − 0 0 0 0 1 − − − 0 0 0 0 − − − − − − − − 00 01 11 10 000 001 011 010 110 111 101 100 Q1Q2Q3 x1x2 (c) Figure 9: (a) FSM specification with numbers of states and inputs not powers of 2; (b) a possible encoding; (c) resulting form of Q+2 . not δi depends on a given variable cannot be answered by the simple procedure described above. Figure 9 illustrates an instance where the procedure from the previous section fails to correctly determine the dependencies of a function δi on Q1 through Qn and x1 through xm. In this figure we have a state machine where the number of states (5) is not a power of two. Consequently, we require at least three flip-flops to implement this state machine. However, since eight distinct states exist for an array of three flip-flops, three flip- flop array states remain unused. In other words, three of the eight possible flip-flop array states do not represent any FSM state at all. Similarly, the number of input values (3) is also not a power of two, and hence the input is encoded by two bits with one of the four possible combinations remaining unused. The effects of these unused states and input combina- tions can be seen in the encoded transition function δ2, where the value of δ2 for the unused states is recorded as a “−”, indicating a “don’t-care”. A “don’t-care” output indicates that the digital logic implementing the FSM may output a value of either 0 or 1 for that combination of flip-flop states and inputs, since the combination should never occur during normal operation. We now observe that at least three possible implementations exist for δ2: Q + 2 = ¬Q1 ∧ ¬Q2, (3) Q + 2 = ¬Q1 ∧ ¬Q3, (4) Q + 2 = ¬Q2 ∧ ¬Q3. (5) Thus, it is clearly possible to implement δ2 with a dependency on only two variables. On the other hand, one can see from inspection that any one of Q1, Q2, Q3, x1, or x2 alone is not enough to determine the value of δ2. Hence, our cost model assigns δ2 a cost of 2. However, the procedure from the previous section finds the cost of δ2 to be 0. For instance, when considering whether δ2 depends on Q1, the procedure considers all pairs of states (S, S′) whose encodings differ only in Q1, and then examines whether the encodings of δ(S, I) and δ(S ′, I) differ 20 in Q2 for any input value I. In this case, the only such pair of states is (S2, S5), and under δ with I = I1, I = I2, and I = I3, the images of this pair are (S1, S1), (S1, S3), and (S1, S1), respectively. For all three image pairs, Q2 does not differ between the encoded values of the two states in the pair. Thus, the procedure determines that δ2 does not depend on Q1. In a similar fashion, the procedure also determines that δ2 does not depend on Q2, Q3, x1, or x2, and consequently calculates the cost of δ2 as 0. This conclusion is clearly incorrect since δ2 is not constant and must therefore depend on at least one variable. Indeed, we previously determined the minimum number of dependencies to be 2. Our procedure’s failure to correctly determine cost in this case ul- timately arises from the fact that, considered individually, δ2 need not depend on any particular one of Q1, Q2, and Q3. For instance, Eq. 5 implements δ2 without a dependency on Q1. Similarly, Eq. 4 and Eq. 3 implement δ2 without dependencies on Q2 and Q3, respectively. It is however not possible to simultaneously avoid two of these dependencies. In other words, any implementation of δ2 that lacks a dependency on Q1 must then depend on both Q2 and Q3. So, although the implementation given by Eq. 5 does not depend on Q1, it depends on both Q2 and Q3. The procedure from the previous section assumes (in this case incorrectly) that any two dependencies can always be simultaneously avoided if they can be individually avoided, which results in an incorrect computed cost. The scenario described here can never occur if all encoded transition functions are actual functions (not relations) in the mathematical sense. To see this, observe that any mathematical function lacking a dependency on each of two variables individually must also lack a dependency on those variables simultaneously. In other words, suppose that a function f of variables5 x1 through xn lacks a dependency on x1, meaning that a change in only x1 cannot affect the value of f and f can be computed without knowledge of the value of x1. Furthermore suppose that f similarly lacks a dependency on x2. Then if the value of x1 changes to a different value x1 ′ and the value of x2 simultaneously changes to x2 ′, we have6 f(x1, x2, . . . , xn) = f(x1, x2 ′ , . . . , xn) = f(x1 ′ , x2 ′ , . . . , xn), showing that simultaneous changes in x1 and x2 cannot affect the value of f. Hence, f can be computed without knowledge of the values of either x1 or x2. This argument breaks down if f is not actually a function but a relation, because then the value of f may not be uniquely defined at a given point. We therefore see that the procedure from the previous section, which only evaluates dependency on a single variable at a time, correctly com- putes cost when all encoded transition functions are actual functions (i.e., there are no “don’t-cares”) but may fail if those “functions” are actually relations. No “don’t-cares” will exist if the state and input encodings are 5As in Section 3.1, the variables x1 through xn here are unrelated to the input variables of an FSM; here, they are simply variables in an arbitrary function f. 6Here we use the notation x1 ′ simply to indicate that the value of x1 has changed. In particular, we do not use the prime (′) symbol to indicate logical negation, as is sometimes done. 21 188 E. TSAI, M. PERKOWSKI A Quantum Algorithm for Automata Encoding 189 I1 I2 I3 S1 S2 S3 S4 S5 S2 S4 S5 S1 S1 S1 S3 S3 S1 S3 S3 S3 S1 S3 S1 (a) Q1Q2Q3S S1 0 0 0 S2 0 1 1 S3 1 0 1 S4 1 1 0 S5 1 1 1 x1 x2I I1 0 0 I2 0 1 I3 1 0 (b) 1 − − − 0 0 0 0 1 − − − 0 0 0 0 1 − − − 0 0 0 0 − − − − − − − − 00 01 11 10 000 001 011 010 110 111 101 100 Q1Q2Q3 x1x2 (c) Figure 9: (a) FSM specification with numbers of states and inputs not powers of 2; (b) a possible encoding; (c) resulting form of Q+2 . not δi depends on a given variable cannot be answered by the simple procedure described above. Figure 9 illustrates an instance where the procedure from the previous section fails to correctly determine the dependencies of a function δi on Q1 through Qn and x1 through xm. In this figure we have a state machine where the number of states (5) is not a power of two. Consequently, we require at least three flip-flops to implement this state machine. However, since eight distinct states exist for an array of three flip-flops, three flip- flop array states remain unused. In other words, three of the eight possible flip-flop array states do not represent any FSM state at all. Similarly, the number of input values (3) is also not a power of two, and hence the input is encoded by two bits with one of the four possible combinations remaining unused. The effects of these unused states and input combina- tions can be seen in the encoded transition function δ2, where the value of δ2 for the unused states is recorded as a “−”, indicating a “don’t-care”. A “don’t-care” output indicates that the digital logic implementing the FSM may output a value of either 0 or 1 for that combination of flip-flop states and inputs, since the combination should never occur during normal operation. We now observe that at least three possible implementations exist for δ2: Q + 2 = ¬Q1 ∧ ¬Q2, (3) Q + 2 = ¬Q1 ∧ ¬Q3, (4) Q + 2 = ¬Q2 ∧ ¬Q3. (5) Thus, it is clearly possible to implement δ2 with a dependency on only two variables. On the other hand, one can see from inspection that any one of Q1, Q2, Q3, x1, or x2 alone is not enough to determine the value of δ2. Hence, our cost model assigns δ2 a cost of 2. However, the procedure from the previous section finds the cost of δ2 to be 0. For instance, when considering whether δ2 depends on Q1, the procedure considers all pairs of states (S, S′) whose encodings differ only in Q1, and then examines whether the encodings of δ(S, I) and δ(S ′, I) differ 20 in Q2 for any input value I. In this case, the only such pair of states is (S2, S5), and under δ with I = I1, I = I2, and I = I3, the images of this pair are (S1, S1), (S1, S3), and (S1, S1), respectively. For all three image pairs, Q2 does not differ between the encoded values of the two states in the pair. Thus, the procedure determines that δ2 does not depend on Q1. In a similar fashion, the procedure also determines that δ2 does not depend on Q2, Q3, x1, or x2, and consequently calculates the cost of δ2 as 0. This conclusion is clearly incorrect since δ2 is not constant and must therefore depend on at least one variable. Indeed, we previously determined the minimum number of dependencies to be 2. Our procedure’s failure to correctly determine cost in this case ul- timately arises from the fact that, considered individually, δ2 need not depend on any particular one of Q1, Q2, and Q3. For instance, Eq. 5 implements δ2 without a dependency on Q1. Similarly, Eq. 4 and Eq. 3 implement δ2 without dependencies on Q2 and Q3, respectively. It is however not possible to simultaneously avoid two of these dependencies. In other words, any implementation of δ2 that lacks a dependency on Q1 must then depend on both Q2 and Q3. So, although the implementation given by Eq. 5 does not depend on Q1, it depends on both Q2 and Q3. The procedure from the previous section assumes (in this case incorrectly) that any two dependencies can always be simultaneously avoided if they can be individually avoided, which results in an incorrect computed cost. The scenario described here can never occur if all encoded transition functions are actual functions (not relations) in the mathematical sense. To see this, observe that any mathematical function lacking a dependency on each of two variables individually must also lack a dependency on those variables simultaneously. In other words, suppose that a function f of variables5 x1 through xn lacks a dependency on x1, meaning that a change in only x1 cannot affect the value of f and f can be computed without knowledge of the value of x1. Furthermore suppose that f similarly lacks a dependency on x2. Then if the value of x1 changes to a different value x1 ′ and the value of x2 simultaneously changes to x2 ′, we have6 f(x1, x2, . . . , xn) = f(x1, x2 ′ , . . . , xn) = f(x1 ′ , x2 ′ , . . . , xn), showing that simultaneous changes in x1 and x2 cannot affect the value of f. Hence, f can be computed without knowledge of the values of either x1 or x2. This argument breaks down if f is not actually a function but a relation, because then the value of f may not be uniquely defined at a given point. We therefore see that the procedure from the previous section, which only evaluates dependency on a single variable at a time, correctly com- putes cost when all encoded transition functions are actual functions (i.e., there are no “don’t-cares”) but may fail if those “functions” are actually relations. No “don’t-cares” will exist if the state and input encodings are 5As in Section 3.1, the variables x1 through xn here are unrelated to the input variables of an FSM; here, they are simply variables in an arbitrary function f. 6Here we use the notation x1 ′ simply to indicate that the value of x1 has changed. In particular, we do not use the prime (′) symbol to indicate logical negation, as is sometimes done. 21 188 E. TSAI, M. PERKOWSKI A Quantum Algorithm for Automata Encoding 189 bijective. Bijectivity of an encoding is equivalent to the condition that the numbers of states and inputs are both powers of two, the minimum possible number of state and input variables are used, and no two distinct states or inputs may be assigned the same encoding. 5 Design of a Quantum Oracle to Find Optimal Encodings 5.1 Binary Representation of Encodings in the Quantum Oracle We now demonstrate how to, given an FSM and a threshold value r, con- struct a quantum oracle that, when given an encoding for that FSM as input, determines whether the cost of the encoding is less than r. Using this quantum oracle, the procedure described in Section 3.2 then consti- tutes a complete algorithm for finding the exact minimum solution to the FSM encoding problem under the assumptions and conditions described before. As the first design step, we must agree on the manner in which a candidate encoding is to be supplied as input to the oracle. We will use the following scheme to represent an encoding as binary data: letting n be the number of bits used by the encoding, we allocate an array of n qubits for each element of the set being encoded (either the state or input set of an FSM), and assign to each such array the encoded value of the corresponding set element. For instance, suppose that S1 through S4 are the internal states of an FSM. Since we require all encodings to be bijective, only 2-bit state encodings will be considered for this FSM. We therefore create four arrays of two qubits each, where the input supplied to each array is the encoded value of the corresponding state. Thus, if S1, S2, S3, and S4 are encoded by 01, 10, 00, and 11, respectively, then we represent this encoding by supplying 01 on the first array of two qubits, 10 on the second array, 00 on the third array, and 11 on the fourth array. Input encodings are also represented in a similar manner. Figure 10 provides an example of an encoding represented as binary data that can be input to a quantum oracle. In this figure as well as others in this section, the notation Qi(Sj) denotes the value assigned to Qi in the encoding of Sj. Similarly, xi(Ij) denotes the value assigned to xi in the encoding of Ij. The number of input qubits to a quantum oracle is of great importance as it determines the run time of Grover’s algorithm. If an FSM has 2n internal states, each state will be encoded using n bits, and therefore, our scheme for representing encodings requires 2n arrays of n qubits each, for a total of n · 2n qubits. Similarly, for an FSM with 2m input values, our scheme requires m · 2m qubits. Thus, an FSM with 2n internal states and 2m input values requires a grand total of n · 2n + m · 2m qubits. 22 Q1Q2S S1 0 1 S2 1 0 S3 0 0 S4 1 1 x1 x2I I1 1 0 I2 1 1 I3 0 1 I4 0 0 (a) Q1(S1) Q2(S1) Q1(S2) Q2(S2) Q1(S3) Q2(S3) Q1(S4) Q2(S4) x1(I1) x2(I1) x1(I4) x2(I4) 0 0 0 1 1 1 0 0 0 1 1 0 Encoding of I4 Encoding of I1 Encoding of S4 Encoding of S3 Encoding of S2 Encoding of S1 y f (b) Figure 10: The quantum oracle’s representation of an encoding as binary data— (a) state and input encodings for an FSM; (b) their representations as supplied to the oracle. 23 190 E. TSAI, M. PERKOWSKI A Quantum Algorithm for Automata Encoding 191 bijective. Bijectivity of an encoding is equivalent to the condition that the numbers of states and inputs are both powers of two, the minimum possible number of state and input variables are used, and no two distinct states or inputs may be assigned the same encoding. 5 Design of a Quantum Oracle to Find Optimal Encodings 5.1 Binary Representation of Encodings in the Quantum Oracle We now demonstrate how to, given an FSM and a threshold value r, con- struct a quantum oracle that, when given an encoding for that FSM as input, determines whether the cost of the encoding is less than r. Using this quantum oracle, the procedure described in Section 3.2 then consti- tutes a complete algorithm for finding the exact minimum solution to the FSM encoding problem under the assumptions and conditions described before. As the first design step, we must agree on the manner in which a candidate encoding is to be supplied as input to the oracle. We will use the following scheme to represent an encoding as binary data: letting n be the number of bits used by the encoding, we allocate an array of n qubits for each element of the set being encoded (either the state or input set of an FSM), and assign to each such array the encoded value of the corresponding set element. For instance, suppose that S1 through S4 are the internal states of an FSM. Since we require all encodings to be bijective, only 2-bit state encodings will be considered for this FSM. We therefore create four arrays of two qubits each, where the input supplied to each array is the encoded value of the corresponding state. Thus, if S1, S2, S3, and S4 are encoded by 01, 10, 00, and 11, respectively, then we represent this encoding by supplying 01 on the first array of two qubits, 10 on the second array, 00 on the third array, and 11 on the fourth array. Input encodings are also represented in a similar manner. Figure 10 provides an example of an encoding represented as binary data that can be input to a quantum oracle. In this figure as well as others in this section, the notation Qi(Sj) denotes the value assigned to Qi in the encoding of Sj. Similarly, xi(Ij) denotes the value assigned to xi in the encoding of Ij. The number of input qubits to a quantum oracle is of great importance as it determines the run time of Grover’s algorithm. If an FSM has 2n internal states, each state will be encoded using n bits, and therefore, our scheme for representing encodings requires 2n arrays of n qubits each, for a total of n · 2n qubits. Similarly, for an FSM with 2m input values, our scheme requires m · 2m qubits. Thus, an FSM with 2n internal states and 2m input values requires a grand total of n · 2n + m · 2m qubits. 22 Q1Q2S S1 0 1 S2 1 0 S3 0 0 S4 1 1 x1 x2I I1 1 0 I2 1 1 I3 0 1 I4 0 0 (a) Q1(S1) Q2(S1) Q1(S2) Q2(S2) Q1(S3) Q2(S3) Q1(S4) Q2(S4) x1(I1) x2(I1) x1(I4) x2(I4) 0 0 0 1 1 1 0 0 0 1 1 0 Encoding of I4 Encoding of I1 Encoding of S4 Encoding of S3 Encoding of S2 Encoding of S1 y f (b) Figure 10: The quantum oracle’s representation of an encoding as binary data— (a) state and input encodings for an FSM; (b) their representations as supplied to the oracle. 23 190 E. TSAI, M. PERKOWSKI A Quantum Algorithm for Automata Encoding 191 5.2 Quantum Circuit to Detect Dependencies We next demonstrate a quantum circuit design that uses the procedure from Section 4.1 to determine whether the next state of a single flip-flop (i.e., one of Q+1 through Q + n ) depends on the current state of another flip-flop (i.e., one of Q1 through Qn) or the current value of a single input bit (i.e., one of x1 through xm). Recall that this procedure involves checking the conditions given by Eq. 1 and Eq. 2 for each pair of states or input values, respectively. In turn, Eq. 1 and Eq. 2 involve checking the conditions Dj(S, S ′), Ai(S, S ′), and Dj(I, I ′) for pairs of states or input values, where Dj and Ai are as defined in Section 4.1. Using the binary representation described in Section 5.1, one can easily construct quantum circuits to check Dj(S, S ′), Ai(S, S ′), and Dj(I, I ′) for any pair of states or inputs. For example, Figure 11(a) shows a quantum circuit that evaluates D1(S, S ′) for any two distinct states S and S′.7 This circuit operates on just a subset of the complete binary representation of an encoding; specifically, it uses the qubits carrying information about the encoded values of S and S′. It uses Feynman (a.k.a. controlled-NOT) gates to perform comparisons and a Toffoli gate to evaluate the logical AND of two comparison results. The final output of the circuit is given by the logical expression ¬(Q2(S) ⊕ Q2(S′)) ∧ ¬(Q3(S) ⊕ Q3(S′)), which evaluates to 1 if and only if the encodings of S and S′ agree in all state variables except Q1, exactly the definition of D1(S, S ′). Although we assumed for the purpose of this particular illustration that each state is encoded by three bits, the general circuit structure applies to encodings of any size. Likewise, although this particular circuit evaluates D1(S, S ′), similar circuits suffice to evaluate Dj(S, S ′) for any j, as well as Dj(I, I ′) for two input values I and I′ instead of two states. In a similar vein, Figure 11(b) shows a quantum circuit that evalu- ates A1(S, S ′). This circuit is extremely simple, as it simply evaluates ¬(Q1(S) ⊕ Q1(S′)), which amounts to just a one-bit comparison. As be- fore, the same circuit structure is usable for encodings of any size, not just three bits. Next, to check the conditions specified by Eq. 1 and Eq. 2, our quantum circuit must be able to evaluate a logical implication. Recalling that the expression a ⇒ b is defined as ¬a ∨ b, we observe that a single Toffoli gate suffices to evaluate a logical implication, as shown in Figure 12. Finally, we are ready to turn to the design of the full quantum circuit for checking Eq. 1 or Eq. 2. This task is complicated by the fact that checking Eq. 1 or Eq. 2 involves evaluating Ai(S, S ′) simultaneously for 7Technically, this circuit only works correctly if the states S and S′ have distinct encodings, as required by the conditions stated at the end of Section 2.2. If S and S′ happen to have the same encoding, the circuit will erroneously output 1. However, later on, in Section 5.5, we describe a circuit that enforces the condition that distinct states have distinct encodings. This circuit is incorporated into the final oracle, as described in Section 5.6, so that it forces the oracle’s output to 0 whenever this condition is violated. The operation of the circuit described in the present section therefore becomes irrelevant in such a case, since Grover’s algorithm will never find such a distinctness-violating encoding as a solution. From now on, we therefore proceed with the implicit assumption that distinct states have distinct encodings. The same applies to input values as well—the operation of the circuit described here is similarly irrelevant if distinct input values do not have distinct encodings. 24 Q1(S ′) Q2(S ′) Q3(S ′) Q1(S) Q2(S) Q3(S) |0〉 Encoding of S′ Encoding of S D1(S, S ′) (a) Q1(S ′) Q2(S ′) Q3(S ′) Q1(S) Q2(S) Q3(S) Encoding of S′ Encoding of S A1(S, S ′) (b) Figure 11: (a) Quantum circuit to check D1(S, S ′); (b) circuit to check A1(S, S ′). a b |1〉 a ⇒ b Figure 12: Logical implication evaluated using a Toffoli gate. 25 192 E. TSAI, M. PERKOWSKI A Quantum Algorithm for Automata Encoding 193 5.2 Quantum Circuit to Detect Dependencies We next demonstrate a quantum circuit design that uses the procedure from Section 4.1 to determine whether the next state of a single flip-flop (i.e., one of Q+1 through Q + n ) depends on the current state of another flip-flop (i.e., one of Q1 through Qn) or the current value of a single input bit (i.e., one of x1 through xm). Recall that this procedure involves checking the conditions given by Eq. 1 and Eq. 2 for each pair of states or input values, respectively. In turn, Eq. 1 and Eq. 2 involve checking the conditions Dj(S, S ′), Ai(S, S ′), and Dj(I, I ′) for pairs of states or input values, where Dj and Ai are as defined in Section 4.1. Using the binary representation described in Section 5.1, one can easily construct quantum circuits to check Dj(S, S ′), Ai(S, S ′), and Dj(I, I ′) for any pair of states or inputs. For example, Figure 11(a) shows a quantum circuit that evaluates D1(S, S ′) for any two distinct states S and S′.7 This circuit operates on just a subset of the complete binary representation of an encoding; specifically, it uses the qubits carrying information about the encoded values of S and S′. It uses Feynman (a.k.a. controlled-NOT) gates to perform comparisons and a Toffoli gate to evaluate the logical AND of two comparison results. The final output of the circuit is given by the logical expression ¬(Q2(S) ⊕ Q2(S′)) ∧ ¬(Q3(S) ⊕ Q3(S′)), which evaluates to 1 if and only if the encodings of S and S′ agree in all state variables except Q1, exactly the definition of D1(S, S ′). Although we assumed for the purpose of this particular illustration that each state is encoded by three bits, the general circuit structure applies to encodings of any size. Likewise, although this particular circuit evaluates D1(S, S ′), similar circuits suffice to evaluate Dj(S, S ′) for any j, as well as Dj(I, I ′) for two input values I and I′ instead of two states. In a similar vein, Figure 11(b) shows a quantum circuit that evalu- ates A1(S, S ′). This circuit is extremely simple, as it simply evaluates ¬(Q1(S) ⊕ Q1(S′)), which amounts to just a one-bit comparison. As be- fore, the same circuit structure is usable for encodings of any size, not just three bits. Next, to check the conditions specified by Eq. 1 and Eq. 2, our quantum circuit must be able to evaluate a logical implication. Recalling that the expression a ⇒ b is defined as ¬a ∨ b, we observe that a single Toffoli gate suffices to evaluate a logical implication, as shown in Figure 12. Finally, we are ready to turn to the design of the full quantum circuit for checking Eq. 1 or Eq. 2. This task is complicated by the fact that checking Eq. 1 or Eq. 2 involves evaluating Ai(S, S ′) simultaneously for 7Technically, this circuit only works correctly if the states S and S′ have distinct encodings, as required by the conditions stated at the end of Section 2.2. If S and S′ happen to have the same encoding, the circuit will erroneously output 1. However, later on, in Section 5.5, we describe a circuit that enforces the condition that distinct states have distinct encodings. This circuit is incorporated into the final oracle, as described in Section 5.6, so that it forces the oracle’s output to 0 whenever this condition is violated. The operation of the circuit described in the present section therefore becomes irrelevant in such a case, since Grover’s algorithm will never find such a distinctness-violating encoding as a solution. From now on, we therefore proceed with the implicit assumption that distinct states have distinct encodings. The same applies to input values as well—the operation of the circuit described here is similarly irrelevant if distinct input values do not have distinct encodings. 24 Q1(S ′) Q2(S ′) Q3(S ′) Q1(S) Q2(S) Q3(S) |0〉 Encoding of S′ Encoding of S D1(S, S ′) (a) Q1(S ′) Q2(S ′) Q3(S ′) Q1(S) Q2(S) Q3(S) Encoding of S′ Encoding of S A1(S, S ′) (b) Figure 11: (a) Quantum circuit to check D1(S, S ′); (b) circuit to check A1(S, S ′). a b |1〉 a ⇒ b Figure 12: Logical implication evaluated using a Toffoli gate. 25 192 E. TSAI, M. PERKOWSKI A Quantum Algorithm for Automata Encoding 193 many pairs of states. For instance, consider the state machine from Fig- ure 2, and suppose that we wish to design a quantum circuit to evaluate Eq. 2 for i = 1, j = 2, and the pair of input values (I, I′) = (I1, I2). The cir- cuit must then check whether A1(δ(S, I), δ(S, I ′)) holds for all states S. In this case, given I = I1 and I ′ = I2, the corresponding pairs (δ(S, I), δ(S, I ′)) of next states are (S2, S2), (S4, S1), (S2, S3), and (S4, S4) for S = S1, S2, S3, and S4, respectively. Since A1(S2, S2) and A1(S4, S4) are trivially true, we can ignore them. Thus, the quantum circuit must check whether A1(S4, S1) and A1(S2, S3) simultaneously hold. The upper portion of Fig- ure 13 demonstrates a subcircuit that accomplishes this task. The lower portion of Figure 13 then combines this subcircuit with another subcircuit (from Figure 11(b)) to evaluate the full Eq. 2. In other words, the final output of this circuit, on the bottommost qubit, will be 1 if Eq. 2 is satis- fied, and 0 if it is not. We reiterate that for an FSM with more than four input values (so that each input value is encoded by at least three bits), one would replace the simplified circuit for evaluating D2(I1, I2) with the full one from Figure 11(a). In some cases, checking Eq. 1 or 2 may involve evaluating Ai(I, I ′) simultaneously for two or more overlapping pairs of inputs (or states). In these scenarios, one must construct the quantum circuit for checking Eq. 1 or 2 using a slightly different design. For example, suppose that we now wish to design a quantum circuit to evaluate Eq. 2 for the same state machine and i = 1, j = 2 as before, but a different pair of input values (I1, I3). The pairs of next states corresponding to current states of S1, S2, S3, and S4 are (S2, S2), (S4, S3), (S2, S3), and (S4, S2), respectively. Therefore, the quantum circuit must evaluate D2(I1, I3) ⇒ A1(S4, S3) ∧ A1(S2, S3) ∧ A1(S4, S2). (6) We then observe that, since the pairs of states on the right-hand side overlap, the entire right-hand side is equivalent to the condition that the encodings of S2, S3, S4 must all agree in the value of Q1. 8 We denote this condition by A1(S2, S3, S4), a natural generalization of our earlier Ai(S, S ′) notation for pairs of states. Figure 14 illustrates the quantum circuit for evaluating Eq. 2 in this case. The critical difference between Figures 13 and 14 is that the Feynman gates in the upper portion of Figure 14 operate on the encodings of overlapping pairs of states, and must therefore be applied in the correct order. Additionally, although the right-hand side of Eq. 6 contains the term A1(S4, S2), the circuit in Figure 14 does not contain a corresponding Feynman gate to evaluate this term. Such a gate is unnecessary because of transitivity—it is enough to check both A1(S2, S3) and A1(S3, S4) since they are together equivalent to A1(S2, S3, S4), which implies A1(S4, S2). More generally, one can construct similar circuits to evaluate Ai(S, S ′) for any number of overlapping pairs of states. One simply takes the union of all such pairs to obtain an arbitrarily-sized set of states and then con- structs a quantum circuit according to the pattern shown in Figure 15(a). 8For this particular example, this condition is impossible because, since we require encod- ings to be bijective, the encodings of at most two states can agree in the value of Q1. However, this condition could be satisfied in an FSM with more states. 26 Q1(S1) Q2(S1) Q1(S2) Q2(S2) Q1(S3) Q2(S3) Q1(S4) Q2(S4) x1(I1) x2(I1) x1(I3) x2(I3) x1(I4) x2(I4) x2(I2) x1(I2) |0〉 |0〉 |1〉 A1(S1, S4) ∧ A1(S2, S3) D2(I1, I2) D2(I1, I2) ⇒ A1(S1, S4) ∧ A1(S2, S3) Figure 13: Quantum circuit to evaluate Eq. 2 for input pair (I1, I2). 27 194 E. TSAI, M. PERKOWSKI A Quantum Algorithm for Automata Encoding 195 many pairs of states. For instance, consider the state machine from Fig- ure 2, and suppose that we wish to design a quantum circuit to evaluate Eq. 2 for i = 1, j = 2, and the pair of input values (I, I′) = (I1, I2). The cir- cuit must then check whether A1(δ(S, I), δ(S, I ′)) holds for all states S. In this case, given I = I1 and I ′ = I2, the corresponding pairs (δ(S, I), δ(S, I ′)) of next states are (S2, S2), (S4, S1), (S2, S3), and (S4, S4) for S = S1, S2, S3, and S4, respectively. Since A1(S2, S2) and A1(S4, S4) are trivially true, we can ignore them. Thus, the quantum circuit must check whether A1(S4, S1) and A1(S2, S3) simultaneously hold. The upper portion of Fig- ure 13 demonstrates a subcircuit that accomplishes this task. The lower portion of Figure 13 then combines this subcircuit with another subcircuit (from Figure 11(b)) to evaluate the full Eq. 2. In other words, the final output of this circuit, on the bottommost qubit, will be 1 if Eq. 2 is satis- fied, and 0 if it is not. We reiterate that for an FSM with more than four input values (so that each input value is encoded by at least three bits), one would replace the simplified circuit for evaluating D2(I1, I2) with the full one from Figure 11(a). In some cases, checking Eq. 1 or 2 may involve evaluating Ai(I, I ′) simultaneously for two or more overlapping pairs of inputs (or states). In these scenarios, one must construct the quantum circuit for checking Eq. 1 or 2 using a slightly different design. For example, suppose that we now wish to design a quantum circuit to evaluate Eq. 2 for the same state machine and i = 1, j = 2 as before, but a different pair of input values (I1, I3). The pairs of next states corresponding to current states of S1, S2, S3, and S4 are (S2, S2), (S4, S3), (S2, S3), and (S4, S2), respectively. Therefore, the quantum circuit must evaluate D2(I1, I3) ⇒ A1(S4, S3) ∧ A1(S2, S3) ∧ A1(S4, S2). (6) We then observe that, since the pairs of states on the right-hand side overlap, the entire right-hand side is equivalent to the condition that the encodings of S2, S3, S4 must all agree in the value of Q1. 8 We denote this condition by A1(S2, S3, S4), a natural generalization of our earlier Ai(S, S ′) notation for pairs of states. Figure 14 illustrates the quantum circuit for evaluating Eq. 2 in this case. The critical difference between Figures 13 and 14 is that the Feynman gates in the upper portion of Figure 14 operate on the encodings of overlapping pairs of states, and must therefore be applied in the correct order. Additionally, although the right-hand side of Eq. 6 contains the term A1(S4, S2), the circuit in Figure 14 does not contain a corresponding Feynman gate to evaluate this term. Such a gate is unnecessary because of transitivity—it is enough to check both A1(S2, S3) and A1(S3, S4) since they are together equivalent to A1(S2, S3, S4), which implies A1(S4, S2). More generally, one can construct similar circuits to evaluate Ai(S, S ′) for any number of overlapping pairs of states. One simply takes the union of all such pairs to obtain an arbitrarily-sized set of states and then con- structs a quantum circuit according to the pattern shown in Figure 15(a). 8For this particular example, this condition is impossible because, since we require encod- ings to be bijective, the encodings of at most two states can agree in the value of Q1. However, this condition could be satisfied in an FSM with more states. 26 Q1(S1) Q2(S1) Q1(S2) Q2(S2) Q1(S3) Q2(S3) Q1(S4) Q2(S4) x1(I1) x2(I1) x1(I3) x2(I3) x1(I4) x2(I4) x2(I2) x1(I2) |0〉 |0〉 |1〉 A1(S1, S4) ∧ A1(S2, S3) D2(I1, I2) D2(I1, I2) ⇒ A1(S1, S4) ∧ A1(S2, S3) Figure 13: Quantum circuit to evaluate Eq. 2 for input pair (I1, I2). 27 194 E. TSAI, M. PERKOWSKI A Quantum Algorithm for Automata Encoding 195 Q1(S1) Q2(S1) Q1(S2) Q2(S2) Q1(S3) Q2(S3) Q1(S4) Q2(S4) x1(I1) x2(I1) x1(I2) x2(I2) x1(I4) x2(I4) x2(I3) x1(I3) |0〉 |0〉 |1〉 A1(S2, S3, S4) D2(I1, I3) D2(I1, I3) ⇒ A1(S2, S3, S4) Figure 14: Quantum circuit to evaluate Eq. 2 for input pair (I1, I3). 28 Figure 15(b) then shows a circuit that checks whether Ai is simultaneously satisfied for multiple sets of states. These circuit structures are sufficient to algorithmically construct a quantum circuit for evaluating Eq. 1 or 2 in any case. Specifically, given any FSM with any number of states and input values, the following procedure constructs a quantum circuit to evaluate Eq. 1 for any i, j, and pair of states9 (S, S′): 1. List all of the pairs of states appearing on the right-hand side of Eq. 1 when expanded. In other words, create a list containing the pair of states (δ(S, I), δ(S′, I)) for every possible input value I. 2. In this list, merge any overlapping pairs of states together to obtain a collection of mutually disjoint sets of states. 3. Using the circuit structures from Figure 15, construct a circuit that checks whether Ai is simultaneously satisfied for every set of states produced by the previous step. 4. Using the circuit created in step 3 as a subcircuit, construct a circuit that checks the full Eq. 1, following the general pattern illustrated in Figures 13 and 14. From now on, we will refer to any circuit generated by this procedure as a partial dependency checker for the given pair of states, because it checks Eq. 1 for a single pair of states while the existence of a dependency is determined by checking Eq. 1 for all possible pairs of states. We observe that crucially, the quantum circuit design procedure de- scribed in this section requires at compile time only knowledge of the transition function of the FSM being encoded. In particular, the quan- tum circuit cannot be modified depending on the encoding whose cost is being evaluated, because individual encodings are not considered at com- pile time. Individual encodings are only considered at run time, when Grover’s algorithm is used to simultaneously evaluate the cost of every possible encoding in the search space. Thus, in a single run of Grover’s algorithm, the same quantum circuit must be able to evaluate any encod- ing in the search space without any modifications. 5.3 Quantum Circuit to Calculate Total Cost of an Encoding With the ability to generate a quantum circuit to evaluate Eq. 1 or 2 for any i, j, and pair of states or inputs, we now consider the task of designing a quantum circuit to calculate the full cost of a given encoding. Following the procedure from Section 4.1, the quantum circuit determines whether a given Q+i depends on Qj by checking if Eq. 1 is satisfied for all possible pairs of states.10 Figure 16 shows a circuit structure that accomplishes this task. From now on, we will refer to this circuit as a dependency checker. 9We describe the procedure here using Eq. 1 with a pair of states, but it functions equally well for Eq. 2 with a pair of input values. 10Once again, although we use dependencies on state variables for the sake of explanation, the whole discussion applies to dependencies on input variables as well. 29 196 E. TSAI, M. PERKOWSKI A Quantum Algorithm for Automata Encoding 197 Q1(S1) Q2(S1) Q1(S2) Q2(S2) Q1(S3) Q2(S3) Q1(S4) Q2(S4) x1(I1) x2(I1) x1(I2) x2(I2) x1(I4) x2(I4) x2(I3) x1(I3) |0〉 |0〉 |1〉 A1(S2, S3, S4) D2(I1, I3) D2(I1, I3) ⇒ A1(S2, S3, S4) Figure 14: Quantum circuit to evaluate Eq. 2 for input pair (I1, I3). 28 Figure 15(b) then shows a circuit that checks whether Ai is simultaneously satisfied for multiple sets of states. These circuit structures are sufficient to algorithmically construct a quantum circuit for evaluating Eq. 1 or 2 in any case. Specifically, given any FSM with any number of states and input values, the following procedure constructs a quantum circuit to evaluate Eq. 1 for any i, j, and pair of states9 (S, S′): 1. List all of the pairs of states appearing on the right-hand side of Eq. 1 when expanded. In other words, create a list containing the pair of states (δ(S, I), δ(S′, I)) for every possible input value I. 2. In this list, merge any overlapping pairs of states together to obtain a collection of mutually disjoint sets of states. 3. Using the circuit structures from Figure 15, construct a circuit that checks whether Ai is simultaneously satisfied for every set of states produced by the previous step. 4. Using the circuit created in step 3 as a subcircuit, construct a circuit that checks the full Eq. 1, following the general pattern illustrated in Figures 13 and 14. From now on, we will refer to any circuit generated by this procedure as a partial dependency checker for the given pair of states, because it checks Eq. 1 for a single pair of states while the existence of a dependency is determined by checking Eq. 1 for all possible pairs of states. We observe that crucially, the quantum circuit design procedure de- scribed in this section requires at compile time only knowledge of the transition function of the FSM being encoded. In particular, the quan- tum circuit cannot be modified depending on the encoding whose cost is being evaluated, because individual encodings are not considered at com- pile time. Individual encodings are only considered at run time, when Grover’s algorithm is used to simultaneously evaluate the cost of every possible encoding in the search space. Thus, in a single run of Grover’s algorithm, the same quantum circuit must be able to evaluate any encod- ing in the search space without any modifications. 5.3 Quantum Circuit to Calculate Total Cost of an Encoding With the ability to generate a quantum circuit to evaluate Eq. 1 or 2 for any i, j, and pair of states or inputs, we now consider the task of designing a quantum circuit to calculate the full cost of a given encoding. Following the procedure from Section 4.1, the quantum circuit determines whether a given Q+i depends on Qj by checking if Eq. 1 is satisfied for all possible pairs of states.10 Figure 16 shows a circuit structure that accomplishes this task. From now on, we will refer to this circuit as a dependency checker. 9We describe the procedure here using Eq. 1 with a pair of states, but it functions equally well for Eq. 2 with a pair of input values. 10Once again, although we use dependencies on state variables for the sake of explanation, the whole discussion applies to dependencies on input variables as well. 29 196 E. TSAI, M. PERKOWSKI A Quantum Algorithm for Automata Encoding 197 Q1(S1) Q2(S1) Qn(S1) Q1(S2) Q2(S2) Qn(S2) Q1(S3) Q2(S3) Qn(S3) Q1(SN ) Q2(SN ) Qn(SN ) |0〉 A1(S1, . . . , SN) (a) Qi(S1) Qi(S2) Qi(S3) Qi(S4) Qi(S5) Qi(S6) Qi(S7) Qi(S8) |0〉 Ai(S1, S2, S3) ∧ Ai(S4, S5, S6) ∧ Ai(S7, S8) (b) Figure 15: (a) Circuit to evaluate A1(S1, . . . , Sn) for an arbitrary number of states; (b) circuit for multiple sets of states. 30 Input qubits Ancilla qubits |0〉 |0〉 |0〉 |1〉 S1, S2 S1, S2S1, S3 S1, S3S3, S4 S3, S4 Figure 16: Quantum circuit to check dependency of Q+i on a single state or input variable. In Figure 16, the labeled “input qubits” represent the entire collection of qubits storing the binary representation of an encoding, as described in Section 5.1. Each block represents a partial dependency checker that checks Eq. 1 for the given i, j, and the pair of states with which it is labeled. “Ancilla qubits” represents the ancilla qubits that are used by these partial dependency checkers, as shown in Figures 13 and 14. For illustrative purposes, we have assumed an FSM with four states, resulting in six possible pairs of states; partial dependency checkers for three of them are shown. The same circuit structure, scaled up to accommodate the correspondingly larger number of subcircuits, would be used for an FSM with more states. The output from each partial dependency checker is stored on an ancilla qubit so that the final result can be obtained by taking their logical AND. Each partial dependency checker must be ap- plied again after the result is computed to restore the ancilla qubits to their original states, which, as previously discussed in Section 3.1, is re- quired for Grover’s algorithm to work correctly. The final output from the dependency checker is 1 if and only if Q+i depends on Qj. Next, we require another quantum circuit to calculate the total cost of the encoding by counting the total number of dependencies over all Q+i . We introduce a quantum counter for this purpose. The quantum counter consists of a register of qubits, which stores an integer in base- two representation, together with incrementer circuits that add one to this stored integer when a control qubit is in the state |1〉. Figure 17(a) shows a three-qubit incrementer. If the input qubits rep- resent an integer a2a1a0, with a2 being the most significant and a0 being the least significant bit, then the output of the incrementer is (the base- two representation of) a2a1a0 + 1 mod 2 3. The result is taken modulo 23 because due to reversibility, the maximum value of 23 − 1 must wrap 31 198 E. TSAI, M. PERKOWSKI A Quantum Algorithm for Automata Encoding 199 Q1(S1) Q2(S1) Qn(S1) Q1(S2) Q2(S2) Qn(S2) Q1(S3) Q2(S3) Qn(S3) Q1(SN ) Q2(SN ) Qn(SN ) |0〉 A1(S1, . . . , SN) (a) Qi(S1) Qi(S2) Qi(S3) Qi(S4) Qi(S5) Qi(S6) Qi(S7) Qi(S8) |0〉 Ai(S1, S2, S3) ∧ Ai(S4, S5, S6) ∧ Ai(S7, S8) (b) Figure 15: (a) Circuit to evaluate A1(S1, . . . , Sn) for an arbitrary number of states; (b) circuit for multiple sets of states. 30 Input qubits Ancilla qubits |0〉 |0〉 |0〉 |1〉 S1, S2 S1, S2S1, S3 S1, S3S3, S4 S3, S4 Figure 16: Quantum circuit to check dependency of Q+i on a single state or input variable. In Figure 16, the labeled “input qubits” represent the entire collection of qubits storing the binary representation of an encoding, as described in Section 5.1. Each block represents a partial dependency checker that checks Eq. 1 for the given i, j, and the pair of states with which it is labeled. “Ancilla qubits” represents the ancilla qubits that are used by these partial dependency checkers, as shown in Figures 13 and 14. For illustrative purposes, we have assumed an FSM with four states, resulting in six possible pairs of states; partial dependency checkers for three of them are shown. The same circuit structure, scaled up to accommodate the correspondingly larger number of subcircuits, would be used for an FSM with more states. The output from each partial dependency checker is stored on an ancilla qubit so that the final result can be obtained by taking their logical AND. Each partial dependency checker must be ap- plied again after the result is computed to restore the ancilla qubits to their original states, which, as previously discussed in Section 3.1, is re- quired for Grover’s algorithm to work correctly. The final output from the dependency checker is 1 if and only if Q+i depends on Qj. Next, we require another quantum circuit to calculate the total cost of the encoding by counting the total number of dependencies over all Q+i . We introduce a quantum counter for this purpose. The quantum counter consists of a register of qubits, which stores an integer in base- two representation, together with incrementer circuits that add one to this stored integer when a control qubit is in the state |1〉. Figure 17(a) shows a three-qubit incrementer. If the input qubits rep- resent an integer a2a1a0, with a2 being the most significant and a0 being the least significant bit, then the output of the incrementer is (the base- two representation of) a2a1a0 + 1 mod 2 3. The result is taken modulo 23 because due to reversibility, the maximum value of 23 − 1 must wrap 31 198 E. TSAI, M. PERKOWSKI A Quantum Algorithm for Automata Encoding 199 a2 a1 a0 (a2a1a0)2 + 1 mod 2 3 (a) a2 a1 a0 an (b) a2 a1 a0 an c (c) c anan−1...a1a0 n +1 (d) Figure 17: (a) A three-qubit incrementer; (b) general n-qubit incrementer; (c) controlled three-qubit incrementer; (d) schematic symbol for the controlled in- crementer. around to 0 upon increment. Figure 17(b) illustrates how the incrementer is extended to any number of qubits. Figure 17(c) then demonstrates how, by adding an additional control qubit to each individual gate making up the incrementer, a controlled incrementer is produced. As the name sug- gests, the controlled incrementer only increments the register an . . . a2a1a0 if the control qubit c is in the state |1〉. Figure 17(d) depicts the schematic symbol that we will use from now on to compactly represent a controlled incrementer. Observe that the lower line in this schematic represents not a single qubit but an entire register or array of n qubits. Using controlled incrementers, Figure 18 illustrates how a quantum counter is formed by a sequence of controlled incrementers all acting on the same target register. This register stores a running count which will be incremented once for each control qubit in the state |1〉. Since the register is initialized to |000〉, the final value on the register is simply the total number of control qubits in the state |1〉, represented as a base-two integer as before. We observe that the quantum counter depicted here is limited to a maximum of seven control qubits because the maximum value of the three-qubit target register is |111〉. Attempting to count further than this would simply result in the counter wrapping around back to |000〉, as previously mentioned. This limit can be raised by increasing the size of the target register; a target register consisting of n qubits will allow the quantum counter to count up a maximum value of 2n − 1. With quantum counters, it is easy to construct a quantum circuit that calculates the total cost of an encoding. We recall that cost is equal to the total number of dependencies of each Q+i on state and input variables 32 c1 c2 c7 |000〉 ∑ ci 3 +1 +1 +1 Figure 18: an example of a quantum counter. |1〉 |00 . . . 0〉 Input qubits Ancilla qubits D.C. Q+1 , Q1 D.C. Q+1 , Q1 +1 D.C. Q+1 , Q2 D.C. Q+1 , Q2 +1 D.C. Q+n , xm D.C. Q+n , xm +1 Figure 19: Quantum circuit to calculate total cost using a quantum counter. Qj and xk, summed over all i. Therefore, we create a quantum circuit consisting of many dependency checkers, one to evaluate each possible dependency, where the outputs of the dependency checkers are fed to a quantum counter that counts the total number of dependencies. The final value of the quantum counter then gives the cost of the encoding represented by the input qubits. Figure 19 depicts the structure of the resulting circuit. In Figure 19, each block labeled “D.C. Q+i , Qj” or “D.C. Q + i , xj” represents a dependency checker that checks whether Q+i depends on Qj or xj, respectively. Due to space constraints, only a few checkers are shown in Figure 19, but the full circuit requires dependency checkers for every possible combination of a Q+i and a Qj or xj. In other words, the circuit contains dependency checkers for Q+1 depending on each of Q1 through Qn and x1 through xm, Q + 2 depending on each of Q1 through Qn and x1 through xm, and so on up to Q + n depending on each of Q1 through Qn and x1 through xm, where n is the number of state variables and m is the number of input variables. Thus, the total number of dependency checkers is n(n + m). This number is actually quite small relative to the size of the state machine being encoded, since the number of state and input variables grow only logarithmically with the number of states and input values, respectively, in the FSM. We additionally observe that the quantum counter used in Figure 19 is constructed slightly differently from the example shown in Figure 18. 33 200 E. TSAI, M. PERKOWSKI A Quantum Algorithm for Automata Encoding 201 a2 a1 a0 (a2a1a0)2 + 1 mod 2 3 (a) a2 a1 a0 an (b) a2 a1 a0 an c (c) c anan−1...a1a0 n +1 (d) Figure 17: (a) A three-qubit incrementer; (b) general n-qubit incrementer; (c) controlled three-qubit incrementer; (d) schematic symbol for the controlled in- crementer. around to 0 upon increment. Figure 17(b) illustrates how the incrementer is extended to any number of qubits. Figure 17(c) then demonstrates how, by adding an additional control qubit to each individual gate making up the incrementer, a controlled incrementer is produced. As the name sug- gests, the controlled incrementer only increments the register an . . . a2a1a0 if the control qubit c is in the state |1〉. Figure 17(d) depicts the schematic symbol that we will use from now on to compactly represent a controlled incrementer. Observe that the lower line in this schematic represents not a single qubit but an entire register or array of n qubits. Using controlled incrementers, Figure 18 illustrates how a quantum counter is formed by a sequence of controlled incrementers all acting on the same target register. This register stores a running count which will be incremented once for each control qubit in the state |1〉. Since the register is initialized to |000〉, the final value on the register is simply the total number of control qubits in the state |1〉, represented as a base-two integer as before. We observe that the quantum counter depicted here is limited to a maximum of seven control qubits because the maximum value of the three-qubit target register is |111〉. Attempting to count further than this would simply result in the counter wrapping around back to |000〉, as previously mentioned. This limit can be raised by increasing the size of the target register; a target register consisting of n qubits will allow the quantum counter to count up a maximum value of 2n − 1. With quantum counters, it is easy to construct a quantum circuit that calculates the total cost of an encoding. We recall that cost is equal to the total number of dependencies of each Q+i on state and input variables 32 c1 c2 c7 |000〉 ∑ ci 3 +1 +1 +1 Figure 18: an example of a quantum counter. |1〉 |00 . . . 0〉 Input qubits Ancilla qubits D.C. Q+1 , Q1 D.C. Q+1 , Q1 +1 D.C. Q+1 , Q2 D.C. Q+1 , Q2 +1 D.C. Q+n , xm D.C. Q+n , xm +1 Figure 19: Quantum circuit to calculate total cost using a quantum counter. Qj and xk, summed over all i. Therefore, we create a quantum circuit consisting of many dependency checkers, one to evaluate each possible dependency, where the outputs of the dependency checkers are fed to a quantum counter that counts the total number of dependencies. The final value of the quantum counter then gives the cost of the encoding represented by the input qubits. Figure 19 depicts the structure of the resulting circuit. In Figure 19, each block labeled “D.C. Q+i , Qj” or “D.C. Q + i , xj” represents a dependency checker that checks whether Q+i depends on Qj or xj, respectively. Due to space constraints, only a few checkers are shown in Figure 19, but the full circuit requires dependency checkers for every possible combination of a Q+i and a Qj or xj. In other words, the circuit contains dependency checkers for Q+1 depending on each of Q1 through Qn and x1 through xm, Q + 2 depending on each of Q1 through Qn and x1 through xm, and so on up to Q + n depending on each of Q1 through Qn and x1 through xm, where n is the number of state variables and m is the number of input variables. Thus, the total number of dependency checkers is n(n + m). This number is actually quite small relative to the size of the state machine being encoded, since the number of state and input variables grow only logarithmically with the number of states and input values, respectively, in the FSM. We additionally observe that the quantum counter used in Figure 19 is constructed slightly differently from the example shown in Figure 18. 33 200 E. TSAI, M. PERKOWSKI A Quantum Algorithm for Automata Encoding 201 Specifically, the quantum counter in Figure 19 is able to count using only one control qubit, while the one in Figure 18 counts the number of ones present in a whole collection of control qubits. The reason for this differ- ence is that the circuit in Figure 19 counts the number of ones not in a collection of qubits, but appearing on a single qubit at different times. In other words, the circuit places the result of a given dependency checker onto the single counter control qubit and uses it to update the counter, but crucially, the circuit then applies the dependency checker again to re- store that control qubit to its original state so that the next dependency checker can also use it to update the counter as well. In this way, the cir- cuit is able to count dependencies without using a separate ancilla qubit to store the result of each dependency checker. As previously mentioned, the maximum value that a quantum counter can reach before wrapping around to zero is determined by the number of qubits in the counter’s target register. In Figure 19, the size of the quan- tum counter’s target register is not explicitly indicated because it depends on the maximum possible cost. The maximum possible cost is equal to the total number of possible dependencies, which as we previously saw is n(n + m) where n and m are the number of states and input values, re- spectively. Therefore, the quantum counter’s target register must contain at least �log2(n(n + m) + 1)� qubits to guarantee that no wrap-around can occur, which would cause the circuit to produce an incorrect result. 5.4 Quantum Threshold Circuit With a quantum circuit for calculating the cost of an encoding, we now add a threshold circuit to create a quantum oracle that determines whether the cost of the encoding is less than r, where r is the threshold for which the oracle is being generated. The threshold circuit accepts a set of qubits representing a base-two integer as input and produces an output that de- pends on whether the input is less than or equal to r. Designing such threshold circuits is a well-known and solved problem in classical digital logic. For instance, the following recursive procedure allows one to gener- ate a logical expression that determines whether a given base-two integer (anan−1 . . . a1a0)2 is less than or equal to a threshold (rnrn−1 . . . r1r0)2: 1. If the threshold and value to be compared against it consist of only a single bit, the expression is ¬a0 if r0 = 0 and a constant 1 if r0 = 1. In this case, stop immediately as we are finished. 2. Otherwise, recursively use this procedure to generate a logical ex- pression that determines whether (an−1 . . . a0)2 ≤ (rn−1 . . . r0)2. 3. If rn = 1, take the logical OR of ¬an with the expression generated in step 2. Otherwise, if rn = 0, take the logical AND. Return the resulting expression as the output of this procedure. 4. At the very end, when all recursive steps are complete, it may be possible to simplify the expression using the identities x ∨ 1 = 1 and x ∧ 1 = x. For example, suppose we wish to generate a logical expression that determines whether a2a1a0 is less than or equal to 5, whose base-two 34 a0 a1 a2 a3 a4 a5 |1〉 |0〉 |1〉 y Figure 20: Quantum circuit implementing the expression y = ¬a5 ∨(¬a4 ∧¬a3 ∧ ¬a2 ∧ (¬a1 ∨ ¬a0)). representation is 101. Then, since r2 = 1, we take the logical OR of ¬a2 with an expression recursively generated to determine whether a1a0 is less than or equal to (01)2 = 1. Since r1 = 0, we take the logical AND of ¬a1 with the expression that determines whether a0 is less than 1. This is the base case for which the procedure above returns a constant 1. Therefore, the complete generated expression is ¬a2 ∨ (¬a1 ∧ 1), which simplifies to ¬a2 ∨ ¬a1. Once a logical expression is obtained, constructing a quantum thresh- old circuit is simply a matter of implementing that logical expression with quantum gates. This can be achieved using a cascade of Toffoli gates as shown in Figure 20, where consecutive logical operations of the same type (either AND or OR) can be combined into a single Toffoli gate to reduce the number of ancilla qubits required. We observe that the threshold is “hard-coded” into the circuit (i.e., it is built into the circuit structure itself and can only be changed by changing the circuit) and therefore, generating a quantum oracle for a different threshold involves generating a new threshold circuit, as discussed in Section 3.2. 5.5 Quantum Circuit to Enforce Bijectivity of Encodings In Section 4.2, we saw that it is necessary for all encodings to be bijective, which implies that no two states or inputs of an FSM may be encoded by the same value. Therefore, the quantum oracle must include a circuit to check for and rule out encodings where the same encoded value is used more than once. This can be achieved by comparing the encoded values for every possible pair of states/inputs and verifying that the encoded values are different for every such pair. We therefore construct the circuit shown in Figure 21. Since there are four states in this figure, six pairs of states must be checked, of which three are shown. Similarly, checks for three out of the six pairs of inputs are shown, with the understanding that the 35 202 E. TSAI, M. PERKOWSKI A Quantum Algorithm for Automata Encoding 203 Specifically, the quantum counter in Figure 19 is able to count using only one control qubit, while the one in Figure 18 counts the number of ones present in a whole collection of control qubits. The reason for this differ- ence is that the circuit in Figure 19 counts the number of ones not in a collection of qubits, but appearing on a single qubit at different times. In other words, the circuit places the result of a given dependency checker onto the single counter control qubit and uses it to update the counter, but crucially, the circuit then applies the dependency checker again to re- store that control qubit to its original state so that the next dependency checker can also use it to update the counter as well. In this way, the cir- cuit is able to count dependencies without using a separate ancilla qubit to store the result of each dependency checker. As previously mentioned, the maximum value that a quantum counter can reach before wrapping around to zero is determined by the number of qubits in the counter’s target register. In Figure 19, the size of the quan- tum counter’s target register is not explicitly indicated because it depends on the maximum possible cost. The maximum possible cost is equal to the total number of possible dependencies, which as we previously saw is n(n + m) where n and m are the number of states and input values, re- spectively. Therefore, the quantum counter’s target register must contain at least �log2(n(n + m) + 1)� qubits to guarantee that no wrap-around can occur, which would cause the circuit to produce an incorrect result. 5.4 Quantum Threshold Circuit With a quantum circuit for calculating the cost of an encoding, we now add a threshold circuit to create a quantum oracle that determines whether the cost of the encoding is less than r, where r is the threshold for which the oracle is being generated. The threshold circuit accepts a set of qubits representing a base-two integer as input and produces an output that de- pends on whether the input is less than or equal to r. Designing such threshold circuits is a well-known and solved problem in classical digital logic. For instance, the following recursive procedure allows one to gener- ate a logical expression that determines whether a given base-two integer (anan−1 . . . a1a0)2 is less than or equal to a threshold (rnrn−1 . . . r1r0)2: 1. If the threshold and value to be compared against it consist of only a single bit, the expression is ¬a0 if r0 = 0 and a constant 1 if r0 = 1. In this case, stop immediately as we are finished. 2. Otherwise, recursively use this procedure to generate a logical ex- pression that determines whether (an−1 . . . a0)2 ≤ (rn−1 . . . r0)2. 3. If rn = 1, take the logical OR of ¬an with the expression generated in step 2. Otherwise, if rn = 0, take the logical AND. Return the resulting expression as the output of this procedure. 4. At the very end, when all recursive steps are complete, it may be possible to simplify the expression using the identities x ∨ 1 = 1 and x ∧ 1 = x. For example, suppose we wish to generate a logical expression that determines whether a2a1a0 is less than or equal to 5, whose base-two 34 a0 a1 a2 a3 a4 a5 |1〉 |0〉 |1〉 y Figure 20: Quantum circuit implementing the expression y = ¬a5 ∨(¬a4 ∧¬a3 ∧ ¬a2 ∧ (¬a1 ∨ ¬a0)). representation is 101. Then, since r2 = 1, we take the logical OR of ¬a2 with an expression recursively generated to determine whether a1a0 is less than or equal to (01)2 = 1. Since r1 = 0, we take the logical AND of ¬a1 with the expression that determines whether a0 is less than 1. This is the base case for which the procedure above returns a constant 1. Therefore, the complete generated expression is ¬a2 ∨ (¬a1 ∧ 1), which simplifies to ¬a2 ∨ ¬a1. Once a logical expression is obtained, constructing a quantum thresh- old circuit is simply a matter of implementing that logical expression with quantum gates. This can be achieved using a cascade of Toffoli gates as shown in Figure 20, where consecutive logical operations of the same type (either AND or OR) can be combined into a single Toffoli gate to reduce the number of ancilla qubits required. We observe that the threshold is “hard-coded” into the circuit (i.e., it is built into the circuit structure itself and can only be changed by changing the circuit) and therefore, generating a quantum oracle for a different threshold involves generating a new threshold circuit, as discussed in Section 3.2. 5.5 Quantum Circuit to Enforce Bijectivity of Encodings In Section 4.2, we saw that it is necessary for all encodings to be bijective, which implies that no two states or inputs of an FSM may be encoded by the same value. Therefore, the quantum oracle must include a circuit to check for and rule out encodings where the same encoded value is used more than once. This can be achieved by comparing the encoded values for every possible pair of states/inputs and verifying that the encoded values are different for every such pair. We therefore construct the circuit shown in Figure 21. Since there are four states in this figure, six pairs of states must be checked, of which three are shown. Similarly, checks for three out of the six pairs of inputs are shown, with the understanding that the 35 202 E. TSAI, M. PERKOWSKI A Quantum Algorithm for Automata Encoding 203 full circuit requires checks on all six. Observe that the exact same circuit applies for checking both state and input encodings, and that although Figure 21 assumes four states, the same structure may of course be scaled up for FSMs with any number of states or inputs. 5.6 The Complete Quantum Oracle Finally, we consider how the quantum circuits we have demonstrated thus far are assembled to form a complete quantum oracle. Recall that the cost calculation circuit (Section 5.3), which is itself assembled using a quantum counter and dependency checkers outputs the cost of an encoding expressed as a base-two integer, which is then passed to the threshold circuit (Section 5.4). The threshold circuit produces a single-qubit answer indicating whether the calculated cost is below the threshold or not. At the same time, an encoding must be bijective in order to be considered at all. This condition is enforced by a circuit that checks uniqueness of each state or input’s encoding (Section 5.5). We therefore see that our quantum oracle should only output 1 (true) if both the threshold and uniqueness checking circuits output 1. The complete quantum oracle therefore requires one additional Toffoli gate to produce its final output, as shown in Figure 22. In Figure 22, the block labeled “Cost” denotes the cost calculation circuit, “Th(r)” denotes a threshold circuit with threshold r, and “U.C.” (“uniqueness checker”) denotes the uniqueness checking circuit. The ora- cle also requires additional mirror circuits to restore the ancilla qubits to their original values. These are denoted by overbars; e.g., “U.C” denotes the mirror circuit for the uniqueness checker. In particular, the mirror of the cost calculation circuit contains decrementer instead of incrementer circuits; these decrementer circuits naturally arise from reversing the order of the gates in the incrementer circuits from Figure 17. Observe that the design of the oracle allows us to omit additional mirror circuits that would be necessary if these subcircuits were being used as stand-alone circuits. For instance, as a stand-alone circuit, the threshold circuit shown in Figure 20 would require additional mirror gates (as shown in Figure 23) if one wished to preserve the states of the two ancilla qubits for later reuse. However, when used in the quantum oracle, these additional mirror gates become unnecessary because the Th(r) and Th(r) subcircuits already act as mirrors to each other. Hence, the circuit structure shown in Figure 20, without additional mirror gates, can be used for both of these subcircuits (except, of course, that the Th(r) subcircuit is reversed compared to its counterpart). This simplification effectively halves the size of both of these subcircuits, as compared with their stand- alone form as seen in Figure 23. The exact same observation also applies to the uniqueness checking subcircuits U.C. and U.C.—their stand-alone forms would require additional mirror gates on top of the circuit structure shown in Figure 21, which become unnecessary when the subcircuits are used as components of the oracle in Figure 22. We observe that the threshold circuit is the only part of the oracle that must be regenerated for each run of Grover’s algorithm as described in Section 3.2. The other parts of the oracle are generated depending on the 36 Q1(S1) Q2(S1) Q1(S2) Q2(S2) Q1(S3) Q2(S3) Q1(S4) Q2(S4) x1(I1) x2(I1) x1(I2) x2(I2) x1(I3) x2(I3) x1(I4) x2(I4) |1〉 |1〉 |1〉 |1〉 |1〉 |1〉 |0〉 Figure 21: Quantum circuit to verify uniqueness of encoding for each state/input. |00 . . . 0〉 |0〉 |0〉 Output qubit Input/ Ancilla qubits Cost Th(r) U.C. U.C. Th(r) Cost Figure 22: High-level view of the quantum oracle. 37 204 E. TSAI, M. PERKOWSKI A Quantum Algorithm for Automata Encoding 205 full circuit requires checks on all six. Observe that the exact same circuit applies for checking both state and input encodings, and that although Figure 21 assumes four states, the same structure may of course be scaled up for FSMs with any number of states or inputs. 5.6 The Complete Quantum Oracle Finally, we consider how the quantum circuits we have demonstrated thus far are assembled to form a complete quantum oracle. Recall that the cost calculation circuit (Section 5.3), which is itself assembled using a quantum counter and dependency checkers outputs the cost of an encoding expressed as a base-two integer, which is then passed to the threshold circuit (Section 5.4). The threshold circuit produces a single-qubit answer indicating whether the calculated cost is below the threshold or not. At the same time, an encoding must be bijective in order to be considered at all. This condition is enforced by a circuit that checks uniqueness of each state or input’s encoding (Section 5.5). We therefore see that our quantum oracle should only output 1 (true) if both the threshold and uniqueness checking circuits output 1. The complete quantum oracle therefore requires one additional Toffoli gate to produce its final output, as shown in Figure 22. In Figure 22, the block labeled “Cost” denotes the cost calculation circuit, “Th(r)” denotes a threshold circuit with threshold r, and “U.C.” (“uniqueness checker”) denotes the uniqueness checking circuit. The ora- cle also requires additional mirror circuits to restore the ancilla qubits to their original values. These are denoted by overbars; e.g., “U.C” denotes the mirror circuit for the uniqueness checker. In particular, the mirror of the cost calculation circuit contains decrementer instead of incrementer circuits; these decrementer circuits naturally arise from reversing the order of the gates in the incrementer circuits from Figure 17. Observe that the design of the oracle allows us to omit additional mirror circuits that would be necessary if these subcircuits were being used as stand-alone circuits. For instance, as a stand-alone circuit, the threshold circuit shown in Figure 20 would require additional mirror gates (as shown in Figure 23) if one wished to preserve the states of the two ancilla qubits for later reuse. However, when used in the quantum oracle, these additional mirror gates become unnecessary because the Th(r) and Th(r) subcircuits already act as mirrors to each other. Hence, the circuit structure shown in Figure 20, without additional mirror gates, can be used for both of these subcircuits (except, of course, that the Th(r) subcircuit is reversed compared to its counterpart). This simplification effectively halves the size of both of these subcircuits, as compared with their stand- alone form as seen in Figure 23. The exact same observation also applies to the uniqueness checking subcircuits U.C. and U.C.—their stand-alone forms would require additional mirror gates on top of the circuit structure shown in Figure 21, which become unnecessary when the subcircuits are used as components of the oracle in Figure 22. We observe that the threshold circuit is the only part of the oracle that must be regenerated for each run of Grover’s algorithm as described in Section 3.2. The other parts of the oracle are generated depending on the 36 Q1(S1) Q2(S1) Q1(S2) Q2(S2) Q1(S3) Q2(S3) Q1(S4) Q2(S4) x1(I1) x2(I1) x1(I2) x2(I2) x1(I3) x2(I3) x1(I4) x2(I4) |1〉 |1〉 |1〉 |1〉 |1〉 |1〉 |0〉 Figure 21: Quantum circuit to verify uniqueness of encoding for each state/input. |00 . . . 0〉 |0〉 |0〉 Output qubit Input/ Ancilla qubits Cost Th(r) U.C. U.C. Th(r) Cost Figure 22: High-level view of the quantum oracle. 37 204 E. TSAI, M. PERKOWSKI A Quantum Algorithm for Automata Encoding 205 a0 a1 a2 a3 a4 a5 |1〉 |0〉 |1〉 Figure 23: Threshold circuit from Figure 20 with mirror gates. The mirror gates turn out to be unnecessary as explained in the main text. FSM being encoded, but are independent of the chosen threshold; thus, they remain unchanged throughout the entire search procedure described in Section 3.2. With this oracle,11 we have met the objective stated at the end of Section 3.2 and therefore, the procedure described in Section 3.2 gives a complete algorithm for finding an exact optimal encoding of an FSM with the help of Grover’s algorithm. 6 Run Time Complexity Analysis 6.1 Run Time Complexity of the Proposed Quan- tum Algorithm We now wish to determine the run time complexity of our proposed quan- tum algorithm, in order to compare its performance against that of an analogous exhaustive search-based classical algorithm for the same prob- lem. In this determination, we make certain simplifying assumptions, as described below. These simplifications are justified because our goal is not to perform the most detailed and nuanced analysis possible, but rather to show that our proposed algorithm can reasonably be expected to outperform the classical algorithm. When computing the run time complexity of a quantum circuit, we must take into account the differing quantum cost [19] of the various quan- tum gates used in the circuit—in our case, these are Feynman, Toffoli, and multiple-control Toffoli gates. We recall that quantum gates are not phys- ical hardware components like classical digital logic gates; instead, they are manipulations of the physical qubits, consisting of sequences of fun- damental physical operations on those qubits. The quantum cost of a 11To be more precise, we have described not a single oracle but a design according to which a whole sequence of oracles (for different thresholds) can be generated for any given FSM. This ability to generate a sequence of oracles is exactly what we need, as discussed in Section 3.2. 38 a b c d |0〉 |0〉 |0〉 a ∧ b ∧ c ∧ d Figure 24: Implementation of a multiple-control Toffoli gate with quantum cost scaling linearly with gate size. quantum gate is then the number of physical operations required to im- plement that gate, which roughly corresponds to the run time complexity of the gate if we assume that each fundamental physical operation requires approximately the same amount of time. Authors in the quantum com- puting literature have proposed a variety of quantum cost models, based on differing assumptions about the physical implementation of a quan- tum computing system and the fundamental operations available therein. For instance, a well-known result due to Barenco et al. [20] suggests12 that the quantum cost of a multiple-control Toffoli may be up to O(2n), where n is the size of the gate. However, this result assumes that no ancilla qubits are used. With the use of ancilla qubits, it is easy to see that multiple-control Toffoli gates of arbitrary size may be implemented with a quantum cost that is linear with respect to the size of the gate. A cascade of Toffoli gates, as shown in Figure 24, accomplishes this task. Throughout the following analysis, we will assume that an arbitrary number of ancilla qubits are available, and therefore the quantum cost of a multiple-control Toffoli gate is linear with respect to the gate’s size. We make this assumption as it simplifies our calculations and is most conducive to our goal of obtaining a rough estimate of the run time com- plexity of our proposed quantum algorithm. The question of how the run time complexity varies in other quantum cost models is an interesting one, but outside the scope of the present paper. We leave further investigation of this question open for future work. Our algorithm operates under the condition that the numbers of states and input values of the FSM must both be powers of two. Let us denote the number of states by NS and the number of input values by NI. Then, NS = 2 nS and NI = 2 nI for some nonnegative integers nS and nI, where nS and nI are respectively the number of state and input variables. Con- versely, nS = log2 NS = O(log NS) and NI = log2 NI = O(log NI). We first 12We say “suggests” because, although the results of Barenco et al. are widely used through- out the literature as a standard quantum cost function for multiple-control Toffoli gates, we do not know of a conclusive proof that it is impossible to implement a multiple-control Toffoli gate with lower cost complexity (assuming that no ancilla qubits are used). In any case, our results are unaffected since we assume instead that ancilla qubits are used to implement multiple-control Toffoli gates with O(n) quantum cost, as illustrated in the main text. 39 206 E. TSAI, M. PERKOWSKI A Quantum Algorithm for Automata Encoding 207 a0 a1 a2 a3 a4 a5 |1〉 |0〉 |1〉 Figure 23: Threshold circuit from Figure 20 with mirror gates. The mirror gates turn out to be unnecessary as explained in the main text. FSM being encoded, but are independent of the chosen threshold; thus, they remain unchanged throughout the entire search procedure described in Section 3.2. With this oracle,11 we have met the objective stated at the end of Section 3.2 and therefore, the procedure described in Section 3.2 gives a complete algorithm for finding an exact optimal encoding of an FSM with the help of Grover’s algorithm. 6 Run Time Complexity Analysis 6.1 Run Time Complexity of the Proposed Quan- tum Algorithm We now wish to determine the run time complexity of our proposed quan- tum algorithm, in order to compare its performance against that of an analogous exhaustive search-based classical algorithm for the same prob- lem. In this determination, we make certain simplifying assumptions, as described below. These simplifications are justified because our goal is not to perform the most detailed and nuanced analysis possible, but rather to show that our proposed algorithm can reasonably be expected to outperform the classical algorithm. When computing the run time complexity of a quantum circuit, we must take into account the differing quantum cost [19] of the various quan- tum gates used in the circuit—in our case, these are Feynman, Toffoli, and multiple-control Toffoli gates. We recall that quantum gates are not phys- ical hardware components like classical digital logic gates; instead, they are manipulations of the physical qubits, consisting of sequences of fun- damental physical operations on those qubits. The quantum cost of a 11To be more precise, we have described not a single oracle but a design according to which a whole sequence of oracles (for different thresholds) can be generated for any given FSM. This ability to generate a sequence of oracles is exactly what we need, as discussed in Section 3.2. 38 a b c d |0〉 |0〉 |0〉 a ∧ b ∧ c ∧ d Figure 24: Implementation of a multiple-control Toffoli gate with quantum cost scaling linearly with gate size. quantum gate is then the number of physical operations required to im- plement that gate, which roughly corresponds to the run time complexity of the gate if we assume that each fundamental physical operation requires approximately the same amount of time. Authors in the quantum com- puting literature have proposed a variety of quantum cost models, based on differing assumptions about the physical implementation of a quan- tum computing system and the fundamental operations available therein. For instance, a well-known result due to Barenco et al. [20] suggests12 that the quantum cost of a multiple-control Toffoli may be up to O(2n), where n is the size of the gate. However, this result assumes that no ancilla qubits are used. With the use of ancilla qubits, it is easy to see that multiple-control Toffoli gates of arbitrary size may be implemented with a quantum cost that is linear with respect to the size of the gate. A cascade of Toffoli gates, as shown in Figure 24, accomplishes this task. Throughout the following analysis, we will assume that an arbitrary number of ancilla qubits are available, and therefore the quantum cost of a multiple-control Toffoli gate is linear with respect to the gate’s size. We make this assumption as it simplifies our calculations and is most conducive to our goal of obtaining a rough estimate of the run time com- plexity of our proposed quantum algorithm. The question of how the run time complexity varies in other quantum cost models is an interesting one, but outside the scope of the present paper. We leave further investigation of this question open for future work. Our algorithm operates under the condition that the numbers of states and input values of the FSM must both be powers of two. Let us denote the number of states by NS and the number of input values by NI. Then, NS = 2 nS and NI = 2 nI for some nonnegative integers nS and nI, where nS and nI are respectively the number of state and input variables. Con- versely, nS = log2 NS = O(log NS) and NI = log2 NI = O(log NI). We first 12We say “suggests” because, although the results of Barenco et al. are widely used through- out the literature as a standard quantum cost function for multiple-control Toffoli gates, we do not know of a conclusive proof that it is impossible to implement a multiple-control Toffoli gate with lower cost complexity (assuming that no ancilla qubits are used). In any case, our results are unaffected since we assume instead that ancilla qubits are used to implement multiple-control Toffoli gates with O(n) quantum cost, as illustrated in the main text. 39 206 E. TSAI, M. PERKOWSKI A Quantum Algorithm for Automata Encoding 207 consider the run time complexity for the dependency checking quantum circuits described in Sections 5.2 and 5.3. Calculation of this complexity is complicated by the fact that the partial dependency checkers described in Section 5.2 do not have a fixed complexity; rather, as discussed in that section, their internal structure depends on the particular details of the state machine under consideration. However, we may still calculate an upper bound for the complexity of each partial dependency checker. In the following paragraph, we use the example circuits shown in Fig- ures 11, 13, and 14 as a reference. Evaluating Dj(S, S ′) for a pair of states requires O(nS) = O(log NS) time, since nS − 1 Feynman gates are required together with a multiple-control Toffoli gate of size nS (nS − 1 control qubits and one target qubit). By analogous reasoning, evaluating Dj(I, I ′) requires O(nI) = O(log NI) time. Meanwhile, evaluating Ai(S, S′) is an O(1) operation, since only a single Feynman gate is needed. Ob- serve that the upper portion of every partial dependency checker (as in Figures 13 and 14) must evaluate Ai(S, S ′) for up to NS − 1 state pairs, with this maximum being obtained when all state pairs are overlapping, as in (S1, S2), (S2, S3), (S3, S4), etc. The lower portion of each partial de- pendency checker always evaluates Dj(S, S ′) or Dj(I, I ′) for only one pair of inputs/states. The total complexity of a partial dependency checker is therefore (NS − 1) · O(1) + 1 · O(log NS) = O(NS + log NS) = O(NS), for a partial dependency checker that evaluates Dj(S, S ′) for a pair of states and checks Eq. 1, or (NS − 1) · O(1) + 1 · O(log NS) = O(NS + log NI), for a partial dependency checker that evaluates Dj(I, I ′) for a pair of inputs and checks Eq. 2. From Figure 16 we can see that checking the dependencies of the next state of a single flip-flop on a single state or input variable requires ei- ther NS(NS − 1)/2 (for a state variable) or NI(NI − 1)/2 (for an input variable) partial dependency checkers. Combining with the previously derived complexity for a single partial dependency checker gives O(NS3) (for a state variable) or O(NI2(NS + log NI)) (for an input variable). The central Toffoli gate in Figure 16 has either NS(NS − 1)/2 or NI(NI − 1)/2 control qubits, so its time complexity is dominated by that of the partial dependency checkers. In Figure 19, we can see that there are nS 2 = (log NS) 2 checks for de- pendency of Q+i (for any i) on a state variable, and nSnI = log NS log NI checks for dependency on an input variable. Therefore, the total complex- ity of all the dependency checkers in the circuit from Figure 19 is (log NS) 2 · O(NS3) + log NS log NI · O(NI2(NS + log NI)) = O(NS3(log NS)2 + NI2(NS + log NI)(log NS log NI)). (7) The complexity of the incrementer circuits in Figure 19 is clearly dom- inated by that of the dependency checkers, so the preceding expression gives the time complexity for the entire cost-calculating portion of the quantum oracle. Finally, we must consider the complexity of the two other components of the oracle, as shown in Figure 22—the threshold circuit and uniqueness- checking circuit. The complexity of the cost-calculating circuit clearly dominates that of the threshold circuit, but the situation with respect to 40 the uniqueness-checking circuit is less clear. As seen in Figure 21, the uniqueness-checking circuit performs a comparison for every possible pair of states, of which there are NS(NS −1)/2, and every possible pair of input values, of which there are NI(NI − 1)/2. Furthermore, a comparison of a pair of states has complexity O(nS) = O(log NS), since each individual state variable assignment must be compared between the two states, and a comparison of a pair of inputs similarly has complexity O(nI) = O(log NI). The final Toffoli gate in Figure 21 has NS(NS −1)/2+NI(NI −1)/2 control qubits, giving the entire uniqueness-checking circuit a complexity of NS(NS − 1) 2 · O(log NS) + NI(NI − 1) 2 · O(log NI) +O ( NS(NS − 1) 2 + NI(NI − 1) 2 ) = O(N2S log NS + N 2 I log NI). Comparison with Eq. 7 shows that the cost-calculating circuit dominates the uniqueness-checking circuit in terms of complexity. Therefore, the run time complexity of the entire quantum oracle is still given by Eq. 7. As we recall from Section 3.2, our proposed quantum algorithm in- volves executing Grover’s algorithm multiple times to find an optimal encoding for an FSM. It is uncertain exactly how many executions of Grover’s algorithm are required, as we do not consider the details of the search procedure used to find the minimum cost. However, we may con- sider the time complexity of just a single execution of Grover’s algorithm. This does not affect our ability to compare the performance of quantum and classical algorithms because they both must perform a search proce- dure as described in Section 3.2 in order to find the minimum possible cost. We discussed in Section 3.1 how Grover’s algorithm (together with its extensions for the case of multiple solutions) is able to find a so- lution to a satisfaction problem, or detect the non-existence of a solu- tion, with O( √ M) executions of the quantum oracle, where M is the size of the search space. (We have used M to avoid confusion with the numbers of states and input values.) As discussed in Section 5.1 and shown in Figure 10(b), our proposed oracle requires NSnS + NInI = O(NS log NS + NI + log NI) input qubits, corresponding to a search space of size O(2NS log NS+NI+log NI) = O(NSNSNINI). Hence, a single execution of Grover’s algorithm requires O( √ NS NSNI NI) executions of the quantum oracle. The total complexity of one execution of Grover’s algorithm, tak- ing into account the previously determined complexity of the oracle, is then O( √ NS NSNI NI(NS 3 (log NS) 2 + NI 2 (NS + log NI)(log NS log NI))). (8) Eq. 8 is rather unwieldy for a simple, rough comparison between the performance of quantum and classical algorithms. If we assume that NS = NI, that is, the FSM has the same number of states as input values, then 41 208 E. TSAI, M. PERKOWSKI A Quantum Algorithm for Automata Encoding 209 consider the run time complexity for the dependency checking quantum circuits described in Sections 5.2 and 5.3. Calculation of this complexity is complicated by the fact that the partial dependency checkers described in Section 5.2 do not have a fixed complexity; rather, as discussed in that section, their internal structure depends on the particular details of the state machine under consideration. However, we may still calculate an upper bound for the complexity of each partial dependency checker. In the following paragraph, we use the example circuits shown in Fig- ures 11, 13, and 14 as a reference. Evaluating Dj(S, S ′) for a pair of states requires O(nS) = O(log NS) time, since nS − 1 Feynman gates are required together with a multiple-control Toffoli gate of size nS (nS − 1 control qubits and one target qubit). By analogous reasoning, evaluating Dj(I, I ′) requires O(nI) = O(log NI) time. Meanwhile, evaluating Ai(S, S′) is an O(1) operation, since only a single Feynman gate is needed. Ob- serve that the upper portion of every partial dependency checker (as in Figures 13 and 14) must evaluate Ai(S, S ′) for up to NS − 1 state pairs, with this maximum being obtained when all state pairs are overlapping, as in (S1, S2), (S2, S3), (S3, S4), etc. The lower portion of each partial de- pendency checker always evaluates Dj(S, S ′) or Dj(I, I ′) for only one pair of inputs/states. The total complexity of a partial dependency checker is therefore (NS − 1) · O(1) + 1 · O(log NS) = O(NS + log NS) = O(NS), for a partial dependency checker that evaluates Dj(S, S ′) for a pair of states and checks Eq. 1, or (NS − 1) · O(1) + 1 · O(log NS) = O(NS + log NI), for a partial dependency checker that evaluates Dj(I, I ′) for a pair of inputs and checks Eq. 2. From Figure 16 we can see that checking the dependencies of the next state of a single flip-flop on a single state or input variable requires ei- ther NS(NS − 1)/2 (for a state variable) or NI(NI − 1)/2 (for an input variable) partial dependency checkers. Combining with the previously derived complexity for a single partial dependency checker gives O(NS3) (for a state variable) or O(NI2(NS + log NI)) (for an input variable). The central Toffoli gate in Figure 16 has either NS(NS − 1)/2 or NI(NI − 1)/2 control qubits, so its time complexity is dominated by that of the partial dependency checkers. In Figure 19, we can see that there are nS 2 = (log NS) 2 checks for de- pendency of Q+i (for any i) on a state variable, and nSnI = log NS log NI checks for dependency on an input variable. Therefore, the total complex- ity of all the dependency checkers in the circuit from Figure 19 is (log NS) 2 · O(NS3) + log NS log NI · O(NI2(NS + log NI)) = O(NS3(log NS)2 + NI2(NS + log NI)(log NS log NI)). (7) The complexity of the incrementer circuits in Figure 19 is clearly dom- inated by that of the dependency checkers, so the preceding expression gives the time complexity for the entire cost-calculating portion of the quantum oracle. Finally, we must consider the complexity of the two other components of the oracle, as shown in Figure 22—the threshold circuit and uniqueness- checking circuit. The complexity of the cost-calculating circuit clearly dominates that of the threshold circuit, but the situation with respect to 40 the uniqueness-checking circuit is less clear. As seen in Figure 21, the uniqueness-checking circuit performs a comparison for every possible pair of states, of which there are NS(NS −1)/2, and every possible pair of input values, of which there are NI(NI − 1)/2. Furthermore, a comparison of a pair of states has complexity O(nS) = O(log NS), since each individual state variable assignment must be compared between the two states, and a comparison of a pair of inputs similarly has complexity O(nI) = O(log NI). The final Toffoli gate in Figure 21 has NS(NS −1)/2+NI(NI −1)/2 control qubits, giving the entire uniqueness-checking circuit a complexity of NS(NS − 1) 2 · O(log NS) + NI(NI − 1) 2 · O(log NI) +O ( NS(NS − 1) 2 + NI(NI − 1) 2 ) = O(N2S log NS + N 2 I log NI). Comparison with Eq. 7 shows that the cost-calculating circuit dominates the uniqueness-checking circuit in terms of complexity. Therefore, the run time complexity of the entire quantum oracle is still given by Eq. 7. As we recall from Section 3.2, our proposed quantum algorithm in- volves executing Grover’s algorithm multiple times to find an optimal encoding for an FSM. It is uncertain exactly how many executions of Grover’s algorithm are required, as we do not consider the details of the search procedure used to find the minimum cost. However, we may con- sider the time complexity of just a single execution of Grover’s algorithm. This does not affect our ability to compare the performance of quantum and classical algorithms because they both must perform a search proce- dure as described in Section 3.2 in order to find the minimum possible cost. We discussed in Section 3.1 how Grover’s algorithm (together with its extensions for the case of multiple solutions) is able to find a so- lution to a satisfaction problem, or detect the non-existence of a solu- tion, with O( √ M) executions of the quantum oracle, where M is the size of the search space. (We have used M to avoid confusion with the numbers of states and input values.) As discussed in Section 5.1 and shown in Figure 10(b), our proposed oracle requires NSnS + NInI = O(NS log NS + NI + log NI) input qubits, corresponding to a search space of size O(2NS log NS+NI+log NI) = O(NSNSNINI). Hence, a single execution of Grover’s algorithm requires O( √ NS NSNI NI) executions of the quantum oracle. The total complexity of one execution of Grover’s algorithm, tak- ing into account the previously determined complexity of the oracle, is then O( √ NS NSNI NI(NS 3 (log NS) 2 + NI 2 (NS + log NI)(log NS log NI))). (8) Eq. 8 is rather unwieldy for a simple, rough comparison between the performance of quantum and classical algorithms. If we assume that NS = NI, that is, the FSM has the same number of states as input values, then 41 208 E. TSAI, M. PERKOWSKI A Quantum Algorithm for Automata Encoding 209 Eq. 8 simplifies to the much more manageable O( √ NS NSNI NI(NS 3 (log NS) 2 + NI 2 (NS + log NI)(log NS log NI))) = O(NSNS(NS3(log NS)2 + NS2(NS + log NS)(log NS log NS))) = O(NSNS(NS3(log NS)2)) = O(NSNS+3(log NS)2). (9) 6.2 Comparison With a Classical Algorithm A comparable classical algorithm to solve the FSM encoding problem would operate in much the same way as our proposed quantum algorithm, with the main difference being that a classical computer of course cannot use Grover’s algorithm and must instead use a straightforward exhaustive search. In particular, a classical computer must also use Eqs. 1 and 2 to calculate the cost of a given encoding. Most, if not all, modern digital computers are capable of performing so-called bitwise logical operations on words of significant length (at least 32 or 64 bits), which allows them to evaluate Dj(S, S ′) and Ai(S, S ′) for any pair of states or Dj(I, I ′) for any pair of inputs in O(1) time. (We need not consider state machines with more than 232 states or input values, as such a machine would be far too large to be of practical interest.) It follows that a classical computer can evaluate Eq. 1 in O(NI) time, since it requires iterating over all input values. Then, determining whether Q+i depends on Qj, for any values of i and j, requires evaluating Eq. 1 for all NS(NS − 1)/2 pairs of states and therefore takes O(NS2NI) time. Similarly, a single evaluation of Eq. 2 requires O(NS) time and determining whether Q+i depends on xk, for any values of i and k, requires O(NSNI2) time. Calculating the total cost of an encoding involves checking the de- pendency of Q+i on Qj for all combinations of i and j, of which there are (log2 NS) 2 , and the dependency of Q+i on xk for all combinations of i and k, of which there are (log2 NS)(log2 NI). Therefore, the complete calculation of the cost of an encoding on a classical computer requires O(NS2NI(log NS)2 + NSNI2(log NS)(log NI)) time. The number of possi- ble encodings is NS!NI!, so a full exhaustive search on a classical computer has a total time complexity of O(NS!NI!(NS2NI(log NS)2 + NSNI2(log NS)(log NI))). (10) Just as for the quantum algorithm, we can simplify this expression if we assume that NS = NI; in this case, Eq. 10 reduces to O(NS!NS!(NS3(log NS)2 + NS3(log NS)(log NS))) = O(NS!2NS3(log NS)2). (11) Comparing Eqs. 9 and 11, we see that the factor of NS 3 log NS is com- mon to both. We may therefore compare the relative complexities of the quantum and classical algorithms, if NS = NI, by looking only at the terms NS NS (for the quantum algorithm) and NS! 2 (for the classical algo- rithm). Table 1 shows the results for a few values of NS. We immediately see that the quantum algorithm appears to be significantly faster than the 42 210 E. TSAI, M. PERKOWSKI A Quantum Algorithm for Automata Encoding 211 Eq. 8 simplifies to the much more manageable O( √ NS NSNI NI(NS 3 (log NS) 2 + NI 2 (NS + log NI)(log NS log NI))) = O(NSNS(NS3(log NS)2 + NS2(NS + log NS)(log NS log NS))) = O(NSNS(NS3(log NS)2)) = O(NSNS+3(log NS)2). (9) 6.2 Comparison With a Classical Algorithm A comparable classical algorithm to solve the FSM encoding problem would operate in much the same way as our proposed quantum algorithm, with the main difference being that a classical computer of course cannot use Grover’s algorithm and must instead use a straightforward exhaustive search. In particular, a classical computer must also use Eqs. 1 and 2 to calculate the cost of a given encoding. Most, if not all, modern digital computers are capable of performing so-called bitwise logical operations on words of significant length (at least 32 or 64 bits), which allows them to evaluate Dj(S, S ′) and Ai(S, S ′) for any pair of states or Dj(I, I ′) for any pair of inputs in O(1) time. (We need not consider state machines with more than 232 states or input values, as such a machine would be far too large to be of practical interest.) It follows that a classical computer can evaluate Eq. 1 in O(NI) time, since it requires iterating over all input values. Then, determining whether Q+i depends on Qj, for any values of i and j, requires evaluating Eq. 1 for all NS(NS − 1)/2 pairs of states and therefore takes O(NS2NI) time. Similarly, a single evaluation of Eq. 2 requires O(NS) time and determining whether Q+i depends on xk, for any values of i and k, requires O(NSNI2) time. Calculating the total cost of an encoding involves checking the de- pendency of Q+i on Qj for all combinations of i and j, of which there are (log2 NS) 2 , and the dependency of Q+i on xk for all combinations of i and k, of which there are (log2 NS)(log2 NI). Therefore, the complete calculation of the cost of an encoding on a classical computer requires O(NS2NI(log NS)2 + NSNI2(log NS)(log NI)) time. The number of possi- ble encodings is NS!NI!, so a full exhaustive search on a classical computer has a total time complexity of O(NS!NI!(NS2NI(log NS)2 + NSNI2(log NS)(log NI))). (10) Just as for the quantum algorithm, we can simplify this expression if we assume that NS = NI; in this case, Eq. 10 reduces to O(NS!NS!(NS3(log NS)2 + NS3(log NS)(log NS))) = O(NS!2NS3(log NS)2). (11) Comparing Eqs. 9 and 11, we see that the factor of NS 3 log NS is com- mon to both. We may therefore compare the relative complexities of the quantum and classical algorithms, if NS = NI, by looking only at the terms NS NS (for the quantum algorithm) and NS! 2 (for the classical algo- rithm). Table 1 shows the results for a few values of NS. We immediately see that the quantum algorithm appears to be significantly faster than the 42 Table 1: Comparison of relative complexities of quantum and classical algo- rithms, assuming NS = NI. NS NS NS NS! 2 NS! 2 NS NS 4 256 576 2.25 8 1.68 · 107 1.63 · 109 96.9 16 1.84 · 1019 4.38 · 1026 2.37 · 107 32 1.46 · 1048 6.92 · 1070 4.74 · 1022 classical algorithm. Care must be taken in this comparison because we are only comparing the relative complexities of the two algorithms and not their actual run times. In particular, the actual ratio of run times between the two algorithms is better approximated as CNS! 2/NS NS, where C is an unknown constant. For example, C = 1/1000 indicates, very roughly speaking, that the classical computer’s “clock speed”—by which we mean not necessarily the hardware’s physical clock speed, but rather the num- ber of low-level instructions executed per second—is on the order of 1000 times faster than the quantum computer’s. From Table 1, we can see that for NS = 16, our proposed quantum algorithm is expected to be faster even if the quantum computer on which it is running has a clock speed a million times slower than the competing classical computer. For NS = 32, our proposed quantum algorithm will, nearly unquestionably, run many orders of magnitude faster than the comparable classical algorithm using an exhaustive search. This gives us a high degree of confidence in our expectation that our proposed quantum algorithm will outperform the classical algorithm for state machines of reasonable size. It is interesting to observe that the quantum algorithm actually con- tains a significant inefficiency in comparison to the classical algorithm. The inefficiency arises from the fact that Grover’s algorithm can only search through a space consisting of all possible binary strings of a given length. Therefore, the quantum algorithm searches through all possible combinations of inputs to the oracle as illustrated in Figure 10(b), even those that do not represent a valid encoding. This means that a large portion of the search space is effectively extraneous, and is excluded by the uniqueness checking circuit from Figure 21. The classical algorithm has no such difficulty as it can simply search through only the set of valid encodings, and is not forced to search through a space of all possible bi- nary strings of a given length, as Grover’s algorithm is. The fact that the quantum algorithm still outperforms the classical algorithm, with a lower run time complexity, shows that this disadvantage is outweighed by the quadratic speedup in searching obtained from using Grover’s algorithm. 43 210 E. TSAI, M. PERKOWSKI A Quantum Algorithm for Automata Encoding 211 7 Conclusion We presented a quantum algorithm for finding an exact solution to the problem of encoding a finite state machine with the lowest cost possible. Specifically, our algorithm finds an optimal encoding for any FSM with numbers of inputs and states that are powers of two, under the assump- tions that the number of state and input variables must be the smallest possible and that the cost of an encoding is given by the total number of variables on which the encoded transition functions resulting from that encoding depend. Our algorithm contains the following notable features: 1. It uses a quantum computer with Grover’s algorithm as a subrou- tine to perform exhaustive searches with lower time complexity than that which is achievable using a classical computer alone, thus mak- ing those exhaustive searches more practical. Little to no published work exists on the subject of applying Grover’s algorithm to directly solve a practically useful problem, and the present work is the first to apply Grover’s algorithm to the problem of finding optimal en- codings, based on the simple metric of dependencies for completely specified finite state machines where both the number of states and the number of input values are a power of 2. 2. It simultaneously optimizes both state and input encodings for an FSM. Currently, [12] is the only other published method that finds exact minimum solutions; however, [12] only solves the problem of state, and not input, encoding. Additionally, the method presented in [12] is specialized for FSMs implemented using PLAs because it minimizes the total number of PLA product terms. In comparison, we use the cruder but more generally applicable cost metric of the total number of variables on which a function depends. 3. It uses Grover’s algorithm to solve an optimization, rather than sat- isfaction, problem. It achieves this by solving a sequence of sat- isfaction problems using Grover’s algorithm; each such satisfaction problem is of the form “find an encoding with cost at most r” where r is a threshold that is varied. By repeatedly executing Grover’s algorithm for different thresholds, where the threshold is varied ac- cording to an appropriate strategy (e.g., a binary search strategy), the algorithm eventually finds the exact minimum possible cost and an encoding with that cost. 4. We introduced the concept of using a quantum counter in tandem with a threshold circuit as part of a quantum oracle. Such oracles check whether the value of a certain function (in this case, our cost function) lies below a given threshold and are exactly what is needed to solve an optimization problem using the procedure described in Section 3.2. The use of quantum counters and threshold circuits in quantum oracles is not limited to solving the FSM encoding prob- lem. It can be applied to many other optimization problems such as MAXSAT, in which the objective is to satisfy as many terms of a Boolean expression as possible. We compared the run time complexity of the proposed quantum al- gorithm against that of the analogous exhaustive search-based classical 44 algorithm. This analysis does not tell us the absolute run times of either algorithm, as calculating such would require much more detailed infor- mation regarding the precise specifications of the quantum and classical computers being used. Nevertheless, the comparison of run time complexi- ties provides strong evidence that the quantum algorithm can significantly outperform the classical algorithm for FSMs of reasonable size that might be encountered in practice. In addition, our work may serve as the basis for further investigation in a number of different directions. We leave these possibilities open to future exploration. Among them, the most promising include: Incompletely specified transition functions—a significant limi- tation of our method is that it requires all encoded transition functions to be completely specified, which means that it is only applicable to FSMs with a number of states that is a power of two. Extending our method for encoded transition functions that are incompletely specified would allow it to apply to all FSMs. Output encodings—in a realistic digital logic design scenario, the outputs of a state machine of course cannot be ignored. We believe that the methods presented here can, without too much difficulty, be extended to the problem of encoding outputs of FSMs as well. Such an extension would represent the first quantum algorithm to solve the FSM encoding problem simultaneously for states, inputs, and outputs. A more detailed cost model—we used a simple cost model which only takes into account the number of dependencies of each encoded tran- sition function on state and input variables. While this simple model pos- sesses the advantage of not being closely tied to a single digital logic im- plementation technology, it is still clearly desirable to extend our method to more realistic cost models that take into account additional factors. Comparison of threshold search strategies—one of the key el- ements of our method is the execution of Grover’s algorithm multiple times with a sequence of quantum oracles generated for different thresh- olds as described in Section 3.2. We did not attempt to compare different strategies for varying the threshold. Such a comparison could significantly improve our algorithm, because the selected strategy affects the expected number of Grover runs needed to find the minimum possible threshold, which in turn affects the run time of our entire algorithm. An analysis of threshold search strategies would also be applicable to problems other than FSM encoding (see also the following paragraph). Application to other problems—as mentioned before, the prin- ciple of solving an optimization problem by running Grover’s algorithm multiple times using a sequence of quantum oracles can be applied to other problems. One such problem, for example, is MAXSAT, where the objective is to maximize the number of simultaneously satisfied clauses in a Boolean formula expressed in conjunctive normal form. Further in- vestigation into this and other such problems would greatly increase the generality of the method presented here. 45 212 E. TSAI, M. PERKOWSKI A Quantum Algorithm for Automata Encoding 213 7 Conclusion We presented a quantum algorithm for finding an exact solution to the problem of encoding a finite state machine with the lowest cost possible. Specifically, our algorithm finds an optimal encoding for any FSM with numbers of inputs and states that are powers of two, under the assump- tions that the number of state and input variables must be the smallest possible and that the cost of an encoding is given by the total number of variables on which the encoded transition functions resulting from that encoding depend. Our algorithm contains the following notable features: 1. It uses a quantum computer with Grover’s algorithm as a subrou- tine to perform exhaustive searches with lower time complexity than that which is achievable using a classical computer alone, thus mak- ing those exhaustive searches more practical. Little to no published work exists on the subject of applying Grover’s algorithm to directly solve a practically useful problem, and the present work is the first to apply Grover’s algorithm to the problem of finding optimal en- codings, based on the simple metric of dependencies for completely specified finite state machines where both the number of states and the number of input values are a power of 2. 2. It simultaneously optimizes both state and input encodings for an FSM. Currently, [12] is the only other published method that finds exact minimum solutions; however, [12] only solves the problem of state, and not input, encoding. Additionally, the method presented in [12] is specialized for FSMs implemented using PLAs because it minimizes the total number of PLA product terms. In comparison, we use the cruder but more generally applicable cost metric of the total number of variables on which a function depends. 3. It uses Grover’s algorithm to solve an optimization, rather than sat- isfaction, problem. It achieves this by solving a sequence of sat- isfaction problems using Grover’s algorithm; each such satisfaction problem is of the form “find an encoding with cost at most r” where r is a threshold that is varied. By repeatedly executing Grover’s algorithm for different thresholds, where the threshold is varied ac- cording to an appropriate strategy (e.g., a binary search strategy), the algorithm eventually finds the exact minimum possible cost and an encoding with that cost. 4. We introduced the concept of using a quantum counter in tandem with a threshold circuit as part of a quantum oracle. Such oracles check whether the value of a certain function (in this case, our cost function) lies below a given threshold and are exactly what is needed to solve an optimization problem using the procedure described in Section 3.2. The use of quantum counters and threshold circuits in quantum oracles is not limited to solving the FSM encoding prob- lem. It can be applied to many other optimization problems such as MAXSAT, in which the objective is to satisfy as many terms of a Boolean expression as possible. We compared the run time complexity of the proposed quantum al- gorithm against that of the analogous exhaustive search-based classical 44 algorithm. This analysis does not tell us the absolute run times of either algorithm, as calculating such would require much more detailed infor- mation regarding the precise specifications of the quantum and classical computers being used. Nevertheless, the comparison of run time complexi- ties provides strong evidence that the quantum algorithm can significantly outperform the classical algorithm for FSMs of reasonable size that might be encountered in practice. In addition, our work may serve as the basis for further investigation in a number of different directions. We leave these possibilities open to future exploration. Among them, the most promising include: Incompletely specified transition functions—a significant limi- tation of our method is that it requires all encoded transition functions to be completely specified, which means that it is only applicable to FSMs with a number of states that is a power of two. Extending our method for encoded transition functions that are incompletely specified would allow it to apply to all FSMs. Output encodings—in a realistic digital logic design scenario, the outputs of a state machine of course cannot be ignored. We believe that the methods presented here can, without too much difficulty, be extended to the problem of encoding outputs of FSMs as well. Such an extension would represent the first quantum algorithm to solve the FSM encoding problem simultaneously for states, inputs, and outputs. A more detailed cost model—we used a simple cost model which only takes into account the number of dependencies of each encoded tran- sition function on state and input variables. While this simple model pos- sesses the advantage of not being closely tied to a single digital logic im- plementation technology, it is still clearly desirable to extend our method to more realistic cost models that take into account additional factors. Comparison of threshold search strategies—one of the key el- ements of our method is the execution of Grover’s algorithm multiple times with a sequence of quantum oracles generated for different thresh- olds as described in Section 3.2. We did not attempt to compare different strategies for varying the threshold. Such a comparison could significantly improve our algorithm, because the selected strategy affects the expected number of Grover runs needed to find the minimum possible threshold, which in turn affects the run time of our entire algorithm. An analysis of threshold search strategies would also be applicable to problems other than FSM encoding (see also the following paragraph). Application to other problems—as mentioned before, the prin- ciple of solving an optimization problem by running Grover’s algorithm multiple times using a sequence of quantum oracles can be applied to other problems. One such problem, for example, is MAXSAT, where the objective is to maximize the number of simultaneously satisfied clauses in a Boolean formula expressed in conjunctive normal form. Further in- vestigation into this and other such problems would greatly increase the generality of the method presented here. 45 212 E. TSAI, M. PERKOWSKI A Quantum Algorithm for Automata Encoding 213 References [1] J. M. Gambetta, J. M. Chow, and M. Steffen, “Building logical qubits in a superconducting quantum computing system,” npj Quantum In- formation, vol. 3, p. 2, Jan. 2017. [2] L. K. Grover, “A fast quantum mechanical algorithm for database search,” in Proceedings of the Twenty-Eighth Annual ACM Sympo- sium on Theory of Computing, pp. 212–219, May 1996. [3] L. K. Grover, “Quantum mechanics helps in searching for a needle in a haystack,” Phys. Rev. Lett., vol. 79, pp. 325–328, Jul 1997. [4] L. K. Grover, “A framework for fast quantum mechanical algo- rithms,” in Proceedings of the Thirtieth Annual ACM Symposium on Theory of Computing, STOC ’98, (New York, NY, USA), pp. 53–62, ACM, 1998. [5] G. Wendin, “Quantum information processing with superconducting circuits: a review,” Reports on Progress in Physics, vol. 80, no. 10, p. 106001, 2017. [6] J. Hartmanis, “On the state assignment problem for sequential ma- chines. I,” IRE Transactions on Electronic Computers, vol. EC-10, pp. 157–165, June 1961. [7] R. E. Stearns and J. Hartmanis, “On the state assignment problem for sequential machines. II,” IRE Transactions on Electronic Com- puters, vol. EC-10, pp. 593–603, Dec. 1961. [8] L. Benini and G. D. Micheli, “State assignment for low power dissi- pation,” IEEE Journal of Solid-State Circuits, vol. 30, pp. 258–268, Mar. 1995. [9] 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. [10] G. D. Micheli, R. K. Brayton, and A. Sangiovanni-Vincentelli, “Op- timal state assignment for finite state machines,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 4, pp. 269–285, July 1985. [11] 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. [12] S. Devadas and A. R. Newton, “Exact algorithms for output encod- ing, state assignment and four-level boolean minimization,” in Sys- tem Sciences, 1990., Proceedings of the Twenty-Third Annual Hawaii International Conference on, vol. 1, pp. 387–396, IEEE, 1990. [13] E. F. Moore, “Gedanken Experiments on Sequential Machines,” in Automata Studies, pp. 129–153, Princeton U., 1956. 46 [14] J. Hartmanis, “Loop-free structure of sequential machines,” Infor- mation and Control, vol. 5, no. 1, pp. 25–43, 1962. [15] G. H. Mealy, “A method for synthesizing sequential circuits,” Bell System Technical Journal, vol. 34, no. 5, pp. 1045–1079, 1955. [16] M. A. Nielsen and I. L. Chuang, Quantum Computation and Quan- tum Information. Cambridge University Press, 10th anniversary ed., 2010. [17] 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. [18] G. Brassard, P. Høyer, and A. Tapp, “Quantum counting,” in Au- tomata, Languages and Programming, pp. 820–831, Springer Berlin Heidelberg, 1998. [19] D. Maslov and G. Dueck, “Improved quantum cost for n-bit toffoli gates,” Electronics Letters, vol. 39, pp. 1790–1791, December 2003. [20] 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. 47 214 E. TSAI, M. PERKOWSKI A Quantum Algorithm for Automata Encoding 215 References [1] J. M. Gambetta, J. M. Chow, and M. Steffen, “Building logical qubits in a superconducting quantum computing system,” npj Quantum In- formation, vol. 3, p. 2, Jan. 2017. [2] L. K. Grover, “A fast quantum mechanical algorithm for database search,” in Proceedings of the Twenty-Eighth Annual ACM Sympo- sium on Theory of Computing, pp. 212–219, May 1996. [3] L. K. Grover, “Quantum mechanics helps in searching for a needle in a haystack,” Phys. Rev. Lett., vol. 79, pp. 325–328, Jul 1997. [4] L. K. Grover, “A framework for fast quantum mechanical algo- rithms,” in Proceedings of the Thirtieth Annual ACM Symposium on Theory of Computing, STOC ’98, (New York, NY, USA), pp. 53–62, ACM, 1998. [5] G. Wendin, “Quantum information processing with superconducting circuits: a review,” Reports on Progress in Physics, vol. 80, no. 10, p. 106001, 2017. [6] J. Hartmanis, “On the state assignment problem for sequential ma- chines. I,” IRE Transactions on Electronic Computers, vol. EC-10, pp. 157–165, June 1961. [7] R. E. Stearns and J. Hartmanis, “On the state assignment problem for sequential machines. II,” IRE Transactions on Electronic Com- puters, vol. EC-10, pp. 593–603, Dec. 1961. [8] L. Benini and G. D. Micheli, “State assignment for low power dissi- pation,” IEEE Journal of Solid-State Circuits, vol. 30, pp. 258–268, Mar. 1995. [9] 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. [10] G. D. Micheli, R. K. Brayton, and A. Sangiovanni-Vincentelli, “Op- timal state assignment for finite state machines,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 4, pp. 269–285, July 1985. [11] 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. [12] S. Devadas and A. R. Newton, “Exact algorithms for output encod- ing, state assignment and four-level boolean minimization,” in Sys- tem Sciences, 1990., Proceedings of the Twenty-Third Annual Hawaii International Conference on, vol. 1, pp. 387–396, IEEE, 1990. [13] E. F. Moore, “Gedanken Experiments on Sequential Machines,” in Automata Studies, pp. 129–153, Princeton U., 1956. 46 [14] J. Hartmanis, “Loop-free structure of sequential machines,” Infor- mation and Control, vol. 5, no. 1, pp. 25–43, 1962. [15] G. H. Mealy, “A method for synthesizing sequential circuits,” Bell System Technical Journal, vol. 34, no. 5, pp. 1045–1079, 1955. [16] M. A. Nielsen and I. L. Chuang, Quantum Computation and Quan- tum Information. Cambridge University Press, 10th anniversary ed., 2010. [17] 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. [18] G. Brassard, P. Høyer, and A. Tapp, “Quantum counting,” in Au- tomata, Languages and Programming, pp. 820–831, Springer Berlin Heidelberg, 1998. [19] D. Maslov and G. Dueck, “Improved quantum cost for n-bit toffoli gates,” Electronics Letters, vol. 39, pp. 1790–1791, December 2003. [20] 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. 47 214 E. TSAI, M. PERKOWSKI A Quantum Algorithm for Automata Encoding 215