Skip to main content
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,127
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,127
5 votes
Accepted

Why does the definition of the oracle in Deutsch's algorithm fail to specify its action on superpositions?

Oracle's action on computational basis The oracle's action is defined by the equation $$ U_f|x\rangle|y\rangle = |x\rangle|y\oplus f(x)\rangle\tag1 $$ where $x\in\{0,1\}^n$ and $y\in\{0,1\}$ are ...
Adam Zalcman's user avatar
4 votes
Accepted

Phase kickback without controlled operator

In the case where $f(0)=f(1)=1$, $U_f$ is just the controlled-Identity gate. This is still a controlled gate, though a trivial one. And, as one should expect, the phase we get is the eigenvalue of $\...
Norbert Schuch's user avatar
3 votes
Accepted

Was Deutsch contemplating a positive-operator valued measurement to distinguish balancedness from constancy?

Deutsch is explicit that what he is doing is a projective measurement, namely $$\{|+-\rangle, |--\rangle, |++\rangle, |-+\rangle\},$$ where the first outcome indicates the function is constant, the ...
Mateus Araújo's user avatar
3 votes

Why this QC probability drop to $|01⟩$ and $|11⟩$ instead of $|10⟩$ and $|11⟩$?

Could it be that states are labeled from right to left? Try the H gate on q0 and see if the labeling reverses.
SC_87's user avatar
  • 31
2 votes

What is the intuition behind uniform Hadamard superposition?

On a basic level, I always thought of it as using Quantum Parallelism. Applying a Hadamard on each input qubit transforms your 'classical' input (e.g. 00) to a quantum input consisting of every ...
K0mp0t1k's user avatar
2 votes

What is the hidden subgroup in Deutsch-Jozsa?

Thinking about this some more, for the Deutsch-Jozsa problem I don't think the parent group $G$ is $n$ copies of $\mathbb Z_2$, but is rather $\mathbb Z/(2^n\mathbb Z)$. That is, the parent group is ...
Mark Spinelli's user avatar
1 vote

How is the oracle actually implemented for Deutsch-Jozsa algorithm?

In the Deutsch-Jozsa scheme, you want to determine if your function is balance or constant. You do not have any information on the intern functioning of the function but you can access it as a black ...
baptistechev's user avatar
1 vote

Implementation of quantum oracles in Deutsch's algorithm

Marked CW Because "whence oracles" is such a commonly asked question, this suggests, to me at least, the community struggles with properly motivating their use and study. For example, a ...
1 vote
Accepted

In Deutsch–Jozsa algorithm, why one can safely ignore the last qubit of oracle output?

TL;DR: Yes, if the registers $x$ and $y$ are in a product state (as is the case in Deutsch-Jozsa algorithm) then the outcome of any measurement on $x$ is independent of the state of $y$. Consider an ...
Adam Zalcman's user avatar
1 vote

In Deutsch–Jozsa algorithm, why one can safely ignore the last qubit of oracle output?

Welcome to QCSE. Versions of this question have been asked many times on this site. Most quantum algorithms have this odd feel where work is done and evaluated into a bottom (second) register, but ...
Mark Spinelli's user avatar
1 vote

How is this step performed in Deutsch's algorithm?

Your misunderstanding is that $|x\rangle$ is only meant to denote either $|0\rangle$ or $|1\rangle$ -- not the superposition $H|0\rangle$. So $f(x)$ respectively denotes either $f(0)$ or $f(1)$, ...
Nick Mertes's user avatar
1 vote

How is this step performed in Deutsch's algorithm?

The key point here is that the query oracle $U_f$ is a linear transformation. Linearity means, if $|x\rangle = \alpha|0\rangle+\beta|1\rangle$, then $$U_f|x\rangle|y\rangle=U_f(\alpha|0\rangle+\beta|1\...
Egretta.Thula's user avatar
1 vote
Accepted

Algorithm to compute the parity of n qubits in n/2 queries

You should think of Deutsch's algorithm as comparing two different bit values, and telling you if they're the same or different. Now, if you need to know the parity of $n$ bits, think of this as ...
DaftWullie's user avatar
  • 59.3k

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