![]() ![]() The current DFA accepts only binary numbers that are multiples of 2. Upon reading a symbol (0 or 1), the DFA will jump deterministically from one state to another following the transition arrow. ![]() ![]() For each state, there is a transition arrow leading out to a next state for both 0 and 1. S 0 and S 1 are the two possible states of the DFA, where S 0 is both the start state and the accepted state. State diagrams of deterministic finite automata (DFAs) and quantum finite automata (QFAs). For example, determining whether a binary number is even or not is a typical decision problem, which can be solved by the DFA shown in Fig. DFAs are often used to solve (recognize) decision problems, which are defined as computational problems where the answer for every instance is either Yes or No. If the automaton ends at an accepted state after reading the last symbol of the input string, this string of symbols is regarded as being accepted by the DFA otherwise, it is regarded as being rejected by the DFA. A DFA has a start state (denoted graphically by an arrow coming in from nowhere) where computations begin, and a set of accepted states (denoted graphically by a double circle). For example, if the automaton is currently in state S 0 and the current input symbol is 1, then it deterministically jumps to state S 1. Upon reading a symbol, a DFA jumps deterministically from one state to another by following the transition arrow. The automaton takes a finite sequence of 0 s and 1 s as input. In this example automaton, there are two states S 0 and S 1, which are denoted graphically by circles. 1a, a typical DFA is illustrated with a state diagram. We only consider the case of DFAs as it has been proven that DFAs have equivalent computing power to non-deterministic finite automata. Here deterministic refers to the fact that a DFA only produces a unique computation for each input string. At last, we will present our experimental demonstration of an optical QFA solving a promise problem.Ī deterministic finite automaton (DFA) is a finite-state machine that accepts or rejects input strings of symbols. Then we will explain how to use a QFA to solve a certain promise problem. We will first introduce some background knowledge about FA and QFA. In our experiment, we have proven that a QFA composed with a three-dimensional quantum state suffice to solve a promise problem whereas a classical FA needs much larger state space to solve the same problem. In this letter, we have built a proof-of-principle optical QFA that can solve some certain problems more space-efficiently than a classical FA. 21, 22 However, to the best of our knowledge, no experiment has been performed to prove the quantum benefits of QFA yet. 20 It has been theoretically predicted that QFA can solve certain problems more efficiently than its classical counterpart. 17, 18 The concept of quantum finite automaton (QFA) was invented as the quantum version of FA by Kondacs and Watrous 19 and also by Moore and Crutchfield. As one of the most fundamental models in computer science, FA can be used to model problems in many fields, including mathematics, artificial intelligence, games or linguistics. Finite automaton (FA) is another good example. 12, 13, 14, 15, 16Ĭomputer is not the only device whose capability can be boosted by introducing quantum elements. 5, 6, 7, 8, 9, 10, 11 A series of quantum algorithms have been demonstrated on these prototype machines to show the quantum benefits in tackling particular problems. 2, 3, 4 Extensive efforts have been made to build such computing machine and small-scale quantum computers have already been constructed in different physical systems. The most prominent example is quantum computer-by changing the basic elements of a computer from bits and logic gates to quantum bits and quantum logic gates, quantum computer can achieve an exponential speedup in solving certain problems, including factoring 1 and simulation of complex systems. Quantum information science is a research field focused on enhancing problem-solving efficiency by utilizing quantum effects. ![]()
0 Comments
Leave a Reply. |