# Questions tagged [oracles]

An oracle is a "black box" operation (function) that is used as an input to an another algorithm (for example Deutch-Jozsa, Grover etc.). A parameter or feature of the Oracle is infered by the algorithm.

90 questions
Filter by
Sorted by
Tagged with
1 vote
91 views

15 views

### Mapping a classical cipher into quantum implementation of Grover Oracle

I am translating simple ciphers into quantum implementation in order to create oracle for Grover algorithm. I have started the task with a light weight SPECK cipher (got both classical and quantum ...
• 181
69 views

### High level implementation of quantum oracles

My question is related to a similar question which did not get a satisfactory answer. Since it was asked in 2020 and was somewhat general, I hope to ask a similar question in 2022 with a concrete ...
• 1,161
83 views

### What makes oracle algorithms difficult to design and implement?

Recently, I have paid attention to some oracle algorithms, such as Grover. Generally speaking, an oracle is a kind of black box, and Grover's algorithm constructs an oracle through quantum circuits. ...
• 388
1 vote
12 views

• 173
206 views

### BHT algorithm implementation

Summary of Method Amplitude Amplification Summary The BHT algorithm uses amplitude amplification, a nice generalisation of Grover's algorithm, where there is a subset $G\subset X$ of good elements in ...
• 183
64 views

### Is it possible to convert classical oracle to quantum ones?

If an attacker possesses a classical oracle, so she could apply chosen plain text attacks. Is there an easy way to reduce this oracle to quantum ones allowing her to make quantum chosen plain text ...
• 85
110 views

### Can we use reversible computation to construct oracle circuits?

One of the question while I discussed with my colleague in the math department was the construction of oracle circuit. In computer science, specifically in algorithm, we take oracle as granted and ...
• 33
47 views

### Proving that with probability 1 $NP \nsubseteq BQP$ with respect to random oracles

In the paper Strength and Weakneses of Quantum Computers (https://arxiv.org/abs/quant-ph/9701001) by Bennet, Bernstein, Brassard and Vazirani, it is shown the statement in the title (Theorem 3.5 in ...
• 493
1 vote
90 views

### How is the oracle physically implemented in Deutsch algorithm?

In the Deutsch algorithm, the oracle implementation for the function f is taken as a black box, but physically, how is the oracle implemented? Why can we assume such a black box exists for the ...
1 vote
76 views

### Can there be different gate implementations of same oracle implementation?

I have been reading about Bernstein-Vazirani Algorithm, and it uses what is known as a phase oracle. Basically, it is CNOT gate with several controls attached to the ancilla qubit $|-\rangle$ (it is ...
67 views

Consider a Boolean function with multiple outputs $f: \{0, 1\}^{n} \rightarrow \{0, 1\}^{m}$, and consider being given oracle access to the function $f$. Let us denote the oracle by $O_f$. For an $x \... • 953 3 votes 1 answer 77 views ### How can one evaluation of$U_f$in Grover's algorithm use only one query of$f$? I am very much new to quantum computation and do not have a background in quantum mechanics, which I believe is at the root of my confusion around Grover's algorithm. Suppose that we have a search ... • 33 3 votes 1 answer 91 views ### Quantum Katas - Tutorials - Oracles - Task 3.3 (OR oracle of all bits except for a single bit) Let$x$be an arbitrary state composed of$N$qubits and$k$be an integer such that$0\leq k \leq N.$The task is to ignore the$k$-th bit and to flip the sign of$x$if any of the remaining bits are ... 3 votes 1 answer 457 views ### Implementing 3-Qubit Grover Algorithm in Qiskit The Qiskit tutorial on Grover's Algorithm shows an example of finding two marked solutions out of 8 items, produced by 3 qubits. Using the general diffuser code it provides, however, I realize that ... • 139 8 votes 3 answers 386 views ### In the adiabatic version of Grover's algorithm, how is the Hamiltonian constructed? X-posted on physics.stackexchange In quantum computation, there is a famous algorithm to search a marked item in an unstructured database called Grover's algorithm. It achieves a quadratic speedup ... 3 votes 1 answer 325 views ### How can Grover's algorithm be implemented when having a string or other data type as input? For some reason, I'm having difficulty with a seemingly very basic component of Grover's. When reading most explanations, the problem is framed as "consider an unstructured database of N items. ... 1 vote 0 answers 116 views ### In Grover's oracle, how is the matrix$U_f$derived for a generic$n$? Grover's algorithm works by iteration of the operator $$\tag{1}G:=U_S^\perp U_f=H^{\otimes n}U_0^\perp H^{\otimes n}.$$ I know how to write down the matrix for$U_S^\perp\$ (the inversion about the ...
• 133
I want to turn a state $$|\Psi_1⟩ = \frac{1}{\sqrt{8}}(|000⟩+|001⟩+|010⟩+|011⟩+|100⟩+|101⟩+|110⟩+|111⟩)$$ into $$|\Psi_2⟩ = \frac{1}{\sqrt{8}}(|000⟩+|001⟩+|010⟩+|011⟩+|100⟩-|101⟩-|110⟩+|111⟩)$$ ...