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
17
votes
5answers
4k views

How would I implement the quantum oracle in Deutsch's algorithm?

I am trying to simulate Deutsch's algorithm (elementary case of Deutsch-Jozsa algorithm), and I am not entirely sure how I would go about implementing the quantum oracle necessary for the algorithm to ...
2
votes
1answer
164 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 ...
10
votes
2answers
990 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-...
3
votes
1answer
135 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 $...
3
votes
2answers
79 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 ...
5
votes
1answer
1k views

How does an oracle function in Grover's algorithm actually work?

I have lately been studying quantum algorithms. I have gone through the Deutsch algorithm and Grover's algorithm. There's always a function in the oracle which somehow 'recognizes' the solution ...
4
votes
3answers
169 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 ...
4
votes
4answers
578 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 ...
1
vote
2answers
327 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 ...
1
vote
1answer
363 views

What can be a mini research project based on Grover's algorithm or the Deutsch Jozsa algorithm?

I need to work out a research project on quantum computing as a part of my curriculum. I was wondering how to implement something theoretically with the basic knowledge I have. I have learned about ...
0
votes
1answer
98 views

In Deutsch's algorithm, how to we get $(-1)^{f(x)}|x\rangle(|0\rangle-|1\rangle)$ from $|x\rangle(|0\rangle-|1\rangle)$?

While reading "Quantum Computation and Quantum Information" (by Nielsen and Chuang) I came across this line A little thought shows that if we apply $U_f$ to the state $\vert x \rangle (\dfrac{\...