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.
90
questions
1
vote
1
answer
91
views
Confusion about quantum walks and the quantum walk operator
I am looking at the Quantum Signal Processing paper by GH Low and IL Chuang here. One step that they used was Child's quantum walks. They constructed a walk operator, $W \left | u_\lambda \right > =...
- 87
1
vote
1
answer
34
views
Insufficient memory to run circuit using the statevector simulator
I am a newbie to quantum and have been trying qiskit library for learning quantum computing (in order to explore quantum effects on cryptography). I am basically ...
- 181
0
votes
1
answer
85
views
How to implement this oracle?
Suppose I have an oracle $U_f$ that maps $|x\rangle \mapsto (-1)^{f(x)}|x\rangle$ where $f : \{0,\dots,N\} \to \{0,1\}$ is such that $f(0)=0$. I want to show that I can implement the oracle $|x\rangle|...
0
votes
0
answers
15
views
Mapping a classical cipher into quantum implementation of Grover Oracle
I am translating simple ciphers into quantum implementation in order to create oracle for Grover algorithm. I have started the task with a light weight SPECK cipher (got both classical and quantum ...
- 181
2
votes
1
answer
69
views
High level implementation of quantum oracles
My question is related to a similar question which did not get a satisfactory answer. Since it was asked in 2020 and was somewhat general, I hope to ask a similar question in 2022 with a concrete ...
- 1,161
3
votes
1
answer
83
views
What makes oracle algorithms difficult to design and implement?
Recently, I have paid attention to some oracle algorithms, such as Grover. Generally speaking, an oracle is a kind of black box, and Grover's algorithm constructs an oracle through quantum circuits. ...
- 388
1
vote
0
answers
12
views
Encode Matrix Elements on register
I am trying to construct a circuit which makes the following encoding
$$O_H \left| i \right> \left| j \right> \left| z \right> = \left| i \right> \left| j \right> \left| z \oplus H_{ij} ...
- 159
1
vote
3
answers
85
views
How are black-box oracles implemented in Hamiltonian simulation?
I am currently trying to decompose a hessian to a sum of unitaries $H=\sum a_i U_i$.
The papers
VQLS and
Black-box Hamiltonian Simulation state that it can be done, but requires the use of an oracle ...
- 159
2
votes
0
answers
40
views
Mark a state if it is part of another register
I am wondering something, especially about Grover algorithm: imagine I have a quantum register $a$ and a quantum register $b$ of equal length.
Then, suppose I apply some algorithms on $a$ s.t. it is ...
- 63
1
vote
0
answers
90
views
Mapping $| y \rangle$ to $(-1)^{x \cdot y}| y \rangle$
I was checking some QC lecture notes by Ronald de Wolf and I came across this exercise that I can't solve.
Page 27 (pdf page 35), question 5, part b link: https://homepages.cwi.nl/~rdewolf/qcnotes.pdf
...
- 267
0
votes
0
answers
15
views
Parallelizing a circuit with repetitive blocks on permuted qubits
Assume one has access to the following oracle:
$$
O
|i\rangle|z\rangle = |i\rangle|z\oplus f(i_{N-1},i_{N-2},\ldots i_{1},i_{0})\rangle
$$
where $ |i\rangle =|i_{N-1}i_{N-2}\ldots i_{1}i_{0}\rangle $...
- 1,488
1
vote
1
answer
21
views
Why is quantum circuit version of oracle function changing inputs?
I'm new to quantum computing and trying to learn the basics. In the Deutsch–Jozsa algorithm, the oracle function $ f: \{ 0,1 \}^n \to \{0, 1\}$ is defined as a quantum circuit, which doesn't change ...
- 143
1
vote
2
answers
76
views
Quantum algorithm to determine the existence of a solution
Consider two vectors $u$, $t$ living in some space (let's say $ℝ^{n}$), and the following (simple) problem:
Find a vector $v$ such that $∃a,b\inℝ$, $au+bv=t$
Imagine I want to use Grover to find a ...
- 63
2
votes
1
answer
45
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{...
- 1,488
0
votes
1
answer
67
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 ...
- 275
1
vote
1
answer
76
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 ...
1
vote
1
answer
52
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}}}{\...
- 388
4
votes
1
answer
63
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 ...
- 195
1
vote
1
answer
75
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"?
- 143
6
votes
2
answers
136
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 ...
- 347
1
vote
2
answers
76
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 ...
- 51
0
votes
1
answer
65
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 ...
1
vote
1
answer
38
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 :
...
- 15
0
votes
1
answer
49
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 ...
- 15
1
vote
1
answer
92
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 ...
- 25
2
votes
1
answer
88
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)$...
- 51
5
votes
1
answer
111
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 ...
- 1,488
2
votes
1
answer
211
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\...
- 715
4
votes
2
answers
241
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 ...
- 441
3
votes
1
answer
144
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 ...
0
votes
0
answers
71
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 ...
- 1
0
votes
0
answers
31
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 ...
0
votes
1
answer
69
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
3
votes
1
answer
164
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 ...
- 31
1
vote
1
answer
63
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 ...
- 13
3
votes
0
answers
60
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\}\...
- 173
5
votes
1
answer
206
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 ...
- 183
2
votes
1
answer
64
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 ...
- 85
3
votes
2
answers
110
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 ...
- 33
4
votes
0
answers
47
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 ...
- 493
1
vote
1
answer
90
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
2
answers
76
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 ...
- 211
3
votes
1
answer
67
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 \...
- 953
3
votes
1
answer
77
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 ...
- 33
3
votes
1
answer
91
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 ...
- 55
3
votes
1
answer
457
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 ...
- 139
8
votes
3
answers
386
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
1
answer
325
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. ...
- 153
1
vote
0
answers
116
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 ...
- 133
4
votes
2
answers
608
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⟩)
$$
...
- 139