Deterministic Quantum Search for Arbitrary Initial Success Probabilities

• URL: http://arxiv.org/abs/2505.15512v1
• Date: Wed, 21 May 2025 13:35:42 GMT
• Title: Deterministic Quantum Search for Arbitrary Initial Success Probabilities
• Authors: Harishankar Mishra, Asvija Balasubramanyam, Gudapati Naresh Raghava,
• Abstract summary: 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.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Unstructured search remains as one of the significant challenges in computer science, as classical search algorithms become increasingly impractical for large-scale systems due to their linear time complexity. Quantum algorithms, notably Grover's algorithm, leverages quantum parallelism to achieve quadratic speedup over classical approaches. Its generalization, the amplitude amplification algorithm, extends this advantage to a broader class of search problems. However, both algorithms are inherently probabilistic and fail to guarantee success with certainty, also they offer no quantum advantage when the initial success probability exceeds 0.5. This work presents a deterministic quantum search algorithm that operates effectively for arbitrary initial success probabilities, providing guaranteed success in searching target states. The proposed approach introduces at most one additional iteration beyond the optimal count required by probabilistic quantum search algorithms. The algorithm preserves the quadratic speedup characteristic of quantum search methods. Additionally, an approach is proposed for the exact search of multiple target states within a bounded number of steps. A complete circuit-level implementation of the proposed algorithm is also presented.

Related papers

• Provably Robust Training of Quantum Circuit Classifiers Against Parameter Noise [49.97673761305336]
  Noise remains a major obstacle to achieving reliable quantum algorithms.<n>We present a provably noise-resilient training theory and algorithm to enhance the robustness of parameterized quantum circuit classifiers.
  arXiv  Detail & Related papers  (2025-05-24T02:51:34Z)
• A quantum speedup algorithm for TSP based on quantum dynamic programming with very few qubits [0.0]
  We propose a quantum algorithm to generate the uniform superposition state of all N-length Hamiltonian cycles as an initial state within gate complexity.<n>Compared to some algorithms that theoretically have lower query complexities but lack practical implementation solutions, our algorithm has feasible circuit implementation.
  arXiv  Detail & Related papers  (2025-02-12T23:58:25Z)
• An optimized quantum minimum searching algorithm with sure-success probability and its experiment simulation with Cirq [4.987556615430226]
  We propose an optimized quantum minimum searching algorithm with sure-success probability. The performance evaluation shows that our algorithm has higher accuracy and efficiency than DHA algorithm.
  arXiv  Detail & Related papers  (2023-09-25T14:07:27Z)
• Iterative Quantum Algorithms for Maximum Independent Set: A Tale of Low-Depth Quantum Algorithms [0.0]
  We study a new class of hybrid approaches to quantum optimization, termed Iterative Maximum Quantum Algorithms. We show that for QAOA with depth $p=1$, this algorithm performs exactly the same operations and selections as the classical greedy algorithm for MIS.
  arXiv  Detail & Related papers  (2023-09-22T18:00:03Z)
• Quantum Annealing for Single Image Super-Resolution [86.69338893753886]
  We propose a quantum computing-based algorithm to solve the single image super-resolution (SISR) problem. The proposed AQC-based algorithm is demonstrated to achieve improved speed-up over a classical analog while maintaining comparable SISR accuracy.
  arXiv  Detail & Related papers  (2023-04-18T11:57:15Z)
• 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)
• 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)
• Synthesis of Quantum Circuits with an Island Genetic Algorithm [44.99833362998488]
  Given a unitary matrix that performs certain operation, obtaining the equivalent quantum circuit is a non-trivial task. Three problems are explored: the coin for the quantum walker, the Toffoli gate and the Fredkin gate. The algorithm proposed proved to be efficient in decomposition of quantum circuits, and as a generic approach, it is limited only by the available computational power.
  arXiv  Detail & Related papers  (2021-06-06T13:15:25Z)
• 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)
• 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)
• Learning to Accelerate Heuristic Searching for Large-Scale Maximum Weighted b-Matching Problems in Online Advertising [51.97494906131859]
  Bipartite b-matching is fundamental in algorithm design, and has been widely applied into economic markets, labor markets, etc. Existing exact and approximate algorithms usually fail in such settings due to either requiring intolerable running time or too much computation resource. We propose textttNeuSearcher which leverages the knowledge learned from previously instances to solve new problem instances.
  arXiv  Detail & Related papers  (2020-05-09T02:48:23Z)

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.