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

Number theory in quantum computing

Sebastian Schönnenbeck

Published Jan 1, 2018• 0 citations
Publisher

Abstract

Algorithms are mathematical procedures developed to solve a problem. When encoded on a computer, algorithms must be "translated" to a series of simple steps, each of which the computer knows how to do. This task is relatively easy to do on a classical computer and we witness the benefits of this success in our everyday life. Quantum mechanics, the physical theory of the very small, promises to enable completely novel architectures of our machines, which will provide specific tasks with higher computing power. Translating and implementing algorithms on quantum computers is hard. However, we will show that solutions to this problem can be found and yield surprising applications to number theory.

DOI
10.14760/snap-2018-012-en

Related papers

Small scale quantum algorithms

B. C. Travaglione

It appears, in principle, that the laws of quantum mechanics allow a quantum computer to solve certain mathematical problems more rapidly than can be done using a classical computer. However, in order to build such a quantum computer, a number of technological problems need to be overcome. A stepping stone to this goal is the implementation of relatively simple quantum algorithms using current experimental techniques. The research work presented in this thesis consists of several theoretical studies exploring small scale quantum algorithms and methods of implementing them. Included in this thesis are an investigation of a small scale version of the phase estimation algorithm, methods of implementing the quantum random walk, a discussion of protecting quantum information by encoding it in an oscillator, and a look at the power of a quantum computer with a restricted number of qubits.

•Jan 1, 2002•0 citations

Designing and implementing small quantum circuits and algorithms

B. C. Travaglione

It appears, in principle, that the laws of quantum mechanics allow a quantum computer to solve certain mathematical problems more rapidly than can be done using a classical computer. However, in order to build such a quantum computer a number of technological problems need to be overcome. A stepping stone to this goal is the implementation of relatively simple quantum algorithms using current experimental techniques.This paper explores small scale quantum algorithms from two different perspectives. Firstly, it will be shown how small scale quantum algorithms can be tailored to fit current schemes for implementing a quantum computer. Secondly, I will review a simple model of computation, based on read-only-memory. This model allows the comparison of the space-efficiency of reversible error-free classical computation with reversible, error-free quantum computation. The quantum model has been shown to be more powerful than the classical model.

ACM/IEEE Design Automation Conference (DAC)•Jan 1, 2003•0 citations

Designing and implementing small quantum circuits and algorithms

B. C. Travaglione

It appears, in principle, that the laws of quantum mechanics allow a quantum computer to solve certain mathematical problems more rapidly than can be done using a classical computer. However, in order to build such a quantum computer a number of technological problems need to be overcome. A stepping stone to this goal is the implementation of relatively simple quantum algorithms using current experimental techniques.This paper explores small scale quantum algorithms from two different perspectives. Firstly, it will be shown how small scale quantum algorithms can be tailored to fit current schemes for implementing a quantum computer. Secondly, I will review a simple model of computation, based on read-only-memory. This model allows the comparison of the space-efficiency of reversible error-free classical computation with reversible, error-free quantum computation. The quantum model has been shown to be more powerful than the classical model.

ACM/IEEE Design Automation Conference (DAC)•Mar 2, 2004•0 citations

Designing and implementing small quantum circuits and algorithms

B. C. Travaglione

It appears, in principle, that the laws of quantum mechanics allow a quantum computer to solve certain mathematical problems more rapidly than can be done using a classical computer. However, in order to build such a quantum computer a number of technological problems need to be overcome. A stepping stone to this goal is the implementation of relatively simple quantum algorithms using current experimental techniques.This paper explores small scale quantum algorithms from two different perspectives. Firstly, it will be shown how small scale quantum algorithms can be tailored to fit current schemes for implementing a quantum computer. Secondly, I will review a simple model of computation, based on read-only-memory. This model allows the comparison of the space-efficiency of reversible error-free classical computation with reversible, error-free quantum computation. The quantum model has been shown to be more powerful than the classical model.

ACM/IEEE Design Automation Conference (DAC)•Jun 2, 2003•1 citation

Exploring Number Theory and Its Applications in Quantum Computing

Prasanna Kumar K

This paper discusses the deep connection between Number Theory, Cryptography, and Quantum Computing techniques in an endeavor to understand their application in developing new cryptographic techniques, optimization problems, and computational complexity. Like modular arithmetic, which uses prime factorization, in most quantum algorithms like Shor’s and Grover's algorithms, number theory is one of the significant paradigms. This work gives a detailed analysis of some mathematical derivation, theore,m and proof of these algorithms to their practical use as well as computational efficiency. Discussed issues include scaling, correction of errors, and unsolved concerns applying number theory; all discussed from the perspective of existing quantum architecture. Addressing this new research directions of the field, the paper also presents further developments in quantum cryptography, topological quantum computing, and the algorithmic area. In highlighting both theoretical and computational challenges, this work has shown that the synergy between number theory and quantum computing has the opportunity to revolutionize cryptography and optimization and to lay the groundwork for future quantum advancements

International Journal for Research in Applied Science and Engineering Technology•Dec 28, 2024•0 citations

QUANTUM ALGORITHMS FOR PROBLEMS IN NUMBER THEORY, ALGEBRAIC GEOMETRY, AND GROUP THEORY

Wim van Dam, Yoshitaka Sasaki

Quantum computers can execute algorithms that sometimes dramatically outperform classical computation. Undoubtedly the best-known example of this is Shor's discovery of an efficient quantum algorithm for factoring integers, whereas the same problem appears to be intractable on classical computers. Understanding what other computational problems can be solved significantly faster using quantum algorithms is one of the major challenges in the theory of quantum computation, and such algorithms motivate the formidable task of building a large-scale quantum computer. This article will review the current state of quantum algorithms, focusing on algorithms for problems with an algebraic flavor that achieve an apparent superpolynomial speedup over classical computation.

arXiv:1206.6126•Dec 1, 2012•5 citations
Algorithms are mathematical procedures developed to solve a problem. When encoded on a computer, algorithms must be "translated" to a series of simple steps, each of which the computer knows how to do. This task is relatively easy to do on a classical computer and we witness the benefits of this success in our everyday life. Quantum mechanics, the physical theory of the very small, promises to enable completely novel architectures of our machines, which will provide specific tasks with higher computing power. Translating and implementing algorithms on quantum computers is hard. However, we will show that solutions to this problem can be found and yield surprising applications to number theory.
It appears, in principle, that the laws of quantum mechanics allow a quantum computer to solve certain mathematical problems more rapidly than can be done using a classical computer. However, in order to build such a quantum computer, a number of technological problems need to be overcome. A stepping stone to this goal is the implementation of relatively simple quantum algorithms using current experimental techniques. The research work presented in this thesis consists of several theoretical studies exploring small scale quantum algorithms and methods of implementing them. Included in this thesis are an investigation of a small scale version of the phase estimation algorithm, methods of implementing the quantum random walk, a discussion of protecting quantum information by encoding it in an oscillator, and a look at the power of a quantum computer with a restricted number of qubits.
It appears, in principle, that the laws of quantum mechanics allow a quantum computer to solve certain mathematical problems more rapidly than can be done using a classical computer. However, in order to build such a quantum computer a number of technological problems need to be overcome. A stepping stone to this goal is the implementation of relatively simple quantum algorithms using current experimental techniques.This paper explores small scale quantum algorithms from two different perspectives. Firstly, it will be shown how small scale quantum algorithms can be tailored to fit current schemes for implementing a quantum computer. Secondly, I will review a simple model of computation, based on read-only-memory. This model allows the comparison of the space-efficiency of reversible error-free classical computation with reversible, error-free quantum computation. The quantum model has been shown to be more powerful than the classical model.
It appears, in principle, that the laws of quantum mechanics allow a quantum computer to solve certain mathematical problems more rapidly than can be done using a classical computer. However, in order to build such a quantum computer a number of technological problems need to be overcome. A stepping stone to this goal is the implementation of relatively simple quantum algorithms using current experimental techniques.This paper explores small scale quantum algorithms from two different perspectives. Firstly, it will be shown how small scale quantum algorithms can be tailored to fit current schemes for implementing a quantum computer. Secondly, I will review a simple model of computation, based on read-only-memory. This model allows the comparison of the space-efficiency of reversible error-free classical computation with reversible, error-free quantum computation. The quantum model has been shown to be more powerful than the classical model.
It appears, in principle, that the laws of quantum mechanics allow a quantum computer to solve certain mathematical problems more rapidly than can be done using a classical computer. However, in order to build such a quantum computer a number of technological problems need to be overcome. A stepping stone to this goal is the implementation of relatively simple quantum algorithms using current experimental techniques.This paper explores small scale quantum algorithms from two different perspectives. Firstly, it will be shown how small scale quantum algorithms can be tailored to fit current schemes for implementing a quantum computer. Secondly, I will review a simple model of computation, based on read-only-memory. This model allows the comparison of the space-efficiency of reversible error-free classical computation with reversible, error-free quantum computation. The quantum model has been shown to be more powerful than the classical model.
This paper discusses the deep connection between Number Theory, Cryptography, and Quantum Computing techniques in an endeavor to understand their application in developing new cryptographic techniques, optimization problems, and computational complexity. Like modular arithmetic, which uses prime factorization, in most quantum algorithms like Shor’s and Grover's algorithms, number theory is one of the significant paradigms. This work gives a detailed analysis of some mathematical derivation, theore,m and proof of these algorithms to their practical use as well as computational efficiency. Discussed issues include scaling, correction of errors, and unsolved concerns applying number theory; all discussed from the perspective of existing quantum architecture. Addressing this new research directions of the field, the paper also presents further developments in quantum cryptography, topological quantum computing, and the algorithmic area. In highlighting both theoretical and computational challenges, this work has shown that the synergy between number theory and quantum computing has the opportunity to revolutionize cryptography and optimization and to lay the groundwork for future quantum advancements
Quantum computers can execute algorithms that sometimes dramatically outperform classical computation. Undoubtedly the best-known example of this is Shor's discovery of an efficient quantum algorithm for factoring integers, whereas the same problem appears to be intractable on classical computers. Understanding what other computational problems can be solved significantly faster using quantum algorithms is one of the major challenges in the theory of quantum computation, and such algorithms motivate the formidable task of building a large-scale quantum computer. This article will review the current state of quantum algorithms, focusing on algorithms for problems with an algebraic flavor that achieve an apparent superpolynomial speedup over classical computation.