Dgdrxrt

The past simple of "gaslight" – "gaslighted" or "gaslit"?

Reference request: Grassmannian and Plucker coordinates in type B, C, D

Should I tutor a student who I know has cheated on their homework?

How I can get glyphs from a fraktur font and use them as identifiers?

Is it my responsibility to learn a new technology in my own time my employer wants to implement?

What is meant by "large scale tonal organization?"

When you upcast Blindness/Deafness, do all targets suffer the same effect?

What does "Its cash flow is deeply negative" mean?

How to get from Geneva Airport to Metabief, Doubs, France by public transport?

Is wanting to ask what to write an indication that you need to change your story?

Why do remote US companies require working in the US?

0 rank tensor vs 1D vector

Is micro rebar a better way to reinforce concrete than rebar?

Would a grinding machine be a simple and workable propulsion system for an interplanetary spacecraft?

What steps are necessary to read a Modern SSD in Medieval Europe?

Example of a Mathematician/Physicist whose Other Publications during their PhD eclipsed their PhD Thesis

How many extra stops do monopods offer for tele photographs?

What did we know about the Kessel run before the prequels?

Why isn't the Mueller report being released completely and unredacted?

Easy to read palindrome checker

WOW air has ceased operation, can I get my tickets refunded?

How to write a definition with variants?

Can MTA send mail via a relay without being told so?

Is it possible to use a NPN BJT as switch, from single power source?

Help with Inductive Proof - Grover Search

1

1

$begingroup$

I have a question about an inductive proof. First of all, let me explain the problem.

The algorithm starts in $|psirangle$ and applies $O_x$ $k$-times, with some unitary operators. We now define:

$$O_x=I-2|xranglelangle x|$$
$$|psi_k^xrangle=U_kO_xU_k-1O_x...U_1O_x|psirangle$$
$$|psi_krangle=U_kU_k-1...U_1|psirangle$$
$O_x$ is an oracle operator which gives a phase shift -1
to the solution $|xrangle$

$D_k$ is defined as a deviation after $k$ steps:

$$D_k=sum_x |||psi_k^xrangle-|psi_krangle||^2$$

With a proof it should now be shown that $D_k$ is restricted and can not grow fatser than $O(k^2)$. Now we come to the actual problem.

I am interested in the proof of some points:

1. Why does it have to be shown that $D_k$ is limited?


2. Why must it be shown that $D_k$ does not grow faster than $O(k^2)$? What
   is the idea behind it?


3. In the second proof it is to be assumed that $D_kOmega(N)$ holds, why is that exactly important? Which statement is behind it?

If someone needs more information, I have a helpful PDF HERE. Otherwise, I can also give more information.

I hope the question is understandable. It would be very nice if someone could explain to me what the ideas behind it are.

vector-spaces induction quantum-information

share|cite|improve this question

edited yesterday

P_Gate

asked Mar 27 at 19:55

P_GateP_Gate

163

$endgroup$

add a comment | 

1

1

$begingroup$

I have a question about an inductive proof. First of all, let me explain the problem.

The algorithm starts in $|psirangle$ and applies $O_x$ $k$-times, with some unitary operators. We now define:

$$O_x=I-2|xranglelangle x|$$
$$|psi_k^xrangle=U_kO_xU_k-1O_x...U_1O_x|psirangle$$
$$|psi_krangle=U_kU_k-1...U_1|psirangle$$
$O_x$ is an oracle operator which gives a phase shift -1
to the solution $|xrangle$

$D_k$ is defined as a deviation after $k$ steps:

$$D_k=sum_x |||psi_k^xrangle-|psi_krangle||^2$$

With a proof it should now be shown that $D_k$ is restricted and can not grow fatser than $O(k^2)$. Now we come to the actual problem.

I am interested in the proof of some points:

1. Why does it have to be shown that $D_k$ is limited?


2. Why must it be shown that $D_k$ does not grow faster than $O(k^2)$? What
   is the idea behind it?


3. In the second proof it is to be assumed that $D_kOmega(N)$ holds, why is that exactly important? Which statement is behind it?

If someone needs more information, I have a helpful PDF HERE. Otherwise, I can also give more information.

I hope the question is understandable. It would be very nice if someone could explain to me what the ideas behind it are.

vector-spaces induction quantum-information

share|cite|improve this question

edited yesterday

P_Gate

asked Mar 27 at 19:55

P_GateP_Gate

163

$endgroup$

add a comment | 

$begingroup$

I have a question about an inductive proof. First of all, let me explain the problem.

The algorithm starts in $|psirangle$ and applies $O_x$ $k$-times, with some unitary operators. We now define:

$$O_x=I-2|xranglelangle x|$$
$$|psi_k^xrangle=U_kO_xU_k-1O_x...U_1O_x|psirangle$$
$$|psi_krangle=U_kU_k-1...U_1|psirangle$$
$O_x$ is an oracle operator which gives a phase shift -1
to the solution $|xrangle$

$D_k$ is defined as a deviation after $k$ steps:

$$D_k=sum_x |||psi_k^xrangle-|psi_krangle||^2$$

With a proof it should now be shown that $D_k$ is restricted and can not grow fatser than $O(k^2)$. Now we come to the actual problem.

I am interested in the proof of some points:

1. Why does it have to be shown that $D_k$ is limited?


2. Why must it be shown that $D_k$ does not grow faster than $O(k^2)$? What
   is the idea behind it?


3. In the second proof it is to be assumed that $D_kOmega(N)$ holds, why is that exactly important? Which statement is behind it?

If someone needs more information, I have a helpful PDF HERE. Otherwise, I can also give more information.

I hope the question is understandable. It would be very nice if someone could explain to me what the ideas behind it are.

vector-spaces induction quantum-information

share|cite|improve this question

edited yesterday

P_Gate

asked Mar 27 at 19:55

P_GateP_Gate

163

$endgroup$

share|cite|improve this question

edited yesterday

P_Gate

asked Mar 27 at 19:55

P_GateP_Gate

163

share|cite|improve this question

edited yesterday

P_Gate

asked Mar 27 at 19:55

P_GateP_Gate

163

asked Mar 27 at 19:55

P_GateP_Gate

163

asked Mar 27 at 19:55

P_GateP_Gate

163