Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

International Conference on Computer and Communication Systems (ICCCS)

Quantum Rough Counting and Its Application to Grover's Search Algorithm

Naphan Benchasattabuse, Prabhas Chongstitvatana, Chatchawit Apomtewan

Published Apr 1, 2018• 9 citations
Publisher

Abstract

We propose in this paper a rough counting algorithm and modified version of Grover's search algorithm. The proposed counting algorithm uses Deutsch-Jozsa's algorithm to roughly estimate the number of items satisfying some search conditions by reconstructing the output distribution. The modified Grover's search combines the counting into one part of the algorithm and uses the counting result to determine the number of Grover's iterations taken to get such items. We provide an analysis of expected probability of the proposed algorithm taking into account the problem size, the number of satisfying items and the query complexity to show that the proposed modified Grover's search is optimal.

DOI
10.1109/ccoms.2018.8463331

Related papers

Quantum Multi-object Search Algorithm with the Availability of Partial Information

Goong Chen, Zijian Diao

Abstract Consider the unstructured search of an unknown number I of items in a large unsorted database of size N. The multi-object quantum search algorithm consists of two parts. The first part of the algorithm is to generalize Grover's single-object search algorithm to the multi-object case, and the second part is to solve a counting problem to determine l. In this paper we study the multi-object quantum search algorithm (in continuous time), but in a more structured way by taking into account the availability of partial information. The modeling of available partial information is done simply by the combination of several pre­scribed, possibly overlapping, information sets with varying weights to signify the reliability of each set. The associated statistics is estimated and the algorithm efficiency and complexity are analyzed. Our analysis shows that the search described here may not be more efficient than the unstructured (generalized) multi-object Grover search if there is "misplaced confidence". However, if the information sets have a "basic confidence" property in the sense that each information set contains at least one search item, then a quadratic speedup holds on a much smaller data space, which further expedites the quantum search for the first item.

arXiv:quant-ph/0011019•Zeitschrift für Naturforschung A•Dec 1, 2001•0 citations

Quantum Approximate Counting with Nonadaptive Grover Iterations

Venkateswaran, Ramgopal, Ryan O’Donnell

Approximate Counting refers to the problem where we are given query access to a function $f : [N] \to \{0,1\}$, and we wish to estimate $K = #\{x : f(x) = 1\}$ to within a factor of $1+ε$ (with high probability), while minimizing the number of queries. In the quantum setting, Approximate Counting can be done with $O\left(\min\left(\sqrt{N/ε}, \sqrt{N/K}/ε\right)\right)$ queries. It has recently been shown that this can be achieved by a simple algorithm that only uses "Grover iterations"; however the algorithm performs these iterations adaptively. Motivated by concerns of computational simplicity, we consider algorithms that use Grover iterations with limited adaptivity. We show that algorithms using only nonadaptive Grover iterations can achieve $O\left(\sqrt{N/ε}\right)$ query complexity, which is tight.

arXiv:2010.04370•Leibniz international proceedings in informatics•Oct 9, 2020•4 citations

Quantum Search with Prior Knowledge

Xiaoyu He, Jialin Zhang, Xiaoming Sun

Search-base algorithms have widespread applications in different scenarios. Grover's quantum search algorithms and its generalization, amplitude amplification, provide a quadratic speedup over classical search algorithms for unstructured search. We consider the problem of searching with prior knowledge. More preciously, search for the solution among N items with a prior probability distribution. This letter proposes 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:2009.08721•Sep 18, 2020•1 citation

Optimization of partial search

V. E. Korepin

A quantum Grover search algorithm can find a target item in a database faster than any classical algorithm. One can trade accuracy for speed and find a part of the database (a block) containing the target item even faster; this is partial search. A partial search algorithm was recently suggested by Grover and Radhakrishnan. Here we optimize it. Efficiency of the search algorithm is measured by the number of queries to the oracle. The author suggests a new version of the Grover–Radhakrishnan algorithm which uses a minimal number of such queries. The algorithm can run on the same hardware that is used for the usual Grover algorithm.

arXiv:quant-ph/0503238•Journal of Physics A Mathematical and General•Oct 19, 2005•27 citations

Quantum Approximate Counting, Simplified

Scott Aaronson, Patrick Rall

In 1998, Brassard, Høyer, Mosca, and Tapp (BHMT) gave a quantum algorithm for approximate counting. Given a list of N items, K of them marked, their algorithm estimates K to within relative error ∊ by making only queries. Although this speedup is of “Grover” type, the BHMT algorithm has the curious feature of relying on the Quantum Fourier Transform (QFT), more commonly associated with Shor's algorithm. Is this necessary? This paper presents a simplified algorithm, which we prove achieves the same query complexity using Grover iterations only. We also generalize this to a QFT-free algorithm for amplitude estimation. Related approaches to approximate counting were sketched previously by Grover, Abrams and Williams, Suzuki et al., and Wie (the latter two as we were writing this paper), but in all cases without rigorous analysis.

arXiv:1908.10846•Society for Industrial and Applied Mathematics eBooks•Dec 17, 2019•123 citations

Grover algorithm with zero theoretical failure rate

Gui‐Lu Long

In a standard Grover's algorithm for quantum searching, the probability of finding the marked item is not exactly 1. In this paper we present a modified version of Grover's algorithm that searches a marked state with full successful rate. The modification is done by replacing the phase inversion by phase rotation through angle $\ensuremath{\varphi}.$ The rotation angle is given analytically to be $\ensuremath{\varphi}=2\mathrm{arcsin}(\mathrm{sin}[\ensuremath{\pi}/(4J+6)]/\mathrm{sin}\ensuremath{\beta}),$ where $\mathrm{sin}\ensuremath{\beta}=1/\sqrt{N},$ N is the number of items in the database, and J is any integer equal to or greater than the integer part of $[(\ensuremath{\pi}/2)\ensuremath{-}\ensuremath{\beta}]/(2\ensuremath{\beta}).$ Upon measurement at the $(J+1)\mathrm{th}$ iteration, the marked state is obtained with certainty.

arXiv:quant-ph/0106071•Physical Review A•Jul 11, 2001•456 citations
We propose in this paper a rough counting algorithm and modified version of Grover's search algorithm. The proposed counting algorithm uses Deutsch-Jozsa's algorithm to roughly estimate the number of items satisfying some search conditions by reconstructing the output distribution. The modified Grover's search combines the counting into one part of the algorithm and uses the counting result to determine the number of Grover's iterations taken to get such items. We provide an analysis of expected probability of the proposed algorithm taking into account the problem size, the number of satisfying items and the query complexity to show that the proposed modified Grover's search is optimal.
Abstract Consider the unstructured search of an unknown number I of items in a large unsorted database of size N. The multi-object quantum search algorithm consists of two parts. The first part of the algorithm is to generalize Grover's single-object search algorithm to the multi-object case, and the second part is to solve a counting problem to determine l. In this paper we study the multi-object quantum search algorithm (in continuous time), but in a more structured way by taking into account the availability of partial information. The modeling of available partial information is done simply by the combination of several pre­scribed, possibly overlapping, information sets with varying weights to signify the reliability of each set. The associated statistics is estimated and the algorithm efficiency and complexity are analyzed. Our analysis shows that the search described here may not be more efficient than the unstructured (generalized) multi-object Grover search if there is "misplaced confidence". However, if the information sets have a "basic confidence" property in the sense that each information set contains at least one search item, then a quadratic speedup holds on a much smaller data space, which further expedites the quantum search for the first item.
Approximate Counting refers to the problem where we are given query access to a function f:[N]→{0,1}f : [N] \to \{0,1\}f:[N]→{0,1}, and we wish to estimate $K = #\{x : f(x) = 1\}$ to within a factor of 1+ε1+ε1+ε (with high probability), while minimizing the number of queries. In the quantum setting, Approximate Counting can be done with O(min⁡(N/ε,N/K/ε))O\left(\min\left(\sqrt{N/ε}, \sqrt{N/K}/ε\right)\right)O(min(N/ε​,N/K​/ε)) queries. It has recently been shown that this can be achieved by a simple algorithm that only uses "Grover iterations"; however the algorithm performs these iterations adaptively. Motivated by concerns of computational simplicity, we consider algorithms that use Grover iterations with limited adaptivity. We show that algorithms using only nonadaptive Grover iterations can achieve O(N/ε)O\left(\sqrt{N/ε}\right)O(N/ε​) query complexity, which is tight.
Search-base algorithms have widespread applications in different scenarios. Grover's quantum search algorithms and its generalization, amplitude amplification, provide a quadratic speedup over classical search algorithms for unstructured search. We consider the problem of searching with prior knowledge. More preciously, search for the solution among N items with a prior probability distribution. This letter proposes 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.
A quantum Grover search algorithm can find a target item in a database faster than any classical algorithm. One can trade accuracy for speed and find a part of the database (a block) containing the target item even faster; this is partial search. A partial search algorithm was recently suggested by Grover and Radhakrishnan. Here we optimize it. Efficiency of the search algorithm is measured by the number of queries to the oracle. The author suggests a new version of the Grover–Radhakrishnan algorithm which uses a minimal number of such queries. The algorithm can run on the same hardware that is used for the usual Grover algorithm.
In 1998, Brassard, Høyer, Mosca, and Tapp (BHMT) gave a quantum algorithm for approximate counting. Given a list of N items, K of them marked, their algorithm estimates K to within relative error ∊ by making only queries. Although this speedup is of “Grover” type, the BHMT algorithm has the curious feature of relying on the Quantum Fourier Transform (QFT), more commonly associated with Shor's algorithm. Is this necessary? This paper presents a simplified algorithm, which we prove achieves the same query complexity using Grover iterations only. We also generalize this to a QFT-free algorithm for amplitude estimation. Related approaches to approximate counting were sketched previously by Grover, Abrams and Williams, Suzuki et al., and Wie (the latter two as we were writing this paper), but in all cases without rigorous analysis.
In a standard Grover's algorithm for quantum searching, the probability of finding the marked item is not exactly 1. In this paper we present a modified version of Grover's algorithm that searches a marked state with full successful rate. The modification is done by replacing the phase inversion by phase rotation through angle $\ensuremath{\varphi}.$ The rotation angle is given analytically to be $\ensuremath{\varphi}=2\mathrm{arcsin}(\mathrm{sin}[\ensuremath{\pi}/(4J+6)]/\mathrm{sin}\ensuremath{\beta}),$ where $\mathrm{sin}\ensuremath{\beta}=1/\sqrt{N},$ N is the number of items in the database, and J is any integer equal to or greater than the integer part of $[(\ensuremath{\pi}/2)\ensuremath{-}\ensuremath{\beta}]/(2\ensuremath{\beta}).$ Upon measurement at the (J+1)th(J+1)\mathrm{th}(J+1)th iteration, the marked state is obtained with certainty.