Questions tagged [deutsch-jozsa-algorithm]
The Deutsch–Jozsa algorithm is a quantum algorithm, proposed by David Deutsch and Richard Jozsa in 1992. Although of little practical use, it is one of the first examples of a quantum algorithm that is exponentially faster than any possible deterministic classical algorithm. It is also a deterministic algorithm, meaning that it always produces an answer, and that answer is always correct. (Wikipedia)
92
questions
2
votes
1
answer
62
views
How is this step performed in Deutsch's algorithm?
I am reading Quantum Computing for Computer Scientists.
Given the circuit for Deutsch's algorithm:
Denoting $H|0\rangle$ as $|x\rangle$, the book says that
$|\phi_2\rangle = (-1)^{f(x)}|x\rangle\left\...
- 121
2
votes
0
answers
34
views
What's a quantum algorithm in the black box model to find $j_1,j_2$ such that $f(x_1,...,x_n)=x_{j1}\oplus x_{j2}$?
Consider the set of all functions $f : \{0, 1\}^n → \{0, 1\}$ that are of the form $f(x_1, x_2, . . . , x_n) = x_{j1}\oplus x_{j2}$
for some distinct $j_1, j_2 \in \{1, 2, . . . , n\}$. Suppose that ...
- 51
1
vote
1
answer
37
views
Algorithm to compute the parity of n qubits in n/2 queries
Deutsch's algorithm is a special case of Deutsch-Josza's algorithm where the number of qubits evaluated = 2. This is equivalent to performing the operation $x_1 ⊕ x_2$ i.e. checking the parity of 2 ...
- 161
4
votes
1
answer
137
views
What is the hidden subgroup in Deutsch-Jozsa?
It is noted by several sources (e.g. this paper) that the problem solved by the Deutsch-Jozsa (DJ) algorithm is an instance of the Hidden Subgroup Problem (HSP). However, I fail to see this for $n>...
- 106
3
votes
2
answers
108
views
In Deutsch–Jozsa algorithm, why one can safely ignore the last qubit of oracle output?
Wikipedia article about Deutsch-Jozsa algorithm says, under the section Algorithm, that:
At this point the last qubit, $$\frac{|0\rangle - |1\rangle}{\sqrt{2}}$$ may be ignored.
Does it mean that, ...
- 133
1
vote
1
answer
170
views
The difference between the Deutsch-Jozsa Algorithm and the Bernstein-Vazirani Algorithm
I am reading a book section about the difference between the Deutsch-Jozsa and the Bernstein-Vazirani Algorithm and here is the text:
As with DJ, the goal of BV is also to ascertain the nature of a
...
- 269
0
votes
1
answer
85
views
ChatGPT gave me Qiskit code that used += to append a circuit?
I asked ChatGPT for a Qiskit implementation of Deutsch's algorithm. I pasted the code it returned below. Under where it says "# Apply the oracle gate", it tries to use "circuit += ...
- 129
0
votes
1
answer
192
views
Deutsch-Jozsa Algorithm - classical solution
so I'm self-studying quantum computing and have a question about the proposed classical solution to the Deustch-Jozsa problem.
So given your function $f: \{0,1\}^n \rightarrow \{0,1\}$ say you were to ...
7
votes
1
answer
248
views
Were quantum computers conjectured to factor large numbers before Shor developed his algorithm?
Peter Shor has given wonderful accounts of the development of his algorithm, with a lot of detail on the activity in the field at around the early-mid 90's. He's been very free about emphasizing that ...
- 10.7k
6
votes
1
answer
520
views
Is the Deutsch-Jozsa problem in NP?
The Deutsch-Jozsa problem is a problem that quantum computers can solve deterministically, while classical computers cannot. However, there are classical algorithms that can solve it probabilistically....
- 237
2
votes
1
answer
146
views
How to modify the Deutsch-Jozsa algorithm to distinguish between two types of $n$-bit inputs
I am trying to solve this problem in Ronald de wolf lecture notes.
But I am not able to solve.
Suppose our N-bit input x satisfies the following promise:
either (1) the first N/2 bits of x are all 0 ...
1
vote
1
answer
184
views
Deustch-Jozsa algorithm for a specific problem, doesn't make sense?
I am trying to implement Deustch-Jozsa Algorithm where function f(x) = 0 for even and f(x) = 1 for odd, for a four-bit number. After writing the numbers out I found a pattern as described below
...
- 51
-2
votes
1
answer
111
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
0
votes
1
answer
404
views
Kaye Exercise 6.4.2 Classical deutsch jozsa algorithm
Can anyone help with this problem from, An Introduction to Quantum
Computing, Phillip Kaye, Raymond Laflamme, Michele Mosca
Exercise 6.4.2: Show that a probabilistic classical algorithm that makes $O(...
1
vote
1
answer
267
views
Kaye Exercise 6.3.1, Deutsch algorithm modification
This exercise is worded as follows:
In the Deutsch algorithm, when we consider $U_f$ as a single-qubit operator $\hat{U_{f(x)}}$, $\frac{|0\rangle - |1\rangle}{\sqrt{2}}$ is an eigenstate of $\hat{U_{...
1
vote
1
answer
109
views
Implementing deutsch_problem(seed=None) and deutsch() from qiskit text
I'm attempting to work through the exercise at the end of https://learn.qiskit.org/course/ch-gates/phase-kickback#phase-8-0 where I am to build and implement Deutsch's algorithm. I understand that <...
- 452
3
votes
3
answers
295
views
Understanding the output of a Deutsch-Jozsa circuit
I'm looking at the Deustch-Jozsa algorithm. While reading this Qiskit tutorial. I didn't understand what the presented result in plot mean. That is, why the output 1111 means a balanced function? What ...
- 189
5
votes
2
answers
219
views
How are Deutsch-Jozsa and Bernstein-Vazirani algorithms a fair comparison to classical ones
In both of these example algorithms, the Classical one is restricted to a single bit of output, while the Quantum one is allowed to use information exposed from multiple bits. There is no question ...
- 51
2
votes
1
answer
205
views
Can the oracle in the Deutsch-Jozsa algorithm be neither balanced nor constant?
I know that the oracle $U_f$ has to be either constant or balanced. But what if $f$ is an AND function? I know in that case it is neither.
So my question is what happens if $U_f$ is neither constant ...
- 173
0
votes
1
answer
125
views
How to create a quantum circuit checking whether two functions $f$ or $g$ are of the same type?
I want to create a quantum circuit that checks whether two functions f and g are of the same type, i.e., constant or balanced, or not. In other words, the output of the circuit should output 1 if both ...
- 173
1
vote
1
answer
66
views
How to construct Deutsch-Jozsa using CX and Hadamard gates?
How can I construct Deutsch-Jozsa?
I know that I need superposition and phase kickback, which means I need to apply Hadamard Gate at the beginning the at the end, I also need to apply an $X$ gate then ...
- 173
6
votes
2
answers
175
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 ...
- 359
1
vote
0
answers
100
views
Measuring Deutsch-Jozsa in the Fourier Basis
Let $f$ be a function from $N$ bits to one bit, where $f$ is either constant or balanced. Consider the Deutsch-Jozsa algorithm, where each of the $N$ output qubits is measured in the Fourier basis $\{|...
- 353
1
vote
1
answer
159
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 ...
- 37
4
votes
1
answer
354
views
Deutsch's algorithm makes no sense
Here are the 4 classical functions over $1$ bit we're examining, $f(x) = \{0,1\}, x \in\{0,1\}$:
identity (balanced) -> $f(x) = x$: \begin{bmatrix}1&0\\0&1\end{bmatrix}
negation (balanced) ...
- 117
5
votes
1
answer
582
views
Where does Deutsch's algorithm use entanglement?
I have read that to be useful, all quantum algorithms must use entanglement somewhere. However, reading several tutorials describing Deutsch's algorithm, I haven't seen any mention of how entanglement ...
- 373
2
votes
1
answer
146
views
What is quantum advantage truly?
Let's consider the Deutsch Jozsa algorithm, I understand that the superposition principle in quantum mechanics, helps us design circuits which would give answers in one single query. But then I would ...
- 203
1
vote
1
answer
176
views
Derivation of the state after applying $U_f$ in the Deutsch–Jozsa algorithm
On page 35 in Nielsen and Chuang, it's said that for the following quantum circuit implementing the general Deutsch–Jozsa algorithm:
Next, the function $f$ is evaluated (by Bob) using $U_f$, giving
$$...
0
votes
1
answer
107
views
Derivation of the effect of the Hadamard transform on a state |x⟩ in the Deutsch–Jozsa algorithm
On pg. 35 of Nielsen and Chuang, there's the following paragraph:
By checking the cases $x=0$ and $x=1$ separately we see that for a single qubit $H|x\rangle=\sum_x (-1)^{xz}|z\rangle/\sqrt{2}$.
I'm ...
3
votes
1
answer
213
views
What are quantum algorithms with only one possible outcome with probability equal to one?
I would like to study circuits with only one possible outcome. Quantum phase estimation, Bernstein-Vazirani, and in part Deutsch-Jozsa (for constant functions) come to mind - do you know any other ...
- 373
1
vote
1
answer
109
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
2
votes
1
answer
89
views
Reason for sending numbers from 0 to $2^n − 1$ in Deutsch–Jozsa algorithm
In Nielsen and Chuang, when talking about the Deutsch–Jozsa algorithm. The Deutsch’s problem is described as the following game.
Alice, in Amsterdam, selects a number x from 0 to $2^n − 1$, and mails ...
0
votes
2
answers
195
views
Why would matter if $f(0)$ equals to $f(1)$ in Deutsch’s algorithm?
I have a question on the following quantum circuit implementing Deutsch’s algorithm
Why would matter if $f(0)$ equals to $f(1)$? Are they what changes the phase of the first qubit state from + to -? ...
- 669
3
votes
2
answers
164
views
How come classical Deutsch-Jozsa is $O(1)$ when allowing "a small error rate"?
I'm reading Quantum Computing: An Applied Approach, by Hidary. Chapter 8.2 (p104) says:
While it is true that Deutsch-Jozsa demonstrates an advantage of quantum over classical computing, if we allow ...
- 5,573
1
vote
1
answer
124
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 ...
2
votes
1
answer
265
views
What are min and max numbers of inputs needed to know whether the 4-bit classical Deutsch-Jozsa algorithm is balanced?
What are the minimum and maximum number of inputs you would need to check to know whether this 4-bit classical Deutsch-Jozsa oracle is balanced or constant?
- 67
3
votes
1
answer
159
views
In the Deutsch-Jozsa algorithm, why is the resulting amplitude for the constant and balanced cases $\pm 1$ and $0$, respectively?
I am currently learning from Nielsen and Chuang and I am currently learning about Deutsch-Jozsa algorithm. However, I am stumped with the mathematics of the algorithm at the following section:
I ...
2
votes
1
answer
264
views
Quantum parallelism and Deutsch's algorithm - what is $U_f$ really? [closed]
I'm trying to understand quantum parallelism ideas leading the Deutsch's algorithm. The circuit in question is
I understand that we end up with
$$|\psi_3 \rangle = \pm | f(0) \oplus f(1) \rangle \...
- 141
0
votes
1
answer
281
views
Understanding Deutsch Algorithm
From the image below, if we focus on the first qubit, we know after Hadamard (state 1) $|0\rangle$ will become $|+\rangle$ and the second qubit $|1\rangle$ will become $|-\rangle$.
What exactly would ...
- 13
3
votes
1
answer
66
views
Shouldn't the input state of Deutsh-Jozsa's algorithm look like $|0\rangle^{\otimes n}\otimes |1\rangle$ rather than $|0\rangle^{\otimes n}|1\rangle$?
According to this wikipedia page the initial state in Deutsch–Jozsa algorithm is written as follows:
$$|0\rangle^{\otimes n} |1\rangle$$
shouldn't it look like this?:
$$|0\rangle^{\otimes n} \otimes |...
- 33
2
votes
1
answer
172
views
How does $U_f$ act on a qudit state in the Deutsch-Jozsa Algorithm
The problem starts with the given the input state $|\psi_{in} \rangle = |0 \rangle |1 \rangle$, I'm asked to calculate $|\psi'\rangle = H_d \otimes H_d |\psi_{in} \rangle$ where $H_d$ is the Hadamard ...
- 139
7
votes
5
answers
345
views
Why isn't output of Deutsch–Jozsa Algorithm simply $|0\rangle$?
If I look at the circuit diagram of the Deutsch–Jozsa Algorithm:
Now given the fact that Hadamard matrix or gate is its own inverse (see here), shouldn't the output (top wire) simply give back $|0\...
- 349
7
votes
2
answers
266
views
What kind of boolean functions are faster to compute on qc?
Deutsch-Jozsa algorithm can compute if some function $f : \{0,1\}^n \rightarrow \{0,1\} $ is constant. This goes exponentially faster than on classical computers.
If we consider the set of all boolean ...
- 173
10
votes
2
answers
1k
views
Where is the parallelism in Deutsch-Jozsa algorithm?
I am newbie on Quantum Computing. Actually I am a software engineer but I want to understand how quantum computers work. So my question may be absurd. Sorry about that.
I tried to understand Deutsch-...
- 203
3
votes
1
answer
389
views
How to solve this Deutsch Jozsa variant?
You are given a function $f : \{0,1\}^n \to \{0,1\}$ and a quantum circuit, $C$, computing the signed implementation of $f$. Let $I_0$ be the input bit-strings of length $n$ where the first bit is $0$,...
- 129
3
votes
1
answer
324
views
BQP and PH separation
I was reading the Quanta article here which shows that there exists a problem which achieves "oracle separation between BQP and PH". In simple terms, there exists a problem which a quantum ...
- 2,597
1
vote
2
answers
129
views
If I use probabilistic algorithm on a normal computer, can't I just input once a single $0$ in the oracle, then input once a single $1$?
I fail to understand Deutsch-Jozsa algorithm.
As wikipedia suggests: ${\displaystyle f\colon \{0,1\}^{n}\rightarrow \{0,1\}}$. The function takes n-digit binary values as input and produces either a 0 ...
- 13
3
votes
1
answer
98
views
Prove entanglement in the final state of the Deutsch-Jozsa circuit
I am asked to prove the following:
Consider the Deutsch-Jozsa circuit. The output of the circuit is of the form $|\psi\rangle \otimes \frac{1}{\sqrt{2}}(|0\rangle-|1\rangle)$. Prove that the state$|\...
- 117
4
votes
2
answers
233
views
Why does the Hadamard gate satisfy $H|x\rangle=\frac{1}{\sqrt2}\sum_{z\in\{0,1\}}(-1)^{xz}\lvert z\rangle$?
I'm studying Deutsch–Jozsa algorithm and I don't understand this passage about Hadamard gate result:
$$\newcommand{\ket}[1]{\lvert #1\rangle}H\ket x=\frac{1}{\sqrt2}(\ket0+(-1)^x\ket1)=\frac{1}{\sqrt2}...
- 75
1
vote
0
answers
66
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\}$ ...
- 301