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

67 questions
Filter by
Sorted by
Tagged with
830 views

### How can a CNOT gate change the control qbit (e.g. in the Deutsch Oracle problem)?

It is very confusing how the CNOT gate can change the properties of the controlled qubit (possibly because I am still stuck in the classical programming mindset): Many books have explained the ...
156 views

### Implementing the one-bit Deutsch Oracle algorithm using phase

The standard method of implementing the one-bit Deutsch Oracle algorithm is to use two qbits, one as input & one as output (which allows you to write the non-reversible constant functions in a ...
347 views

### Implementing Deutsch's problem on IBM Q composer

I tried to implement the Deutsch's problem on IBM Q but didn't get the results as expected. So here is the circuit for the Deutsch algorithm and this is my implementation on the composer: so let me ...
2k 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 ...
197 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 ...
705 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 \...
364 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 ...
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 ...
969 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?
690 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$ ...
115 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). ...
412 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 ...
141 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 ...
258 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 ...
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 \oplus ...