Quantum Query Algorithms | Understanding Quantum Information & Computation: Lesson 05

This lesson is on the quantum query model of computation. It describes a progression of quantum algorithms that offer advantages over classical algorithms within this model, including Deutsch’s algorithm, the Deutsch-Josza algorithm, and Simon’s algorithm.

0:00 — Introduction
2:13 — Overview
3:45 — A standard picture of computation
5:19 — The query model of computation
8:19 — Examples of query problems
12:49 — Query gates
22:08 — Deutsch’s algorithm
22:50 — Deutsch’s problem
24:46 — Deutsch’s algorithm
31:08 — Phase kickback
34:06 — The Deutsch-Jozsa circuit
35:40 — The Deutsch-Jozsa problem
37:48 — Deutsch-Jozsa analysis
47:30 — The Bernstein-Vazirani problem
51:53 — Simon’s algorithm
52:46 — Simon’s problem
57:46 — Simon’s algorithm
59:25 — Simon’s algorithm analysis
1:09:28 — Classical post-processing
1:15:31 — Classical difficulty
1:18:14 — Conclusion

#ibmquantum #learnquantum #qiskit

[ChimeraZone]

I really appreciate the professionalism presented here. The host is very engaging.

[sciencefordreamers]

Thank you so very much for generously producing such qualitative content freely! You are extremely professional!

[hiteshnaval]

Great lecture sir Thank you for your continuous work on QIS

[vadymfedyukovych]

The concise and easy-to-see way to kick f(\alpha) into a phase was introduced at 27:00. Thanx!
Reminds me my presentation and students asking for a sort of "physical meaning", only having "the math works this way" answer.

With this approach, one might say eigenvectors were guessed, both having \ket{-} for the second qubit part of the state, and having plus/minus phase as the eigenvalues. Ignoring the same second part, we effectively get the first "input" qubit modified (affected by the eigen-phases on different input basis vectors), despite the original idea to pass it as-is on both base vectors. The last step would be to transform the states we need to distinguish into the computation basis, for a measurement with certainty.

There might be a tricky exam question, to give an explicit example of the "input" qubit changed by the circuit as the whole, but not by the quantum gate itself.

Could we confirm/update/polish this please? Thanx.

[sheidalv]

Great job, John! I truly appreciate your effort! In my journey in quantum information theory. It's the best course I have seen!

[iniukut]

Thank you very much for this lesson, it has helped me to understand the query model of computation!

[Radical]

This guy is cool he reminds me of Joey from friends he should do all or at least most of their videos I can actually follow what He says unlike some of the other male speakers they had on the channels.

[arpanchoudhury]

Have been waiting for this one to come, wow, just came at the right time 😍

[fgfgdfgfgf]

You are the best. Thank you. Much better than my professor

[rsreza]

Thanks for the lectures.
An important question that has occupied my mind is that according to the definition of the unitary matrix UF, the inputs are |x> and |y>, and the upper output is exactly |x> without modification. In fact, the computation inside the function does not cause any modification on |x>. In Deutsch's algorithm, the upper input is measured. If the unitary matrix has no effect on the upper variable, then by removing it, we should not have any difference in the output. I mean the circuit is the same as ( |0>--H--H--measure ). Of course, in mathematical analysis, |x> is the input of UF and the output is (-1)^f(x) |->. It means that the above output is changed and it is not equal to the above input of UF. Is there a mistake in the definition of UF or am I completely wrong?

[ellenripley]

Something that boggles my mind is about Deutsch's algorithm, , that viewed in isolation q0 seems like is not touched by U_f, since it is the input-bit of the operation. Still in the end the state of q0 is definitely impacted by the choice of f. The math confirms all of this, but is there an intuitive way to understand what happens?

[asmaa.ali]

First, this lecture is a master piece. you are a brilliant content creator. Thank you so much for the effort here . Second, at 59:23 why there is some uncertainty so we had to run the algorithm several times to have the s string with confidence, where errors can come from ?

[leonelsternberg]

At 40:00, to be consistent with the above equation should'nt y sub(i) be in the set {0, 1}, rather E? What does E at the bottom of the summation sign mean anyhow?
At 42:34, I don't understand why you substitute |y> by |x>?
At 44:35, but if |x>=|0000...0> there is only one way of arranging x not 2^n on the probability equation?
basically I am confused by the alternating values of |x> versus |y>'s. Could you clarify this distinction please.
ADDENDUM: I think I understand my confusion between |x> and |y>'s. I would like to offer a notation suggestion to avoid this confusion. At about 38:20 you introduce a condensed equation to express the hadamard gate on q-bits in a classical state |0> or |1>. You introduce two new variables a and b on this expression. These are two very different kind of variables, while a is fixed, b sort of represents a bit in superposition it could be either 1 or 0. Why not differentiate between these two kinds of variables "a" being not bold and "b" being bold, a variable representing a q- bit in superposition? Here I will use upper case to represent bold. Later on with the equation for Hadamard gate on several q-bits in a classical state the y variable introduced would be . With this notation, it can also be understood that there is only one permutation of since these are fixed values, while there are 2^n permutation of .

[Chia-YingLin-ueyi]

Hello! At 42:55 after the U_f is applied, since we are dealing with a string of n bits, I am wondering why we can just use the phase kickback formula which we derived with f(x) standing for one bit?

[압둘하미드이드리스]

Can the instructor explain the aspect of deterministic function?

[asmaa.ali]

Another question please: at 1:03:14 doesn't reformulating the probability formula to be accurate tell that there is deficiency in the previous formula having only one sum over x ?

Regarding this too, the double sum is for taking into account cases where f(x) is not unique or for going straightforward for the analysis and get a result we need? Thank you so much

[MathFromTheGut]

Question. I understand the math that he is showing w.r.t. Deutsch’s algorithm. I’m struggling, however, to understand what is going on physically. The upper output for Uf should just be a copy of the quantum bit going into Uf, right? So shouldn’t it always just be the + state? If that were the case, then the output of that last Hadamard transform would always be “0”.
I guess that I’m not sure how all the work we are doing to compute the bottom output bit can affect what gets read on the unentangled upper bit. Again, I understand all the math but I just don’t see how the upper output bit gets affected here.
Help!

[schrodingercatquantum]

At 9:20 you mentioned this is called OR function because it can use bits in X string to determine the function value. I think OR function is just one of the many possible functions that behaves based on your definition. For example I can have a function f(X) =1 where X is all 0s and f(X)=0 where X is otherwise. Here X is definitely has not 1s and OR function does not apply. Is my understanding correct?

[sciencefordreamers]

Can a quantum algorithm be used to multiply two floating point numbers? Thank you for the amazing lesson!

[fgfgdfgfgf]

You are amazing. Sadly could not find the name of presenter.