Quantum mechanics can find a needle in a haystack every time

• URL: http://arxiv.org/abs/2506.06435v1
• Date: Fri, 06 Jun 2025 18:00:10 GMT
• Title: Quantum mechanics can find a needle in a haystack every time
• Authors: Fatemeh Mohit, Joshua Guanzon, Jaden McKinlay, Till J. Weinhold, Casey R. Myers, Marcelo P. Almeida, Markus Rambach, Andrew G. White,
• Abstract summary: Grover's algorithm is one of the pioneering demonstrations of the advantages of quantum computing over its classical counterpart.<n>We explore databases of 4 to 10 elements, with every choice of a single marked element, achieving an average success probability of $99.77 pm 0.05%$.
• Score: 0.0
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: Grover's algorithm is one of the pioneering demonstrations of the advantages of quantum computing over its classical counterpart, providing - at most - a quadratic speed-up over the classical solution for unstructured database search. The original formulation of Grover's algorithm is non-deterministic, finding the answer with a probability that varies with the size of the search space and the number of marked elements. A recent reformulation introduced a deterministic form of Grover's algorithm that - in principle - finds the answer with certainty. Here we realise the deterministic Grover's algorithm on a programmable photonic integrated circuit, finding that it not only outperforms the original Grover's algorithm as predicted, but is also markedly more robust against technological imperfections. We explore databases of 4 to 10 elements, with every choice of a single marked element, achieving an average success probability of $99.77 \pm 0.05\%$.

Related papers

• Deterministic Quantum Search for Arbitrary Initial Success Probabilities [0.0]
  This work presents a deterministic quantum search algorithm that operates effectively for arbitrary initial success probabilities.<n>The proposed approach introduces at most one additional iteration beyond the optimal count required by probabilistic quantum search algorithms.
  arXiv  Detail & Related papers  (2025-05-21T13:35:42Z)
• Arbitrary state creation via controlled measurement [49.494595696663524]
  This algorithm creates an arbitrary $n$-qubit pure quantum superposition state with precision of $m$-decimals.<n>The algorithm uses one-qubit rotations, Hadamard transformations and C-NOT operations with multi-qubit controls.
  arXiv  Detail & Related papers  (2025-04-13T07:23:50Z)
• On the practicality of quantum sieving algorithms for the shortest vector problem [42.70026220176376]
  lattice-based cryptography is one of the main candidates of post-quantum cryptography.<n> cryptographic security against quantum attackers is based on lattice problems like the shortest vector problem (SVP)<n>Asymptotic quantum speedups for solving SVP are known and rely on Grover's search.
  arXiv  Detail & Related papers  (2024-10-17T16:54:41Z)
• Near-deterministic quantum search algorithm without phase design [10.754825115553086]
  Grover's algorithm can find the target state with certainty only if searching one out of four.<n> deterministic search algorithm is also designed when searching one out of eight, sixteen, and thirty-two.
  arXiv  Detail & Related papers  (2024-07-15T14:20:47Z)
• 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)
• When can you trust feature selection? -- I: A condition-based analysis of LASSO and generalised hardness of approximation [49.1574468325115]
  We show how no (randomised) algorithm can determine the correct support sets (with probability $> 1/2$) of minimisers of LASSO when reading approximate input. For ill-posed inputs, the algorithm runs forever, hence, it will never produce a wrong answer. For any algorithm defined on an open set containing a point with infinite condition number, there is an input for which the algorithm will either run forever or produce a wrong answer.
  arXiv  Detail & Related papers  (2023-12-18T18:29:01Z)
• Generalized Hybrid Search and Applications to Blockchain and Hash Function Security [50.16790546184646]
  We first examine the hardness of solving various search problems by hybrid quantum-classical strategies. We then construct a hybrid quantum-classical search algorithm and analyze its success probability.
  arXiv  Detail & Related papers  (2023-11-07T04:59:02Z)
• Hybrid classical-quantum text search based on hashing [0.0]
  It is known that the complexity of a classical search query in an unordered database is linear in the length of the text and a given. We propose a hybrid classical-quantum algorithm that implements Grover's search to find a given in a text.
  arXiv  Detail & Related papers  (2023-11-02T13:16:07Z)
• Opening the Black Box Inside Grover's Algorithm [0.0]
  Grover's algorithm is a primary algorithm 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 a linear number of calls to (simulations of) the oracle.
  arXiv  Detail & Related papers  (2023-03-20T17:56:20Z)
• Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
  We study the problem of designing worst-case to average-case reductions for quantum algorithms. We provide an explicit and efficient transformation of quantum algorithms that are only correct on a small fraction of their inputs into ones that are correct on all inputs.
  arXiv  Detail & Related papers  (2022-12-06T22:01:49Z)
• 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)
• Deterministic Grover search with a restricted oracle [2.976027966501599]
  Grover's quantum search algorithm provides a quadratic quantum advantage over classical algorithms. We present a modified version to return the correct result with certainty without having user control over the quantum search oracle.
  arXiv  Detail & Related papers  (2022-01-01T02:04:11Z)
• Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
  This paper investigates the classical integer least-squares problem which estimates signals integer from linear models. The problem is NP-hard and often arises in diverse applications such as signal processing, bioinformatics, communications and machine learning. We propose a general hyper-accelerated tree search (HATS) algorithm by employing a deep neural network to estimate the optimal estimation for the underlying simplified memory-bounded A* algorithm.
  arXiv  Detail & Related papers  (2021-01-07T08:00:02Z)
• Quantum Search with Prior Knowledge [15.384459603233978]
  We propose a new generalization of Grover's search algorithm which performs better than the standard Grover algorithm in average under this setting. We prove that our new algorithm achieves the optimal expected success probability of finding the solution if the number of queries is fixed.
  arXiv  Detail & Related papers  (2020-09-18T09:50:33Z)

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.