Oracle Quantum Algorithms: An Overview

David S. Simon

Walid E. Gomaa

This presentation gives a comprehensive overview of quantum query algorithms, beginning with an introduction to the query model of computation where input is accessed via an oracle function. It then details several foundational quantum algorithms that demonstrate a quantum advantage over classical approaches: Deutsch's problem is solved with a single query using phase kickback to determine if a function is constant or balanced; the Deutsch-Jozsa algorithm extends this to n-bit inputs, efficiently distinguishing constant from balanced functions with one query versus an exponential need classically; the Bernstein-Vazirani algorithm identifies a hidden string with one query, outperforming classical linear requirements; and Simon's algorithm, which finds a hidden period in a two-to-one function with a linear number of queries, showcases an exponential speedup over the best classical probabilistic algorithms.

Bhupendra Singh, Mohankumar Mylsamy, Thamaraimanalan Thangarajan

“Simon's Algorithm: Collision Finding” explains Simon's Algorithm, focusing on how it helps in finding collisions. It starts with an overview of how the algorithm works. A literature review is included, covering both Simon's algorithm and its uses in cryptography. The section then introduces Simon's problem, comparing how classical and quantum methods solve it, and explains how to build a quantum circuit for a blackbox function. Different examples of blackbox functions (oracles) are shown, such as 1-to-1 and 2-to-1 mappings, with detailed implementations of Simon's algorithm for both 4-bit and 8-bit cases. The section also looks at a suggested attack method on the Grain-128a cipher, explaining how the key and initialization vector (IV) are set up, how the keystream is generated, and how the authenticated tag is created. It provides a quantum circuit design for the Simon attack on Grain-4a, along with steps for carrying out the attack. The section also presents experimental results from several test cases and quantum resource estimates. It wraps up with a discussion of the results and thoughts on future improvements and developments in using Simon's algorithm for cryptographic attacks.

Davide Pastorello

Sanjay Chakraborty, Soharab Hossain Shaikh, Sudhindu Bikash Mandal +2 more

Traditional machine learning shares several benefits with quantum information processing field. The study of machine learning with quantum mechanics is called quantum machine learning. Data clustering is an important tool for machine learning where quantum computing plays a vital role in its inherent speed up capability. In this paper, a hybrid quantum algorithm for data clustering (quantum walk-based hybrid clustering (QWBHC)) is introduced where one-dimensional discrete time quantum walks (DTQW) play the central role to update the positions of data points according to their probability distributions. A quantum oracle is also designed and it is mainly implemented on a finite [Formula: see text]-regular bipartite graph where data points are initially distributed as a predefined set of clusters. An overview of a quantum walk (QW) based clustering algorithm on 1D lattice structure is also introduced and described in this paper. In order to search the nearest neighbors, a unitary and reversible DTQW gives a quadratic speed up over the traditional classical random walk. This paper also demonstrates the comparisons of our proposed hybrid quantum clustering algorithm with some state-of-the-art clustering algorithms in terms of clustering accuracy and time complexity analysis. The proposed quantum oracle needs [Formula: see text] queries to mark the nearest data points among clusters and modify the existing clusters. Finally, the proposed QWBHC algorithm achieves [Formula: see text] performance.