Questions tagged [oracles]
An oracle O is a "black box" operation that is used as input to another algorithm.
13
questions
2
votes
2answers
55 views
In Grover's Algorithm, does the exact solution need to be given to the oracle?
From my understanding, the oracle function in Grover's algorithm is used as a way to check for the desired outcome.
I have looked at this example which implements the Exactly-1 3-SAT problem and the ...
4
votes
0answers
26 views
Oracle for welded tree walk
There is a famous paper by Childs, et al, in which it is shown that a quantum algorithm can find the name of the exit node for a certain graph in a way that is exponentially faster than any classical ...
3
votes
1answer
140 views
Deutsch-Jozsa on non-balanced oracles
I'm interested in deciding if an oracle is constant or not, but cannot guarantee that the non-constant oracles are balanced. The Deutsch-Jozsa seems like the obvious starting place, but handling the ...
7
votes
0answers
89 views
What are examples of non-oracular versions of famous oracular problems?
Most quantum algorithms proposed, including Deutsch-Jozsa, Simon's, Bernstein-Vazirani etc, involve querying an oracle. If I understand correctly, the speedups depend on the oracle being efficiently ...
2
votes
1answer
31 views
Hamming with prefix oracle
I'm doing the Q# quantum katas and I'm stuck on an oracle in the Deutsch-Josza algorithm katas.
Let $|x\rangle=|x_0x_1\dots x_{n-1}\rangle$ be a qubit array and $r$ be bit string of $k\leq n$. The $...
9
votes
1answer
138 views
Separating NP from BQP relative to an oracle
I was looking at this lecture note where the author gives an oracle separation between $\mathsf{BQP}$ and $\mathsf{NP}$. He hints at how "standard diagonalisation techniques can be used to make this ...
2
votes
1answer
45 views
Coding an oracle for Simon's algorithm
I am trying to implement Simon's algorithm which calls for a 2-to-1 mapping function that satisfies $f(x) = f(x⊕s)$.
I am looking for a simple way to code the oracle (using $H$, $Cx$, and $R$ gates), ...
3
votes
1answer
67 views
Why is the second register needed to define bit flip quantum oracles in a way that distinguishes between complementary oracles?
If our input $x \in \{0, 1\}^{n}$ is given as a black box, we usually query an oracle as follows.
$$O_{x}|i, b \rangle = (-1)^{b x_{i}} |i, b \rangle$$
$i = \{1, 2, \cdots, n \}$ is the index of the ...
5
votes
3answers
327 views
Why is the application of an oracle function not a measurement?
Why is the application of an oracle function not a measurement, causing the collapse of the system? How can you know the state of the system (the input of the oracle function) without measurement?
4
votes
1answer
221 views
How does an oracle function in Grover's algorithm actually work?
I have lately been studying quantum algorithms. I have gone through the Deutsch algorithm and Grover's algorithm. There's always a function in the oracle which somehow 'recognizes' the solution ...
19
votes
1answer
3k views
What exactly is an oracle?
What exactly is an "oracle"? Wikipedia says that an oracle is a "blackbox", but I'm not sure what that means.
For example, in the Deutsch–Jozsa algorithm,$\hspace{85px}$,is the oracle just the box ...
10
votes
5answers
1k views
How would I implement the quantum oracle in Deutsch's algorithm?
I am trying to simulate Deutsch's algorithm (elementary case of Deutsch-Josza algorithm), and I am not entirely sure how I would go about implementing the quantum oracle necessary for the algorithm to ...
9
votes
1answer
333 views
Grover's algorithm: what to input to Oracle?
I am confused about what to input to Oracle in Grover's algorithm.
Don't we need to input what we are looking for and where to find what we are looking for to Oracle, in addition to the ...
