Basic Quantum Algorithms
- URL: http://arxiv.org/abs/2201.10574v6
- Date: Wed, 12 Apr 2023 22:13:10 GMT
- Title: Basic Quantum Algorithms
- Authors: Renato Portugal
- Abstract summary: Quantum computing is evolving so rapidly that it forces us to revisit, rewrite, and update the foundations of the theory.
Basic Quantum Algorithms revisits the earliest quantum algorithms.
- Score: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Quantum computing is evolving so rapidly that it forces us to revisit,
rewrite, and update the foundations of the theory. Basic Quantum Algorithms
revisits the earliest quantum algorithms. The journey began in 1985 with
Deutsch attempting to evaluate a function at two domain points simultaneously.
Then, in 1992, Deutsch and Jozsa created a quantum algorithm that determines
whether a Boolean function is constant or balanced. The following year,
Bernstein and Vazirani realized that the same algorithm could be used to
identify a specific Boolean function within a set of linear Boolean functions.
In 1994, Simon introduced a novel quantum algorithm that determined whether a
function was one-to-one or two-to-one exponentially faster than any classical
algorithm for the same problem. That same year, Shor developed two
groundbreaking quantum algorithms for integer factoring and calculating
discrete logarithms, posing a threat to the widely used cryptography methods.
In 1995, Kitaev proposed an alternative version of Shor's algorithms that
proved valuable in numerous other applications. The following year, Grover
devised a quantum search algorithm that was quadratically faster than its
classical equivalent. With an emphasis on the circuit model, this work provides
a detailed description of all these remarkable algorithms.
Related papers
- Unconditional correctness of recent quantum algorithms for factoring and computing discrete logarithms [0.0]
In 2023, Regev proposed a multi-dimensional version of Shor's algorithm that requires far fewer quantum gates.
We prove a version of this conjecture using tools from analytic number theory.
As a result, we obtain an unconditional proof of correctness of this improved quantum algorithm.
arXiv Detail & Related papers (2024-04-25T09:30:19Z) - 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) - 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) - 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 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) - Benchmarking Small-Scale Quantum Devices on Computing Graph Edit
Distance [52.77024349608834]
Graph Edit Distance (GED) measures the degree of (dis)similarity between two graphs in terms of the operations needed to make them identical.
In this paper we present a comparative study of two quantum approaches to computing GED.
arXiv Detail & Related papers (2021-11-19T12:35:26Z) - On Applying the Lackadaisical Quantum Walk Algorithm to Search for
Multiple Solutions on Grids [63.75363908696257]
The lackadaisical quantum walk is an algorithm developed to search graph structures whose vertices have a self-loop of weight $l$.
This paper addresses several issues related to applying the lackadaisical quantum walk to search for multiple solutions on grids successfully.
arXiv Detail & Related papers (2021-06-11T09:43:09Z) - Quantum Inspired Adaptive Boosting [0.0]
We show that the quantum ensemble method does not have advantage over classical algorithms.
We propose methods inspired by combining the quantum ensemble method with adaptive boosting.
The algorithms were tested and found to be comparable to the AdaBoost algorithm on publicly available data sets.
arXiv Detail & Related papers (2021-02-01T16:33:14Z) - Characterization of exact one-query quantum algorithms (ii): for partial
functions [0.2741266294612775]
The query model (or black-box model) has attracted much attention from the communities of both classical and quantum computing.
Usually, quantum advantages are revealed by presenting a quantum algorithm that has a better query complexity than its classical counterpart.
For example, the well-known quantum algorithms including Deutsch-Jozsa algorithm, Simon algorithm and Grover algorithm all show a considerable advantage of quantum computing from the viewpoint of query complexity.
arXiv Detail & Related papers (2020-08-27T09:06:34Z) - Quadratic Sieve Factorization Quantum Algorithm and its Simulation [16.296638292223843]
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.
arXiv Detail & Related papers (2020-05-24T07:14:19Z)
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.