# Tag Info

30

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

25

The function $f$ is simply an arbitrary boolean function of a bit string: $f\colon \{0,1\}^n \to \{0,1\}$. For applications to breaking cryptography, such as , , or , this is not actually a ‘database lookup’, which would necessitate storing the entire database as a quantum circuit somehow, but rather a function such as \begin{equation*} x \...

10

Apply it twice: $$O_xO_x|i\rangle|b\rangle=O_x|i\rangle|b\oplus x_i\rangle=|i\rangle|b\oplus x_i\oplus x_i\rangle=|i\rangle|b\rangle$$ Hence, $O_x$ is its own inverse, and therefore reversible. To prove unitarity, it makes more sense to prove that $O_x$ has eigenvectors $$|i\rangle(|0\rangle+|1\rangle)\quad\text{and}\quad|i\rangle(|0\rangle-|1\rangle)$$ ...

10

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

8

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

7

There are different ways to achieve that, my favorite is probably this one: The oracle you describe above is just a classical function ("True if my bitstring is 101 or 110") converted to a quantum phase flip. So essentially you only have to build a circuit that implements that classical logic plus some gates to do the phase flip. Option A: Via ...

6

A lot of explanations of Grover's search suffer from the common issue of claiming it's a database search or, worse yet, looking for a hardcoded element. (You have examples of both in your question, so you've already noticed this!) In reality Grover's search is best thought of as a way of searching for an element that satisfies a certain condition, i.e., ...

6

Grover's algorithm We are given a function $f(a)$ such that $f(a)=0$ for all of the $N$ possible values of $a$, except when $a=\omega$ in which case we have $f(\omega)=1$. Assuming that this $f(a)$ can be calculated using a classical reversible code or hardware, we can find $\omega$ with $\mathcal{O}(\sqrt{N})$ steps using a quantum circuit as opposed to a ...

5

Notice that $\mathcal O_x$ is a permutation matrix. The matrix elements are $$\langle j, c\rvert\mathcal O_x\lvert i,b\rangle =\delta_{ij}\langle c\rvert b\oplus x_i\rangle =\delta_{ij}\delta_{c,b\oplus x_i}.$$ In other words, $\mathcal O_x$ is diagonal with respect to the first register, and, for each block corresponding to a given $i$, connects all and ...

5

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

5

Well, Grover's original paper, "Quantum mechanics helps in searching for a needle in a haystack" clearly states, it assumes that C(S) can be evaluated in a constant time. Grover's search is not concerned about the implementability, but the polynomial reduction in what's called a query complexity (how many times you consult the oracle, like a classical ...

5

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

5

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

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

5

Typically the oracle is a reversible circuit that implements some classical pass/fail check. In order to query the circuit under superposition, it has to be run on a quantum computer instead of a classical computer. That's all the authors mean when they say quantum hardware is required.

4

You can implement a multiple controlled $\operatorname{Z}$ gate on $n+1$ qubits together with two $\operatorname{X}$-gates on the $n+1$-th qubit before and after the multiple controlled gate. This gate can be made by constructing a multiple controlled $\operatorname{NOT}$ gate, that is a $C^n\operatorname{NOT}$ gate, and on the $n+1$-th qubit a $\... 4 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 ... 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 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 ... 4 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 ... 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 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 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 In general, you want to understand the process by which you compute the matrix elements if you were doing it by hand. In the example you give, for instance, you're effectively computing |i-j|==1. This has a classical algorithm which you can figure out, and there's your oracle. In this specific instance there are probably some smarter things you can do. For ... 4 Assuming x is n bits, here's a simple procedure: take n ancilla qubits, all prepared in |0\rangle. Do a transversal controlled-not (i.e. bit by bit controlled-not) from the register with |x\rangle to the ancilla register. THis means that if you started wuth$$ \sum_xa_x|x\rangle, $$you now have$$ \sum_xa_x|x\rangle|x\rangle.$$Next, find a bit ... 4 For adiabatic Grover you want the ground state of the final Hamiltonian to be the marked item. The key idea with Grover is that the item is hard to find but easy to verify. So the idea is you embed the 'easy to verify' into the Hamiltonian, which is the similar as marking the item via the phase oracle in the gate model. For example consider a simple case ... 3 Ancilla-free solution: replace the two controlled-SWAPs in the "summary update" of Craig Gidney's solution with controlled-$Z$s between the second and fourth qubits in the diagram, and remove the third qubit. (That is, instead of swapping$|-\rangle$with a$|+\rangle$state stored in the second register, conditioned on$|q\rangle$being set to 1, ... 3 As mentioned above there is nothing called "Oracle free" algorithm. Let's put this in simple words: Consider we are making a problem solving algorithm to solve the roots of a quadratic equation. Let the equation be$ax^2+bx+c$and the algorithm finds the values of$x$. Here the function to create$ax^2+bx+c$acts as an oracle. You can put this ... 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 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 ...

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