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

66 questions
Filter by
Sorted by
Tagged with
15 views

### Derivation of the state after applying $U_f$ in the Deutsch–Jozsa algorithm

On pg. 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 I'm ...
32 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 ...
151 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 ...
20 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 ...
39 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 ...
60 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 -? ...
66 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 ...
45 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 ...
133 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?
61 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 ...
61 views

60 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 ...
168 views

122 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}{\lvert #1\rangle}H\ket x=\frac{1}{\sqrt2}(\ket0+(-1)^x\ket1)=\frac{1}{\sqrt2}...
57 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\}$ ...
163 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 ...
170 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). ...
364 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). ...
319 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 ...
46 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 ...
77 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 ...
545 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 ...
55 views

219 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 ...
96 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 ...
119 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$ ...
163 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 ...
575 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 ...
96 views

### Why do multi-bit hadamards expands to what they do?

I'm a Computer Scientist undergrad student studying for an exam in Quantum computing. In all of the algorithms I have been studying (Deutsch–Jozsa, Simons, Shors, Grovers) I constantly see multi-qubit ...
97 views

165 views

### How to factor the output of a CNOT acting on the input $|-,+\rangle$

I am trying to implement the Deutsch oracle in classical computer, using direction from this talk. There is this slide where they show how the CNOT gate modify 2 Hadamard transformed Qubits: While ...
282 views

### Deutsch-Jozsa on non-balanced oracles

I'm interested in deciding if an oracle is constant or not, but cannot guarantee that the non-constant oracles are balanced. The Deutsch-Jozsa seems like the obvious starting place, but handling the ...
240 views

### What are examples of non-oracular versions of famous oracular problems?

Most quantum algorithms proposed, including Deutsch-Jozsa, Simon's, Bernstein-Vazirani etc, involve querying an oracle. If I understand correctly, the speedups depend on the oracle being efficiently ...