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

International Journal of Mathematics Trends and Technology

A New Efficient Quantum Algorithm for Computing Primality Measure

Gaurav Saxena, Shilpee Srivastava Saxena

Published Jun 25, 2021• 0 citations
Publisher
DOI
10.14445/22315373/ijmtt-v67i6p504

Related papers

A quantum algorithm for computing the Carmichael function

Juan Carlos García-Escartín

Quantum computers can solve many number theory problems efficiently. Using the efficient quantum algorithm for order finding as an oracle, this paper presents an algorithm that computes the Carmichael function for any integer $N$ with a probability as close to 1 as desired. The algorithm requires $O((\log n )^3n^3)$ quantum operations, or $O(\log\log n (\log n)^4 n^2)$ operations using fast multiplication. Verification, quantum optimizations and applications to RSA and primality tests are also discussed.

arXiv:2111.02488•Nov 3, 2021•1 citation

A New Efficient Quantum Algorithm for Solving NP-complete Problems

Dhananjay P. Mehendale

•Jan 1, 2026•0 citations

A New Simple and Efficient Quantum Algorithm for Factoring Composite Integers

Dhananjay P. Mehendale

Quantum Physics Letters•Aug 1, 2018•1 citation

A Combinatorial, Primal-Dual Approach to Semidefinite Programs

Sanjeev Arora, Satyen Kale

Semidefinite programs (SDPs) have been used in many recent approximation algorithms. We develop a general primal-dual approach to solve SDPs using a generalization of the well-known multiplicative weights update rule to symmetric matrices. For a number of problems, such as S parsest C ut and B alanced S eparator in undirected and directed weighted graphs, M in U n C ut and M in 2CNF D eletion , this yields combinatorial approximation algorithms that are significantly more efficient than interior point methods. The design of our primal-dual algorithms is guided by a robust analysis of rounding algorithms used to obtain integer solutions from fractional ones. Our ideas have proved useful in quantum computing, especially the recent result of Jain et al. [2011] that QIP = PSPACE.

Journal of the ACM•May 4, 2016•82 citations

Quantum Algorithms for Integer Factorization

Song Yuan Yan

Springer eBooks•Jan 1, 2015•0 citations

Prime Number Primality Testing via Quantum Lattice-Based Search

Jincheng Zhang

This paper introduces a novel quantum algorithm for efficient primality testing, aiming to surpass the limitations of classical methods through the application of lattice-based search. We detail the design of a quantum circuit that explores the prime number space, leveraging superposition and entanglement to achieve significantly reduced computational complexity. The core mechanism centers around quantum search, allowing for parallel exploration of the vast space of possible prime factors. We present a comprehensive analysis of the algorithm's performance, including a detailed mathematical justification of its efficiency gains compared to established techniques. The paper concludes with a discussion of the potential implications of this quantum approach for cryptography and other applications requiring prime number verification.

•Aug 31, 2026•0 citations
Quantum computers can solve many number theory problems efficiently. Using the efficient quantum algorithm for order finding as an oracle, this paper presents an algorithm that computes the Carmichael function for any integer NNN with a probability as close to 1 as desired. The algorithm requires O((log⁡n)3n3)O((\log n )^3n^3)O((logn)3n3) quantum operations, or O(log⁡log⁡n(log⁡n)4n2)O(\log\log n (\log n)^4 n^2)O(loglogn(logn)4n2) operations using fast multiplication. Verification, quantum optimizations and applications to RSA and primality tests are also discussed.
Semidefinite programs (SDPs) have been used in many recent approximation algorithms. We develop a general primal-dual approach to solve SDPs using a generalization of the well-known multiplicative weights update rule to symmetric matrices. For a number of problems, such as S parsest C ut and B alanced S eparator in undirected and directed weighted graphs, M in U n C ut and M in 2CNF D eletion , this yields combinatorial approximation algorithms that are significantly more efficient than interior point methods. The design of our primal-dual algorithms is guided by a robust analysis of rounding algorithms used to obtain integer solutions from fractional ones. Our ideas have proved useful in quantum computing, especially the recent result of Jain et al. [2011] that QIP = PSPACE.
This paper introduces a novel quantum algorithm for efficient primality testing, aiming to surpass the limitations of classical methods through the application of lattice-based search. We detail the design of a quantum circuit that explores the prime number space, leveraging superposition and entanglement to achieve significantly reduced computational complexity. The core mechanism centers around quantum search, allowing for parallel exploration of the vast space of possible prime factors. We present a comprehensive analysis of the algorithm's performance, including a detailed mathematical justification of its efficiency gains compared to established techniques. The paper concludes with a discussion of the potential implications of this quantum approach for cryptography and other applications requiring prime number verification.