On Some Aspects of Quantum Computational Models

Abstract

Quantum computing is concerned with computer technology based on the principles of quantum mechanics, in which operations are performed at the quantum level. Quantum computational models make it possible to analyze the resources required for computations. Quantum automata can be classified thusly: quantum finite automata, quantum sequential machine, quantum pushdown automata, quantum Turing machine, and orthomodular lattice-valued automata. These models are useful for determining the expressive power and boundaries of various computational features. In many cases, quantum models are more superior to classical models in terms of language recognition. Thus, mathematical models of quantum computation can be view as generalizations of its physical models. Motivated from the above-mentioned facts, we proposed a variant of two-way quantum finite automata named two-way multihead quantum finite automata and determined its language recognition capability. Moreover, we have proposed a quantum analogue of classical queue automata by using the definition of the quantum Turing machine and quantum finite-state automata. Further, we have also introduced a generalization of real-time deterministic queue automata, the real-time quantum queue automata which work in real-time i.e., the input head can move towards the right direction only and takes precisely one step per input symbol. We have proved that real-time quantum queue automaton is more superior than its real-time classical variants by using quantum transitions. Classical systems are not robust and capable of describing quantum systems. Some tasks that are impossible in classical systems can be realized in quantum systems. The most significant property ‘entanglement’ separates the classical world from the quantum world. It is one of the most central topics in quantum information theory. In fact, quantum many-body systems cannot be simulated by classical systems because of the increase in size of Hilbert space. In this Thesis, we have efficiently simulated well-known examples of matrix product state and designed their quantum finite-state machines (QFSMs) using unitary criteria. Furthermore, the proposed unitary criterion is used to analyze the dynamic behavior of matrix product states with quantum weightless neural networks. The relationship between the theory of automata and logic had a great influence on computer science. Linear temporal logic is a widely used method for verification of model checking and expressing the system specifications. We have investigated the relationship between quantum finite automata and linear temporal logic. It has a variable free compact syntax, intuitive semantics, and it can be transformed into automata more efficiently. Further, we have characterized the class of languages accepted by quantum finite automata using linear temporal logic formulas. In the past few years, the research has been focused on applying assets of quantum computing in various areas such as quantum cryptography, quantum machine learning, quantum neural computation, tensor network theory, quantum dynamics to study behavior of biological sequences, weather forecasting, quantum optics, quantum chemistry as well as others. We have modeled various ribonucleic acid (RNA) secondary structure loops such as hairpin loop, internal loop, and double helix using two-way quantum finite automata. It has been proved that two-way quantum finite automata can be designed for such structure loops in linear time with bounded error. Next, we have explored and examined the implications of the most successful McEliece cryptosystem in post-quantum cryptography. The proposed cryptosystem is based on extended Golay code in place of the usual Goppa code. Furthermore, we have implemented a McEliece cryptosystem based on extended Golay code using MATLAB. In recent years, quantum computation is receiving much attention for its capability to solve difficult problems efficiently contrast to classical computers. Specifically, some well-known public-key cryptosystems depend on the difficulty of factoring of large numbers takes a long time. Furthermore, a quantum variant of classical factorization algorithm named Quadratic Sieve has been designed and its simulation framework using high-level programming language Mathematica is constructed. Further, its simulation results are examined on a classical computer to get a feel of the quantum system.