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:0804.1109 · Lecture notes in computer science

Classical and Quantum Algorithms for Exponential Congruences

Wim van Dam, Igor E. Shparlinski

Published Jan 1, 2008• 28 citations
arXivHTMLPDF
DOI
10.1007/978-3-540-89304-2_1

Related papers

On zeros of exponential polynomials and quantum algorithms

Yoshitaka Sasaki

arXiv:0908.1657•Quantum Information Processing•Oct 21, 2009•4 citations

Quantum speedup to some types of polynomial equations

Changpeng Shao

In this paper, we consider three types of polynomial equations in quantum computer: linear divisibility equation, which belongs to a special type of binary-quadratic Diophantine equation; quadratic congruence equation with restriction in the solution and exponential congruence equation in finite field. Quantum algorithms based on Grover's algorithm and Shor's algorithm to these problems are given. As for the exponential congruence equation, which has been considered by Dam and Shparlinski \cite{dam} at 2008, a relatively simple quantum algorithm is given here. And some other results and generalizations are discovered.

arXiv:1711.09546•Nov 27, 2017•0 citations

Fast Quantum Algorithms of Solving an Instance of Quadratic Congruence on a Quantum Computer

Weng-Long Chang, Mang Feng

It is assumed that P is the product of two prime numbers q1and q2. If there is an integer 02= C (mod P), i.e., the congruence has a solution, then C is said to be a quadratic congruence (mod P). Quadratic congruence (mod P) is a NP-complete problem. If the value of C is equal to one, then four integer solutions for M2= 1 (mod P) are, respectively, b, P - b, 1 and P - 1, where 12= 1 (mod P) can be found by means of the proposed quantum algorithms with polynomial quantum gates, polynomial quantum bits and the successful probability that is the same as that of Shor's order-finding algorithm.

International Symposium on Parallel Architectures, Algorithms and Programming•Dec 1, 2012•0 citations

ON 3-VARIABLE EXPONENTIAL POLYNOMIALS AND QUANTUM ALGORITHMS

Yasuo Ohno, Yoshitaka Sasaki, Chika Yamazaki

•Jul 16, 2012•0 citations

Quantum Algorithms for Integer Factorization

Song Yuan Yan

Springer eBooks•Jan 1, 2015•0 citations

On the application of matrix congruence to QUBO formulations for systems of linear equations

Sun Woo Park, Hyunju Lee, Byung Chun Kim +2 more

Recent studies on quantum computing algorithms focus on excavating features of quantum computers which have potential for contributing to computational model enhancements. Among various approaches, quantum annealing methods effectively parallelize quadratic unconstrained binary optimization (QUBO) formulations of systems of linear equations. In this paper, we simplify these formulations by exploiting congruence of real symmetric matrices to diagonal matrices. We further exhibit computational merits of the proposed QUBO models, which can outperform classical algorithms such as QR and SVD decomposition.

arXiv:2111.00747•International Conference on Information and Communication Technology Convergence (ICTC)•Oct 20, 2021•1 citation
In this paper, we consider three types of polynomial equations in quantum computer: linear divisibility equation, which belongs to a special type of binary-quadratic Diophantine equation; quadratic congruence equation with restriction in the solution and exponential congruence equation in finite field. Quantum algorithms based on Grover's algorithm and Shor's algorithm to these problems are given. As for the exponential congruence equation, which has been considered by Dam and Shparlinski \cite{dam} at 2008, a relatively simple quantum algorithm is given here. And some other results and generalizations are discovered.
It is assumed that P is the product of two prime numbers q1and q2. If there is an integer 02= C (mod P), i.e., the congruence has a solution, then C is said to be a quadratic congruence (mod P). Quadratic congruence (mod P) is a NP-complete problem. If the value of C is equal to one, then four integer solutions for M2= 1 (mod P) are, respectively, b, P - b, 1 and P - 1, where 12= 1 (mod P) can be found by means of the proposed quantum algorithms with polynomial quantum gates, polynomial quantum bits and the successful probability that is the same as that of Shor's order-finding algorithm.
Recent studies on quantum computing algorithms focus on excavating features of quantum computers which have potential for contributing to computational model enhancements. Among various approaches, quantum annealing methods effectively parallelize quadratic unconstrained binary optimization (QUBO) formulations of systems of linear equations. In this paper, we simplify these formulations by exploiting congruence of real symmetric matrices to diagonal matrices. We further exhibit computational merits of the proposed QUBO models, which can outperform classical algorithms such as QR and SVD decomposition.