Известия Южного федерального университета. Технические науки
STUDY OF POSSIBILITIES OF USING PHOTONIC AND QUANTUM COMPUTING TECHNOLOGIES TO CALCULATE EXACT PROBABILITY DISTRIBUTIONS OF STATISTIC VALUES FROM FINITE DISCRETE SEQUENCES
This article explores the feasibility of using photonic and quantum computing technologies to calculate exact probability distributions of discrete sequence statistics, assuming the existence of working hardware prototypes of computing systems and the development of the required quantum algorithms. The performance evaluation of computing systems based on photonic computing technologies is based on materials from the Sarov Scientific Center for Physics and Microphysics of the Russian Academy of Sciences. The performance of a quantum computing system is assessed by comparing the time it takes to solve a boson sampling problem from a given distribution on a computing system with known performance and the time it takes to solve it on a quantum computing system. To assess the feasibility of using photonic and quantum computing technologies to calculate exact distributions, modern methods for calculating them are considered. These methods are based on solving the type multiplicity equation and a system of linear equations in non-negative integers. Analytical expressions determining the computational complexity of these methods are presented. The values of the boundaries of the parameters of exact distributions accessible for calculation using photonic and quantum computing technologies are determined. A comparison of the obtained results with the results of using multiprocessor computing technologies to calculate exact distributions using various methods is presented. An analysis of the feasibility of using photonic and quantum computing technologies to calculate exact distributions is conducted by comparing the number of parameter pairs that can be calculated for exact distributions with the total number of distribution parameters within the Fisher region, which determines a fivefold increase in sample size over the alphabet size. An analysis of the data on the number of sample parameters shows that with increasing performance of the computing technologies used, the ability to calculate exact distributions increases. However, even with the most powerful quantum technologies, this number does not exceed one-tenth of the total number of exact distributions required for statistical analysis of discrete sequences in alphabets up to 256 characters long
This article explores the feasibility of using photonic and quantum computing technologies to calculate exact probability distributions of discrete sequence statistics, assuming the existence of working hardware prototypes of computing systems and the development of the required quantum algorithms. The performance evaluation of computing systems based on photonic computing technologies is based on materials from the Sarov Scientific Center for Physics and Microphysics of the Russian Academy of Sciences. The performance of a quantum computing system is assessed by comparing the time it takes to solve a boson sampling problem from a given distribution on a computing system with known performance and the time it takes to solve it on a quantum computing system. To assess the feasibility of using photonic and quantum computing technologies to calculate exact distributions, modern methods for calculating them are considered. These methods are based on solving the type multiplicity equation and a system of linear equations in non-negative integers. Analytical expressions determining the computational complexity of these methods are presented. The values of the boundaries of the parameters of exact distributions accessible for calculation using photonic and quantum computing technologies are determined. A comparison of the obtained results with the results of using multiprocessor computing technologies to calculate exact distributions using various methods is presented. An analysis of the feasibility of using photonic and quantum computing technologies to calculate exact distributions is conducted by comparing the number of parameter pairs that can be calculated for exact distributions with the total number of distribution parameters within the Fisher region, which determines a fivefold increase in sample size over the alphabet size. An analysis of the data on the number of sample parameters shows that with increasing performance of the computing technologies used, the ability to calculate exact distributions increases. However, even with the most powerful quantum technologies, this number does not exceed one-tenth of the total number of exact distributions required for statistical analysis of discrete sequences in alphabets up to 256 characters long
The paper is devoted to the evaluation of the hardware resource of computer systems forsolving a computational-expensive problem such as calculation of the probability distributions ofstatistics by the second multiplicity method based on Δ-exact approximations for samples with asize of 320-1280 characters and an alphabet power of 128-256 characters, and with an accuracyof Δ=10-5. The total solution time should not exceed 30 days or 2.592·106 seconds for 24/7 computing.Owing to the use of the properties of the second multiplicity method, the computational complexityof the calculations can be brought to the range of 9.68·1022-1.60·1052 operations with thenumber of tested vectors of 6.50·1023-1.39·1050. The solution of this problem for the specified parametersof samples during the given time requires the hardware resource which cannot be providedby modern computer means such as processors, graphics accelerators, programmable logicintegrated circuits. Therefore, in the paper we analyze the possibilities of promising quantum andphoton technologies for solving the problem with the given parameters. The main advantage ofquantum computer systems is the high speed of calculations for all possible parameter values.However, quantum acceleration will not be achieved to calculate the probability distributions ofstatistics due to the need to check all the obtained solutions. Here, the number of obtained solutionscorresponds to the dimension of the problem. In addition, due to the current developmentlevel of the quantum hardware components, it is impossible to create and use the 120-qubit quantumcomputers for the solution of the considered problem. Photon computers can provide highcomputation speed at low power consumption and require the smallest number of nodes to solvethe considered problem. However, unsolved problems with the physical implementation of efficientmemory elements and the lack of available hardware components make the use of photon computertechnologies impossible for calculation of the probability distributions of statistics in the nearfuture (5-7 years). Therefore, it is most reasonable to use hybrid computer systems containingnodes of different architectures. To solve the problem on various hardware platforms (generalpurposeprocessors, GPUs, FPGAs) and configurations of hybrid computer systems, we suggest touse an architecture independent high-level programming language SET@L. The language combinesthe representation of calculations as sets and collections (based on the alternative set theoryof P. Vopenka), the absolutely parallel form of the problem represented as an information graph,and the paradigm of aspect-oriented programming.
This paper is devoted to the evaluation of the hardware resources of computer systems for solving a computationally expensive problem such as the calculation of the probability distributions of statistics by the second multiplicity method based on ∆-exact approximations of samples with a size of 320-1280 characters and an alphabet power of 128-256 characters.The accuracy is ∆ = 10 -5 and the total solution time should not exceed 30 days or 2.592 × 10 6 seconds for 24/7 computing.Owing to the use of the properties of the second multiplicity method, the computational complexity of the calculations can be brought within the range of 9.68 × 10 22 -1.60 × 10 52 operations with the number of tested vectors at 6.50 × 10 23 -1.39 × 10 50 .The solution of this problem for the specified parameters of samples during the given time requires hardware resources which cannot be provided by modern computer technology such as processors, graphics accelerators and programmable logic integrated circuits.Therefore, in this paper, we analyze the possibilities of promising quantum and photon technologies for solving the problem with the given parameters.The main advantage of quantum computer systems is the high speed of calculations for all possible parameter values.However, quantum acceleration will not be achieved to calculate the probability distributions of statistics due to the need to check all the obtained solutions.Here, the number of obtained solutions corresponds to the dimension of the problem.In addition, due to the current development level of quantum hardware components, it is impossible to create and use 120 qubit quantum computers for the solution of the considered problem.Photon computers can provide high computation speeds at low power consumptions and require the smallest number of nodes to solve the considered problem.However, unsolved problems with the physical implementation of efficient memory elements and the lack of available hardware components make the use of photon computer technologies impossible for calculating the probability distributions of statistics in the near future (5-7 years).Therefore, it is most reasonable to use hybrid computer systems containing nodes of different architectures.To solve the problem on various hardware platforms (general purpose processors, GPUs and FPGAs) and configurations of hybrid computer systems, we suggest to use the architecture-independent high-level programming language SET@L.The language combines the representation of calculations as sets and collections (based on the alternative set theory of P. Vopenka), the absolutely parallel form of the problem represented as an information graph and the paradigm of aspect-oriented programming.
We consider the problem of calculating the approximate value (estimate) of the permanent of a square matrix over the field of real numbers using a photonic quantum computer that sampling bosons from a given distribution. It is pointed out that it is possible to effectively solve this problem for the following three classes of matrices: symmetric matrices which eigenvalues do not exceed 1 in absolute value; orthogonal matrices; doubly stochastic matrices. For the last two classes, we are talking about evaluating the square of the permanent. The mathematical basis for solving the problem is the formula, which represents the permanent of the Hermitian matrix as the mathematical expectation of some random variable which values are equal to the products of the powers of the eigenvalues of the Hermitian matrix. And the corresponding probabilities with which these products are accepted as values of a random variable are also completely determined by the same Hermitian matrix. This circumstance allows using the methods of probability theory in order to solve the problem of permanent estimation.
Currently, significant results have emerged in the field of creation and application of quantum computers. We are talking about the Chinese quantum photonic computers Jiuzhang, Jiuzhang-2 (Jiuzhang 2.0), Jiuzhang-3 (Jiuzhang 3.0), which appeared respectively in 2020, 2021 and 2023, as well as the Canadian quantum photonic computer Borealis, which appeared in 2022. All these computers belong to the class of so-called quantum simulators – variants of quantum computers that solve one problem or a narrow class of problems. In addition to narrow specialization, quantum simulators have another important feature. In quantum simulators, controllable quantum objects simulate and effectively predict the behavior of real quantum systems. For example, in the quantum photonic computers Jiuzhang, Jiuzhang-2, Jiuzhang-3 and Borealis, the photons supplied to the inputs of these computers imitate the behavior of a “system of non-interacting identical bosons.” The Jiuzhang, Jiuzhang-2, Jiuzhang-3, and Borealis quantum simulators solve the problem of sampling bosons from a given distribution. Together they represent a significant scientific, technical and technological breakthrough in the development and creation of quantum computers. However, beyond what has been achieved, a number of important issues that are of interest both theoretically and for the field of practical applications remain unexamined. Among them are the following: about the architecture and composition of the elements of a quantum photonic computer, their number and connection diagram, as well as setting parameters that determine the required probability distribution from which boson samples are taken. The scientific problem addressed in the article is to obtain answers to the above questions by developing the theoretical foundations for creating a quantum photonic computer that solves the problem of sampling bosons from a given distribution in the most general case without restrictions on the distribution. The following results were obtained: the theoretical basis for the creation of a quantum photon computer (called in the article the Fuzuli boson sampler, briefly bsF) was developed that solves the problem of sampling bosons from a given distribution, for use as a quantum computing subsystem of a hybrid computing system to solve the problem of estimating matrix permanents; its constituent elements have been identified and studied, their numbers have been determined, and inter-element connection diagrams have been developed; an algorithm has been developed for tuning the bsF quantum photon computer to solve the problem of estimating matrix permanents; The functioning process of bsF is described. The article assumes that physically, in each cycle of operation of the bsF computer, the process of supplying photons to the inputs of the computer, their “movement” to the detectors, as well as the registration of photons by detectors is organized in such a way that the set of these photons imitates the behavior of a system of non-interacting identical bosons. Physical and engineering issues of ensuring such behavior of photons are not considered in this work. At the same time, the feasibility of such a possibility in practice (experimentally) is assumed to be undeniable. Examples confirming this position are the already created prototypes of quantum photonic computers in China (Jiuzhang, Jiuzhang-2, Jiuzhang-3) and in Canada (Borealis).
It remains questionable whether all physically realizable computational model can be simulated by currently available digital computer in an efficient manner. The theory of Quantum Mechanics offers an answer to this question through one of its branches that intersects with Computer Science, known as Quantum Computing. It claims that current computers, which is operating based on classical mechanics cannot efficiently simulate quantum mechanical process. Under this claim, a computer that is operating based on quantum mechanics holds more computational power than classical computers, promising a possibility to computationally solve problems that are classically intractable. To show that this claim holds, numerous quantum computational models have been proposed and analyzed through the lens of Computational Complexity Theory, providing a rigorous notion of efficiency. Models that are more feasible experimentally, although not necessarily universal, have also been of a particular interests given the numerous complicated challenges surrounding the experimental implementation of a universal quantum computer. One of this non-universal models is called Gaussian Boson Sampling (GBS), which embraces the methods of Quantum Optics by sampling the number of photon outputs from a linear optical network as a means to process quantum information. Compared to its prototype model, Boson Sampling, GBS is more experimentally feasible due to its method of generating photon that is based on the Continuous Variable (CV) paradigm of Quantum Information. Nevertheless as with Boson Sampling, it was also shown that classical simulation of GBS cannot be performed efficiently under some highly plausible conjectures. In the work presented in this thesis, we probe the complexity of classically constructing the probability distribution induced by GBS using the method of Quantum Homodyne Tomography. Instead of photon number measurement, this method further embraces the CV paradigm in the measurement of GBS by using Homodyne measurements that outputs real numbers. Sample data obtained from the measurement outcomes is then classically processed using Pattern Functions, which we use to approximate the probability distribution of GBS. A series of computer simulations that approximates some probability values of GBS are presented here, which shows that the number of samples needed to decrease the error of the approximation increases rapidly for more accurate approximation. We have derived a bound for the approximation error which can be achieved given that the sampled data satisfies a certain statistical property. This statistical property can eventually be satisfied as the number of Homodyne samples increases. Having shown another evidence for the complexity of approximating GBS using Homodyne Tomography, we further investigate the nature of the complexity of GBS by analyzing its classical-quantum computational boundary in the spectrum of amount of noise present in a GBS setup. In doing this, we built our discussions on the measure of non-classicality using the presence of negative values in the Quasi-probability distribution (QPD) representation of states of a quantum system. We then discuss existing results that shows the possibility of efficient classical simulation of a quantum computational model given a sufficient amount of noise. These results impose a necessary criteria of the minimum amount of noise that an experiment has to surpass in order for it to be impossible to simulate classically in an efficient manner. We extend this idea for GBS, where we propose a modified GBS where we consider noise in its measurements that opens a way for a possible formulation of a noise condition that a GBS experiment has to fulfill to rule out possible efficient classical simulation. To further probe the classical-quantum computational boundary, we also propose a different quantum computational model called the Photon-added Thermal State CV-Sampling (PATS CVS), which can be formulated similarly to our noisy GBS model. We then discuss existing results that analyzes the negativity of the QPD representation of a noisy Photon-added Thermal state (PATS), which constitutes the inputs for PATS CVS. Using the result that shows the quantum-classical transition in terms of the QPD negativity for a PATS state when the amount of noise changes, we discuss the potential of PATS CVS model as a possible avenue to further probe the transition between efficiently simulable and non-efficiently simulable quantum mechanical experiment.
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.