Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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)

2
votes
1answer
53 views

How to understand Deutsch-Jozsa algorithm from an adiabatic perspective?

I'm trying to understand the Deutsch-Josza algorithm from an adiabatic perspective as presented in Adiabatic quantum computing A: Review of modern physics, vol 90, (2018) pp 015002-1 (arXiv version). ...
4
votes
1answer
727 views

Understanding the oracle in Deutsch's algorithm

I am reading John Watrous' notes from his course CPSC 519 on quantum computing. In a pre-discussion before presenting Deutsch's algorithm to determine whether a function is constant or not, the author ...
2
votes
1answer
68 views

What happens in Deutsch algorithm if I use equal input bits?

I am currently working on the algorithm of Deutsch. The algorithm defines two starting states, which are for $|x\rangle = |0\rangle$ and for $|y\rangle = |1\rangle$. So far, that's clear to me. But ...
3
votes
1answer
43 views

Deutsch-Jozsa algorithm as a generalization of Bernstein-Vazirani

It is known that both algorithms use the same gates: $H^{\oplus n}U_fH^{\oplus n}$. After the circuit, the qubits are in the state $\sum_y \left( \sum_x (-1)^{f(x)+xy} \right) |y\rangle $. In DJ's ...
1
vote
1answer
48 views

Correct way of expressing a measurement in a different computational basis

Sometimes we find that the result we want from a quantum algorithm is expressed in terms of a basis that is different from the usual computational basis, which I will call $$ B_C = \left\{ \lvert 0 \...
2
votes
1answer
153 views

Deutsch–Jozsa algorithm: why is $f$ constant?

I'm trying to understand how the Deutsch–Jozsa algorithm works with the following circuit: Circuit in Quirk Since we have the top 2 wires measuring $|0\rangle$ with 100% probability, it means $U_f$ ...
0
votes
1answer
92 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 ...
3
votes
1answer
104 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 ...
10
votes
4answers
786 views

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

I am trying to simulate Deutsch's algorithm (elementary case of Deutsch-Josza algorithm), and I am not entirely sure how I would go about implementing the quantum oracle necessary for the algorithm to ...
5
votes
2answers
493 views

How to prove that the query oracle is unitary?

The query oracle: $O_{x}|i\rangle|b\rangle = |i\rangle|b \oplus x_{i}\rangle$ used in algorithms like Deutsch Jozsa is unitary. How do I prove it is unitary?
6
votes
1answer
126 views

Why doesn't Deutsch-Jozsa Algorithm show that P ≠ BQP?

To my understanding, Deutsch-Jozsa algorithm solves a specific problem in constant time, using a fixed circuit depth, compared to a classical deterministic algorithm, which would require time ...
7
votes
2answers
120 views

Balanced vs unbalanced superposition distinguisher

I've been looking at basic quantum algorithms such as the Deutsch-Jozsa algorithm that are able to characterize functions very well and I was wondering if similar approaches exist to characterize ...
6
votes
2answers
1k views

How is the Deutsch-Jozsa algorithm faster than classical for practical implementation?

There is something I really misunderstand about the Deutsch-Jozsa algorithm. To check if $f$ is balanced or constant, we use the following algorithm : Where $U_f$ gives $(x,y) \rightarrow (x, y \...
3
votes
0answers
61 views

Deutsch Algorithm on a Quantum Turing Machine

I understood how a Quantum Turing Machine works from this lecture. It would be great if someone could give an example of how this machine could be used to solve a real problem though, for example, ...