Hot answers tagged

38 votes
Accepted

What exactly is an oracle?

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 ...
DaftWullie's user avatar
31 votes
Accepted

How is the oracle in Grover's search algorithm implemented?

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 [1], [2], or [3], this is not actually a ‘...
Squeamish Ossifrage's user avatar
12 votes

How would I implement the quantum oracle in Deutsch's algorithm?

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 ...
ahelwer's user avatar
  • 4,078
10 votes

How to prove that the query oracle is unitary?

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 ...
DaftWullie's user avatar
10 votes
Accepted

Nielsen and Chuang, Exercise 6.5: How to simulate oracle for n+1 qubits using one oracle gate for n qubits and one extra qubit?

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....
Craig Gidney's user avatar
  • 35.3k
7 votes
Accepted

Preparing a quantum state from a classical probability distribution

Suppose we have two quantum circuits, the first one $S$ computes (or at least approximates) the classical squareroot function ($\sqrt{\cdot}$) via $$S|x\rangle|0\rangle=|x\rangle |\sqrt{x}\rangle,$$ ...
Condo's user avatar
  • 1,968
7 votes
Accepted

Implementing Grover's oracle with multiple solutions in Qiskit

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 ...
Cryoris's user avatar
  • 2,893
6 votes
Accepted

In Grover's Algorithm, does the exact solution need to be given to the oracle?

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 ...
Mariia Mykhailova's user avatar
6 votes

How is the oracle in Grover's search algorithm implemented?

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 ...
Aritra's user avatar
  • 303
6 votes

How to implement an Oracle

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$. ...
DaftWullie's user avatar
6 votes
Accepted

How can Grover's algorithm be implemented when having a string or other data type as input?

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 ...
Mariia Mykhailova's user avatar
6 votes

In the adiabatic version of Grover's algorithm, how is the Hamiltonian constructed?

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)$ ...
user1271772's user avatar
  • 13.5k
5 votes

How would I implement the quantum oracle in Deutsch's algorithm?

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 ...
Norbert Schuch's user avatar
5 votes

Grover's algorithm: what to input to Oracle?

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{...
Craig Gidney's user avatar
  • 35.3k
5 votes
Accepted

Separating NP from BQP relative to an oracle

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&...
Niel de Beaudrap's user avatar
5 votes
Accepted

Implementing the one-bit Deutsch Oracle algorithm using phase

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 ...
ahelwer's user avatar
  • 4,078
5 votes
Accepted

How to prove that the query oracle is unitary?

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\...
glS's user avatar
  • 24.1k
5 votes

Deutsch-Jozsa on non-balanced oracles

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 ...
DaftWullie's user avatar
5 votes

Convert a quantum Phase Oracle into a Probability Oracle

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 ...
DaftWullie's user avatar
5 votes

Is Grovers Algorithm Oracle creation a hardware level aspect?

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 ...
Craig Gidney's user avatar
  • 35.3k
5 votes
Accepted

Is it possible to construct Grover search from Clifford gates only?

The diffusion operator is a multi controlled not operation (modulo some hadamards). It's not a Clifford operation. Also any useful oracle you'd use with Grover's algorithm won't be Clifford operations ...
Craig Gidney's user avatar
  • 35.3k
5 votes

When is it justified to have an oracle in a quantum algorithm?

Your question already contains the answer: oracles are used when the general algorithm described doesn't know the specific structure of the problem it's solving and thus cannot rely on it. In this ...
Mariia Mykhailova's user avatar
5 votes
Accepted

Given $f: \{0, 1\}^n\to\{0, 1\}^m$, how many qubits are needed to implement the oracle $\mathcal U|x,0\rangle^{\otimes m}=|x,f(x)\rangle$?

Usually, saying that there is access to an oracle compute $f$ is equivalence to saying that you assume a model in which it is given that $f$ can be computed for free, Namely, In your case $f :\{0,1\}^...
Dudu Ponar's user avatar
4 votes

Oracle for welded tree walk

I often wonder if the welded trees considered in the Childs et al. paper have any applicability to questions in algorithmic knot theory such as knot identification/knot canonization. For example, I ...
Mark Spinelli's user avatar
4 votes
Accepted

Controlled NOT gate using multiple control qubits in Q#

You can implement a controlled version of any gate in Q# using Controlled functor; for the oracles, you'll use something like ...
Mariia Mykhailova's user avatar
4 votes
Accepted

Implementing an oracle

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 ...
nippon's user avatar
  • 1,497
4 votes
Accepted

Coding an oracle for Simon's algorithm

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, ...
DaftWullie's user avatar
4 votes
Accepted

Why is the second register needed to define bit flip quantum oracles in a way that distinguishes between complementary oracles?

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 [...] ...
Niel de Beaudrap's user avatar
4 votes

How would I implement the quantum oracle in Deutsch's algorithm?

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&...
Niel de Beaudrap's user avatar
4 votes
Accepted

Why is the function $f_s(x)=\sum_i x_i s_i \pmod 2$ balanced?

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 ...
Mariia Mykhailova's user avatar

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