An Efficient Quantum Factoring Algorithm
- URL: http://arxiv.org/abs/2308.06572v3
- Date: Sun, 7 Jan 2024 12:57:45 GMT
- Title: An Efficient Quantum Factoring Algorithm
- Authors: Oded Regev
- Abstract summary: 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.
- Score: 0.27195102129094995
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We show that $n$-bit integers can be factorized by independently running a
quantum circuit with $\tilde{O}(n^{3/2})$ gates for $\sqrt{n}+4$ times, and
then using polynomial-time classical post-processing. The correctness of the
algorithm relies on a number-theoretic heuristic assumption reminiscent of
those used in subexponential classical factorization algorithms. It is
currently not clear if the algorithm can lead to improved physical
implementations in practice.
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) - Fast quantum integer multiplication with zero ancillas [0.5755004576310334]
We introduce a new paradigm for sub-quadratic-time quantum multiplication with zero ancilla qubits.
The only qubits involved are the input and output registers themselves.
Our algorithm has the potential to outperform previous problem sizes relevant in practice.
arXiv Detail & Related papers (2024-03-26T18:00:03Z) - When can you trust feature selection? -- I: A condition-based analysis
of LASSO and generalised hardness of approximation [49.1574468325115]
We show how no (randomised) algorithm can determine the correct support sets (with probability $> 1/2$) of minimisers of LASSO when reading approximate input.
For ill-posed inputs, the algorithm runs forever, hence, it will never produce a wrong answer.
For any algorithm defined on an open set containing a point with infinite condition number, there is an input for which the algorithm will either run forever or produce a wrong answer.
arXiv Detail & Related papers (2023-12-18T18:29:01Z) - 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) - Efficient quantum linear solver algorithm with detailed running costs [0.0]
We introduce a quantum linear solver algorithm combining ideasdiabatic quantum computing with filtering techniques based on quantum signal processing.
Our protocol reduces the cost of quantum linear solvers over state-of-the-art close to an order of magnitude for early implementations.
arXiv Detail & Related papers (2023-05-19T00:07:32Z) - Quantum Clustering with k-Means: a Hybrid Approach [117.4705494502186]
We design, implement, and evaluate three hybrid quantum k-Means algorithms.
We exploit quantum phenomena to speed up the computation of distances.
We show that our hybrid quantum k-Means algorithms can be more efficient than the classical version.
arXiv Detail & Related papers (2022-12-13T16:04:16Z) - 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) - Alternatives to a nonhomogeneous partial differential equation quantum
algorithm [52.77024349608834]
We propose a quantum algorithm for solving nonhomogeneous linear partial differential equations of the form $Apsi(textbfr)=f(textbfr)$.
These achievements enable easier experimental implementation of the quantum algorithm based on nowadays technology.
arXiv Detail & Related papers (2022-05-11T14:29:39Z) - Using Shor's algorithm on near term Quantum computers: a reduced version [0.0]
We introduce a reduced version of Shor's algorithm that proposes a step forward in increasing the range of numbers that can be factorized on noisy Quantum devices.
In particular, we have found noteworthy results in most cases, often being able to factor the given number with only one of the proposed algorithm.
arXiv Detail & Related papers (2021-12-23T15:36:59Z) - Benchmarks for quantum computers from Shor's algorithm [0.0]
Properties of Shor's algorithm and the related period-finding algorithm could serve as benchmarks for the operation of a quantum computer.
Distinctive universal behaviour is expected for the probability for success of the period-finding as the input quantum register is increased.
arXiv Detail & Related papers (2021-11-27T09:46:16Z) - A quantum algorithm for computing the Carmichael function [0.0]
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.
arXiv Detail & Related papers (2021-11-03T19:30:27Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.