The design of state machines for quantum algorithms remains a largely unexplored topic. The abstract models for quantum computation proposed by Feynman [1], Deutsch [2] etc have been related to the theory of Quantum Turing Machines (QTM) and the work was later expanded by Bernstein and Vazirani [3] to lay the foundations of quantum complexity theory. However, no papers deal with the following problem: “how to realize the quantum state machine in hardware as an operational quantum circuit that the internal states of which can be measured and used as inputs in a system of such machines”. This is an equivalent to the fundamental problem of “structural synthesis of FSM”. This paper creates models of quantum state machines that are useful from an engineering perspective. The objective of the paper is to propose models that can be used for circuit-level implementation. We restrict our study to binary logic realized in quantum, the so-called binary permutative quantum circuits; the “permutative machines”. The presented synthesis procedure is analogous to classical logic circuits synthesis and is a necessary step in the entire design procedure of quantum automata. Thus state minimization, state assignment and excitation function realization aspects are also of interest and some preliminary experimental results are presented.
The design of state machines for quantum algorithms remains a largely unexplored topic. The abstract models for quantum computation proposed by Feynman [1], Deutsch [2] etc have been related to the theory of Quantum Turing Machines (QTM) and the work was later expanded by Bernstein and Vazirani [3] to lay the foundations of quantum complexity theory. However, no papers deal with the following problem: “how to realize the quantum state machine in hardware as an operational quantum circuit that the internal states of which can be measured and used as inputs in a system of such machines”. This is an equivalent to the fundamental problem of “structural synthesis of FSM”. This paper creates models of quantum state machines that are useful from an engineering perspective. The objective of the paper is to propose models that can be used for circuit-level implementation. We restrict our study to binary logic realized in quantum, the so-called binary permutative quantum circuits; the “permutative machines”. The presented synthesis procedure is analogous to classical logic circuits synthesis and is a necessary step in the entire design procedure of quantum automata. Thus state minimization, state assignment and excitation function realization aspects are also of interest and some preliminary experimental results are presented.
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.
We want in this article to show the usefulness of Quantum Turing Machine (QTM) in a high-level didactic context as well as in theoretical studies. We use QTM to show its equivalence with quantum circuit model for Deutsch and Deutsch-Jozsa algorithms. Further we introduce a strategy of translation from Quantum Circuit to Quantum Turing models by these examples. Moreover we illustrate some features of Quantum Computing such as superposition from a QTM point of view and starting with few simple examples very known in Quantum Circuit form.
Abstract In classical logic design, there are machine learning methods based on converting a set of input-output traces to non-deterministic automata that are then converted to deterministic automata and synthesized using logic gates. This approach has not yet been extended to quantum automata. In this paper, we present a method to convert a set of input-output traces to a non-deterministic automaton, which is then converted to an incompletely specified multi-output Boolean function. The existing logic synthesis approaches for designing quantum circuits are insufficient to handle incompletely specified functions. So, we present a novel algorithm to synthesize logic functions with don’t cares using permutative quantum gates. The original MMD (D.M.Miller, D. Maslov, and G.W.Dueck) algorithm minimizes only completely specified reversible functions using cascades of reversible gates. In this paper, this algorithm is modified to allow for the inclusion of don’t cares within the given function’s truth table (reversible or irreversible). The distinguishing property of our presented algorithm QAS, is that it does not add any ancilla qubits if it is not necessary. This algorithm solves the problem of synthesizing deterministic and non-deterministic quantum state machines, both completely specified and incompletely specified.
Very few papers have been written on the topic of a quantum version of the finite state machine, (or finite state automata). Furthermore, these papers only serve to define what a quantum finite state machine might be in the mathematical sense using the early languages of Turing machines. This paper seeks to further develop the notion of a quantum finite state machine (FSM) using constructs developed for the classical FSM and utilized for classical FSM design. In particular the quantum state transition diagram (QSTD) is constructed to further the understanding and realization of quantum finite state machines and quantum computers.
We present a model of Quantum Finite State Machines (QFSM) based on the quantum circuit representation. In this model, properties of quantum bits are exploited in order to implement Quantum Finite State Machines without an explicit external memory. We show that because of the the natural ability of quantum systems to retain the quantum state, quantum circuits can be directly used to implement some classes of the quantum finite state machines. In particular, the circuit model allows to remove the logic-memory distinction as it is used in the classically established model of finite state machines. Rather, the quantum register implementing the QFSM as a circuit is alternatively used as memory and as logic. In order to allow such behavior the quantum circuit (processor) is controlled by a classical circuit that provides the necessary timing of the quantum operations as well as the interface between the quantum and the classical world. Moreover, additional mechanism for preserving unknown quantum qubit state is used and a novel computational protocol allowing the implementation of the QFSM is proposed. This framework is is called the Classically Controlled Quantum Computer (CCQC). The CCQC thus combines a quantum processor with a classical controller in such manner that computation is carried from the classical inputs, through quantum processing to classical outputs. We discuss a high level synthesis approach to quantum sequence detection based on the synthesis of quantum sequential circuits. Such machines can find many applications for instance in robotics; for example a robot is required to recognize certain sequences of input sensor values.
Contrary to the classical case, the relation between quantum programming languages and quantum Turing Machines (QTM) has not been fully investigated. In particular, there are features of QTMs that have not been exploited, a notable example being the intrinsic infinite nature of any quantum computation. In this paper, we propose a definition of QTM, which extends and unifies the notions of Deutsch and Bernstein & Vazirani. In particular, we allow both arbitrary quantum input, and meaningful superpositions of computations, where some of them are “terminated” with an “output”, while others are not. For some infinite computations an “output” is obtained as a limit of finite portions of the computation. We propose a natural and robust observation protocol for our QTMs, which does not modify the probability of the possible outcomes of the machines. Finally, we use QTMs to define a class of quantum computable functions—any such function is a mapping from a general quantum state to a probability distribution of natural numbers. We expect that our class of functions, when restricted to classical input-output, will not be different from the set of the recursive functions.