Basic Quantum Algorithms

• URL: http://arxiv.org/abs/2201.10574v7
• Date: Wed, 11 Sep 2024 16:41:54 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

• 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)
• 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)
• 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.