REVIEW 4 cited by
Tight bounds on quantum searching
Not yet reviewed by Pith; the record is open.
This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.
SPECIMEN: schema-true, not a live event
T0 review · schema-true
One-sentence machine reading of the paper's core claim.
pith:XXXXXXXX · record.json · timestamp
read the original abstract
We provide a tight analysis of Grover's recent algorithm for quantum database searching. We give a simple closed-form formula for the probability of success after any given number of iterations of the algorithm. This allows us to determine the number of iterations necessary to achieve almost certainty of finding the answer. Furthermore, we analyse the behaviour of the algorithm when the element to be found appears more than once in the table and we provide a new algorithm to find such an element even when the number of solutions is not known ahead of time. Using techniques from Shor's quantum factoring algorithm in addition to Grover's approach, we introduce a new technique for approximate quantum counting, which allows to estimate the number of solutions. Finally we provide a lower bound on the efficiency of any possible quantum database searching algorithm and we show that Grover's algorithm nearly comes within a factor 2 of being optimal in terms of the number of probes required in the table.
Forward citations
Cited by 4 Pith papers
-
Constraint-Aware Quantum Optimization of Defect Configurations in Doped ZrO2: XY-Mixer QAOA and Grover Adaptive Search
Presents an end-to-end constraint-aware quantum optimization pipeline using XY-mixer QAOA and Grover Adaptive Search for low-energy defect configurations in doped ZrO2, with QAOA validated against exact enumeration on...
-
Quantum Communication Advantage for Leader Election and Agreement
Quantum communication reduces the message complexity of leader election and agreement in CONGEST networks below classical lower bounds.
-
QSCI-CMP: Quantum-Selected Configuration Interaction with Chemically Motivated Preselection
QSCI-CMP cuts the quantum sampling cost of SQD-AA by classically preselecting low-excitation, low-seniority determinants and using a compact oracle that checks those properties in superposition.
-
Nested Grover's Algorithm for Tree Search
A nested Grover algorithm for tree search claims cost O(m*2^(m/4)) using partial candidate solutions, but the speedup relies on an unexamined assumption that the candidate set contains the solution.
Discussion (0). Continue with ORCID to comment.