Международный журнал Программные продукты и системы

Квантовые вычисления на основе алгоритмических вентилей: проектирование алгоритма квантового поиска Гровера в квантовой программной инженерии

Sergey Victorovich Ulyanov, Sergey Victorovich Ulyanov

Published Dec 13, 2023• 0 citations

Abstract

The difference between classical and quantum algorithms (QA) is following: problem solved by QA is coded in the structure of the quantum operators.Input to QA in this case is always the same.Output of QA says which problem coded.In some sense, give a function to QA to analyze and QA returns its property as an answer without quantitative computing.QA studies qualitative properties of the functions.The core of any QA is a set of unitary quantum operators or quantum gates.In practical representation, quantum gate is a unitary matrix with particular structure.The size of this matrix grows exponentially with an increase in the number of inputs, which significantly limits the QA simulation on a classical computer with von Neumann architecture.Quantum search algorithm (QSA)models apply for the solution of computer science problems as searching in unstructured data base, quantum cryptography, engineering tasks, control system design, robotics, smart controllers, etc. Grover's algorithm is explained in details along with implementations on a local computer simulator.The presented article describes a practical approach to modeling one of the most famous QA on classical computers, the Grover algorithm.

DOI: 10.15827/0236-235x.144.523-538

Related papers

Quantum Algorithmic Gate-Based Computing: Grover Quantum Search Algorithm Design in Quantum Software Engineering

Sergey Victorovich Ulyanov, V.S. Ulyanov

The difference between classical and quantum algorithms (QA) is following: problem solved by QA is coded in the structure of the quantum operators. Input to QA in this case is always the same. Output of QA says which problem coded. In some sense, give a function to QA to analyze and QA returns its property as an answer without quantitative computing. QA studies qualitative properties of the functions. The core of any QA is a set of unitary quantum operators or quantum gates. In practical representation, quantum gate is a unitary matrix with particular structure. The size of this matrix grows exponentially with an increase in the number of inputs, which significantly limits the QA simulation on a classical computer with von Neumann architecture. Quantum search algorithm (QSA) - models apply for the solution of computer science problems as searching in unstructured data base, quantum cryptography, engineering tasks, control system design, robotics, smart controllers, etc. Grovers algorithm is explained in details along with implementations on a local computer simulator. The presented article describes a practical approach to modeling one of the most famous QA on classical computers, the Grover algorithm.

arXiv:2304.13703Apr 20, 20232 citations

Моделирование быстрого алгоритма квантового поиска на классических компьютерах: информационный анализ проблемы останова

Сергей Викторович Ульянов, S.V. Ulyanov, В.С. Ульянов +1 more

The paper describes the simplest technique for simulating a quantum algorithm based on the direct matrix representation of quantum operators.This approach is stable and precise, but it requires allocation of operator's matrices in the computer memory.Since the size of the operators grows exponentially, this approach is useful for simulating quantum algorithms with a relatively small number of qubits (e.g., approximately 11 qubits on a typical desktop computer).This approach enables relatively simple simulation of the operation of the solution quality control system and performance of a reliability analysis.A more efficient fast quality control simulation method is based on computing all or a part of operator matrices as needed on a current computational basis.This method makes it possible to avoid storing all or a part of the operator matrices.In this case, the number of qubits to be simulated (e.g., the number of input qubits or the number of qubits in the system state register) is affected by: (I) the exponential growth in the number of operations required to calculate the result of matrix products; and (II) the size of the state vector allocated in computer memory.It is reasonable if one embodiment of this approach involves simulating up to 19 or more qubits on typical desktop computer, and even more in a system with a vector architecture.Due to particularities of the memory addressing and access processes in a typical desktop computer (such as, for example, a Pentium PC), when a number of qubits is relatively small, the on-demand computing tends to be faster than the direct storage approach.The compute-on-demand approach benefits from applying the results of studying quantum operators and their structure that enables computing the matrix elements more efficiently.The paper considers effective simulation of Grover's quantum search algorithm using a computer with classical architecture.

Международный журнал Программные продукты и системыAug 28, 20232 citations

Программный эмулятор квантовых алгоритмов для эффективного моделирования на персональном компьютере

Sergey Victorovich Ulyanov, Sergey Victorovich Ulyanov

A quantum software engineering platform includes quantum computing methods, a quantum algorithm theory and quantum programming.These areas develop according to a technological structure of nanotechnology development for hardware design of various configurations.In about 10 to 30 years we expect the appearing of an industrial quantum computer for real software engineering; this fact is due to overcoming a number of technological difficulties in implementing hardware, as well as the fundamental difficulty of eliminating decoherence physical phenomenon and correcting errors in quantum computers in near future.A key question in quantum computing is searching for quantum algorithms that potentially have a significant advantage and supremacy over classical algorithms for problems of practical interest.Therefore, currently, an approach is being developed to create quantum algorithm structures for quantum simulators with the possibility of effective implementation on classical architecture computers.This paper proposes an effective modelling method with information analysis of quantum search and decision-making algorithm structures in order to eliminate redundancy in practical implementation of a simulator on a classical structure computer.As an example, we demonstrate the method of modeling Grover's quantum search algorithm with stopping the search for a good solution based on the Shannon information entropy minimum principle.There are modeling examples to demonstrate the effectiveness of the developed approach in quantum software engineering and intelligent control robotics.

Международный журнал Программные продукты и системыMar 16, 20240 citations

Modelling of Grover’s quantum search algorithms: implementations of Simple quantum simulators on classical computers

Sergey Victorovich Ulyanov, Andrey G. Reshetnikov, Olga Tyatyushkina

Models of Grover’s search algorithm is reviewed to build the foundation for the other algorithms. Thereafter, some preliminary modifications of the original algorithms by others are stated, that increases the applicability of the search procedure. A general quantum computation on an isolated system can be represented by a unitary matrix. In order to execute such a computation on a quantum computer, it is common to decompose the unitary into a quantum circuit, i.e., a sequence of quantum gates that can be physically implemented on a given architecture. There are different universal gate sets for quantum computation. Here we choose the universal gate set consisting of CNOT and single-qubit gates. We measure the cost of a circuit by the number of CNOT gates as they are usually more difficult to implement than single qubit gates and since the number of single-qubit gates is bounded by about twice the number of CNOT’s.

System Analysis in Science and EducationSep 30, 20204 citations

Mathlab Implementation of Quantum Computation in Searching an Unstructured Database

Iyabo Olukemi Awoyelu, P. Okoh

In the classical model of a computer, the most fundamental building block, the bit, can only exist in one of two distinct states, a 0 or a 1. Computations are carried out by logic gates that act on these bits to produce other bits. Unless there is duplicate (parallel) hardware, only one problem instance (i.e. input data set) can be handled at a time. In this classical computing, increasing the number of bits increases the complexity of the problem and the time necessary to arrive at a solution. A quantum algorithm consists of a sequence of operations on a register, to transform it into a state which, when measured, yields the desired result with high probability. An n-bit quantum register can store an exponential amount of information. This paper aims at taking advantage of the superiority of quantum computing over classical computing to solve the problem of searching unstructured databases for a particular item or more than one item in good time. The general aim of this work is to establish the correctness and optimality of Grover’s quantum database search algorithm compared against classical database search methods in order to investigate the superiority or otherwise of quantum computing over classical computing. This is followed by a simulation of the algorithm using a classical computer, namely through functions that are present in MATLAB, referred to as “Quantum Computing Functions”. Povzetek: Clanek predstavlja implementacijo kvantnega iskanja v nestrukturiranih bazah.

Jan 1, 20120 citations

Fast quantum search algorithm modelling on conventional computers: Information analysis of termination problem

Sergey Victorovich Ulyanov, V.S. Ulyanov

The simplest technique for simulating a quantum algorithm - QA described based on the direct matrix representation of the quantum operators. Using this approach, it is relatively simple to simulate the operation of a QA and to perform fidelity analysis. A more efficient fast QA simulation technique is based on computing all or part of the operator matrices on an as needed current computational basis. Using this technique, it is possible to avoid storing all or part of the operator matrices. The compute on demand approach benefits from a study of the quantum operators, and their structure so that the matrix elements can be computed more efficiently. Effective simulation of Grover quantum search algorithm as example on computer with classical architecture is considered.

arXiv:2304.09745Apr 17, 20230 citations