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.
59
questions
0
votes
1answer
39 views
How to separate initializing qubits from runing algorithm several times
I have read several papers about quantum computing. It looks like any algorithm consists of several phases. For example in Grover algorithm initially qubits must be initialized from reset state $|0\...
3
votes
1answer
62 views
How to implement a quantum array
I'm trying to implement a quantum array. That is one that stores qubits and can be indexed via qubits.
I can create one that handles setting values fairly easy. Have two registers, one for the ...
1
vote
1answer
24 views
Is this a valid implementation of the balanced Deutsch-Jozsa oracle
Is it correct to implement a balanced Deutsch-Jozsa oracle by CNOTing the first qubit with the last one (the ancilla qubit), it would get you a balanced output.
And if it's valid why is it not ...
3
votes
0answers
43 views
How to efficiently construct quantum circuits of oracles in multi-target quantum search?
In standard Grover's quantum search with only one target or its extension of multi-target quantum search, one of the two key parts is to quantize the boolean function
$$f(x):\{0,1,\cdots,N-1\}\...
5
votes
1answer
117 views
BHT algorithm implementation
Summary of Method
Amplitude Amplification Summary
The BHT algorithm uses amplitude amplification, a nice generalisation of Grover's algorithm, where there is a subset $G\subset X$ of good elements in ...
2
votes
1answer
36 views
Is it possible to convert classical oracle to quantum ones?
If an attacker possesses a classical oracle, so she could apply chosen plain text attacks. Is there an easy way to reduce this oracle to quantum ones allowing her to make quantum chosen plain text ...
3
votes
2answers
81 views
Can we use reversible computation to construct oracle circuits?
One of the question while I discussed with my colleague in the math department was the construction of oracle circuit.
In computer science, specifically in algorithm, we take oracle as granted and ...
4
votes
0answers
36 views
Proving that with probability 1 $NP \nsubseteq BQP$ with respect to random oracles
In the paper Strength and Weakneses of Quantum Computers (https://arxiv.org/abs/quant-ph/9701001) by Bennet, Bernstein, Brassard and Vazirani, it is shown the statement in the title (Theorem 3.5 in ...
1
vote
1answer
48 views
How is the oracle physically implemented in Deutsch algorithm?
In the Deutsch algorithm, the oracle implementation for the function f is taken as a black box, but physically, how is the oracle implemented? Why can we assume such a black box exists for the ...
1
vote
2answers
44 views
Can there be different gate implementations of same oracle implementation?
I have been reading about Bernstein-Vazirani Algorithm, and it uses what is known as a phase oracle. Basically, it is CNOT gate with several controls attached to the ancilla qubit $|-\rangle$ (it is ...
3
votes
1answer
48 views
Learning k positions of a Boolean function with a quantum computer
Consider a Boolean function with multiple outputs $f: \{0, 1\}^{n} \rightarrow \{0, 1\}^{m}$, and consider being given oracle access to the function $f$. Let us denote the oracle by $O_f$. For an $x \...
3
votes
1answer
52 views
How can one evaluation of $U_f$ in Grover's algorithm use only one query of $f$?
I am very much new to quantum computation and do not have a background in quantum mechanics, which I believe is at the root of my confusion around Grover's algorithm.
Suppose that we have a search ...
0
votes
0answers
53 views
Simon's Algorithm - Equivalent Oracles Giving Different Results
In Simon's algorithm, is it possible to have two different oracles that return the same results on their own but cause Simon's algorithm to return different results from one another? In what sort of ...
2
votes
1answer
56 views
Quantum Katas - Tutorials - Oracles - Task 3.3 (OR oracle of all bits except for a single bit)
Let $x$ be an arbitrary state composed of $N$ qubits and $k$ be an integer such that $0\leq k \leq N.$
The task is to ignore the $k$-th bit and to flip the sign of $x$ if any of the remaining bits are ...
3
votes
1answer
165 views
Implementing 3-Qubit Grover Algorithm in Qiskit
The Qiskit tutorial on Grover's Algorithm shows an example of finding two marked solutions out of 8 items, produced by 3 qubits. Using the general diffuser code it provides, however, I realize that ...
7
votes
3answers
201 views
In the adiabatic version of Grover's algorithm, how is the Hamiltonian constructed?
X-posted on physics.stackexchange
In quantum computation, there is a famous algorithm to search a marked item in an unstructured database called Grover's algorithm. It achieves a quadratic speedup ...
3
votes
1answer
243 views
How can Grover's algorithm be implemented when having a string or other data type as input?
For some reason, I'm having difficulty with a seemingly very basic component of Grover's. When reading most explanations, the problem is framed as "consider an unstructured database of N items. ...
1
vote
0answers
52 views
In Grover's oracle, how is the matrix $U_f$ derived for a generic $n$?
Grover's algorithm works by iteration of the operator $$\tag{1}G:=U_S^\perp U_f=H^{\otimes n}U_0^\perp H^{\otimes n}.$$
I know how to write down the matrix for $U_S^\perp$ (the inversion about the ...
4
votes
2answers
253 views
Implementing Grover's oracle with multiple solutions in Qiskit
I want to turn a state
$$
|\Psi_1⟩ = \frac{1}{\sqrt{8}}(|000⟩+|001⟩+|010⟩+|011⟩+|100⟩+|101⟩+|110⟩+|111⟩)
$$
into
$$
|\Psi_2⟩ = \frac{1}{\sqrt{8}}(|000⟩+|001⟩+|010⟩+|011⟩+|100⟩-|101⟩-|110⟩+|111⟩)
$$
...
3
votes
1answer
179 views
In Simon's algorithm, is there a general method to define an oracle given a certain periodicity?
I have to implement Simon's algorithm in Cirq. I have problems determining the oracle $f(x)$ defined such that $f(x)=f(x\oplus a)$ from a certain value of $a$.
Given a random $a$, is there a general ...
3
votes
1answer
66 views
Weird Grover's Algorithm Behavior
I am attempting to use Grover's to find elements in an array that satisfy a comparative query (=, <, >, etc). I am using Qiskit, and am using a qRAM to encode my array.
I have experimented with ...
2
votes
3answers
103 views
Grover's algorithm for finding 6/8 states
I'm trying to apply the diffusion operator to this state (normalization factors excluded):
$|000\rangle + |001\rangle - |010\rangle - |011\rangle - |100\rangle - |101\rangle - |110\rangle -|111\...
2
votes
1answer
84 views
Is it possible to construct Grover search from Clifford gates only?
In the article Is Quantum Search Pratical the authors emphasized that a complexity of an oracle is often neglected when advantages of Grover search are discussed. In the end, a total complexity of the ...
2
votes
1answer
36 views
Is Grovers Algorithm Oracle creation a hardware level aspect?
There are numerous questions that asks about practical application demonstration of the Grover algorithm for arrays and databases.
However examples are not seen anywhere.
While searching for its ...
2
votes
1answer
87 views
Is Grover's algorithm only applicable to a pure state?
I've been trying to perform Grover's algorithm on entangled states, e.g. $|00\rangle + |11\rangle$. However, the algorithm apparently doesn't seem to amplify the amplitude of the state $|11\rangle$ ...
4
votes
1answer
85 views
What is the relationship between quantum circuit and quantum query complexities?
I am trying to ascertain a precise understanding of the relationship between the quantum query model of complexity and the quantum circuit model of complexity. Specifically, is there an established ...
5
votes
1answer
240 views
Proof using hybrid method that inverting a permutation requires exponential queries for BQP machines
Let's say I am given a permutation $\sigma$ that maps $n$ bit strings to $n$ bit strings. I want to output $1$ if $\sigma^{-1}(000\cdots1)$ is even and $0$ if $\sigma^{-1}(000\cdots1)$ is odd. It can ...
1
vote
0answers
57 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
117 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}|...
5
votes
2answers
172 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
49 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
47 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
44 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?
7
votes
1answer
431 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
384 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
181 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 ...
2
votes
0answers
53 views
Graphs are represented using oracle, where oracle is the adjacency matrix. Is there any simple example of this? [closed]
I have been reading papers on graph theory in quantum computing. Mostly, papers explain that they use adjacency matrix to represent the graph. But I could't find the practical simple example to ...
5
votes
2answers
349 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
119 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
164 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 ...
5
votes
4answers
740 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 ...
3
votes
2answers
326 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 ...
6
votes
1answer
154 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 ...
4
votes
1answer
289 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 ...
10
votes
1answer
245 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
78 views
Hamming with prefix oracle
I'm doing the Q# quantum katas and I'm stuck on an oracle in the Deutsch-Jozsa 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 $k$...
11
votes
1answer
314 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
156 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 ...
5
votes
1answer
615 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
84 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 ...