Fdtxjr

Sum letters are not two different

If Windows 7 doesn't support WSL, then what does Linux subsystem option mean?

How could we fake a moon landing now?

Should I use a zero-interest credit card for a large one-time purchase?

Can you explain what "processes and tools" means in the first Agile principle?

How does the math work when buying airline miles?

"Lost his faith in humanity in the trenches of Verdun" — last line of an SF story

When a candle burns, why does the top of wick glow if bottom of flame is hottest?

How come Sam didn't become Lord of Horn Hill?

Did Mueller's report provide an evidentiary basis for the claim of Russian govt election interference via social media?

Central Vacuuming: Is it worth it, and how does it compare to normal vacuuming?

Is there hard evidence that the grant peer review system performs significantly better than random?

Aligning an equation at multiple points, with both left and right alignment, as well as equals sign alignment

What is "gratricide"?

How to get all distinct words within a set of lines?

How does the secondary effect of the Heat Metal spell interact with a creature resistant/immune to fire damage?

Is there a kind of relay that only consumes power when switching?

Quadrilaterals with equal sides

Do wooden building fires get hotter than 600°C?

Sentence order: Where to put もう

How often does castling occur in grandmaster games?

Strange behavior of Object.defineProperty() in JavaScript

Putting class ranking in CV, but against dept guidelines

Did Deadpool rescue all of the X-Force?

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 Mar 29 at 7:52

P_Gate

asked Mar 27 at 19:55

P_GateP_Gate

213

$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 Mar 29 at 7:52

P_Gate

asked Mar 27 at 19:55

P_GateP_Gate

213

$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 Mar 29 at 7:52

P_Gate

asked Mar 27 at 19:55

P_GateP_Gate

213

$endgroup$

share|cite|improve this question

edited Mar 29 at 7:52

P_Gate

asked Mar 27 at 19:55

P_GateP_Gate

213

share|cite|improve this question

edited Mar 29 at 7:52

P_Gate

asked Mar 27 at 19:55

P_GateP_Gate

213

asked Mar 27 at 19:55

P_GateP_Gate

213

asked Mar 27 at 19:55

P_GateP_Gate

213