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
2 votes
1 answer
28 views

Oracle for amplitude addition

Assume one is given two oracle circuits providing access to matrices $A_{ij}$ and $B_{ij}$ as follows (see eq. (6.2) here): \begin{equation} O_A |0\rangle|i\rangle|j\rangle=\left(A_{ij}|0\rangle+\sqrt{...
user avatar
  • 1,408
0 votes
1 answer
53 views

Is there a toy oracle to show the feasibility of Grover's algorithm?

Is there any small 'toy' oracle that can show the feasibility of Grover's algorithm for searching (without using the geometric rotation interpretation)? It is confusing that we cannot know the ...
user avatar
1 vote
1 answer
67 views

Why can you check for entanglement using the quantum Fourier transform?

I'm reading this paper on quantum random oracles, and I have some fundamental questions about certain statements that seem to be intuitive (but I can't seem to figure it out). My goal is to have a ...
user avatar
0 votes
1 answer
40 views

Is there such a quantum oracle that makes the oracle corresponding to the function sigmoid?

Is there such a quantum oracle that makes the oracle corresponding to the function sigmoid? That is: ${{U}_{f}}|\psi \rangle =\text{sigmoid}(|\psi \rangle )$, where $\text{sigmoid}=\frac{{{e}^{x}}}{\...
user avatar
3 votes
1 answer
51 views

Quantum Fourier Transform on $\mathbb{Z}_R^n$

I am reading Regev's proof of existence of quantum algorithm to sample from a discrete Gaussian distribution given a CVP oracle and I am confused about his calculation of the Quantum Fourier transform ...
user avatar
  • 185
1 vote
1 answer
46 views

Simon's algorithm circuit with hidden oracle

I am wondering if I have the Output Histogram of a Simon Circuit where the Oracle is hidden, is there a way to reverse engineer or do anything that will make me figure out S "secret"?
user avatar
  • 143
6 votes
2 answers
122 views

How do we know a "quantum function call" is worth the same amount of time as a "classical function call?"

In quantum and classical algorithms, we often need to do "function calls." Quantum algorithms such as Grover's algorithm or the Deutsch–Jozsa algorithm can take a fewer number of function ...
user avatar
1 vote
2 answers
53 views

Implementing the Oracle in Grover

I need your expert opinions/comments on this problem. Suppose I have a database (say 16 entries), such that db[0] = 0.12, db[1] = 0.84, db[2] = 0.55, ..., db[15] = 0.91. I want the oracle to mark ...
user avatar
  • 51
0 votes
1 answer
37 views

Implementing a multioutput quantum oracle on Qiskit

A quantum boolean oracle is an operator that should work as follows: $ \sum_x U_f |x, 0> = \sum_x |x, f(x)>$. Now, suppose that I have two input qubits and two output qubits and I want to ...
user avatar
1 vote
1 answer
34 views

Implementation for a Translationally Invariant Algorithm

I'm working on inserting an item into a sorted list https://arxiv.org/pdf/quant-ph/9901059.pdf. I would like to know how to implement this formula with Qiskit or just the circuit representing it : ...
user avatar
  • 15
0 votes
1 answer
46 views

Oracle for searching in a sorted list

I'm working on the algorithm to search an item in a sorted list based on this article: https://web.mit.edu/rsi/www/pdfs/papers/2003/2003-brianj.pdf I can't see how to make implement this oracle with ...
user avatar
  • 15
1 vote
1 answer
73 views

How do bitstring oracles work in quantum circuits?

In most diagrams of oracles for basic algorithms such as Deutsch-Jozsa (e.g., https://qiskit.org/textbook/ch-algorithms/deutsch-jozsa.html) the inputs are bitstrings $x$ and $y$, and outputs are ...
user avatar
  • 11
2 votes
1 answer
68 views

Implementing the Quantum Oracle

Suppose I have a simple function $f(x): 1 + x$ and I want to find $x$ such that $f(x) = 5$, for instance, using the Grover search. Am I correct to say that I will need to implement this function $f(x)$...
user avatar
  • 51
5 votes
1 answer
101 views

Implementing $a^\dagger|\psi\rangle$

One way or another, I would like to implement the action of the second-quantized creation operator on a quantum state: $|\psi\rangle\mapsto a^\dagger|\psi\rangle$. The motivation, of course, comes ...
user avatar
  • 1,408
2 votes
1 answer
134 views

Construct a standard oracle using a phase oracle

Suppose $i \in \{0,1\}^n, b \in \{0,1\}$. Given a phase oracle $U_{f} |i\rangle = (-1)^{f(i)} |i\rangle$ and its controlled version $CU_f$, it is possible to construct a standard oracle $U_f' |i\...
user avatar
  • 715
4 votes
2 answers
159 views

Phase Oracle in Qiskit Solving Satisfiability Problems using Grover's Algorithm Section

In Qiskit Textbook, there is a section on solving satisfiability problems using Grover's Algorithm. For the 3SAT instance they construct the following phase oracle: Is there any reasoning behind ...
user avatar
  • 399
2 votes
1 answer
97 views

Using Quantum Bit String Comparision inside Grover's algorithm

Intro I am trying to implement a quantum bit string comparator (QBSC) circuit (based on this paper) into a simple Grover's algorithm but I am unfortunately running into issues. The paper has two ...
user avatar
0 votes
0 answers
53 views

Qiskit- Building an oracle to test on Qiskit's Grover

I want to build an oracle with multiple state solutions. For example: For n=4 qubits, I want the state solutions to be 1111, 1101, 1110 and 1100. So, as you can see, in all solutions, there are two ...
user avatar
  • 1
0 votes
0 answers
25 views

Multiple Values Grover's Algorithm Design Circuit

I am currently working on implementing the oracle with multiple solutions, with the equation as follows: $|q\rangle \xrightarrow{\text{oracle}} (-1)^{f(x)}|q\rangle$ where $f(x) \leq \delta $ will ...
user avatar
0 votes
1 answer
60 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\...
user avatar
  • 3
3 votes
1 answer
105 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 ...
user avatar
  • 31
1 vote
1 answer
52 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 ...
user avatar
3 votes
0 answers
49 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\}\...
user avatar
5 votes
1 answer
179 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 ...
user avatar
2 votes
1 answer
49 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 ...
user avatar
  • 55
3 votes
2 answers
101 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 ...
user avatar
  • 33
4 votes
0 answers
42 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 ...
user avatar
  • 483
1 vote
1 answer
72 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 ...
user avatar
1 vote
2 answers
67 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 ...
user avatar
3 votes
1 answer
56 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 \...
user avatar
3 votes
1 answer
69 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 ...
user avatar
2 votes
1 answer
81 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 ...
user avatar
3 votes
1 answer
355 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 ...
user avatar
7 votes
3 answers
324 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 ...
user avatar
3 votes
1 answer
296 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. ...
user avatar
1 vote
0 answers
84 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 ...
user avatar
4 votes
2 answers
486 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⟩) $$ ...
user avatar
3 votes
1 answer
391 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 ...
user avatar
3 votes
1 answer
93 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 ...
user avatar
2 votes
3 answers
148 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\...
user avatar
  • 139
3 votes
1 answer
130 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 ...
user avatar
2 votes
1 answer
42 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 ...
user avatar
2 votes
1 answer
99 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$ ...
user avatar
  • 139
4 votes
1 answer
94 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 ...
user avatar
5 votes
1 answer
262 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 ...
user avatar
1 vote
0 answers
61 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\}$ ...
user avatar
  • 181
0 votes
2 answers
153 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}|...
user avatar
  • 742
5 votes
2 answers
212 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 ...
user avatar
  • 413
2 votes
0 answers
54 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 { ...
user avatar
2 votes
1 answer
104 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 ...
user avatar
  • 285