Skip to main content
Share Your Experience: Take the 2024 Developer Survey
13 votes

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

There are two questions here. The first asks how you might actually implement this in code, and the second asks what's the point if you know which oracle you're passing in. Implementation Probably the ...
ahelwer's user avatar
  • 4,138
10 votes

How to prove that the query oracle is unitary?

Apply it twice: $$ O_xO_x|i\rangle|b\rangle=O_x|i\rangle|b\oplus x_i\rangle=|i\rangle|b\oplus x_i\oplus x_i\rangle=|i\rangle|b\rangle $$ Hence, $O_x$ is its own inverse, and therefore reversible. To ...
DaftWullie's user avatar
  • 58.7k
10 votes
Accepted

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

I believe there are two issues here. The first isn't anything wrong with your statement, but rather that you could make a far stronger (non-quantum) statement by the same reasoning: $\mathsf{P}\neq \...
DaftWullie's user avatar
  • 58.7k
9 votes
Accepted

Understanding the oracle in Deutsch's algorithm

Remember that when you define the oracle effect as $B_f |x \rangle |y \rangle = |x \rangle |y \oplus f(x) \rangle $, $f(x)$ is a classical function of a classical 1-bit argument, so you do not have a ...
Mariia Mykhailova's user avatar
9 votes
Accepted

Is the Deutsch-Jozsa problem in NP?

NP is a class of decision problems, so before considering the membership of the problem in NP, we first need to formulate a decision variant of it. This entails, among other things$^1$, the choice of ...
Adam Zalcman's user avatar
  • 22.9k
8 votes

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

I think there are probably two points to make here: The way that one implements quantum computation is not by simply looking at the unitary matrix and building something out of that, in just the same ...
DaftWullie's user avatar
  • 58.7k
8 votes

Why isn't output of Deutsch–Jozsa Algorithm simply $|0\rangle$?

This is because of what known as Phase kickback. The phase of the bottom qubit can kick back and create a relative phase change on the top qubit. This is a very useful and often use trick in quantum ...
KAJ226's user avatar
  • 13.9k
7 votes
Accepted

Balanced vs unbalanced superposition distinguisher

It is not possible at an information-theoretic level to do what you want to do. Let us suppose we have two pure states: $|\phi\rangle$ and $|\psi\rangle$, where $$ |\phi\rangle = \frac{1}{\sqrt{N}}\...
John Watrous's user avatar
  • 6,097
7 votes
Accepted

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

If you see the operator only from the unitary matrix point of view and you enumerate all inputs/outputs, which makes you visualize the matrix, indeed you somehow already know the answer. However, ...
cnada's user avatar
  • 4,754
7 votes
Accepted

Where is the parallelism in Deutsch-Jozsa algorithm?

In fact, in the original paper of Deutsch and Jozsa they actually implemented two oracles, here comes their procedure. If you omit the second $U_f$ and get a state $|\psi\prime>=\displaystyle\sum_{...
Yitian Wang's user avatar
7 votes
Accepted

What kind of boolean functions are faster to compute on qc?

Following up on @luciano's answer, I think you are envisioning a quantum computer as being fast at evaluating functions, when in actuality, quantum computers are better at evaluating global properties ...
Mark Spinelli's user avatar
7 votes

Where does Deutsch's algorithm use entanglement?

TL;DR: No entanglement is created in the course of Deutsch's algorithm. Generalization Deutsch's algorithm is a special case of Deutsch-Jozsa algorithm with $n=1$ qubits in the query register. ...
Adam Zalcman's user avatar
  • 22.9k
6 votes

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

The controlled dot doesn't do anything: it merely observes the bottom qubit in order to decide whether to apply the 𝑋 gate onto the top qubit. In the answer below, the qubit that appears first is ...
Mahathi Vempati's user avatar
6 votes
Accepted

Understanding Steps in Deutsch's Algorithm

To answer your first question, the quantum oracles are defined by their effect on the basis states $|0\rangle$ and $|1\rangle$, and if the oracle has to be computed on a superposition of basis states, ...
Mariia Mykhailova's user avatar
6 votes

Where is the parallelism in Deutsch-Jozsa algorithm?

"Where is the parallelism in Deutsch-Jozsa algorithm?" Instead of inputting just 0 or just 1 into the black box, you input both 0 and 1 into the black box at the same time, because you send ...
user1271772 No more free time's user avatar
6 votes
Accepted

What is the intuition behind uniform Hadamard superposition?

The first Hadamard gates applied to a fiducial all-zero's ket on $n$ qubits serve to prepare your input register into the uniform superposition over all $2^n$ basis states. The last Hadamard gates ...
Mark Spinelli's user avatar
6 votes
Accepted

Why did Deutsch's original algorithm only succeed 50% of the time?

Deutsch didn't make a mistake. It's just that his original algorithm didn't make use of phase kickback because it hadn't been discovered yet. That discovery came later in this paper: Richard Cleve, ...
John Watrous's user avatar
  • 6,097
6 votes

Time Complexity of Deustch Algorithm

These are natural questions that I address at some length in a lesson on Quantum query algorithms that's part of a short course on quantum algorithms. (See also the video for the lesson on YouTube.) ...
John Watrous's user avatar
  • 6,097
5 votes
Accepted

Implementing the one-bit Deutsch Oracle algorithm using phase

Overview To recap the one-bit Deutsch Oracle problem, there are four possible oracle functions: constant-0, constant-1, identity, and negation. The task is to determine whether the oracle function is ...
ahelwer's user avatar
  • 4,138
5 votes

Deutsch-Jozsa on non-balanced oracles

This is not so straightforward, I suspect. The issue is being able to distinguish between the constant case (e.g. every input gives output 0) and the case where only one input returns 1, and all ...
DaftWullie's user avatar
  • 58.7k
5 votes
Accepted

How to prove that the query oracle is unitary?

Notice that $\mathcal O_x$ is a permutation matrix. The matrix elements are $$\langle j, c\rvert\mathcal O_x\lvert i,b\rangle =\delta_{ij}\langle c\rvert b\oplus x_i\rangle =\delta_{ij}\delta_{c,b\...
glS's user avatar
  • 25.3k
5 votes

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

There is no way to build the oracle in a way which would not defeat the point of Deutsch's algorithm - that's why it is an oracle-based algorithm. The only way would be if you would come up with an ...
Norbert Schuch's user avatar
5 votes
Accepted

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

(Based on the time limitation I assume we're talking about an undergraduate level project, and not something more advanced.) If you look at the questions about Grover's algorithm, you'll notice that ...
Mariia Mykhailova's user avatar
5 votes
Accepted

Analysis of the second Hadamard in the Detusch-Jozsa Algorithm

If you look at the formula you want to prove term-by-term, you'll notice that the sum and the $(-1)^f(x)$ part is the same in both formulas; you just need to show that $$H^{\otimes n} |x\rangle = \...
Mariia Mykhailova's user avatar
5 votes
Accepted

Probability estimate in classical Deutsch-Jozsa problem

Yes, it will depend on $n$ because sampling with replacement is assumed in the proof, which doesn't make sense if $n$ is finite. Intuitively, if a function $f$ really is balanced, and first output ...
Sanchayan Dutta's user avatar
5 votes
Accepted

Understanding the working of oracle in Deutsch - Jozsa Algorithm

Here the subscripts are of the form $1i$, where $i$ is the label of the subsystem (recall that you are using two qubits for this $\left|\psi\right>_0=\left|00\right>_{1}$). So any product of ...
Camilo160's user avatar
  • 284
5 votes

Example of a quantum algorithm better than its classical counterpart which involves only $1$ qubit?

There aren't many examples! The main reason for advantages in quantum computers is the ability to constructively combine amplitudes - if you've only got 1 qubit, there aren't any amplitudes to combine!...
C. Kang's user avatar
  • 1,726
5 votes
Accepted

Why does the Hadamard gate satisfy $H|x\rangle=\frac{1}{\sqrt2}\sum_{z\in\{0,1\}}(-1)^{xz}\lvert z\rangle$?

This is just a compact way of representing the Hadamard operator. The summation operator can be expanded, yielding: $$ \frac{1}{\sqrt{2}} \Big( (-1)^{x \cdot 0} | 0 \rangle + (-1)^{x \cdot 1} | 1 \...
C. Kang's user avatar
  • 1,726
5 votes
Accepted

Why isn't output of Deutsch–Jozsa Algorithm simply $|0\rangle$?

It may naively seem that gates like $U_f$ whose action is defined as $$ U_f|x\rangle|y\rangle = |x\rangle|y\oplus f(x)\rangle $$ have no effect on the first register holding the state $|x\rangle$. ...
Adam Zalcman's user avatar
  • 22.9k
5 votes
Accepted

Shouldn't the input state of Deutsh-Jozsa's algorithm look like $|0\rangle^{\otimes n}\otimes |1\rangle$ rather than $|0\rangle^{\otimes n}|1\rangle$?

This is just a convention. People tend to write $|01 \rangle$ instead of $|0 \rangle \otimes |1\rangle $, but they mean the same thing. In this case, $$ \overbrace{|0\rangle \otimes |0\rangle \otimes \...
KAJ226's user avatar
  • 13.9k

Only top scored, non community-wiki answers of a minimum length are eligible