Quantum computing improves substantially on known classical algorithms for various important problems, but the nature of the relationship between quantum and classical computing is not yet fully understood. This relationship can be clarified by free models, that add to classical computing just enough physical principles to represent quantum computing and no more. Here we develop an axiomatisation of quantum computing that replaces the standard continuous postulates with a small number of discrete equations, as well as a free model that replaces the standard linear-algebraic model with a category-theoretical one. The axioms and model are based on reversible classical computing, isolate quantum advantage in the ability to take certain well-behaved square roots, and link to various quantum computing hardware platforms. This approach allows combinatorial optimisation, including brute force computer search, to optimise quantum computations. The free model may be interpreted as a programming language for quantum computers, that has the same expressivity and computational universality as the standard model, but additionally allows automated verification and reasoning.
Journal reference
Proceedings of the National Academy of Sciences 123(8):e2510881123, 2026
Quantum computing improves substantially on known classical algorithms for various important problems, but the nature of the relationship between quantum and classical computing is not yet fully understood. This relationship can be clarified by free models, that add to classical computing just enough physical principles to represent quantum computing and no more. Here we develop an axiomatisation of quantum computing that replaces the standard continuous postulates with a small number of discrete equations, as well as a free model that replaces the standard linear-algebraic model with a category-theoretical one. The axioms and model are based on reversible classical computing, isolate quantum advantage in the ability to take certain well-behaved square roots, and link to various quantum computing hardware platforms. This approach allows combinatorial optimisation, including brute force computer search, to optimise quantum computations. The free model may be interpreted as a programming language for quantum computers, that has the same expressivity and computational universality as the standard model, but additionally allows automated verification and reasoning.
The presented program aims at speeding up the brute force computation of the so-called L d norm of a matrix M using graphics processing units (GPUs). Alternatives for CPUs have also been implemented, and the algorithm is applicable to any parallel environment. The n × m matrix M has real elements which may represent coefficients of a bipartite Bell expression or those of a linear prepare-and-measure (PM) witness. In this interpretation, the L 1 norm is the local bound of the given correlation-type Bell expression, and the L d norm for d ≥ 2 is the classical d -dimensional bound of the given PM witness, which is associated with the communication of d -level classical messages in the PM scenario. The program is also capable of calculating the local bound of Bell expressions including marginals. In all scenarios, the output is assumed to be binary. The code for GPUs is written in CUDA C and can utilize one NVIDIA GPU in a computer. To illustrate the performance of our implementation, we refer to Brierley et al. [1] who needed approximately three weeks to compute the local bound on a Bell expression defined by a 42 × 42 matrix on a standard desktop using a single CPU core. In contrast, our efficient implementation of the brute force algorithm allows us to reduce this to three minutes using a single NVIDIA RTX 6000 Ada graphics card on a workstation. For CPUs, the algorithm was implemented with OpenMP and MPI according to the shared and distributed memory models, respectively, and achieves a comparable speedup at a number of CPU cores around 100. Program Title: L_CUDA.cu, L_MPI.c, L_OpenMP.c CPC Library link to program files: https://doi.org/10.17632/scfjjt9svm.1 Developer's repository link: https://github.com/istvanmarton/L-norms_BruteForce Licensing provisions: GPLv3 Programming language: C, CUDA, OpenMP, MPI Nature of problem: The computational demand of determining the L d norm of a matrix of real coefficients is high; exact L d norms have been computed so far for relatively small matrices only. Besides that any exact algorithm appears to scale exponentially with the number of rows (or the minimum of rows and columns, for d = 1 ), the naive approach to brute-force compute an L d norm features a contribution that scales linearly with the product of the number of rows and columns, because every matrix element needs to be accessed repeatedly. Improving efficiency is thus both desirable and possibly feasible. Solution method: We attenuate the mentioned secondary contribution by accessing elements only from a single row of the matrix in each step, achieving a linear scaling with the number of columns in terms of memory access. Even though we perform a search for the relevant row, scaling linearly with the number of rows in terms of the number of operations, this precedes the access to the matrix elements, so that multiplication does not occur for time complexity. Besides identifying further important mathematical shortcuts, the problem is very well suited to parallelization, which we take advantage of. In particular, we provide an implementation for graphics processing units besides universal processors. Additional comments including restrictions and unusual features: The entries of the input matrix M must be provided as integers (i.e., conversion from floating-point entries is necessary). The program can utilize a single GPU on a computer.
Quantum computing is a propitious technology which is likely to revolutionize computing.It differs from classical computing, in context of the algorithms it requires for computations and the methods of implementation which correspond to the principles of quantum mechanics.The clock frequency of existing computer processor systems may reach about 40 GHz within the next decade.By then one atom may represent one bit, but electrons under such conditions cannot be described by classical physics, due to this a new model of computing becomes absolutely inevitable.The prospect of quantum computing may have the potential in dealing with the problems faced by classical computing.
The famous Travelling Salesman Problem (TSP) is an important category of optimization problems that is mostly encountered in various areas of science and engineering. Studying optimization problems motivates to develop advanced techniques more suited to contemporary practical problems. Among those, especially the NP hard problems provide an apt platform to demonstrate supremacy of quantum over classical technologies in terms of resources and time. TSP is one such NP hard problem in combinatorial optimization which takes exponential time order for solving by brute force method. Here we propose a quantum algorithm to solve the travelling salesman problem using phase estimation technique. We approach the problem by encoding the given distances between the cities as phases. We construct unitary operators whose eigenvectors are the computational basis states and eigenvalues are various combinations of these phases. Then we apply phase estimation algorithm to certain eigenstates which give us all the total distances possible for all the routes. After obtaining the distances we can search through this information using the quantum search algorithm for finding the minimum to find the least possible distance as well the route taken. This provides us a quadratic speedup over the classical brute force method for a large number of cities. In this paper, we illustrate an example of the travelling salesman problem by taking four cities and present the results by simulating the codes in the IBM's quantum simulator.
Quantum computing is a promising approach of computation that is based on equations from Quantum Mechanics and nanotechnology. Understanding and simulating quantum operations on a classical computer has different approaches and is modeled in different ways. However, the most repute ways are Quantum Turing Machine, Network Model or circuit model of connected gates and Quantum Programming Language. Many simulators do exist that varies in many features such as implementation languages, target platforms, paradigms, visuality, and applied quantum algorithms. There was a developmental trade-off between the simplicity and the functionality of the simulator. The goals and research activities are outlined as follows: First, surveying the quantum computing world, its characteristics, issues, problems, and challenges. Second, surveying the existing quantum simulators, illustrating representative simulators of major approaches, their features, and functionalities. Third, introducing a framework to provide the power of quantum computing , while insisting the simplicity and high usability. Finally, providing a case study for a new quantum algorithm based on the introduced framework.
Combining quantum computers with classical compute power has become a standard means for developing algorithms and heuristics that are, eventually, supposed to beat any purely classical alternatives. While in-principle advantages for solution quality or runtime are expected for increasingly many approaches, substantial challenges remain: Non-functional properties like runtime or solution quality of many suggested approaches are not yet fully understood, and need to be explored empirically. This, in turn, makes it unclear which approach is best suited for a given problem. Accurately predicting behaviour and properties of quantum-classical algorithms opens possibilities for software abstraction layers, which in turn can automate decisionmaking for algorithm selection and parametrisation. While such techniques find frequent use in classical high-performance computing, they are still mostly absent from quantum software toolchains. In this paper, we present a methodology (accompanied by a reproducible reference implementation) to perform algorithm selection based on desirable non-functional requirements. This greatly simplifies decision-making processes for end users. Based on meta-information annotations at the source code level, our framework traces key characteristics of quantum-classical heuristics and algorithms, and uses this information to predict the most suitable approach and its parameters for given computational challenges and their non-functional requirements. As combinatorial optimisation is a very extensively studied aspect of quantumclassical systems, we perform a comprehensive case study based on numerical simulations of algorithmic approaches to implement and validate our ideas. We develop statistical models to quantify the influence of various factors on non-functional properties, and establish predictions for optimal algorithmic choices without manual user effort. We argue that our methodology generalises to problem classes beyond combinatorial optimisation, such as Hamiltonian optimisation, and lays a foundation for integrated software layers for quantum design automation.
Quantum computation is one of the very promising new fields of the new millennium for basic research in theoretical computer science and computational mathematics. Quantum computers have stimulated great interests due to their promise of being able to solve problems considered infeasible on current computers. From a computer scientist's and mathematician's point of view, the growth in the capacities of the underlying hardware is vital since an inefficient algorithm can solve the problem with the faster new hardware. For decades, this attitude was irrelevant but the deadline to change it is near. That is why quantum computation has led to rapid developments in physics, mathematics and computer science.This tutorial paper summarizes our year long series of multidisciplinary seminars on the topics of using computational algebra in quantum computation for finding new theoretical models for the upcoming generation of computers together with finding the models' computational abilities.