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
31 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 <...
user avatar
  • 13
3 votes
2 answers
67 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 ...
user avatar
4 votes
2 answers
101 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 ...
user avatar
2 votes
1 answer
73 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 ...
user avatar
  • 143
0 votes
1 answer
66 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 ...
user avatar
  • 143
1 vote
1 answer
47 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 ...
user avatar
  • 143
6 votes
2 answers
125 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 ...
user avatar
1 vote
0 answers
66 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 $\{|...
user avatar
1 vote
1 answer
79 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 ...
user avatar
  • 25
3 votes
1 answer
129 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) ...
user avatar
4 votes
1 answer
327 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 ...
user avatar
  • 343
2 votes
1 answer
80 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 ...
user avatar
  • 203
1 vote
1 answer
54 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 $$...
user avatar
0 votes
1 answer
51 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 ...
user avatar
3 votes
1 answer
181 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 ...
user avatar
  • 151
1 vote
1 answer
58 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 ...
user avatar
2 votes
1 answer
53 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 ...
user avatar
0 votes
2 answers
67 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 -? ...
user avatar
  • 619
2 votes
2 answers
100 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 ...
user avatar
  • 3,811
1 vote
1 answer
75 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 ...
user avatar
2 votes
1 answer
196 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?
user avatar
  • 67
3 votes
1 answer
94 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 ...
user avatar
2 votes
1 answer
127 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 \...
user avatar
  • 141
0 votes
1 answer
141 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 ...
user avatar
3 votes
1 answer
62 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 |...
user avatar
2 votes
1 answer
121 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 ...
user avatar
  • 139
7 votes
5 answers
242 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\...
user avatar
  • 349
7 votes
2 answers
222 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 ...
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-...
user avatar
  • 203
3 votes
1 answer
173 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$,...
user avatar
3 votes
1 answer
208 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 ...
user avatar
  • 2,097
1 vote
2 answers
115 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 ...
user avatar
  • 13
3 votes
1 answer
80 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$|\...
user avatar
  • 87
4 votes
2 answers
174 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}...
user avatar
  • 75
1 vote
0 answers
61 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\}$ ...
user avatar
  • 181
1 vote
2 answers
191 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 ...
user avatar
  • 591
1 vote
1 answer
219 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). ...
user avatar
2 votes
2 answers
456 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). ...
user avatar
1 vote
2 answers
511 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 ...
user avatar
  • 13
2 votes
1 answer
105 views

Why is the function $f_s(x)=\sum_i x_i s_i \pmod 2$ balanced?

A parity function $f_s:\{0,1\}^{n}\rightarrow\{0,1\}$, for some $s\in \{0,1\}^n$, is a function of the form $f_s(x) = x \cdot s$, where the inner product is taken modulo 2. Show that $f_s$ is a ...
user avatar
  • 285
4 votes
2 answers
98 views

Example of a quantum algorithm better than its classical counterpart which involves only $1$ qubit?

I was reading over the proof of the Deutsch-Jozsa algorithm, which in its simplest case, involves at least 2 qubits. Is there an example of a quantum algorithm that is better than it's classical ...
user avatar
5 votes
1 answer
954 views

Deutsch's algorithm in Qiskit

I am trying to understand and implement the Deutsch algorithm. I follow the logic from Nielsen book and I started to implement it in Qiskit. For implementing the oracle, I use a CNOT gate and now I ...
user avatar
0 votes
1 answer
57 views

How are the two states factored out of Deutsch's circuit?

After placing the Hadamards on the 2 qubits (both initialized in the $|1\rangle$ state) in the circuit, we are given: $ |\psi_{b}\rangle = \frac{1}{2}(|0_{1}0_{2}\rangle -|1_{1}0_{2}\rangle -|0_{1}...
user avatar
  • 321
3 votes
1 answer
145 views

Understanding the working of oracle in Deutsch - Jozsa Algorithm

Reading through the official Qiskit textbook, I fell onto the problem of Deutsch - Jozsa Algorithm, which seemed little mystical to me at first but as I tried out the example of its working, I was ...
user avatar
3 votes
1 answer
177 views

What happens with the oracle $U_f$ if you have different blackbox execution times for different inputs?

What will happen if the 'blackbox' function $f$ in Deutsch's algorithm is designed in such a way that it takes millions of years to deliver result if input is $x = 1$ and few seconds if the input is $...
user avatar
  • 133
3 votes
5 answers
231 views

Any other quantum algorithms than Jozsa-Deutsch decision algorithm, Grover search algorithm, Shor factorization algorithm?

I have been working on implementing Jozsa-Deutsch decision algorithm, Grover search algorithm, Shor factorization algorithm on my home-made 2 qubits device. I am wondering if there are any other ...
user avatar
  • 223
3 votes
1 answer
115 views

Which of the Jozsa axioms does the Hilbert-Schmidt inner product violate?

The paper Quantum fidelity measures for mixed states considers various differently-normalized variants of the Hilbert-Schmidt inner product $\mathrm{Tr}(A^\dagger B)$ on linear operators as candidate ...
user avatar
  • 2,107
5 votes
1 answer
163 views

How does $U_f$ in Deutsch's Algorithm affect the state $|x\rangle$?

I am trying to read Nielsen's and Chuang's book on quantum computing and I am having problem understanding Deutsch's algorithm. According to my understanding of the algorithm, the state $|x\rangle$ ...
user avatar
  • 53
6 votes
1 answer
247 views

Understanding Steps in Deutsch's Algorithm

I am currently working my way through the book Quantum Computation and Quantum Information by Chuang and Nielsen. So far it has been a joy to read, however I am hung up on a couple aspects of quantum ...
user avatar
  • 217
4 votes
4 answers
883 views

Implementing four oracles for the Deutsch Algorithm (preferably on IBM Q Experience)

I guess, I understood simple Deutsch Algorithm (if unary function is balanced or constant) as described here: Introduction to quantum computing: The Deutsch algorithm I need to test it. I was ...
user avatar