Quantum Searching Amidst Uncertainty

D. Li, Xiao-Ming Li, Hongtao Huang +1 more

The quantum search algorithm is a way for finding an item with desired properties in an unsorted database of size N in only$\\sqrt{N}$ steps by means of a sequence of selective inversion and quantum diffusion operations. However, like most quantum algorithms, this requires the algorithm to execute the precise sequence of operations, any further probing into the database only worsens the result. Grover recently showed that by replacing the selective inversion by selective phase shifts of $\\pi /3$, the algorithm converges to the desired item monotonically. This paper builds on that result and considers the problem of retrieving a marked item from a database containing an unknown fraction of marked items, say $\\epsilon $. We derive optimal algorithms for different ranges of $\\epsilon .$ These are similar to Grover's recent algorithm but the phase shift turns out to vary with $\\epsilon $ - this is generally quite different from $\\pi /3$.

Jayesh V. Hire, Vaidehi Gawande, Sagar Dhande

Current flight search platforms primarily consider four essential factors when planning a trip: departure/arrival dates, as well as the origin and destination locations. However, when additional parameters are added to this search, the problem shifts from a simple to a complex search, as the engine must sift through a massive dataset of flights, including information on airlines, flight routes, fees, and more. To address this challenge and improve flight search efficiency amidst data-intensive and resource-demanding environments, this paper proposes the use of Grover's search algorithm. This algorithm is demonstrated as the optimal solution for searches with increased constraints. The paper highlights the practical application of Grover's search algorithm across three datasets of assorted sizes, as well as various quantum hardware and simulators available in the NISQ era. Furthermore, this paper provides an in-depth understanding of the complexity of quantum circuit design, including the key phases of state encoding and amplitude amplification. The effectiveness of these approaches is evaluated through analysis of execution times and quantum measurement results. The aim is to showcase the potential of quantum computing in revolutionizing real-world search tasks, particularly in the realm of flight selection.

Anurag Dutta, John Harshith, Yash Soni +3 more

In the pursuit of knowledge, data is a distinct set of values that convey information, describing quantity, quality, facts, statistics, or simple units of meaning, better known as datum. Now, handling data, in the latest world is really a tedious job that includes all the principles related to data management as a valuable resource. Amidst all data management techniques, Sorting is the most important one. Sorting refers to arranging data in ascending or descending order according to linear relationships between data items. It involves mathematical rigour that causes data units to be arranged in a monotonic order by it’s magnitude. In modern world of informatics, Quantum Computing have caught great heights. So, have the algorithms fused to it. Quantum computing is a type of computation whose operation can exploit quantum mechanical phenomena, such as superposition, interference, and entanglement. In this work, we would try to define a lower bound for the Computational Complexity of Sorting Algorithm, being heterogeneity by the lower bound for Quantum Search of an ordered list. Further, we would also develop a upper bound on the Sorting integrated using Grover’s Search- a real time unstructured Quantum Search.