Hot answers tagged

28

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


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


6

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


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

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

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

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.


5

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


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

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

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

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

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

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

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

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

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


3

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


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

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


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