Questions tagged [oracles]

An oracle is a "black box" operation (function) that is used as an input to an another algorithm (for example Deutch-Jozsa, Grover etc.). A parameter or feature of the Oracle is infered by the algorithm.

Filter by
Sorted by
Tagged with
0
votes
0answers
36 views

Deutsch-Jozsa algorithm: an oracle implementation

I would like to implement the Deutsch-Jozsa algorithm myself using cirq. However, I faced the problem of the implementation of the oracle. I endeavored to apply the Deutsch-Jozsa algorithm for $n+1$-...
1
vote
0answers
44 views

Deutsch-Jozsa: why is only one evaluation of $f$ needed? [duplicate]

I might be asking something quite obvious but why is it stated that only one evaluation of $f$ is needed in the Deutsch-Jozsa algorithm? If we have a quantum oracle for $f:\{0,1\}^n\rightarrow\{0,1\}$ ...
0
votes
2answers
66 views

Is there a way to construct a quantum circuit/oracle to check if 2 qubits in an unknown pure state are entangled?

I have 2 qubits which are in an unknown pure state i.e. their density matrix $\rho$ can be expressed as $|\psi\rangle\langle\psi|$. Let the initial state be $|\psi\rangle = c_{00}|00\rangle + c_{01}|...
3
votes
1answer
71 views

How to implement an Oracle

Often when reading about QC algorithms the Authors assume the existence of an Oracle. I understand this is so that they can focus on the overall structure of the algorithm, and an Oracle can be seen ...
2
votes
0answers
39 views

Recording Quantum Queries

Question is about techniques from this paper. Essentially the paper provides a way to record what queries were asked to a quantum-accessible oracle. We have the oracles: \begin{aligned} &\text { ...
2
votes
1answer
39 views

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

A parity function $f_s:\{0,1\}^{n}\rightarrow\{0,1\}$, for some $s\in \{0,1\}^n$, is a function of the form $f_s(x) = x \cdot s$, where the inner product is taken modulo 2. Show that $f_s$ is a ...
1
vote
0answers
34 views

Equality comparator for two qubits each

I'm trying to implement Grover's algorithm. For the oracle I have three nodes which are represented by two qubits for each node. How can I check if the states of two nodes are not equal?
6
votes
1answer
164 views

Preparing a quantum state from a classical probability distribution

Suppose I have a black-box unitary $U_p$ which is described as follows: given a finite probability distribution $p:\{1,\ldots,n\}\rightarrow \mathbb{R}_{\geq0}$, where $\sum_{x=1}^n p(x)=1$, the ...
1
vote
2answers
140 views

How to write decent code for oracle in Qiskit without custom circuit or long truth table?

I am now practising using Qiskit. The example of Grover's algorithm in tutorials suggests using logical expression, truth table or circuit to construct the oracle. In most textbooks on quantum ...
2
votes
1answer
63 views

How does the Grover's Algorithm work with a real example? [duplicate]

I am new to this field and I have been baffled by the idea of Oracle for a long time. I am aware of the procedure, but I am very confused about how we choose the oracle. Let say we have 4 poker ...
4
votes
2answers
123 views

Convert a quantum Phase Oracle into a Probability Oracle

Suppose we have an oracle $O_f$ that given an initial state $|x\rangle$ maps it into the following state: $$ O_f : |x\rangle \mapsto e^{if(x)} |x\rangle $$ Now, assuming that $f(x) \in [0,1]$, is it ...
4
votes
1answer
69 views

How does $U_f$ in Deutsch's Algorithm affect the state $|x\rangle$?

I am trying to read Nielsen's and Chuang's book on quantum computing and I am having problem understanding Deutsch's algorithm. According to my understanding of the algorithm, the state $|x\rangle$ ...
1
vote
1answer
87 views

Controlled NOT gate using multiple control qubits in Q#

I am trying to implement the Grover's search algorithm using Q# and I am not able to implement the oracle (black box) part for the search of state $|1010\rangle$. How to implement the controlled NOT ...
4
votes
4answers
557 views

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?

In Chapter 6 of "Quantum Computation and Quantum Information" textbook by Nielsen and Chuang, Exercise 6.5 p.255: We have an oracle gate $O$ for $n$ qubit ($2^n=N$ searching items), and we would ...
2
votes
2answers
161 views

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

From my understanding, the oracle function in Grover's algorithm is used as a way to check for the desired outcome. I have looked at this example which implements the Exactly-1 3-SAT problem and the ...
5
votes
0answers
41 views

Oracle for welded tree walk

There is a famous paper by Childs, et al, in which it is shown that a quantum algorithm can find the name of the exit node for a certain graph in a way that is exponentially faster than any classical ...
3
votes
1answer
220 views

Deutsch-Jozsa on non-balanced oracles

I'm interested in deciding if an oracle is constant or not, but cannot guarantee that the non-constant oracles are balanced. The Deutsch-Jozsa seems like the obvious starting place, but handling the ...
8
votes
0answers
148 views

What are examples of non-oracular versions of famous oracular problems?

Most quantum algorithms proposed, including Deutsch-Jozsa, Simon's, Bernstein-Vazirani etc, involve querying an oracle. If I understand correctly, the speedups depend on the oracle being efficiently ...
2
votes
1answer
53 views

Hamming with prefix oracle

I'm doing the Q# quantum katas and I'm stuck on an oracle in the Deutsch-Josza algorithm katas. Let $|x\rangle=|x_0x_1\dots x_{n-1}\rangle$ be a qubit array and $r$ be bit string of $k\leq n$. The $...
10
votes
1answer
235 views

Separating NP from BQP relative to an oracle

I was looking at this lecture note where the author gives an oracle separation between $\mathsf{BQP}$ and $\mathsf{NP}$. He hints at how "standard diagonalisation techniques can be used to make this ...
4
votes
1answer
89 views

Implementing the one-bit Deutsch Oracle algorithm using phase

The standard method of implementing the one-bit Deutsch Oracle algorithm is to use two qbits, one as input & one as output (which allows you to write the non-reversible constant functions in a ...
4
votes
1answer
279 views

Coding an oracle for Simon's algorithm

I am trying to implement Simon's algorithm which calls for a 2-to-1 mapping function that satisfies $f(x) = f(x⊕s)$. I am looking for a simple way to code the oracle (using $H$, $Cx$, and $R$ gates), ...
3
votes
1answer
78 views

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

If our input $x \in \{0, 1\}^{n}$ is given as a black box, we usually query an oracle as follows. $$O_{x}|i, b \rangle = (-1)^{b x_{i}} |i, b \rangle$$ $i = \{1, 2, \cdots, n \}$ is the index of the ...
5
votes
3answers
357 views

Why is the application of an oracle function not a measurement?

Why is the application of an oracle function not a measurement, causing the collapse of the system? How can you know the state of the system (the input of the oracle function) without measurement?
5
votes
1answer
824 views

How does an oracle function in Grover's algorithm actually work?

I have lately been studying quantum algorithms. I have gone through the Deutsch algorithm and Grover's algorithm. There's always a function in the oracle which somehow 'recognizes' the solution ...
7
votes
2answers
182 views

Show that these two expressions for the oracle transformation are equivalent

Suppose $x \in \{0,1\}^n$. The standard way to make a query is with an oracle $O_x$ that given an input $|i,b \rangle $ returns $|i,b \oplus x_i \rangle$. Via the phase kick-back trick, this can be ...
19
votes
1answer
5k views

What exactly is an oracle?

What exactly is an "oracle"? Wikipedia says that an oracle is a "blackbox", but I'm not sure what that means. For example, in the Deutsch–Jozsa algorithm,$\hspace{85px}$,is the oracle just the box ...
14
votes
5answers
3k views

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

I am trying to simulate Deutsch's algorithm (elementary case of Deutsch-Josza algorithm), and I am not entirely sure how I would go about implementing the quantum oracle necessary for the algorithm to ...
9
votes
1answer
460 views

Grover's algorithm: what to input to Oracle?

I am confused about what to input to Oracle in Grover's algorithm. Don't we need to input what we are looking for and where to find what we are looking for to Oracle, in addition to the ...