paint-brush
Understanding Grover’s Search Algorithmby@escholar
New Story

Understanding Grover’s Search Algorithm

tldt arrow

Too Long; Didn't Read

This section covers Grover's quantum algorithm for unstructured search, highlighting its quadratic speedup over classical search methods, especially when M is unknown.
featured image - Understanding Grover’s Search Algorithm
EScholar: Electronic Academic Papers for Scholars HackerNoon profile picture
0-item

Abstract and I. Introduction

A. Quantum Bitcoin Mining

B. Our Contribution

C. Comparison with Related Works

D. Conventions

II. Background

A. Bitcoin Basics

B. Bitcoin Security

C. Grover’s Search Algorithm

D. Quantum Attacks

III. Approach

A. Algorithm

B. Markov Chain

C. Assumptions and Approximations

IV. Results

A. Probability of Success

B. Performance Measures

C. Example Application

V. Discussion, Acknowledgments, and References

C. Grover’s Search Algorithm

In this subsection we review Grover’s quantum algorithm for unstructured search and results we use in our analysis. Grover’s search solves the following problem in the oracle setting.




The function named measure(A) performs a measurement of A in the computational basis and returns the result. An important variant of Grover’s search has been developed for the case in which M is unknown [6]. This algorithm preserves the quadratic speedup over classical algorithms. For a nice geometric description of Grover’s algorithm we direct the reader to [19].




Authors:

(1) Robert R. Nerem, Institute for Quantum Science and Technology, University of Calgary, Alberta T2N 1N4, Canada (riley.nerem@gmail.com);

(2) Daya R. Gaur, Department of Mathematics and Computer Science, University of Lethbridge, Alberta T1K 3M4, Canada.


This paper is available on arxiv under CC BY 4.0 DEED license.