Quantifying Computational Advantage of Grover's Algorithm with the Trace Speed

• URL: http://arxiv.org/abs/2001.04486v2
• Date: Thu, 14 Jan 2021 11:01:20 GMT
• Title: Quantifying Computational Advantage of Grover's Algorithm with the Trace Speed
• Authors: Valentin Gebhart, Luca Pezz\`e, Augusto Smerzi
• Abstract summary: We report a close connection between the trace speed and the quantum speed-up in Grover's search algorithm implemented with pure and pseudo-pure states. For a noiseless algorithm, we find a one-to-one correspondence between the quantum speed-up and the polarization of the pseudo-pure state.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Despite intensive research, the physical origin of the speed-up offered by quantum algorithms remains mysterious. No general physical quantity, like, for instance, entanglement, can be singled out as the essential useful resource. Here we report a close connection between the trace speed and the quantum speed-up in Grover's search algorithm implemented with pure and pseudo-pure states. For a noiseless algorithm, we find a one-to-one correspondence between the quantum speed-up and the polarization of the pseudo-pure state, which can be connected to a wide class of quantum statistical speeds. For time-dependent partial depolarization and for interrupted Grover searches, the speed-up is specifically bounded by the maximal trace speed that occurs during the algorithm operations. Our results quantify the quantum speed-up with a physical resource that is experimentally measurable and related to multipartite entanglement and quantum coherence.

Related papers

• Towards Entropic Constraints on Quantum Speedups [0.0]
  Some quantum algorithms have "quantum speedups": improved time complexity as compared with the best-known classical algorithms for solving the same tasks. Can we understand what fuels these speedups from an entropic perspective? Information theory gives us a multitude of metrics we might choose from to measure how fundamentally 'quantum' is the behavior of a quantum computer running an algorithm.
  arXiv  Detail & Related papers  (2024-11-05T19:00:04Z)
• Power Characterization of Noisy Quantum Kernels [52.47151453259434]
  We show that noise may make quantum kernel methods to only have poor prediction capability, even when the generalization error is small. We provide a crucial warning to employ noisy quantum kernel methods for quantum computation.
  arXiv  Detail & Related papers  (2024-01-31T01:02:16Z)
• Quantum algorithms: A survey of applications and end-to-end complexities [90.05272647148196]
  The anticipated applications of quantum computers span across science and industry. We present a survey of several potential application areas of quantum algorithms. We outline the challenges and opportunities in each area in an "end-to-end" fashion.
  arXiv  Detail & Related papers  (2023-10-04T17:53:55Z)
• 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)
• Quantifying Grover speed-ups beyond asymptotic analysis [0.0]
  We consider an approach that combines classical emulation with detailed complexity bounds that include all constants. We apply our method to some simple quantum speedups of classical algorithms for solving the well-studied MAX-$k$-SAT optimization problem. This requires rigorous bounds (including all constants) on the expected- and worst-case complexities of two important quantum sub-routines.
  arXiv  Detail & Related papers  (2022-03-09T19:00:00Z)
• 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)
• Quantum speedup for track reconstruction in particle accelerators [51.00143435208596]
  We identify four fundamental routines present in every local tracking method and analyse how they scale in the context of a standard tracking algorithm. Although the found quantum speedups are mild, this constitutes to the best of our knowledge, the first rigorous evidence of a quantum advantage for a high-energy physics data processing task.
  arXiv  Detail & Related papers  (2021-04-23T13:32:14Z)
• Hybrid divide-and-conquer approach for tree search algorithms [0.0]
  We study the hybrid divide-and-conquer method in the context of tree search algorithms. We provide conditions for speedups for the well known algorithm of DPLL. We briefly discuss the limitations of hybrid methods in providing speed-ups for larger problems.
  arXiv  Detail & Related papers  (2020-07-14T13:57:12Z)
• Transition Probabilities in Generalized Quantum Search Hamiltonian Evolutions [0.0]
  We study the computational aspects necessary to calculate the transition probability from a source state to a target state in a continuous time quantum search problem. We find it is possible to outperform, in terms of minimum search time, the well-known Farhi-Gutmann analog quantum search algorithm.
  arXiv  Detail & Related papers  (2020-02-06T13:16:37Z)

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.