# 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.

34 questions
Filter by
Sorted by
Tagged with
28 views

### Is Grovers Algorithm Oracle creation a hardware level aspect?

There are numerous questions that asks about practical application demonstration of the Grover algorithm for arrays and databases. However examples are not seen anywhere. While searching for its ...
53 views

### Is Grover's algorithm only applicable to a pure state?

I've been trying to perform Grover's algorithm on entangled states, e.g. $|00\rangle + |11\rangle$. However, the algorithm apparently doesn't seem to amplify the amplitude of the state $|11\rangle$ ...
68 views

### What is the relationship between quantum circuit and quantum query complexities?

I am trying to ascertain a precise understanding of the relationship between the quantum query model of complexity and the quantum circuit model of complexity. Specifically, is there an established ...
213 views

### Proof using hybrid method that inverting a permutation requires exponential queries for BQP machines

Let's say I am given a permutation $\sigma$ that maps $n$ bit strings to $n$ bit strings. I want to output $1$ if $\sigma^{-1}(000\cdots1)$ is even and $0$ if $\sigma^{-1}(000\cdots1)$ is odd. It can ...
59 views

### Deutsch-Jozsa algorithm: an oracle implementation

I would like to implement the Deutsch-Jozsa algorithm myself using cirq. However, I faced the problem of the implementation of the oracle. I endeavored to apply the Deutsch-Jozsa algorithm for $n+1$-...
45 views

### Deutsch-Jozsa: why is only one evaluation of $f$ needed? [duplicate]

I might be asking something quite obvious but why is it stated that only one evaluation of $f$ is needed in the Deutsch-Jozsa algorithm? If we have a quantum oracle for $f:\{0,1\}^n\rightarrow\{0,1\}$ ...
78 views

259 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 ...
109 views

### Implementing the one-bit Deutsch Oracle algorithm using phase

The standard method of implementing the one-bit Deutsch Oracle algorithm is to use two qbits, one as input & one as output (which allows you to write the non-reversible constant functions in a ...
358 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), ...
80 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 ...
368 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?
906 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 ...
211 views

### Show that these two expressions for the oracle transformation are equivalent

Suppose $x \in \{0,1\}^n$. The standard way to make a query is with an oracle $O_x$ that given an input $|i,b \rangle$ returns $|i,b \oplus x_i \rangle$. Via the phase kick-back trick, this can be ...
5k 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 ...