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.
139 questions
0
votes
1
answer
100
views
How to construct an oracle and flips the phase of the solution bit strings?
I am trying to solve the boolean problem (x1 or x2) and (~x1 or ~x2 or x3) using Grover's algorithm. The only measured bits are q0, q1, and q2. This is my oracle:
...
- 3
0
votes
1
answer
79
views
Does applying a balanced function on a single qubit out of n and applying constant function on the remaining n-1 implements overall BALANCED function?
I am studying Deutsch-Josza Algorithm. Here's what I get for 2-qubit case.
$$
\begin{aligned}
|\psi_0\rangle &= |0\rangle\otimes |0\rangle \\
|\psi_1\rangle & = H|0\rangle \otimes H|0\rangle \\...
- 9
0
votes
0
answers
92
views
One Shot Signature Security Proof
I was studying the paper (e-print) "One Shot Signatures and Applications to Hybrid Quantum/Classical Authentication." In it, the authors define "equivocal hashing" and provide a ...
- 23
2
votes
1
answer
196
views
How to Implement an Oracle in Qiskit or Cirq that Maps f(a, b) = (x^a)*(y^b)?
I'm trying to implement an oracle in Qiskit or Cirq for a function f that maps Z x Z to a group A. The function is defined as f(a, b) = (x^a) * (y^b).
a and b are the first two quantum registers,...
- 41
2
votes
2
answers
127
views
Construction of $f(x) = x \pmod 2$ as an oracle function
I'm trying to conceptualise how one would implement an oracle function of f(x) = x in the context of the Deutsch-Josza Algorithm. So far I understand the basic idea of implementing trivial constant ...
-1
votes
1
answer
161
views
Does this quantum circuit reproduce the oracle in Deutsch's algorithm?
This seems to me a fine quantum oracle for the balanced one bit function $f(x)=x$, but putting it in Deutsch's algorithm circuit will give the result $|0\rangle$, i.e. the function is evaluated as ...
2
votes
1
answer
112
views
How to construct the HHL oracle circuit when the entries of $A$ are described by a polynomial?
Among other assumptions, HHL's algorithm assumes that the entries of the coefficient matrix $A$ (where $Ax=b$ is the linear system to be solved) can be realized by means of an oracle circuit $U_A$. ...
- 153
1
vote
0
answers
56
views
QMA-QCMA oracle with quantum gates
While reading the QMA-QCMA paper by Aaronson and Kuperberg I wondered how their result extends to quantum circuits.
Suppose you have an oracle $O$ such that $O\left|\psi\right>=-\left|\psi\right>...
- 1,609
3
votes
2
answers
231
views
Show that transformation $U_f: \left| x, y \right\rangle \to \left| x, y \oplus f(x) \right\rangle$ is unitary [duplicate]
I am reading Quantum Computation and Quantum Information by Chuang and Nielsen and they claim that it is easy to show that transformation $U_f: \left| x, y \right\rangle \to \left| x, y \oplus f(x) \...
- 131
1
vote
1
answer
110
views
Quantum circuit of stateful oracle
Suppose I have operator $U_f$ that maps state $|x\rangle|y\rangle|0\rangle$ to another state $|x\rangle|y\rangle|f(x, y)\rangle$.
The function $f$ has its internal state, that changes on each ...
- 169
3
votes
0
answers
50
views
Is it safe to assume that any hybrid algorithm can be transformed into a purely quantum form with comparable complexity?
Suppose we have a definite function of interest from numbers to numbers (from a finite set).
In general, we have a lot of options when we construct algorithms that compute it (with some errors, ...
- 8,201
0
votes
1
answer
834
views
What is the oracle in every quantum algorithm?
There is a machine called oracle which appears in a lot of algorithm of quantum computing, such as Deutsch's algorithm, QFT period-finding. This oracle machine really makes me confused. I've read ...
- 191
1
vote
0
answers
144
views
Memory Issue When Executing Quantum Circuit on AWS Braket with qiskit
Description:
I'm currently facing memory-related issues while trying to execute quantum circuits as a hybrid job on the aws tensor network simulator 'tn1' using Qiskit. Despite various attempts to ...
- 11
3
votes
1
answer
136
views
Does k-fold FORRELATION problem lies in BQP or $BQP^O$
It is known that the Simon Problem lies in $BQP^O$ (oracular problem). Even it proves $\exists O$ $BPP^O\neq BQP^O$. Or It separates the classes in the Oracle/Query model of computation.
Meanwhile, ...
- 953
2
votes
1
answer
116
views
How to implement the state $|\psi\rangle = \frac{1}{\sqrt{2}}\left[|0\rangle \otimes |X_i\rangle + |1\rangle \otimes |X_j\rangle\right]$
I am trying to implement the quantum k-means algorithm proposed in https://arxiv.org/pdf/1909.04226.pdf.
In the equation (8) of the manuscript we need to implement a state $|\psi\rangle = \frac{1}{\...
- 23
1
vote
0
answers
202
views
How does Qiskit's oracle synthesizer work?
Qiskit provides a phase oracle method that takes a Boolean formula as input and returns a phase oracle circuit for that function as output.
Their source code informed me that the synthesis uses the ...
- 195
4
votes
2
answers
430
views
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$?
Suppose I am given a function $f: \{0, 1\}^n \to \{0, 1\}^m$.
A standard oracle would be of the form $\mathcal{U}|x\rangle|0\rangle^{\otimes m} = |x\rangle|f(x)\rangle$.
I would suspect that this ...
- 195
0
votes
1
answer
308
views
Solving max/min problem for graphs based on Grover
Basis is for this post ist the paper https://arxiv.org/pdf/1902.00445.pdf
I want to do something similar using graph data encoded in quantum states. The circuit structure should look like this (first ...
- 9
1
vote
1
answer
241
views
Defining an oracle with Qiskit
I have a 8-qubits circuit whose final vector state may be for instance:
$$
\frac{\sqrt{2}}{4} |00010101\rangle+\frac{\sqrt{2}}{4} |00101010\rangle+\frac{\sqrt{2}}{4} |01010110\rangle+\frac{\sqrt{2}}{4}...
4
votes
0
answers
63
views
How could one use Grover's algorithm to find pairs of elements?
Imagine we have a set of distinct natural numbers which we divide into two unsorted lists $A$ and $B$. Then, there is a third list $E$ containing pairs of (pairwise) distinct natural numbers. We would ...
- 41
2
votes
0
answers
95
views
Why do Hamiltonian simulation algorithms not depend on the size of the Hamiltonian for the gate complexity?
The wikipedia page for Hamiltonian simulation mentions the gate and query complexities for different algorithms used for the problem (Trotter-Suzuki, Taylor Series, Quantum Walks, and QSP).
They ...
- 433
2
votes
0
answers
43
views
Grover's algorithm is optimal under alternative oracle definition? [duplicate]
Grover's algorithm is traditionally used under an oracle, $U_f$ such that $U_f | x \rangle = (-1)^{f(x)} | x \rangle$ where $f(x)$ is either $0$ or $1$.
But in the Wikipedia page, there is an ...
- 299
2
votes
2
answers
189
views
Quantum algorithm that "searches" for a particular state in a bigger state vector?
Does there exist an oracle that inputs a quantum state, say for example
$$
\frac{1}{2^N} \sum_{n=0}^{2^N - 1} \left | n \right > \left | f(n) \right >
$$
and allows us to find $n$ such that $f(n)...
- 449
1
vote
1
answer
410
views
The physical realisation of a quantum oracle [duplicate]
I am having doubts about the physicality of the quantum oracle used in the quantum search algorithms. The standard definition of the search problem (e.g Nielsen and Chuang) states that we are ...
- 391
-2
votes
1
answer
186
views
Can you give an example of an n-bit constant function for the Deutsch-Joza algorithm?
I was studying the implementation of DJ algorithm using Qiskit. I designed an oracle circuit for a balanced function and verified the output. Now I want to do the same for a constant function. ...
- 37