Grover's Algorithm Offers No Quantum Advantage

• URL: http://arxiv.org/abs/2303.11317v1
• Date: Mon, 20 Mar 2023 17:56:20 GMT
• Title: Grover's Algorithm Offers No Quantum Advantage
• Authors: E.M. Stoudenmire and Xavier Waintal
• Abstract summary: Grover's algorithm is one of the primary algorithms offered as evidence that quantum computers can provide an advantage over classical computers. We construct a quantum inspired algorithm, executable on a classical computer, that performs Grover's task in linear number of call to the oracle. We critically examine the possibility of a practical speedup, a possibility that depends on the nature of the quantum circuit associated with the oracle.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Grover's algorithm is one of the primary algorithms offered as evidence that quantum computers can provide an advantage over classical computers. It involves an "oracle" (external quantum subroutine) which must be specified for a given application and whose internal structure is not part of the formal scaling of the quantum speedup guaranteed by the algorithm. Grover's algorithm also requires exponentially many steps to succeed, raising the question of its implementation on near-term, non-error-corrected hardware and indeed even on error-corrected quantum computers. In this work, we construct a quantum inspired algorithm, executable on a classical computer, that performs Grover's task in a linear number of call to the oracle - an exponentially smaller number than Grover's algorithm - and demonstrate this algorithm explicitly for boolean satisfiability problems (3-SAT). Our finding implies that there is no a priori theoretical quantum speedup associated with Grover's algorithm. We critically examine the possibility of a practical speedup, a possibility that depends on the nature of the quantum circuit associated with the oracle. We argue that the unfavorable scaling of the success probability of Grover's algorithm, which in the presence of noise decays as the exponential of the exponential of the number of qubits, makes a practical speedup unrealistic even under extremely optimistic assumptions on both hardware quality and availability.

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)
• 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 Advantage of Noisy Grover's Algorithm [3.803244458097104]
  Grover's search algorithm is the only quantum algorithm with proven advantage to any possible classical search algorithm. We present a noise-tolerant method that exponentially improves the noise threshold of Grover's algorithm.
  arXiv  Detail & Related papers  (2023-06-19T11:17:32Z)
• 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)
• Making the cut: two methods for breaking down a quantum algorithm [0.0]
  It remains a major challenge to find quantum algorithms that may reach computational advantage in the present era of noisy, small-scale quantum hardware. We identify and characterize two methods of breaking down'' quantum algorithms into rounds of lower (query) depth. We show that for the first problem parallelization offers the best performance, while for the second is the better choice.
  arXiv  Detail & Related papers  (2023-05-17T18:00:06Z)
• 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)
• Iterative Qubits Management for Quantum Index Searching in a Hybrid System [56.39703478198019]
  IQuCS aims at index searching and counting in a quantum-classical hybrid system. We implement IQuCS with Qiskit and conduct intensive experiments. Results demonstrate that it reduces qubits consumption by up to 66.2%.
  arXiv  Detail & Related papers  (2022-09-22T21:54:28Z)
• 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)
• Hybrid Quantum-Classical Search Algorithms [0.0]
  We show that classical computation, unless it by itself can solve the Search problem, cannot assist quantum computation. We generalize this result to algorithms with subconstant success probabilities.
  arXiv  Detail & Related papers  (2022-02-23T11:43:17Z)
• 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)
• Quantum Computing without Quantum Computers: Database Search and Data Processing Using Classical Wave Superposition [101.18253437732933]
  We present experimental data on magnetic database search using spin wave superposition. We argue that in some cases the classical wave-based approach may provide the same speedup in database search as quantum computers.
  arXiv  Detail & Related papers  (2020-12-15T16:21:53Z)

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.