Video Upload Options

During a lecture at the Massachusetts Institute of Technology in the early 1980s on the possibilities and limits of numerical simulation ^[1], Richard Feynman posed a now-famous question: “Can quantum systems be simulated probabilistically by a classical computer with local connections?”. He argued that classical simulations do not scale, as they face fundamental complexity barriers, most notably exponential growth in time and memory requirements. From this observation, Feynman concluded that classical computers cannot faithfully reproduce quantum mechanics, a realization that laid the conceptual foundations of quantum computing. Three years later, David Deutsch introduced the notion of a universal quantum Turing machine ^[2], providing the first formal model of quantum computation. While early works remained largely theoretical, concrete applications began to emerge approximately a decade later. In particular, Peter Shor’s factoring algorithm demonstrated an exponential speedup for integer factorization, threatening widely used cryptographic schemes and triggering intense global interest in universal quantum computing. His first paper dealing with this innovation was proposed in 1994 at an IEEE conference. Shor presented Las Vegas algorithms (probabilistic algorithms which can be viewed as a variant of the Monte Carlo methods that always provide correct results). They were used for finding discrete logarithms and factoring integers on a quantum computer. Considering the number of digits of the integer to be factored, the number of steps required by the quantum algorithms is polynomial, and he then gave examples of quantum cryptanalysis ^[3]. A more complete paper about factoring integers and finding discrete logarithm was then published in the SIAM Review five years later ^[4]. Beyond factoring, Shor also made a crucial, though less widely known, contribution by developing quantum error-correcting codes, which address the intrinsic fragility and decoherence of quantum systems ^[5]. At approximately the same time, advancements were achieved by Lov Grover and Seth Lloyd in different areas. Lloyd showed how quantum systems could be simulated using Hamiltonians (operators that describe the total energy of a system), and this opened the pathway to the simulation of quantum computers ^[6]. This theoretical framework significantly advanced our ability to model and understand quantum dynamics.

Grover, on his side, offered a glimpse into the potential of quantum systems to process information in fundamentally different ways compared to classical computers. The Grover algorithm, in particular, is known for its ability to search unsorted databases quadratically faster than its classical counterparts ^[7][8], representing a significant leap in computing efficiency. Quantum computing exploits the unique properties of quantum mechanics, such as superposition and entanglement, to perform computations, as shown in ^[9]. Quantum mechanics can speed up a range of search applications over unsorted data. For example, imagine a phone directory containing N names arranged in completely random order. To find someone’s phone number within a reasonable probability, any classical algorithm (whether deterministic or probabilistic) will need to access the database a minimum number of times. Quantum mechanical systems can be in a superposition of states and simultaneously examine multiple names. By properly adjusting the phases of various operations, successful computations reinforce each other while others interfere randomly. As a result, the desired phone number can be obtained after limited access to the database. This paradigm shift from classical computing has opened new frontiers in various fields.

While cryptography has considerable implications, optimization and operations research, in general, are not far behind. In this encyclopedic article, we have chosen to present the Grover algorithm since it is useful in many fields. We will first present the approach behind this algorithm, then we will show the potential applications where this algorithm is useful, and next, we will explain the current limitations encountered. Lastly, we will discuss reproducibility issues with different simulators and machines.