# 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)

104 questions
Filter by
Sorted by
Tagged with
40 views

### Turning Deutsch-Josza into a continuous problem

I am wondering whether anyone has investigated if there is a notion of a continuous oracle. My starting off point is to consider the Deutsch-Josza problem, in which the oracle acts on the state in a ...
• 559
46 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 ...
96 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 ...
• 161
1 vote
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 ...
1 vote
74 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 ...
• 129
1 vote
167 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 ...
• 129
1 vote
92 views

• 21
344 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. ...
• 247
107 views

• 216
166 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
353 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
120 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
387 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 ...
277 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 ...
• 12.9k
547 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....
• 279
196 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
340 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 ...
140 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. ...
525 views

1 vote
119 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 <...
• 472
466 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 ...
285 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 ...
267 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 ...
• 183
137 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 ...
• 183
1 vote
70 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 ...
• 183