Quantum algorithm for finding minimum values in a Quantum Random Access Memory

• URL: http://arxiv.org/abs/2301.05122v1
• Date: Thu, 12 Jan 2023 16:22:17 GMT
• Title: Quantum algorithm for finding minimum values in a Quantum Random Access Memory
• Authors: Anton S. Albino, Lucas Q. Galv\~ao, Ethan Hansen, Mauro Q. Nooblath Neto, Clebson Cruz
• Abstract summary: The optimal classical deterministic algorithm can find the minimum value with a time complexity that grows linearly with the number of elements in the database. We propose a quantum algorithm for finding the minimum value of a database, which is quadratically faster than its best classical analogs.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Finding the minimum value in an unordered database is a common and fundamental task in computer science. However, the optimal classical deterministic algorithm can find the minimum value with a time complexity that grows linearly with the number of elements in the database. In this paper, we present the proposal of a quantum algorithm for finding the minimum value of a database, which is quadratically faster than its best classical analogs. We assume a Quantum Random Access Memory (QRAM) that stores values from a database and perform an iterative search based on an oracle whose role is to limit the searched values by controlling the states of the most significant qubits. A complexity analysis was performed in order to demonstrate the advantage of this quantum algorithm over its classical counterparts. Furthermore, we demonstrate how the proposed algorithm would be used in an unsupervised machine learning task through a quantum version of the K-means algorithm.

Related papers

• 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)
• Quantum Search Approaches to Sampling-Based Motion Planning [0.0]
  We present a novel formulation of traditional sampling-based motion planners as database-oracle structures that can be solved via quantum search algorithms. We consider two complementary scenarios: for simpler sparse environments, we formulate the Quantum Full Path Search Algorithm (q-FPS), which creates a superposition of full random path solutions. For dense unstructured environments, we formulate the Quantum Rapidly Exploring Random Tree algorithm, q-RRT, that creates quantum superpositions of possible parent-child connections.
  arXiv  Detail & Related papers  (2023-04-10T19:12:25Z)
• Optimization of probabilistic quantum search algorithm with a priori information [0.21756081703276003]
  Grover's quantum search algorithm is a typical quantum algorithm that proves the superiority of quantum computing over classical computing. We consider a probabilistic Grover search algorithm allowing nonzero probability of failure for a database with a general a priori probability distribution of the elements.
  arXiv  Detail & Related papers  (2023-04-06T04:33:37Z)
• 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)
• Hardware Efficient Quantum Search Algorithm [17.74233101199813]
  We propose a novel hardware efficient quantum search algorithm to overcome this challenge. Our key idea is to replace the global diffusion operation with low-cost local diffusions. The circuit cost reduction leads to a remarkable improvement in the system success rates.
  arXiv  Detail & Related papers  (2021-03-26T01:08:50Z)
• Efficient Algorithms for Causal Order Discovery in Quantum Networks [44.356294905844834]
  Given black-box access to the input and output systems, we develop the first efficient quantum causal order discovery algorithm. We model the causal order with quantum combs, and our algorithms output the order of inputs and outputs that the given process is compatible with. Our algorithms will provide efficient ways to detect and optimize available transmission paths in quantum communication networks.
  arXiv  Detail & Related papers  (2020-12-03T07:12:08Z)
• Quantum Search for Scaled Hash Function Preimages [1.3299507495084417]
  We present the implementation of Grover's algorithm in a quantum simulator to perform a quantum search for preimages of two scaled hash functions. We show that strategies that suggest a shortcut based on sampling the quantum register after a few steps of Grover's algorithm can only provide some marginal practical advantage in terms of error mitigation.
  arXiv  Detail & Related papers  (2020-09-01T18:00:02Z)
• 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)
• Statistical Limits of Supervised Quantum Learning [90.0289160657379]
  We show that if the bound on the accuracy is taken into account, quantum machine learning algorithms for supervised learning cannot achieve polylogarithmic runtimes in the input dimension. We conclude that, when no further assumptions on the problem are made, quantum machine learning algorithms for supervised learning can have at most speedups over efficient classical algorithms.
  arXiv  Detail & Related papers  (2020-01-28T17:35:32Z)

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.