Quantum algorithms are sequences of abstract operations, performed on non-existent computers. They are in obvious need of categorical semantics. We present some steps in this direction, following earlier contributions of Abramsky, Coecke and Selinger. In particular, we analyze function abstraction in quantum computation, which turns out to characterize its classical interfaces. Some quantum algorithms provide feasible solutions of important hard problems, such as factoring and discrete log (which are the building blocks of modern cryptography). It is of a great practical interest to precisely characterize the computational resources needed to execute such quantum algorithms. There are many ideas how to build a quantum computer. Can we prove some necessary conditions? Categorical semantics help with such questions. We show how to implement an important family of quantum algorithms using just abelian groups and relations.
Quantum algorithms are sequences of abstract operations, performed on non-existent computers. They are in obvious need of categorical semantics. We present some steps in this direction, following earlier contributions of Abramsky, Coecke and Selinger. In particular, we analyze function abstraction in quantum computation, which turns out to characterize its classical interfaces. Some quantum algorithms provide feasible solutions of important hard problems, such as factoring and discrete log (which are the building blocks of modern cryptography). It is of a great practical interest to precisely characterize the computational resources needed to execute such quantum algorithms. There are many ideas how to build a quantum computer. Can we prove some necessary conditions? Categorical semantics help with such questions. We show how to implement an important family of quantum algorithms using just abelian groups and relations.
Quantum algorithms are sequences of abstract operations, performed on non-existent computers.They are in obvious need of categorical semantics.We present some steps in this direction, following earlier contributions of Abramsky, Coecke and Selinger.In particular, we analyze function abstraction in quantum computation, which turns out to characterize its classical interfaces.Some quantum algorithms provide feasible solutions of important hard problems, such as factoring and discrete log (which are the building blocks of modern cryptography).It is of a great practical interest to precisely characterize the computational resources needed to execute such quantum algorithms.There are many ideas how to build a quantum computer.Can we prove some necessary conditions?Categorical semantics help with such questions.We show how to implement an important family of quantum algorithms using just abelian groups and relations.
Quantum computation is a sub-discipline of computer science that studies computation performed using quantum-mechanical phenomena such as entanglement and the principle of quantum superposition. The work presented in this dissertation is part of a program of research initiated by S. Abramsky and B. Coecke that aims to establish a categorical foundation for quantum computation.
The usual axiomatisation of quantum computation uses the biproduct structure to express the classical fragment of the theory that comprises, for instance, the result of a measurement or classical control. Following the work of S. Abramsky and B. Coecke, that of P. Selinger for the quantum aspect, and that of B. Coecke and D. Pavlovic for the classical aspect, we will introduce a complete categorical semantics for quantum computation that includes bath the classical and the quantum fragments of the theory. In order to do so, we will introduce the notion of classical-quantum interface, which is sufficiently general to include the two fragments of the theory. Moreover, the classical fragment will be axiomatised exclusively with respect to the tensorial structure, i.e., without using biproducts. In particular, such an approach enables the use of an intuitive and rigorous graphical calculus as a proof technique which is often easier to use than the usual algebraic techniques. Moreover, we will see that the axiomatisation of basis structures from which is derived the notion of classical transformation also enables the definition of many families of classical transformations such as relations, functions, bijections, and stochastic and bistochastic transformations; the latter three being especially suitable in the context of quantum computation. Finally, we will present some quantum protocols and prove some results concerning these, using a graphical calculus developed for the categorical semantics in order to illustrates the usefulness and the well-foundedness of the theory.
Key words: Quantum computation. Classical control. Category theory. Compact closed categories. †-monoidal categories. †-compact categories. Classical-quantum interfaces.
Abstract This guide is based on the IBM Quantum course Quantum Algorithmic Foundations and addresses a central question in quantum computation: Do quantum algorithms offer provable advantages beyond the oracle (black-box) query model, in more standard computational settings where inputs are given explicitly? Answering this question requires building a rigorous theoretical foundation. The course begins with a detailed discussion of computational cost in both classical and quantum models, focusing on how complexity scales with input size rather than on absolute execution time. The emphasis is placed on algorithmic efficiency, independent of hardware improvements. To ground the discussion, the material draws heavily from computational number theory, including problems such as: Integer arithmetic Greatest common divisor (GCD) computation Integer factorization Although number theory represents a specific application domain, it provides a clear and powerful framework for analyzing computational complexity and illustrating the principles underlying quantum speedups. A key theme of the lesson is the distinction between algorithmic scalability and hardware performance. The primary concern is how the cost of an algorithm grows as problem instances become larger — a perspective that remains valid across technological generations. The course concludes by addressing a critically important concept: implementing classical computations on quantum computers. The significance of this idea is not to replace classical machines, but to use classical algorithms as subroutines within quantum procedures. This hybrid approach leverages decades of classical algorithmic research while opening new pathways toward quantum computational advantage. Through practical experimentation on IBM Q, this work connects theoretical foundations with hands-on quantum programming, reinforcing the structural principles that underlie advanced quantum algorithm design.
This thesis focuses on two different aspects of quantum computation: quantum complexity and quantum semantics. In the first part, I study the quantum complexity mainly within the quantum query model. Together with my colleagues, I introduce a new framework for quantum query complexity, phrased in terms of the minimal oracle and analyse limits and strengths of this new model in comparison to their classical and quantum counterparts. Working within the query model I study quantum one-way functions. I show that in the quantum setting, the problem of the existence of a quantum one-way permutation can be reduced to the problem of constructing polynomial size networks for performing the specific task of the reflection about a sequence of states. Furthermore, I extend these results to the domain of the state and operator complexity. I show that if a quantum one-way function exists, then we can construct a sequence of so called “hard” states with the property that the reflection operators about those states are efficiently implementable. In the second part, I study the extension of domain theory to the quantum setting and develop the semantics of quantum computation. By defining a quantum domain I introduce a rigourous definition of quantum computability for quantum states and operators. Furthermore I show that the denotational semantics of quantum computation has the same semantical structure as the denotational semantics of classical probabilistic computation introduced by Kozen. This could be considered as a foundation for designing functional programming languages for quantum computation. Finally, I continue with an abstract mathematical approach to study a general formalism for describing entanglement manipulation and introduce a new approach to derive a unique measure of entanglement for bipartite quantum pure states.
Any computation is necessarily a physical process. The current drive towards increasing speed and miniaturization of computers lead modern technology towards the subatomic domain - quantum computing, where strange quantum behavior takes over from familiar classical notions. The quantum computers have the ability to solve problems with varied computational complexities and more importantly hard problems. A problem is said to be hard, if the best possible algorithm requires exponential resources. This exponential quantum parallelism is the basis for the quantum speedup of many algorithms, and has made the construction of fast algorithms for quantum computers possible. Various proposals exist for modeling and devising procedures on computational problems related to factoring, searching, quantum counting, generalization of quantum algorithms etc. (Shor, 1994). In this paper, we have discussed the importance of algorithms such as order-finding, factoring and quantum searching which require exorbitant resources for their solution which otherwise is impossible on a classical computer
Bringing the promise of quantum computation into reality requires not only building a quantum computer but also correctly programming it to run a quantum algorithm. To obtain asymptotic advantage over classical algorithms for applications including simulation, search, and optimization, quantum algorithms rely on the ability of data in quantum superposition to exhibit phenomena such as interference and entanglement. In turn, an implementation of the algorithm as a program must correctly orchestrate these phenomena in the states of qubits. Otherwise, it would yield incorrect outputs or lose quantum computational advantage. Given a quantum algorithm, what are the challenges and costs of realizing it as a program that can run on a physical quantum computer? In this thesis, I answer this question by showing how the basic abstractions of programming upon which many quantum algorithms rely – such as data structures and control flow – can fail to work correctly or efficiently on a quantum computer. I then demonstrate how we can leverage insights from research in programming languages to re-invent the software stack – including abstractions, libraries, and compilers – to meet the demands of quantum algorithms. This approach holds out a promise of expressive and efficient tools to program a quantum computer and thereby practically realize its computational advantage.