Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Oracle Quantum Algorithms: An Overview

Rafael Pereira da Silva

Published Jan 1, 2024• 0 citations
Publisher
DOI
10.2139/ssrn.4862127

Related papers

Quantum Algorithms Overview

Elena Yndurain

Chapman & Hall/CRC eBooks•Jan 23, 2025•1 citation

Quantum Query Algorithms

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.

•Nov 19, 2025•0 citations

Quantum Computation Relative to Oracles

Christino Tamon, Tomoyuki Yamakami

Springer eBooks•Jan 1, 2001•1 citation

Simon's Algorithm: Collision Finding

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.

CRC Press eBooks•Nov 14, 2025•0 citations

The Hidden Subgroup Problem

Frédéric Wang

We give an overview of the Hidden Subgroup Problem (HSP) as of July 2010, including new results discovered since the survey of arXiv:quant-ph/0411037v1. We recall how the problem provides a framework for efficient quantum algorithms and present the standard methods based on coset sampling. We study the Dihedral and Symmetric HSPs and how they relate to hard problems on lattices and graphs. Finally, we conclude with the known solutions and techniques, describe connections with efficient algorithms as well as miscellaneous variants of HSP. We also bring various contributions to the topic. We show that in theory, we can solve HSP over a given group inductively: the base case is solving HSP over its simple factor groups and the inductive step is building efficient oracles over a normal subgroup N and over the factor group G/N. We apply this analysis to the Dedekindian HSP to get an alternative abelian HSP algorithm based on a change of the underlying group. We also propose a quotient reduction by the normal group obtained via Weak Fourier Sampling. We compute the exact expression of Strong Fourier Sampling over the dihedral group, showing how the previous reduction is natural and matches the standard one. We also give a reduction of rigid graph isomorphism problem to HSP over the alternating group. For this group and other simple groups, we propose maximal subgroup reduction as a possible approach. We also analyse Regev's algorithm for the poly(n)-uniqueSVP, prove how the degree of the polynomial is related to the oracle complexity used and we suggest several variants.

arXiv:1008.0010•Jul 30, 2010•13 citations

Simplified quantum algorithm for the oracle identification problem

Leila Taghavi

arXiv:2109.03902•Quantum Machine Intelligence•Jul 9, 2022•6 citations
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.
“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.
We give an overview of the Hidden Subgroup Problem (HSP) as of July 2010, including new results discovered since the survey of arXiv:quant-ph/0411037v1. We recall how the problem provides a framework for efficient quantum algorithms and present the standard methods based on coset sampling. We study the Dihedral and Symmetric HSPs and how they relate to hard problems on lattices and graphs. Finally, we conclude with the known solutions and techniques, describe connections with efficient algorithms as well as miscellaneous variants of HSP. We also bring various contributions to the topic. We show that in theory, we can solve HSP over a given group inductively: the base case is solving HSP over its simple factor groups and the inductive step is building efficient oracles over a normal subgroup N and over the factor group G/N. We apply this analysis to the Dedekindian HSP to get an alternative abelian HSP algorithm based on a change of the underlying group. We also propose a quotient reduction by the normal group obtained via Weak Fourier Sampling. We compute the exact expression of Strong Fourier Sampling over the dihedral group, showing how the previous reduction is natural and matches the standard one. We also give a reduction of rigid graph isomorphism problem to HSP over the alternating group. For this group and other simple groups, we propose maximal subgroup reduction as a possible approach. We also analyse Regev's algorithm for the poly(n)-uniqueSVP, prove how the degree of the polynomial is related to the oracle complexity used and we suggest several variants.