Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Cybernetics and Computer Technologies

Models of Computer Calculations

V. K. Zadiraka, Олександр Миколайович Хіміч, Інна Віталіївна Швідченко

Published Sep 30, 2022• 5 citations
Publisher

Abstract

Introduction. The complexity of computational algorithms for solving typical problems of computational, applied, and discrete mathematics is analyzed from the perspective of the theory of computation, depending on the computer architecture and the used computing model: single-processor, multiprocessor, and quantum. The following classes of problems are considered: systems of linear algebraic equations, the Cauchy problem for systems of ordinary differential equations, numerical integration, boundary value problems for ordinary differential equations, factorization of numbers, finding the discrete logarithm of a number in multiplicative integer groups, searching for the necessary record in an unordered database, etc. The purposes of the paper are: 1. To investigate how the computational complexity depends on the computer architecture and the computational model. 2. To show that the construction of the computational process under the given conditions of calculations is related to the solution of the following problems: – the existence ε-solution to the problem; – the existence of T-effective computing algorithms; – the possibility of building a real computing process under the given computing conditions. 3. To investigate the effect of rounding numbers on computational complexity (especially when solving problems of transcomputational complexity). 4. To give the complexity estimates and total error of the computational algorithm for a number of typical problems of computational, applied, and discrete mathematics. The results. The complexity estimates of computational algorithms of the listed classes of problems for single-processor, multiprocessor and quantum computing models are given. The main focus is on high-performance computing: using the principles of parallel data processing and quantum mechanics. Conclusions. The connection of complexity estimates of computational algorithms with the architecture of computers and models of calculations is demonstrated. The characteristics of the first quantum computers (2016 – 2022), which have gone beyond laboratory research, are given. Keywords: computer technologies, rounding error, sequential, parallel and quantum computing models, complexity estimate.

DOI
10.34229/2707-451x.22.2.4

Related papers

Introduction and Background

Phillip Kaye, Raymond Laflamme, Michele Mosca

A computer is a physical device that helps us process information by executing algorithms. An algorithm is a well-defined procedure, with finite description, for realizing an information-processing task. An information-processing task can always be translated into a physical task. When designing complex algorithms and protocols for various information-processing tasks, it is very helpful, perhaps essential, to work with some idealized computing model. However, when studying the true limitations of a computing device, especially for some practical reason, it is important not to forget the relationship between computing and physics. Real computing devices are embodied in a larger and often richer physical reality than is represented by the idealized computing model. Quantum information processing is the result of using the physical reality that quantum theory tells us about for the purposes of performing tasks that were previously thought impossible or infeasible. Devices that perform quantum information processing are known as quantum computers. In this book we examine how quantum computers can be used to solve certain problems more efficiently than can be done with classical computers, and also how this can be done reliably even when there is a possibility for errors to occur. In this first chapter we present some fundamental notions of computation theory and quantum physics that will form the basis for much of what follows. After this brief introduction, we will review the necessary tools from linear algebra in Chapter 2, and detail the framework of quantum mechanics, as relevant to our model of quantum computation, in Chapter 3. In the remainder of the book we examine quantum teleportation, quantum algorithms and quantum error correction in detail. We are often interested in the amount of resources used by a computer to solve a problem, and we refer to this as the complexity of the computation. An important resource for a computer is time. Another resource is space, which refers to the amount of memory used by the computer in performing the computation. We measure the amount of a resource used in a computation for solving a given problem as a function of the length of the input of an instance of that problem.

Oxford University Press eBooks•Nov 16, 2006•0 citations

Analysis of mathematical models of quantum parallelism

Petro A. Kravets

This article analyzes mathematical models of quantum parallelism based on the transfer of a quantum system into a superposition state. The principles of quantum parallelism and its mathematical foundations are substantiated. To demonstrate the quantum advantage, mathematical models of fundamental quantum algorithms Deutsch-Joža and Grover are analyzed, which illustrate the efficiency of quantum computing compared to classical methods. The Deutsch-Joshy algorithm is considered, which generalizes the problem of determining the type of a binary function by extending it to a set of arguments written in a quantum register. This algorithm allows determining whether a function is constant or balanced in a single quantum call, while in classical calculations this requires exponential time. It is noted that although the Deutsch-Joshy algorithm demonstrates the possibilities of parallel quantum computing, it is of mainly theoretical importance. Grover’s algorithm implements quantum parallel computing for the practical problem of searching for an element in an unordered database. It is based on iterative amplification of the amplitude of the state corresponding to the searched element and provides quadratic speedup compared to classical algorithms. In addition to database search, Grover’s algorithm can be adapted to solve other optimization problems. The work of the considered algorithms is illustrated by numerical examples, which simplifies the understanding of their principles and contributes to the further methodological development of parallel quantum computing. The article also outlines the advantages of quantum parallelism over classical computing and identifies the prospects for the application of parallel quantum algorithms.

Vìsnik Nacìonalʹnogo unìversitetu Lʹvìvsʹka polìtehnìka Serìâ Ìnformacìjnì sistemi ta merežì•Jun 1, 2025•2 citations

Quantum Algorithms and Complexity for Continuous Problems

Anargyros Papageorgiou, Joseph F. Traub

Most continuous mathematical formulations arising in science and engineering can only be solved numerically and therefore approximately. We shall always assume that we're dealing with a numerical approximation to the solution. There are two major motivations for studying quantum algorithms and complexity for continuous problems. 1. Are quantum computers more powerful than classical computers for important scientific problems? How much more powerful? 2. Many important scientific and engineering problems have continuous formulations. To answer the first question we must know the classical computational complexity of the problem. Knowing the classical complexity of a continuous problem we obtain the quantum computation speedup if we know the quantum complexity. If we know an upper bound on the quantum complexity through the cost of a particular quantum algorithm then we can obtain a lower bound on the quantum speedup. Regarding the second motivation, in this article we'll report on high-dimensional integration, path integration, Feynman path integration, the smallest eigenvalue of a differential equation, approximation, partial differential equations, ordinary differential equations and gradient estimation. We'll also briefly report on the simulation of quantum systems on a quantum computer.

arXiv:0712.1211•Dec 7, 2007•0 citations

S-Word Arithmetic and High Precision Calculations

V. K. Zadiraka, Andrii Tereshchenko, Інна Віталіївна Швідченко

The intricacies of using S-word arithmetic, the influence of the value of the parameter S on the estimation of the rounding error are analyzed; what are high-precision calculations and where they are used. The problems of two-key cryptography, computer steganography and the problem of transcomputational complexity are considered as areas of application of S-word arithmetic. For the development of S-word arithmetic algorithms, sequential, parallel, quantum computing models are used, and systems of residual classes are used. The architectural features of the computer system for the implementation of an effective algorithm in various models of calculations are considered. For the parallel computing model, the importance of reducing the connected steps is indicated, which can increase the amount of processed data, but allows to involve a larger number of parallel processors. This approach is in conflict with a method that reduces the amount of processed data, and there is a need to maintain a balance between these two methods in a parallel computing model. For the quantum computing model, the connection of qubits is a key factor in determining the quantum volume. The physical scheme determines which pairs of qubits can be entangled in a quantum computer. Peculiarities of transferring algorithms to another computing model are considered. An analysis of the complexity of implementing S-word arithmetic operations in sequential, parallel, and quantum computing models is carried out. For the parallel computing model, the importance of reducing the connected steps is indicated, which can increase the amount of processed data, but allows to involve a larger number of parallel processors. This approach is in conflict with a method that reduces the amount of processed data, and there is a need to maintain a balance between these two methods in a parallel computing model. For the quantum computing model, the connection of qubits is a key factor in determining the quantum volume. The physical scheme determines which pairs of qubits can be entangled in a quantum computer. Information is provided about the ongoing scientific forum «Calculation optimization issues», the subject of which is closely related to the topic (1969-2023)

Mathematical and computer modelling Series Physical and mathematical sciences•Sep 30, 2024•2 citations

Quantum Complexity

Stefan Heinrich

A challenging question in the overlap of computer science, mathematics, and physics, is the exploration of potential capabilities of quantum computers. Milestones were the factoring algorithm of Shor (1994) and the search algorithm of Grover (1996). So far, major research was concentrated on discrete and algebraic problems. Much less was known about computational problems of analysis, including such a prominent example as high dimensional numerical integration, which is well-studied in the classical settings. We seek to understand how efficiently this and related problems can be solved in the quantum model of computation (i.e., on a quantum computer) and how the outcome compares to the efficiency of deterministic or randomized algorithms on a classical (i.e. non-quantum) computer. In this paper we give a survey of the state of the art in this field, including also a brief introduction to the general ideas of quantum computing. Introduction A quantum computer is a computing device based on quantum mechanical laws of the (sub)atomic world. The idea of such a computer was developed by Feynman [8] in 1982. He emphasized that simulating quantum mechanics on a classical computer is extremely hard, probably infeasible. So why not try to simulate quantum mechanics using quantum devices themselves. (Thoughts in this direction were also expressed by Manin [21] in 1980, see also [22].) In 1985 Deutsch [6] presented a formal model of computation for quantum computing.

Cambridge University Press eBooks•Mar 25, 2004•2 citations

Chapter 1: Model of computation

Giacomo Nannicini

Quantum computing is a relatively new field of computing that has the potential to greatly speed up the solution of certain problems. This book is about quantum algorithms, with a focus on algorithms that may be useful for mathematical optimization. Quantum computers work in a way that is fundamentally different from classical computers. We begin by introducing the model of computation, and then proceed to study several quantum algorithms. In the following, the term “classical” is used to mean “nonquantum,” as is common in the field.

Society for Industrial and Applied Mathematics eBooks•Dec 17, 2025•0 citations
Introduction. The complexity of computational algorithms for solving typical problems of computational, applied, and discrete mathematics is analyzed from the perspective of the theory of computation, depending on the computer architecture and the used computing model: single-processor, multiprocessor, and quantum. The following classes of problems are considered: systems of linear algebraic equations, the Cauchy problem for systems of ordinary differential equations, numerical integration, boundary value problems for ordinary differential equations, factorization of numbers, finding the discrete logarithm of a number in multiplicative integer groups, searching for the necessary record in an unordered database, etc. The purposes of the paper are: 1. To investigate how the computational complexity depends on the computer architecture and the computational model. 2. To show that the construction of the computational process under the given conditions of calculations is related to the solution of the following problems: – the existence ε-solution to the problem; – the existence of T-effective computing algorithms; – the possibility of building a real computing process under the given computing conditions. 3. To investigate the effect of rounding numbers on computational complexity (especially when solving problems of transcomputational complexity). 4. To give the complexity estimates and total error of the computational algorithm for a number of typical problems of computational, applied, and discrete mathematics. The results. The complexity estimates of computational algorithms of the listed classes of problems for single-processor, multiprocessor and quantum computing models are given. The main focus is on high-performance computing: using the principles of parallel data processing and quantum mechanics. Conclusions. The connection of complexity estimates of computational algorithms with the architecture of computers and models of calculations is demonstrated. The characteristics of the first quantum computers (2016 – 2022), which have gone beyond laboratory research, are given. Keywords: computer technologies, rounding error, sequential, parallel and quantum computing models, complexity estimate.
A computer is a physical device that helps us process information by executing algorithms. An algorithm is a well-defined procedure, with finite description, for realizing an information-processing task. An information-processing task can always be translated into a physical task. When designing complex algorithms and protocols for various information-processing tasks, it is very helpful, perhaps essential, to work with some idealized computing model. However, when studying the true limitations of a computing device, especially for some practical reason, it is important not to forget the relationship between computing and physics. Real computing devices are embodied in a larger and often richer physical reality than is represented by the idealized computing model. Quantum information processing is the result of using the physical reality that quantum theory tells us about for the purposes of performing tasks that were previously thought impossible or infeasible. Devices that perform quantum information processing are known as quantum computers. In this book we examine how quantum computers can be used to solve certain problems more efficiently than can be done with classical computers, and also how this can be done reliably even when there is a possibility for errors to occur. In this first chapter we present some fundamental notions of computation theory and quantum physics that will form the basis for much of what follows. After this brief introduction, we will review the necessary tools from linear algebra in Chapter 2, and detail the framework of quantum mechanics, as relevant to our model of quantum computation, in Chapter 3. In the remainder of the book we examine quantum teleportation, quantum algorithms and quantum error correction in detail. We are often interested in the amount of resources used by a computer to solve a problem, and we refer to this as the complexity of the computation. An important resource for a computer is time. Another resource is space, which refers to the amount of memory used by the computer in performing the computation. We measure the amount of a resource used in a computation for solving a given problem as a function of the length of the input of an instance of that problem.
This article analyzes mathematical models of quantum parallelism based on the transfer of a quantum system into a superposition state. The principles of quantum parallelism and its mathematical foundations are substantiated. To demonstrate the quantum advantage, mathematical models of fundamental quantum algorithms Deutsch-Joža and Grover are analyzed, which illustrate the efficiency of quantum computing compared to classical methods. The Deutsch-Joshy algorithm is considered, which generalizes the problem of determining the type of a binary function by extending it to a set of arguments written in a quantum register. This algorithm allows determining whether a function is constant or balanced in a single quantum call, while in classical calculations this requires exponential time. It is noted that although the Deutsch-Joshy algorithm demonstrates the possibilities of parallel quantum computing, it is of mainly theoretical importance. Grover’s algorithm implements quantum parallel computing for the practical problem of searching for an element in an unordered database. It is based on iterative amplification of the amplitude of the state corresponding to the searched element and provides quadratic speedup compared to classical algorithms. In addition to database search, Grover’s algorithm can be adapted to solve other optimization problems. The work of the considered algorithms is illustrated by numerical examples, which simplifies the understanding of their principles and contributes to the further methodological development of parallel quantum computing. The article also outlines the advantages of quantum parallelism over classical computing and identifies the prospects for the application of parallel quantum algorithms.
Most continuous mathematical formulations arising in science and engineering can only be solved numerically and therefore approximately. We shall always assume that we're dealing with a numerical approximation to the solution. There are two major motivations for studying quantum algorithms and complexity for continuous problems. 1. Are quantum computers more powerful than classical computers for important scientific problems? How much more powerful? 2. Many important scientific and engineering problems have continuous formulations. To answer the first question we must know the classical computational complexity of the problem. Knowing the classical complexity of a continuous problem we obtain the quantum computation speedup if we know the quantum complexity. If we know an upper bound on the quantum complexity through the cost of a particular quantum algorithm then we can obtain a lower bound on the quantum speedup. Regarding the second motivation, in this article we'll report on high-dimensional integration, path integration, Feynman path integration, the smallest eigenvalue of a differential equation, approximation, partial differential equations, ordinary differential equations and gradient estimation. We'll also briefly report on the simulation of quantum systems on a quantum computer.
The intricacies of using S-word arithmetic, the influence of the value of the parameter S on the estimation of the rounding error are analyzed; what are high-precision calculations and where they are used. The problems of two-key cryptography, computer steganography and the problem of transcomputational complexity are considered as areas of application of S-word arithmetic. For the development of S-word arithmetic algorithms, sequential, parallel, quantum computing models are used, and systems of residual classes are used. The architectural features of the computer system for the implementation of an effective algorithm in various models of calculations are considered. For the parallel computing model, the importance of reducing the connected steps is indicated, which can increase the amount of processed data, but allows to involve a larger number of parallel processors. This approach is in conflict with a method that reduces the amount of processed data, and there is a need to maintain a balance between these two methods in a parallel computing model. For the quantum computing model, the connection of qubits is a key factor in determining the quantum volume. The physical scheme determines which pairs of qubits can be entangled in a quantum computer. Peculiarities of transferring algorithms to another computing model are considered. An analysis of the complexity of implementing S-word arithmetic operations in sequential, parallel, and quantum computing models is carried out. For the parallel computing model, the importance of reducing the connected steps is indicated, which can increase the amount of processed data, but allows to involve a larger number of parallel processors. This approach is in conflict with a method that reduces the amount of processed data, and there is a need to maintain a balance between these two methods in a parallel computing model. For the quantum computing model, the connection of qubits is a key factor in determining the quantum volume. The physical scheme determines which pairs of qubits can be entangled in a quantum computer. Information is provided about the ongoing scientific forum «Calculation optimization issues», the subject of which is closely related to the topic (1969-2023)
A challenging question in the overlap of computer science, mathematics, and physics, is the exploration of potential capabilities of quantum computers. Milestones were the factoring algorithm of Shor (1994) and the search algorithm of Grover (1996). So far, major research was concentrated on discrete and algebraic problems. Much less was known about computational problems of analysis, including such a prominent example as high dimensional numerical integration, which is well-studied in the classical settings. We seek to understand how efficiently this and related problems can be solved in the quantum model of computation (i.e., on a quantum computer) and how the outcome compares to the efficiency of deterministic or randomized algorithms on a classical (i.e. non-quantum) computer. In this paper we give a survey of the state of the art in this field, including also a brief introduction to the general ideas of quantum computing. Introduction A quantum computer is a computing device based on quantum mechanical laws of the (sub)atomic world. The idea of such a computer was developed by Feynman [8] in 1982. He emphasized that simulating quantum mechanics on a classical computer is extremely hard, probably infeasible. So why not try to simulate quantum mechanics using quantum devices themselves. (Thoughts in this direction were also expressed by Manin [21] in 1980, see also [22].) In 1985 Deutsch [6] presented a formal model of computation for quantum computing.
Quantum computing is a relatively new field of computing that has the potential to greatly speed up the solution of certain problems. This book is about quantum algorithms, with a focus on algorithms that may be useful for mathematical optimization. Quantum computers work in a way that is fundamentally different from classical computers. We begin by introducing the model of computation, and then proceed to study several quantum algorithms. In the following, the term “classical” is used to mean “nonquantum,” as is common in the field.