Quadratic Sieve Factorization Quantum Algorithm and its Simulation
- URL: http://arxiv.org/abs/2005.11668v1
- Date: Sun, 24 May 2020 07:14:19 GMT
- Title: Quadratic Sieve Factorization Quantum Algorithm and its Simulation
- Authors: Amandeep Singh Bhatia, Ajay Kumar
- Abstract summary: We have designed a quantum variant of the second fastest classical factorization algorithm named "Quadratic Sieve"
We have constructed the simulation framework of quantized quadratic sieve algorithm using high-level programming language Mathematica.
- Score: 16.296638292223843
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Quantum computing is a winsome field that concerns with the behaviour and
nature of energy at the quantum level to improve the efficiency of
computations. In recent years, quantum computation is receiving much attention
for its capability to solve difficult problems efficiently in contrast to
classical computers. Specifically, some well-known public-key cryptosystems
depend on the difficulty of factoring large numbers, which takes a very long
time. It is expected that the emergence of a quantum computer has the potential
to break such cryptosystems by 2020 due to the discovery of powerful quantum
algorithms (Shor's factoring, Grover's search algorithm and many more). In this
paper, we have designed a quantum variant of the second fastest classical
factorization algorithm named "Quadratic Sieve". We have constructed the
simulation framework of quantized quadratic sieve algorithm using high-level
programming language Mathematica. Further, the simulation results are performed
on a classical computer to get a feel of the quantum system and proved that it
is more efficient than its classical variants from computational complexity
point of view.
Related papers
- Efficient Learning for Linear Properties of Bounded-Gate Quantum Circuits [63.733312560668274]
Given a quantum circuit containing d tunable RZ gates and G-d Clifford gates, can a learner perform purely classical inference to efficiently predict its linear properties?
We prove that the sample complexity scaling linearly in d is necessary and sufficient to achieve a small prediction error, while the corresponding computational complexity may scale exponentially in d.
We devise a kernel-based learning model capable of trading off prediction error and computational complexity, transitioning from exponential to scaling in many practical settings.
arXiv Detail & Related papers (2024-08-22T08:21:28Z) - Quantum Algorithm for a Stochastic Multicloud Model [0.0]
A quantum computing algorithm was applied to a problem of the atmospheric science.
The nature of a multi-cloud model was reproduced by utilizing outputs of computed quantum states.
Our results demonstrate that quantum computers can suitably solve some problems in atmospheric and oceanic phenomena.
arXiv Detail & Related papers (2024-06-17T09:14:20Z) - Quantum Subroutine for Variance Estimation: Algorithmic Design and Applications [80.04533958880862]
Quantum computing sets the foundation for new ways of designing algorithms.
New challenges arise concerning which field quantum speedup can be achieved.
Looking for the design of quantum subroutines that are more efficient than their classical counterpart poses solid pillars to new powerful quantum algorithms.
arXiv Detail & Related papers (2024-02-26T09:32:07Z) - Quantum Multiplication Algorithm Based on the Convolution Theorem [0.0]
We propose a quantum algorithm for integer multiplication with time complexity $O(sqrtnlog2 n)$.
Unlike the Harvey algorithm, our algorithm does not have the restriction of being applicable solely to extremely large numbers.
The paper also reviews the history and development of classical multiplication algorithms and motivates us to explore how quantum resources can provide new perspectives and possibilities for this fundamental problem.
arXiv Detail & Related papers (2023-06-14T12:40:54Z) - Quantum Annealing for Single Image Super-Resolution [86.69338893753886]
We propose a quantum computing-based algorithm to solve the single image super-resolution (SISR) problem.
The proposed AQC-based algorithm is demonstrated to achieve improved speed-up over a classical analog while maintaining comparable SISR accuracy.
arXiv Detail & Related papers (2023-04-18T11:57:15Z) - Quantum Machine Learning: from physics to software engineering [58.720142291102135]
We show how classical machine learning approach can help improve the facilities of quantum computers.
We discuss how quantum algorithms and quantum computers may be useful for solving classical machine learning tasks.
arXiv Detail & Related papers (2023-01-04T23:37:45Z) - 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) - Multiple Query Optimization using a Hybrid Approach of Classical and
Quantum Computing [1.7077661158850292]
We tackle the multiple query optimization problem (MQO) which is an important NP-hard problem in the area of data-intensive problems.
We propose a novel hybrid classical-quantum algorithm to solve the MQO on a gate-based quantum computer.
Our algorithm shows a qubit efficiency of close to 99% which is almost a factor of 2 higher compared to the state of the art implementation.
arXiv Detail & Related papers (2021-07-22T08:12:49Z) - Digitized Adiabatic Quantum Factorization [3.53163169498295]
We propose an alternative factorization method, within the digitized-adiabatic quantum computing paradigm, by digitizing an adiabatic quantum factorization algorithm.
We find that this fast factorization algorithm is suitable for available gate-based quantum computers.
arXiv Detail & Related papers (2021-05-19T13:26:23Z) - An Application of Quantum Annealing Computing to Seismic Inversion [55.41644538483948]
We apply a quantum algorithm to a D-Wave quantum annealer to solve a small scale seismic inversions problem.
The accuracy achieved by the quantum computer is at least as good as that of the classical computer.
arXiv Detail & Related papers (2020-05-06T14:18:44Z) - Quantum Solver of Contracted Eigenvalue Equations for Scalable Molecular
Simulations on Quantum Computing Devices [0.0]
We introduce a quantum solver of contracted eigenvalue equations, the quantum analogue of classical methods for the energies.
We demonstrate the algorithm though computations on both a quantum simulator and two IBM quantum processing units.
arXiv Detail & Related papers (2020-04-23T18:35:26Z)
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.