# Tag Info

23

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

9

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

6

The simplest solution is to use an ancilla in the $|+\rangle$ state. Swap that ancilla for the oracle's output qubit, conditioned on the control qubit being false, before and after applying the oracle. Since toggling the $|+\rangle$ state has no effect, this deactivates the oracle when the control is set. Here's this technique applied to a simple comparison ...

5

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

4

You can implement a controlled version of any gate in Q# using Controlled functor; for the oracles, you'll use something like Controlled X(controlQubits, targetQubit), where controlQubits is an array of qubits that have to be in 1 state for the X gate to be applied and targetQubit is the qubit to which the gate is applied. Q# also has a neat library ...

4

Let's say that the first bit of $s$ $s_0=1$ (the argument will be exactly the same for any bit, just for convenience). You can split the space of inputs $x \in \{0,1\}^n$ in two halves: one half where $x_0 = 0$ and the other half where $x_0 = 1$. For each bitstring $x$ from the first half you'll have a bitstring $\tilde{x}$ from the second half which will ...

4

As a bare minimum, you would need access to a controlled version of your oracle. This cannot be created from the oracle itself (I'm sure there's already an SE question about this part, but cannot immediately lay my hands on it). A typical construction would allow you to create (Hadamard - controlled oracle - Hadamard) would create an output $$\cos\frac{f(x)... 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.... 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 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... 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 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 You are given a quantum circuit for U compiled into the H/CNOT/T gateset. Derive a controlled version of U by adding a control qubit q, replacing every H with a controlled H, every CNOT with a CCNOT, and every T with a controlled T. In all cases the new control goes on the q. Recompile the modified gates down into the H/CNOT/T gate set. Prepend and ... 2 This picture can be confusing, since it makes some assumptions that are not clear when you quickly scan through the text. The picture of the oracle U_f describes its effect on the basis states that go into it, not on arbitrary superposition states. If both x and y are basis states, the oracle will behave exactly as the rectangle says, but the ... 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 Suppose we have two quantum circuits, the first computes (or at least approximates) the classical \sqrt{\cdot} function$$S|x\rangle|0\rangle=|x\rangle |\sqrt{x}\rangle,$$while the second circuit A computes (again could probably just approximate) the \arccos(\cdot) function$$A|x\rangle|0\rangle=|x\rangle |\arccos(x)\rangle. Lastly, suppose we have ...

1

If your function is defined in a way that requires you to iterate over all possible inputs to implement the oracle, you clearly lose the advantage of using Grover's algorithm. This question goes into detail about using Grover's search for unordered database search, which is pretty much your example. Instead, the function should be defined in a way that ...

1

In your card example, since you've created the encoding, you've kind of already made Grover's algorithm useless. That is, you already know that 00 is the spade of Ace, so you don't need to search. Grover's algorithm would only help find the spade of Ace if you didn't already know which bitstring encoded it. As an example: Suppose you shuffle the cards and ...

1

Given controlled access to the phase oracle, this is possible with surprisingly small overhead by avoiding phase estimation altogether. The technique you are after relies on applying "quantum singular value transformations" to objects that are known as "block encodings", and it was invented by Gilyén et al. in 2018. The idea was originally introduced in this ...

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

1

If we express the action of $O_x$ on the basis $\mid i, \pm \rangle$ instead of $\mid i , b \rangle$ \begin{eqnarray*} O_x \mid i , + \rangle = \mid i , + \rangle\\ O_x \mid i , - \rangle = (-1)^{x_i} \mid i , - \rangle\\ \end{eqnarray*} Because we say auxiliary qubits must be started and ended with $0$, \begin{eqnarray*} O_x'' &=& (1 \otimes S_x ...

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