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

On oracles and circuits

Christer Berg

Published Jan 1, 1997• 0 citations
OpenAlex

Related papers

Low-Depth Construction of Grover Oracles from Fully Functional Quantum Circuits

Jiaqi Gu, Behzad Abdolmaleki

Grover oracle is the core component of the Grover search algorithm. Instead of constructing a Grover oracle from scratch, we consider a common practice that how to construct a Grover oracle based on an existing fully functional quantum circuits (FFQCs). A FFQC typically performs computations for a primary target and includes ancillas (qubits for intermediate storage) restoration. Although these circuits can be directly integrated into an oracle, we find that this inevitably introduces circuit redundancy. To address this, we propose a low-depth transformation method that can convert an existing FFQC into a low-depth Grover oracle. Additionally, our method can further reduce the width while retaining the previously achieved low depth.

International Conference on Quantum Communications, Networking, and Computing (QCNC)•Apr 6, 2026•0 citations

Oracle Separations in the Fourier Hierarchy

Atul Mantri

The Fourier hierarchy $\mathrm{FH}_0\subseteq\mathrm{FH}_1\subseteq\mathrm{FH}_2\subseteq\cdots$, introduced by Shi (TCS 2005), measures a quantum computation by the number of Hadamard layers it uses. Between two layers the circuit may permute basis states and attach phases, but it may not create superposition; the layers are its only source of interference. The first level is exactly $\mathrm{BPP}$, while the second already solves Simon's problem and, through phase estimation, factors integers. Shi conjectured that every additional layer strictly increases computational power, and asked, as a first step, for oracle separations between consecutive levels. To our knowledge, the question was open at every level $k\ge2$. We prove that for every constant $k\ge2$ there is an oracle relative to which $\mathrm{FH}_k\subsetneq\mathrm{FH}_{k+1}$. The separating problem is built from Forrelation (Aaronson and Ambainis, STOC 2015): the level above solves it with a constant number of queries, whereas at level $k$ it stays hard even for circuits making exponentially many queries. This holds for both of the usual ways of giving a circuit access to an oracle, the phase oracle and the standard oracle, which writes its answer into a register. The two are not interchangeable: relative to an oracle, the standard oracle is strictly more powerful at the same number of layers. We also separate the union of all the levels from $\mathrm{BQP}$ relative to an oracle. The lower bounds rest on a structural property of the hierarchy: the number of Hadamard layers limits how adaptively a circuit can query its oracle. With a phase oracle, a circuit with $k$ layers is reproduced exactly by an algorithm making only $k-1$ rounds of parallel queries, which brings known lower bounds for such algorithms to bear. The standard oracle lets a circuit branch on earlier answers, and that case needs a separate argument.

quant-pharXiv:2609.11830•Sep 11, 2026•1 citation

Reversible Logic: An Introduction

Hari Mohan Gaur, Trailokya Nath Sasamal, Ashutosh Kumar Singh +2 more

Lecture notes in electrical engineering•Jul 28, 2019•13 citations

Conjugate Logic

Niklas Johansson, Felix Huber, Jan-Åke Larsson

arXiv:2102.06572•Springer eBooks•Jan 1, 2023•1 citation

A Programming Language For Quantum Oracle Construction

Ayush Tambde

Many quantum programs require circuits for addition, subtraction and logical operations. These circuits may be packaged within routines known as oracles. However, oracles can be tedious to code with current frameworks. To solve this problem the author developed Higher-Level Oracle Description Language (HODL) -- a C-style programming language for use on quantum computers -- to ease the creation of such circuits. The compiler translates high-level code written in HODL and converts it into OpenQASM, a gate-based quantum assembly language that runs on IBM Quantum Systems and compatible simulators.

arXiv:2110.12487•Oct 24, 2021•1 citation

Computational Circuits

Jarosław Adam Miszczak

Synthesis lectures on quantum computing•Jan 1, 2012•0 citations
Grover oracle is the core component of the Grover search algorithm. Instead of constructing a Grover oracle from scratch, we consider a common practice that how to construct a Grover oracle based on an existing fully functional quantum circuits (FFQCs). A FFQC typically performs computations for a primary target and includes ancillas (qubits for intermediate storage) restoration. Although these circuits can be directly integrated into an oracle, we find that this inevitably introduces circuit redundancy. To address this, we propose a low-depth transformation method that can convert an existing FFQC into a low-depth Grover oracle. Additionally, our method can further reduce the width while retaining the previously achieved low depth.
The Fourier hierarchy FH0⊆FH1⊆FH2⊆⋯\mathrm{FH}_0\subseteq\mathrm{FH}_1\subseteq\mathrm{FH}_2\subseteq\cdotsFH0​⊆FH1​⊆FH2​⊆⋯, introduced by Shi (TCS 2005), measures a quantum computation by the number of Hadamard layers it uses. Between two layers the circuit may permute basis states and attach phases, but it may not create superposition; the layers are its only source of interference. The first level is exactly BPP\mathrm{BPP}BPP, while the second already solves Simon's problem and, through phase estimation, factors integers. Shi conjectured that every additional layer strictly increases computational power, and asked, as a first step, for oracle separations between consecutive levels. To our knowledge, the question was open at every level k≥2k\ge2k≥2. We prove that for every constant k≥2k\ge2k≥2 there is an oracle relative to which FHk⊊FHk+1\mathrm{FH}_k\subsetneq\mathrm{FH}_{k+1}FHk​⊊FHk+1​. The separating problem is built from Forrelation (Aaronson and Ambainis, STOC 2015): the level above solves it with a constant number of queries, whereas at level kkk it stays hard even for circuits making exponentially many queries. This holds for both of the usual ways of giving a circuit access to an oracle, the phase oracle and the standard oracle, which writes its answer into a register. The two are not interchangeable: relative to an oracle, the standard oracle is strictly more powerful at the same number of layers. We also separate the union of all the levels from BQP\mathrm{BQP}BQP relative to an oracle. The lower bounds rest on a structural property of the hierarchy: the number of Hadamard layers limits how adaptively a circuit can query its oracle. With a phase oracle, a circuit with kkk layers is reproduced exactly by an algorithm making only k−1k-1k−1 rounds of parallel queries, which brings known lower bounds for such algorithms to bear. The standard oracle lets a circuit branch on earlier answers, and that case needs a separate argument.
Many quantum programs require circuits for addition, subtraction and logical operations. These circuits may be packaged within routines known as oracles. However, oracles can be tedious to code with current frameworks. To solve this problem the author developed Higher-Level Oracle Description Language (HODL) -- a C-style programming language for use on quantum computers -- to ease the creation of such circuits. The compiler translates high-level code written in HODL and converts it into OpenQASM, a gate-based quantum assembly language that runs on IBM Quantum Systems and compatible simulators.