As of May 31, 2023, we have updated our Code of Conduct.

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
1 vote
1 answer
81 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
  • 259
0 votes
1 answer
49 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
88 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
213 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
472 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
101 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
105 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
75 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
0 answers
32 views

Deutsch Algorithm's matrix, what is the matrix? is there one? what is this oracle?

so I'm still new to the field and am in a class on quantum computing. Basically my question is the title. I've been trying to understand where the speed up comes from in qc as in classical it's fairly ...
Max Rush's user avatar
0 votes
1 answer
362 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
203 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
82 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
2 answers
182 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
4 votes
2 answers
178 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
177 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
  • 143
0 votes
1 answer
112 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
  • 143
1 vote
1 answer
64 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
  • 143
6 votes
2 answers
162 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
86 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
138 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
280 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
484 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
  • 363
2 votes
1 answer
124 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
121 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
75 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
208 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
  • 333
1 vote
1 answer
92 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
74 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
161 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
  • 659
3 votes
2 answers
144 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,078
1 vote
1 answer
110 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
252 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
131 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
197 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
255 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
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 |...
BIGoperaFAN's user avatar
2 votes
1 answer
166 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 ...
jmacuna's user avatar
  • 139
7 votes
5 answers
325 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\...
morpheus's user avatar
  • 349
7 votes
2 answers
252 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 ...
user3680510's user avatar
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-...
overlord's user avatar
  • 203
3 votes
1 answer
321 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$,...
Anurag Singla's user avatar
3 votes
1 answer
277 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 ...
user1936752's user avatar
  • 2,367
1 vote
2 answers
123 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 ...
NiRvanA's user avatar
  • 13
3 votes
1 answer
90 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$|\...
Skyris's user avatar
  • 107
4 votes
2 answers
212 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}...
Quarzo's user avatar
  • 75
1 vote
0 answers
65 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\}$ ...
user823's user avatar
  • 301
1 vote
2 answers
496 views

What is the set of all functions from ℤ to ℤ?

In David Deutsch's classic paper Quantum theory, the Church-Turing principle and the universal quantum computer (1985), Deutsch writes on p. 99: (I thought that this might be in typo in the original ...
vy32's user avatar
  • 611
1 vote
1 answer
328 views

How can a half-wave plate affect the position qubit and not the polarization qubit of a photon?

I recently was watching these 2 videos on Coursera which show how to build a simple quantum computer that can implement the simplest case of the Deutsch-Jozsa algorithm (which uses only 2 qubits). ...
Pranav Jain's user avatar
3 votes
2 answers
593 views

Question about DIY Quantum Computer Prototype

I recently came across these 2 videos on Coursera which show how to build a simple quantum computer that can implement the simplest case of the Deutsch-Jozsa algorithm (which uses only 2 qubits). ...
Pranav Jain's user avatar
1 vote
2 answers
714 views

Hamming Weight algorithm

Is there any quantum algorithm that can improve a calculation time for determining the Hamming weight of an arbitrary bit string? The Deutsch-Jozsa algorithm seems like it would be useful for this ...
Ochalhi's user avatar
  • 13