We’re rewarding the question askers & reputations are being recalculated! Read more.

# Tag Info

22

An oracle (at least in this context) is simply an operation that has some property that you don't know, and are trying to find out. The term "black box" is used equivalently, to convey the idea that it's just a box that you can't see inside, and hence you don't know what it's doing. All you know is that you can supply inputs and receive outputs. In the ...

8

There are two questions here. The first asks how you might actually implement this in code, and the second asks what's the point if you know which oracle you're passing in. Implementation Probably the best way is to create a function IsBlackBoxConstant which takes the oracle as input, then runs the Deutsch Oracle program to determine whether it is constant....

4

Although popular explanations of Grover's algorithm talk about searching over a list, in actuality you use it to search over possible inputs 0..N-1 to a function. The cost of the algorithm is $O(\sqrt{N} \cdot F)$ where $N$ is the number of inputs you want to search over and $F$ is the cost of evaluating the function. If you want that function to search over ...

4

Consider the last part of your question: Why can't we have a query of the form $$O_{x}|i \rangle = (-1)^{x_{i}} |i \rangle$$ This transformation is certainly unitary. Andrew Childs notes [...] that we can't distinguish between $x$ and $\bar{x}$ (bitwise complement of $x$) if we exclude the $|b \rangle$ register. I don't see why this should be the case....

4

Overview To recap the one-bit Deutsch Oracle problem, there are four possible oracle functions: constant-0, constant-1, identity, and negation. The task is to determine whether the oracle function is constant (constant-0 & constant-1) or variable/balanced (identity & negation). You can do this using phases as follows: Rewrite the oracle function as ...

3

You could do something like: assume the most significant bit of $s$ is 1. write a function that says "if the most significant bit of $x$ is 0, return $x$. if the most significant bit of $x$ is 1, return $x\oplus s$. This is easily implemented because you start by doing a transversal set of cNOT gates to copy $x$ from the input register to the output ...

3

An application of an oracle does not return a value; rather, it modifies the state of the system in a non-collapsing way. The oracles are a bit similar to controlled gates in this respect (in fact, a lot of oracles rely on controlled gates for their implementation). Consider, for example, CNOT gate: it does not measure the control qubit and apply an X gate ...

3

This is not so straightforward, I suspect. The issue is being able to distinguish between the constant case (e.g. every input gives output 0) and the case where only one input returns 1, and all others return 0. To distinguish these cases is essentially a Grover Search (the return of 1 being essentially a marked item that you want to search for the existence ...

3

One problem is that you are resetting the $\left|z\right\rangle$ register after applying the Controlled X(z, y) operation. Right before you reset, your $\left|z\right\rangle$ register is entangled with the other two registers, such that resetting in that way collapses any superposition on the $\left|x\right\rangle \left|y\right\rangle$ registers. While that'...

3

There is no way to build the oracle in a way which would not defeat the point of Deutsch's algorithm - that's why it is an oracle-based algorithm. The only way would be if you would come up with an incredibly hard to compute function (this is, an incredibly long circuit) which would take one input bit $x$ and give one output bit $f(x)$ (but on the way could ...

2

I don't have an example for Deutsch's algorithm handy, but here and here are two tutorials which walk you through implementing the Deutsch-Jozsa algorithm and the oracles it uses in Q#. The idea for these two algorithms is the same: you have to provide the oracle to the algorithm as an operation implemented elsewhere. This way the algorithm doesn't know ...

2

You have two examples on the IBM Q Experience page about the algorithm. They show an example of a function. This could inspire you for your simulations I hope.

2

Since this question seems to be in the context of Grover's search, I will explain using what happens in Grover's search, however, this is way more general. The oracle function $f$ itself can be thought of a specification as to what should happen given various basis states (in fact, just classical bit strings to classical bit strings). For example, $f$ can ...

2

Let $f$ be your favorite $\mathrm{SAT}$ problem. For example, one that I like is: Are there integers $x_1, x_2, x_3$, each $-2^{50}\le x_1,x_2,x_3 \le 2^{50}$, with $x_1^3+x_2^3+x_3^3=42?$ Write $f$ as a sequence of irreversible $\mathsf{NAND}$ gates, etc., and convert them to a sequence of reversible $\mathsf{CCNOT}$ gates, etc. to determine a unitary $... 2 The first example you're looking at is closer to the process of building an oracle for practical applications than the second one. The oracle circuit has to encode the Boolean formula for a specific instance of the problem you're trying to solve, and not the known solutions themselves. When you encode the oracle, you don't know the answer to the problem, but ... 2 It seems to me that the diagonalisation arguments that can be used are only slightly different from a standard one, e.g. such as can be found in these lecture notes about the Baker–Gill–Solovay Theorem (i.e., that there are oracles$A$for which$\mathsf P^A = \mathsf{NP}^A$and also oracles$A$for which$\mathsf P^A \ne \mathsf{NP}^A\$...

1

It's hard to know what are you referring to without context, but a "quantum oracle" is just a type of (generally unitary) gate. As such, it does not provide information about the system, and neither it induces collapse. You can find more details about oracles in this other question (and links therein). You cannot know the state of the system without ...

1

I think that ahelwer's answer touches on some the ways that we think about the complexity of algorithms. However — given that we don't literally have "oracles" in the real world which we wish to query, you might wonder why we would worry about query complexity, or the idea of oracles at all. I will try to give some perspective on this, and in ...

Only top voted, non community-wiki answers of a minimum length are eligible