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

arXiv:1006.1010 · Proceedings of symposia in applied mathematics

Geometry of abstraction in quantum computation

Duško Pavlović

Published Jan 1, 2012• 12 citations
arXivHTMLPDF

Abstract

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.

DOI
10.1090/psapm/071/607

Related papers

Mathematical Foundations of Information Flow

Samson Abramsky, Michael W. Mislove

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.

Proceedings of symposia in applied mathematics•Jan 1, 2012•46 citations

Categorical quantum computation

Paquette, Éric Oliver

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.

•Jan 1, 2008•7 citations

Quantum Algorithms and Hard Problems

C. Vidya Raj, H. D. Phaneendra, M. S. Shivakumar

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

IEEE International Conference on Cognitive Informatics•Jul 1, 2006•5 citations

Quantum Computation and Isomorphism Testing

David J. Rosenbaum

In this thesis, we study quantum computation and algorithms for isomorphism problems. Some of the problems that we cover are fundamentally quantum and therefore require quantum techniques. For other problems, classical approaches are more appropriate; however, we often give quantum variants of our classical algorithms as well. The field of quantum computation aims to accelerate algorithms by exploiting the laws of quantum mechanics. Several quantum algorithms are known that are exponentially faster than the best classical algorithms known for the same problems, including several which are relevant to cryptography. Quantum computing is therefore of great importance. On the theory side, it has already transformed our notions of which problems are tractable and which are not. On the practical side, the construction of a quantum computer would render many popular techniques for encryption obsolete. We derive several results in quantum computation. Quantum algorithms are normally formulated in an abstract way that ignores practical details such as where different parts of the computation are located physically. Using naive methods for translating these algorithms into practical quantum computing technologies increases the time complexity by a linear factor, while previous work reduced this factor to a square root. We further reduce this factor to a constant at the cost of requiring additional space. This retroactively justifies an important assumption made in many quantum algorithms. Another interesting problem is to determine the query complexity of extracting different types of information from physical processes. In the case of deterministic processes, it is well known that quantum algorithms cannot outperform deterministic algorithms by more than an exponential factor. We show --- somewhat surprisingly --- that when the process is allowed to be randomized, there are problems that have a constant quantum query complexity but cannot be solved classically no matter how many queries are made. In fact, we show how to construct such an infinity-vs-one separation from any weaker separation between the classical and quantum query complexities. In an isomorphism problem, we seek to determine if two algebraic or combinatorial objects have the same structure. One of the most well-known of these is the graph isomorphism problem, which is interesting since it is suspected to be of complexity intermediate between P and the NP-complete problems. We transition from quantum computation to isomorphism testing by considering the tree isomorphism problem. While linear-time classical algorithms are known for this problem, we show that a promising framework for developing efficient quantum algorithms for graph isomorphism, known as the state preparation approach, can also solve tree isomorphism. While this result might seem modest, it is important to know that the state preparation approach works for trees, since otherwise there would be little hope of using it to obtain efficient algorithms for more interesting classes of graphs. We also derive a powerful primitive along the way that is of independent interest. Next, we study the group isomorphism problem, which is a special case of graph isomorphism. Group isomorphism is suspected to be significantly easier than graph isomorphism, but still has unknown complexity. While group isomorphism is already of interest since it is a fundamental computational question about groups, searching for faster algorithms for group isomorphism is therefore also one way of approaching the graph isomorphism problem. We use collision detection methods to give a classical algorithm that obtains a square-root speedup over the best algorithm previously known for the general group isomorphism problem. For the solvable groups (which are conjectured to be difficult and contain almost all groups), we combine our collision detection techniques with group-theoretic methods to obtain a classical fourth-root speedup over the best algorithm known previously. Prior to this work, it was a longstanding open problem to obtain any improvement for either of these classes of groups. Finally, we give a general framework that yields speedups for many isomorphism problems. In particular, it yields the square-root speedup for testing isomorphism of general groups mentioned above. All of our group isomorphism-testing algorithms also have quantum variants that are slightly faster than their classical counterparts.

•Jan 1, 2015•2 citations

Foundational Abstractions for Quantum Programming

Charles Yuan

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.

•Sep 1, 2025•0 citations

Explaining Basic Aspects of Quantum Computation Based on Functional Approach

Marcos B. Cardoso, Eduarda Monteiro, Felipe Camargo Munhoz +3 more

The aim of this paper is to obtain an inter-pretation of foundations of the quantum compu-tation under the light of the level of functional abstraction [1] and supported by its mathemat-ical basis. This approach seems more accessi-ble to programmers and increases the study and interest in quantum programming. The neces-sity for secret message exchange and the possi-bility of reading secret information have devel-oped cryptographic methods. The security of current methods is based on hard computational problems enabling a good safety level. However, if there is a marked growth in computational power, leaks in the safety system of the crypto-

•Jan 1, 2006•0 citations
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.
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
In this thesis, we study quantum computation and algorithms for isomorphism problems. Some of the problems that we cover are fundamentally quantum and therefore require quantum techniques. For other problems, classical approaches are more appropriate; however, we often give quantum variants of our classical algorithms as well. The field of quantum computation aims to accelerate algorithms by exploiting the laws of quantum mechanics. Several quantum algorithms are known that are exponentially faster than the best classical algorithms known for the same problems, including several which are relevant to cryptography. Quantum computing is therefore of great importance. On the theory side, it has already transformed our notions of which problems are tractable and which are not. On the practical side, the construction of a quantum computer would render many popular techniques for encryption obsolete. We derive several results in quantum computation. Quantum algorithms are normally formulated in an abstract way that ignores practical details such as where different parts of the computation are located physically. Using naive methods for translating these algorithms into practical quantum computing technologies increases the time complexity by a linear factor, while previous work reduced this factor to a square root. We further reduce this factor to a constant at the cost of requiring additional space. This retroactively justifies an important assumption made in many quantum algorithms. Another interesting problem is to determine the query complexity of extracting different types of information from physical processes. In the case of deterministic processes, it is well known that quantum algorithms cannot outperform deterministic algorithms by more than an exponential factor. We show --- somewhat surprisingly --- that when the process is allowed to be randomized, there are problems that have a constant quantum query complexity but cannot be solved classically no matter how many queries are made. In fact, we show how to construct such an infinity-vs-one separation from any weaker separation between the classical and quantum query complexities. In an isomorphism problem, we seek to determine if two algebraic or combinatorial objects have the same structure. One of the most well-known of these is the graph isomorphism problem, which is interesting since it is suspected to be of complexity intermediate between P and the NP-complete problems. We transition from quantum computation to isomorphism testing by considering the tree isomorphism problem. While linear-time classical algorithms are known for this problem, we show that a promising framework for developing efficient quantum algorithms for graph isomorphism, known as the state preparation approach, can also solve tree isomorphism. While this result might seem modest, it is important to know that the state preparation approach works for trees, since otherwise there would be little hope of using it to obtain efficient algorithms for more interesting classes of graphs. We also derive a powerful primitive along the way that is of independent interest. Next, we study the group isomorphism problem, which is a special case of graph isomorphism. Group isomorphism is suspected to be significantly easier than graph isomorphism, but still has unknown complexity. While group isomorphism is already of interest since it is a fundamental computational question about groups, searching for faster algorithms for group isomorphism is therefore also one way of approaching the graph isomorphism problem. We use collision detection methods to give a classical algorithm that obtains a square-root speedup over the best algorithm previously known for the general group isomorphism problem. For the solvable groups (which are conjectured to be difficult and contain almost all groups), we combine our collision detection techniques with group-theoretic methods to obtain a classical fourth-root speedup over the best algorithm known previously. Prior to this work, it was a longstanding open problem to obtain any improvement for either of these classes of groups. Finally, we give a general framework that yields speedups for many isomorphism problems. In particular, it yields the square-root speedup for testing isomorphism of general groups mentioned above. All of our group isomorphism-testing algorithms also have quantum variants that are slightly faster than their classical counterparts.
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.
The aim of this paper is to obtain an inter-pretation of foundations of the quantum compu-tation under the light of the level of functional abstraction [1] and supported by its mathemat-ical basis. This approach seems more accessi-ble to programmers and increases the study and interest in quantum programming. The neces-sity for secret message exchange and the possi-bility of reading secret information have devel-oped cryptographic methods. The security of current methods is based on hard computational problems enabling a good safety level. However, if there is a marked growth in computational power, leaks in the safety system of the crypto-