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)

Filter by
Sorted by
Tagged with
0 votes
1 answer
37 views

How is the oracle actually implemented for Deutsch-Jozsa algorithm? [duplicate]

In the quantum computation circuit for the Deutsch-Jozsa algorithm, it is said that $U_f$ oracle will affect certain specific operations on the qubits using $f(x)$ and finally will give the answer in ...
K S Mallesh's user avatar
3 votes
2 answers
87 views

Time Complexity of Deustch Algorithm

The Deustch algorithm use an oracle, the quantum gate $U_f$ The first question is can we count the complexity of $U_f$ as one if it is used once. I mean since one computation of $U_f$ can't be ...
tangyao's user avatar
  • 95
1 vote
0 answers
67 views

How does Chernoff's bound help to solve Exercise 6.4.2 in Kaye et al.'s textbook? [duplicate]

I was wondering if anyone could help me with this question, I'm kind of new to quantum computing in general. I understand the Deutsch Josza Algorithm, but I'm not really sure where to even begin with ...
sdfsdfsdf555's user avatar
1 vote
1 answer
60 views

Phase kickback without controlled operator

I have some doubts about the phase kickback trick when used in some algorithm. Consider a quantum system with two qubits, and suppose we have a boolean oracle $U_f$. We know that if we put the second ...
aghin00's user avatar
  • 129
1 vote
1 answer
102 views

Implementation of quantum oracles in Deutsch's algorithm

I am studying Deutsch's algorithm (elementary version of Deutsch-Josza) but I'm struggling with the actual implementation of the quantum oracle. I understand the whole point of the algorithm and what ...
aghin00's user avatar
  • 129
1 vote
1 answer
85 views

Was Deutsch contemplating a positive-operator valued measurement to distinguish balancedness from constancy?

This is a follow up to a couple of questions on Deutsch's foundational paper on quantum Turing machines. In it, he determines $f(0)\oplus f(1)$ with a single query by measuring a state prepared as $\...
Mark Spinelli's user avatar
3 votes
1 answer
395 views

Why did Deutsch's original algorithm only succeed 50% of the time?

In his landmark 1985 paper "Quantum theory, the Church–Turing principle and the universal quantum computer" Deutsch gives a quantum algorithm to calculate $G(\mathbf f)=f(0)\oplus f(1)$ with ...
Mark Spinelli's user avatar
0 votes
0 answers
45 views

Algorithmic Benchmark: What is the reason for unevenness (spike) in the runtime graph by the number of qubits of the Deutsch-Jozsa algorithm?

I am testing quantum simulators based on runtime and memory usage. I impelmented Deutsch-Jozsa algorithm as follows in Qiskit: ...
Ahmadrv's user avatar
2 votes
1 answer
250 views

Why does the definition of the oracle in Deutsch's algorithm fail to specify its action on superpositions?

I’m trying to understand the Deutsch algorithm. I can see that the math shows the algorithm to be correct, but I don’t understand how the math represents the given conditions. The oracle is supposed ...
Jon Vote's user avatar
  • 123
2 votes
1 answer
65 views

Why this QC probability drop to $|01⟩$ and $|11⟩$ instead of $|10⟩$ and $|11⟩$? [duplicate]

I have QC like this The final state before measure should be $|1⟩ ⊗ |-⟩$, and it will be $\frac{1}{\sqrt{2}}(|10⟩ - |11⟩)$, so the probability of this QC should be a half is $|10⟩$ and other half is $...
Joe_LL's user avatar
  • 21
3 votes
2 answers
331 views

What is the intuition behind uniform Hadamard superposition?

I noticed that in many quantum algorithms, you apply a layer of uniform Hadamard transformation before and after the operations in between. For example, Deutsch-Josza, Simon's, and Grover's search. ...
Ryan Wang's user avatar
  • 247
3 votes
2 answers
102 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\...
cadaniluk's user avatar
  • 131
2 votes
0 answers
37 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 ...
metaUser's user avatar
1 vote
1 answer
102 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 ...
requiemman's user avatar
5 votes
1 answer
163 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>...
smitke6's user avatar
  • 116
3 votes
2 answers
151 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, ...
ElleryL's user avatar
  • 133
1 vote
1 answer
273 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 ...
Hamideh's user avatar
  • 269
0 votes
1 answer
107 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 += ...
user3146's user avatar
  • 129
0 votes
1 answer
298 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 ...
Proliferate309's user avatar
7 votes
1 answer
271 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 ...
Mark Spinelli's user avatar
6 votes
1 answer
534 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....
Andrew Baker's user avatar
2 votes
1 answer
178 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 ...
Bhushan Khope's user avatar
1 vote
1 answer
308 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 ...
JaZZyCooL's user avatar
-2 votes
1 answer
127 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. ...
Jayakumar's user avatar
0 votes
1 answer
506 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(...
user21545's user avatar
1 vote
1 answer
412 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_{...
Giorgos Giapitzakis's user avatar
1 vote
1 answer
116 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 <...
PGibbon's user avatar
  • 452
3 votes
3 answers
378 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 ...
Herr Schrödinger's user avatar
5 votes
2 answers
246 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 ...
user20364's user avatar
2 votes
1 answer
249 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 ...
n22's user avatar
  • 183
0 votes
1 answer
132 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 ...
n22's user avatar
  • 183
1 vote
1 answer
69 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 ...
n22's user avatar
  • 183
6 votes
2 answers
184 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 ...
Maximal Ideal's user avatar
1 vote
0 answers
113 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 $\{|...
SVMteamsTool's user avatar
1 vote
1 answer
181 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 ...
Eleeza's user avatar
  • 37
4 votes
1 answer
388 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) ...
Ognyan Tsvetkov's user avatar
5 votes
1 answer
637 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 ...
sitems's user avatar
  • 373
2 votes
1 answer
156 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 ...
Jaswin's user avatar
  • 203
1 vote
1 answer
203 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 $$...
June-Barcarolle's user avatar
0 votes
1 answer
124 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 ...
June-Barcarolle's user avatar
3 votes
1 answer
222 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 ...
stopper's user avatar
  • 443
1 vote
1 answer
117 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 ...
user18226's user avatar
2 votes
1 answer
91 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 ...
June-Barcarolle's user avatar
0 votes
2 answers
227 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 -? ...
Claire's user avatar
  • 669
3 votes
2 answers
165 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 ...
luciano's user avatar
  • 5,763
1 vote
1 answer
141 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 ...
snickers_stickers's user avatar
2 votes
1 answer
273 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?
Mg Sein's user avatar
  • 67
3 votes
1 answer
178 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 ...
Michael Teguh Laksana's user avatar
2 votes
1 answer
306 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 \...
theQman's user avatar
  • 141
0 votes
1 answer
307 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 ...
feefifoo's user avatar