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:2403.14703 · Physical Review A

Using quantum computers to identify prime numbers via entanglement dynamics

Victor F. dos Santos, Jonas Maziero

Published Aug 2, 2024• 3 citations
arXivHTMLPDF

Abstract

Recently, the entanglement dynamics of two harmonic oscillators initially prepared in a separable-coherent state was demonstrated to offer a pathway for prime number identification. This article presents a generalized approach and outlines a deterministic algorithm making possible the implementation of this theoretical concept on scalable fault-tolerant qubit-based quantum computers. We prove that the diagonal unitary operations employed in our algorithm exhibit a polynomial-time complexity of degree two, contrasting with the previously reported exponential complexity of general diagonal unitaries.

DOI
10.1103/physreva.110.022405

Related papers

Identification of prime numbers with quantum computers

Victor Penchel Alvarenga Balthar dos Santos

The identification of prime numbers is an ancient area of study with applications in cryptography and fundamental mathematical problems, such as the Riemann Hypothesis (RH). Classical algorithms, like the Sieve of Eratosthenes and the AKS Primality Test, are efficient examples for this purpose. However, quantum computing (QC), with its superior theoretical capacity, has inspired the development of quantum algorithms, many of which are probabilistic or rely on the RH. In this dissertation, we propose a deterministic and efficient quantum algorithm that generalizes a recent method from quantum optics to identify prime numbers through entanglement dynamics. We adapted this method for QC, removing several constraints from the original work, and showed that discrete bipartite quantum systems prepared in certain initial states can be used to identify prime numbers through the Fourier modes of the reduced purity of one of the subsystems. The proposed algorithm is viable for implementation in future fault-tolerant QC systems. The initial steps involve encoding the system in qubits and preparing a maximally superposed state. In the state evolution step, we use Walsh matrices to efficiently prepare diagonal unitary gates. The reduced purity is measured using a modified controlled-SWAP test, and the Fourier modes are obtained via the numerical calculation of a one-dimensional integral. Subsequently, we present the simulations performed in Qiskit, which demonstrate the validity of the algorithm in all its stages. Finally, we discuss the computational cost, quantifying the number of elementary gates as a function of the number of qubits and speculating the total computational complexity of the algorithm.

•Sep 30, 2024•0 citations

On the Synthesis of Quantum Circuits for Diagonal Operators in Quantum Computation

Jonathan Welch

Diagonal unitary operators are commonly found in many quantum algorithms. They find application as analytical potential operators for quantum simulation, as well as for complex oracles used in quantum searches. However, in order to implement a quantum algorithm on a given quantum device, each operator must be decomposed into a sequence of fault-tolerant, device-level instructions. In general, to implement an $n$-qubit diagonal unitary {\\em exactly} on a quantum computer generally requires $2^{n+1}-3$ one- and two-qubit gates. However, for most practical implementations of diagonal unitaries, some degree of approximation will be necessary if the circuit is to be efficient. In this thesis we develop two complementary methods for the approximate synthesis of quantum circuits for diagonal unitaries. We show how to apply these techniques to real-space quantum simulation and show how efficient high fidelity quantum simulations can be implemented with low-depth quantum circuits.

•Sep 29, 2015•2 citations

Quantum computers that can be simulated classically in polynomial time

Leslie Gabriel Valiant

A model of quantum computation based on unitary matrix operations was introduced by Feynman and Deutsch. It has been asked whether the power of this model exceeds that of classical Turing machines. We show here that a significant class of these quantum computations can be simulated classically in polynomial time. In particular we show that two-bit operations characterized by 4 \times 4 matrices in which the sixteen entries obey a set of five polynomial relations can be composed according to certain rules to yield a class of circuits that can be simulated classically in polynomial time. This contrasts with the known universality of two-bit operations, and demonstrates that efficient quantum computation of restricted classes is reconcilable with the Polynomial Time Turing Hypothesis. In other words it is possible that quantum phenomena can be used in a scalable fashion to make computers but that they do not have superpolynomial speedups compared to Turing machines for any problem. The techniques introduced bring the quantum computational model within the realm of algebraic complexity theory. In a manner consistent will one view of quantum physics, the wave function is simulated deterministically, and randomization arises only in the course of making measurements. The results generalize the quantum model in that they do not require the matrices to be unitary. In a different direction these techniques also yield deterministic polynomial time algorithms for the decision and parity problems for certain classes of read-twice Boolean formulae. All our results are based on the use of gates that are defined in terms of their graph matching properties.

ACM Symposium on Theory of Computing (STOC)•Jul 6, 2001•90 citations

Prime Number Identification Demonstrated with Quantum Processors Using a New Rescaling-Based Noise Mitigation Technique

Victor F. dos Santos, Victor P. Brasil, Pedro A. S. Contri +1 more

We implement a quantum protocol for prime number identification based on entanglement dynamics, using IBM quantum processors. The method links the primality of an integer to specific Fourier components extracted from the time evolution of entanglement in a bipartite quantum system. To mitigate experimental noise, we introduce a noise-mitigation method based on a global rescaling factor, which is calibrated on a subset of circuits and extrapolated across different configurations. Theoretical support is provided by a new analytical bound for the Fourier modes derived assuming an initial uniform superposition state. This new bound enhances the separation between prime and composite numbers under moderate experimental deviations. These results represent a step toward practical number-theoretic applications on noisy intermediate-scale quantum (NISQ) devices.

quant-pharXiv:2605.28964•Advanced Quantum Technologies•May 29, 2026•0 citations

Factoring semi-primes with (quantum) SAT-solvers

Michele Mosca, Sebastian R. Verschoor

The computational difficulty of factoring large integers forms the basis of security for RSA public-key cryptography. The best-known factoring algorithms for classical computers run in sub-exponential time. The integer factorization problem can be reduced to the Boolean Satisfiability problem (SAT). While this reduction has proved to be useful for studying SAT solvers, large integers have not been factored via such a reduction. Shor's quantum factoring algorithm factors integers in expected polynomial time. Large-scale fault-tolerant quantum computers capable of implementing Shor's algorithm are not yet available, preventing relevant benchmarking experiments. Recently, several authors have attempted quantum factorizations via reductions to SAT or similar NP-hard problems. While this approach may shed light on algorithmic approaches for quantum solutions to NP-hard problems, in this paper we study and question its practicality. We find no evidence that this is a viable path toward factoring large numbers, even for scalable fault-tolerant quantum computers, as well as for various quantum annealing or other special purpose quantum hardware.

arXiv:1902.01448•Scientific Reports•May 14, 2022•22 citations

Logarithmic-depth quantum state preparation of polynomials

Baptiste Claudon, Alexis Lucas, Jean-Philip Piquemal +2 more

Quantum state preparation is a central primitive in many quantum algorithms, yet it is generally resource intensive, with efficient constructions known only for structured families of states. This work introduces a method for preparing quantum states whose amplitudes are given by a degree$-d$ polynomial, using circuits with logarithmic depth in the number $n$ of qubits and only $\mathcal O(n)$ ancilla qubits, improving previous approaches that required linear-depth circuits. The construction first relies on a block-encoding of an affine diagonal operator based on its Pauli-basis decomposition, which involves only $n$ terms. A modified linear-combination-of-unitaries (LCU) technique is introduced to implement this decomposition in logarithmic depth, together with a novel circuit for the EXACT-one oracle that flags basis states in which exactly one qubit is in the state $|1\rangle$. It then uses a generalized quantum eigenvalue transformation (GQET) to promote this affine operator to an arbitrary degree polynomial. Theoretical analysis and numerical simulations are reported along with a proof-of-principle implementation on a trapped-ion quantum processor using $14$ qubits and more than $500$ primitive quantum gates. Because polynomial approximations are ubiquitous in scientific computing, this construction provides a scalable and resource-efficient approach to quantum state preparation, further improving the potential of quantum algorithms in fields such as chemistry, physics, engineering, and finance.

quant-pharXiv:2603.16527•Mar 18, 2026•4 citations
Recently, the entanglement dynamics of two harmonic oscillators initially prepared in a separable-coherent state was demonstrated to offer a pathway for prime number identification. This article presents a generalized approach and outlines a deterministic algorithm making possible the implementation of this theoretical concept on scalable fault-tolerant qubit-based quantum computers. We prove that the diagonal unitary operations employed in our algorithm exhibit a polynomial-time complexity of degree two, contrasting with the previously reported exponential complexity of general diagonal unitaries.
The identification of prime numbers is an ancient area of study with applications in cryptography and fundamental mathematical problems, such as the Riemann Hypothesis (RH). Classical algorithms, like the Sieve of Eratosthenes and the AKS Primality Test, are efficient examples for this purpose. However, quantum computing (QC), with its superior theoretical capacity, has inspired the development of quantum algorithms, many of which are probabilistic or rely on the RH. In this dissertation, we propose a deterministic and efficient quantum algorithm that generalizes a recent method from quantum optics to identify prime numbers through entanglement dynamics. We adapted this method for QC, removing several constraints from the original work, and showed that discrete bipartite quantum systems prepared in certain initial states can be used to identify prime numbers through the Fourier modes of the reduced purity of one of the subsystems. The proposed algorithm is viable for implementation in future fault-tolerant QC systems. The initial steps involve encoding the system in qubits and preparing a maximally superposed state. In the state evolution step, we use Walsh matrices to efficiently prepare diagonal unitary gates. The reduced purity is measured using a modified controlled-SWAP test, and the Fourier modes are obtained via the numerical calculation of a one-dimensional integral. Subsequently, we present the simulations performed in Qiskit, which demonstrate the validity of the algorithm in all its stages. Finally, we discuss the computational cost, quantifying the number of elementary gates as a function of the number of qubits and speculating the total computational complexity of the algorithm.
Diagonal unitary operators are commonly found in many quantum algorithms. They find application as analytical potential operators for quantum simulation, as well as for complex oracles used in quantum searches. However, in order to implement a quantum algorithm on a given quantum device, each operator must be decomposed into a sequence of fault-tolerant, device-level instructions. In general, to implement an nnn-qubit diagonal unitary {\\em exactly} on a quantum computer generally requires 2n+1−32^{n+1}-32n+1−3 one- and two-qubit gates. However, for most practical implementations of diagonal unitaries, some degree of approximation will be necessary if the circuit is to be efficient. In this thesis we develop two complementary methods for the approximate synthesis of quantum circuits for diagonal unitaries. We show how to apply these techniques to real-space quantum simulation and show how efficient high fidelity quantum simulations can be implemented with low-depth quantum circuits.
A model of quantum computation based on unitary matrix operations was introduced by Feynman and Deutsch. It has been asked whether the power of this model exceeds that of classical Turing machines. We show here that a significant class of these quantum computations can be simulated classically in polynomial time. In particular we show that two-bit operations characterized by 4 \times 4 matrices in which the sixteen entries obey a set of five polynomial relations can be composed according to certain rules to yield a class of circuits that can be simulated classically in polynomial time. This contrasts with the known universality of two-bit operations, and demonstrates that efficient quantum computation of restricted classes is reconcilable with the Polynomial Time Turing Hypothesis. In other words it is possible that quantum phenomena can be used in a scalable fashion to make computers but that they do not have superpolynomial speedups compared to Turing machines for any problem. The techniques introduced bring the quantum computational model within the realm of algebraic complexity theory. In a manner consistent will one view of quantum physics, the wave function is simulated deterministically, and randomization arises only in the course of making measurements. The results generalize the quantum model in that they do not require the matrices to be unitary. In a different direction these techniques also yield deterministic polynomial time algorithms for the decision and parity problems for certain classes of read-twice Boolean formulae. All our results are based on the use of gates that are defined in terms of their graph matching properties.
We implement a quantum protocol for prime number identification based on entanglement dynamics, using IBM quantum processors. The method links the primality of an integer to specific Fourier components extracted from the time evolution of entanglement in a bipartite quantum system. To mitigate experimental noise, we introduce a noise-mitigation method based on a global rescaling factor, which is calibrated on a subset of circuits and extrapolated across different configurations. Theoretical support is provided by a new analytical bound for the Fourier modes derived assuming an initial uniform superposition state. This new bound enhances the separation between prime and composite numbers under moderate experimental deviations. These results represent a step toward practical number-theoretic applications on noisy intermediate-scale quantum (NISQ) devices.
The computational difficulty of factoring large integers forms the basis of security for RSA public-key cryptography. The best-known factoring algorithms for classical computers run in sub-exponential time. The integer factorization problem can be reduced to the Boolean Satisfiability problem (SAT). While this reduction has proved to be useful for studying SAT solvers, large integers have not been factored via such a reduction. Shor's quantum factoring algorithm factors integers in expected polynomial time. Large-scale fault-tolerant quantum computers capable of implementing Shor's algorithm are not yet available, preventing relevant benchmarking experiments. Recently, several authors have attempted quantum factorizations via reductions to SAT or similar NP-hard problems. While this approach may shed light on algorithmic approaches for quantum solutions to NP-hard problems, in this paper we study and question its practicality. We find no evidence that this is a viable path toward factoring large numbers, even for scalable fault-tolerant quantum computers, as well as for various quantum annealing or other special purpose quantum hardware.
Quantum state preparation is a central primitive in many quantum algorithms, yet it is generally resource intensive, with efficient constructions known only for structured families of states. This work introduces a method for preparing quantum states whose amplitudes are given by a degree−d-d−d polynomial, using circuits with logarithmic depth in the number nnn of qubits and only O(n)\mathcal O(n)O(n) ancilla qubits, improving previous approaches that required linear-depth circuits. The construction first relies on a block-encoding of an affine diagonal operator based on its Pauli-basis decomposition, which involves only nnn terms. A modified linear-combination-of-unitaries (LCU) technique is introduced to implement this decomposition in logarithmic depth, together with a novel circuit for the EXACT-one oracle that flags basis states in which exactly one qubit is in the state ∣1⟩|1\rangle∣1⟩. It then uses a generalized quantum eigenvalue transformation (GQET) to promote this affine operator to an arbitrary degree polynomial. Theoretical analysis and numerical simulations are reported along with a proof-of-principle implementation on a trapped-ion quantum processor using 141414 qubits and more than 500500500 primitive quantum gates. Because polynomial approximations are ubiquitous in scientific computing, this construction provides a scalable and resource-efficient approach to quantum state preparation, further improving the potential of quantum algorithms in fields such as chemistry, physics, engineering, and finance.