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.
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 observe an enormous increase in the computational power of digital computers. This was due to the revolution in manufacturing processes and controlling semiconductor structures on submicron scale, ultimately leading to the control of individual atoms. Eventually, the classical electric circuits encountered the barrier of quantum mechanics and its effects. However, the laws of quantum mechanics can be also used to produce computational devices that lead to extraordinary speed increases over classical computers. Thus quantum computing becomes a very promising and attractive research area. The Computer Aided Design for Quantum circuits becomes an essential ingredient for such emerging research which may lead to these powerful computers to be realized—an era of Quantum computing. This thesis presents an integrated theoretical study of software algorithms to design circuits of quantum oracles as well as methods for designing quantum oracles for Grover algorithm to solve combinatorial problems. An implementation of quantum algorithm involves the initialization of the input state and its manipulation with quantum gates followed by the measurements. In Grover algorithm the problem to be solved is specified by a permutative logic oracle – the fundamental problem is then how to build this oracle from quantum logic circuits and how to optimize these circuits. These problems are NP-hard and require search algorithms. In future, the search will be also done in quantum and this thesis leads to quantum algorithms to design quantum circuits more efficiently.
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.
Abstract In the coding theory, it is one of the most important research problems to find an efficient algorithm for the decoding process. A quantum computer is an innovative computing device that performs calculations using the principles of quantum mechanics. In this paper, we find a decoding algorithm for binary linear codes using quantum circuits; this is the first time that quantum circuits are used as a main tool for decoding binary linear codes. Our decoding algorithm is mainly based on Grover’s search algorithm. In detail, we study the process of implementing the exhaustive search using quantum circuits for decoding binary linear codes. For our purpose, we design a modified Grover’s algorithm (algorithm 1) using three tools: the matrix multiplier, the Hamming weight counter, and the state indicator. We present algorithm 2, which is a quantum decoding algorithm for binary linear codes. We illustrate algorithm 1 using the [7, 4, 3] Hamming code, and algorithm 2 is implemented by IBM Quantum Composer.
Quantum search is one of the most important algorithmic developments in quantum computing because it demonstrates how quantum principles can improve the efficiency of solving unstructured search problems. Grover’s algorithm provides a quadratic speed-up over classical linear search by reducing query complexity from O(N) to O(√N), where N represents the size of the search space. This review examines the principles, performance, and applications of Grover’s algorithm, with emphasis on its theoretical foundation and practical relevance. The discussion covers the roles of superposition, quantum interference, oracle operations, diffusion operators, and amplitude amplification in increasing the probability of measuring a desired solution. The manuscript also reviews the computational performance of quantum search in comparison with classical search methods and considers its relevance to database searching, combinatorial optimisation, cryptography, machine learning, bioinformatics, quantum chemistry, and materials science. The review highlights that Grover’s algorithm is not limited to database retrieval, as many computationally intensive problems can be reformulated as search or optimisation tasks. However, practical implementation remains constrained by current quantum hardware limitations, including decoherence, quantum noise, limited qubit availability, circuit depth, and the difficulty of designing efficient oracles. Despite these challenges, continuing progress in quantum hardware, error correction, cloud-based quantum platforms, and hybrid quantum-classical architectures suggests that quantum search will remain an important area of research. Overall, Grover’s algorithm represents a foundational quantum algorithm with significant theoretical value and potential long-term application in computational domains involving large and unstructured search spaces.
We introduce an quantum-classical hybrid algorithm, named automatic quantum circuit encoding (AQCE), that is designed to encode an arbitrary quantum state | Ψ 〉 onto an optimal quantum circuit C ̂ composed of a finite set of single- and two-qubit quantum gates. The algorithm employs an objective function based on the absolute value of fidelity, F = 〈 0 | C ̂ † | Ψ 〉 , which is iteratively maximized to construct an optimal quantum circuit C ̂ with controlled accuracy. Here, | 0 〉 denotes a trivial product state in the computational basis of a quantum computer. The core of this algorithm lies in the sequential determination of an optimal set of two-qubit unitary operators, identified one by one through the singular value decomposition of the fidelity tensor. Once an optimal set of operators is determined, including the location of qubits on which each operator acts, elementary quantum gates are assigned algebraically to these two-qubit unitary operators. Importantly, these procedures are deterministic without assuming any quantum circuit ansatz and therefore eliminate the need for parameter optimization of parametrized quantum gates. Through noiseless numerical simulations, we demonstrate the effectiveness of the AQCE algorithm in encoding ground states of quantum many-body systems, including the spin-1/2 antiferromagnetic Heisenberg model and the spin-1/2 X Y model. We also compare these results with quantum circuit encoding employing predefined circuit structures such as Trotter-like and MERA-like circuit ansatze. Furthermore, our algorithm extends to classical data, for instance, classical images represented as quantum states using amplitude encoding. The adaptability enables us to adjust the quantum resource requirement, i.e., the number of qubits, by partitioning classical data into multiple distinct segments. This feature holds potential for near-term applications in quantum machine learning, such as a state preparation of classical data for an input quantum state to be processed. Finally, using a real quantum device provided by IBM Quantum, we experimentally validate that a quantum circuit generated by the AQCE algorithm can indeed reasonably represent the original quantum state. Published by the American Physical Society 2024
The K-SAT problem is a fundamental challenge in computational theory, widely used in artificial intelligence, cryptography, and optimization. Classical algorithms struggle with exponential time complexity, making them inefficient for large-scale instances. In this research, we propose an efficient quantum computing approach based on Grover’s algorithm to enhance the search process for satisfiable solutions in K-SAT problems. Our implementation leverages quantum superposition and amplitude amplification to explore multiple possible solutions simultaneously, reducing the search complexity from O (2ⁿ) in classical methods to O(√2ⁿ) in quantum computing. We design a quantum oracle that encodes the K-SAT clauses and integrates it into Grover’s iterative search framework. The performance is evaluated through Qiskit simulations, demonstrating a significant improvement in search efficiency compared to classical brute-force techniques. The results highlight the potential of quantum algorithms in solving complex combinatorial problems with enhanced speed and accuracy. This study contributes to the development of quantum-accelerated optimization methods, paving the way for real-world applications in machine learning, cryptanalysis, and large-scale data processing.