Related papers: A quantum algorithm for computing the Carmichael function

A quantum algorithm for computing the Carmichael function

URL: http://arxiv.org/abs/2111.02488v1
Date: Wed, 3 Nov 2021 19:30:27 GMT
Title: A quantum algorithm for computing the Carmichael function
Authors: Juan Carlos Garcia-Escartin
Abstract summary: Quantum computers can solve many number theory problems efficiently. This paper presents an algorithm that computes the Carmichael function for any integer $N$ with a probability as close to 1 as desired.
Score: 0.0
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: 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.

Related papers

Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
Recently proposed quantum algorithm arXiv:2206.14999 is based on semidefinite programming (SDP) We generalize the SDP-inspired quantum algorithm to sum-of-squares. Our results show that our algorithm is suitable for large problems and approximate the best known classicals.
arXiv Detail & Related papers (2024-08-14T19:04:13Z)
Calculating response functions of coupled oscillators using quantum phase estimation [40.31060267062305]
We study the problem of estimating frequency response functions of systems of coupled, classical harmonic oscillators using a quantum computer. Our proposed quantum algorithm operates in the standard $s-sparse, oracle-based query access model. We show that a simple adaptation of our algorithm solves the random glued-trees problem in time.
arXiv Detail & Related papers (2024-05-14T15:28:37Z)
Quantum algorithms for Hopcroft's problem [45.45456673484445]
We study quantum algorithms for Hopcroft's problem which is a fundamental problem in computational geometry. The classical complexity of this problem is well-studied, with the best known algorithm running in $O(n4/3)$ time. Our results are two different quantum algorithms with time complexity $widetilde O(n5/6)$.
arXiv Detail & Related papers (2024-05-02T10:29:06Z)
Generalized quantum Arimoto-Blahut algorithm and its application to quantum information bottleneck [55.22418739014892]
We generalize the quantum Arimoto-Blahut algorithm by Ramakrishnan et al. We apply our algorithm to the quantum information bottleneck with three quantum systems. Our numerical analysis shows that our algorithm is better than their algorithm.
arXiv Detail & Related papers (2023-11-19T00:06:11Z)
Integer Factorization by Quantum Measurements [0.0]
Quantum algorithms are at the heart of the ongoing efforts to use quantum mechanics to solve computational problems unsolvable on classical computers. Among the known quantum algorithms, a special role is played by the Shor algorithm, i.e. a quantum-time algorithm for integer factorization. Here we present a different algorithm for integer factorization based on another genuine quantum property: quantum measurement.
arXiv Detail & Related papers (2023-09-19T17:00:01Z)
An Efficient Quantum Factoring Algorithm [0.27195102129094995]
We show that $n$bit integers can be factorized by independently running a quantum circuit with $tildeO(n3/2)$. The correctness of the algorithm relies on a number-theoretic assumption reminiscent of those used in subexponential classical factorization algorithms.
arXiv Detail & Related papers (2023-08-12T13:57:38Z)
Quantum Complexity for Discrete Logarithms and Related Problems [7.077306859247421]
We establish a generic model of quantum computation for group-theoretic problems, which we call the quantum generic group model. We show the quantum complexity lower bounds and almost matching algorithms of the DL and related problems in this model. variations of Shor's algorithm can take advantage of classical computations to reduce the number of quantum group operations.
arXiv Detail & Related papers (2023-07-06T15:32:50Z)
Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
Bernstein-Vazirani algorithm allows one to determine a bit string encoded into an oracle. We analyze in detail the quantum resources in the Bernstein-Vazirani algorithm. We show that in the absence of entanglement, the performance of the algorithm is directly related to the amount of quantum coherence in the initial state.
arXiv Detail & Related papers (2022-05-26T20:32:36Z)
Time and Query Optimal Quantum Algorithms Based on Decision Trees [2.492300648514128]
We show that a quantum algorithm can be implemented in time $tilde O(sqrtGT)$. Our algorithm is based on non-binary span programs and their efficient implementation.
arXiv Detail & Related papers (2021-05-18T06:51:11Z)
An integer factorization algorithm which uses diffusion as a computational engine [0.0]
We develop an algorithm which computes a divisor of an integer $N$, which is assumed to be neither prime nor the power of a prime. By comparison, Shor's algorithm is known to use at most $O(log N)2log (log N) log (log log N)$ quantum steps on a quantum computer.
arXiv Detail & Related papers (2021-04-23T14:11:33Z)
Quantum Gram-Schmidt Processes and Their Application to Efficient State Read-out for Quantum Algorithms [87.04438831673063]
We present an efficient read-out protocol that yields the classical vector form of the generated state. Our protocol suits the case that the output state lies in the row space of the input matrix. One of our technical tools is an efficient quantum algorithm for performing the Gram-Schmidt orthonormal procedure.
arXiv Detail & Related papers (2020-04-14T11:05:26Z)

This list is automatically generated from the titles and abstracts of the papers in this site.