arXiv:2304.09745

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

Sergey Victorovich Ulyanov, V.S. Ulyanov

Published Apr 17, 2023• 0 citations

Abstract

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.

DOI: 10.48550/arxiv.2304.09745

Related papers

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

Сергей Викторович Ульянов, 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

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

Fast quantum search algorithm and Bounds on it

Arun Kumar Pati

We recast Grover's generalised search algorithm in a geometric language even when the states are not approximately orthogonal. We provide a possible search algorithm based on an arbitrary unitary transformation which can speed up the steps still further. We discuss the lower and upper bounds on the transition matrix elements when the unitary operator changes with time, thereby implying that quantum search process can not be too fast or too slow. This is a remarkable feature of quantum computation unlike classical one. Quantum mechanical uncertainty relation puts bounds on search process. Also we mention the problems of perturbation and other issues in time-dependent search operation.

arXiv:quant-ph/9807067Jul 24, 19988 citations

Analysis and Simulation of Grover’s Search Algorithm

Jiayu Zhuang, Junsuo Zhao, Fanjiang Xu +2 more

A quantum computation problem of quantum search is discussed in this paper.Grover's search algorithm, the most commonly used quantum search algorithm, is introduced in details.The flow of quantum search algorithm and the quantum circuit model are shown.And the error of the search value, as well as the probability of measurement, is analyzed.For further research we simulated the Grover's search algorithm in classical computer.By quantum simulator the probability distribution of the measuring result of search value is presented and the computational efficiency is discussed.The simulation result demonstrates the effectiveness of the proposed algorithm.

International Journal of Machine Learning and ComputingFeb 1, 20145 citations

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

Sergey Victorovich Ulyanov, Sergey Victorovich 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. 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.

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

Quantum Search in Hilbert Space

Michail A. Zak

A proposed quantum-computing algorithm would perform a search for an item of information in a database stored in a Hilbert-space memory structure. The algorithm is intended to make it possible to search relatively quickly through a large database under conditions in which available computing resources would otherwise be considered inadequate to perform such a task. The algorithm would apply, more specifically, to a relational database in which information would be stored in a set of N complex orthonormal vectors, each of N dimensions (where N can be exponentially large). Each vector would constitute one row of a unitary matrix, from which one would derive the Hamiltonian operator (and hence the evolutionary operator) of a quantum system. In other words, all the stored information would be mapped onto a unitary operator acting on a quantum state that would represent the item of information to be retrieved. Then one could exploit quantum parallelism: one could pose all search queries simultaneously by performing a quantum measurement on the system. In so doing, one would effectively solve the search problem in one computational step. One could exploit the direct- and inner-product decomposability of the unitary matrix to make the dimensionality of the memory space exponentially large by use of only linear resources. However, inasmuch as the necessary preprocessing (the mapping of the stored information into a Hilbert space) could be exponentially expensive, the proposed algorithm would likely be most beneficial in applications in which the resources available for preprocessing were much greater than those available for searching.

Jan 1, 20030 citations