[Quantum Computing] Verify a circuit implementing and operation

[Haorong Wu]

Homework Statement

Verify that the circuit implement the operation $exp \left ( -i \left | \psi \right > \left < \psi \right | \Delta t \right )$ with $\left | \psi \right >=\frac {\sum _{x=0}^{N-1} \left | x \right >} {\sqrt N}$, and $N$ is the number of elements in a search space.

Relevant Equations

For small $\Delta t$, $exp \left ( -i \left | \psi \right > \left < \psi \right | \Delta t \right ) = I -i \Delta t \left | \psi \right > \left < \psi \right |$.

This is an exercise from "Quantum search as a quantum simulation " in Chapter "Quantum search algorithms".

The circuit is shown as the following picture.

For small time interval, the effect of the operation in the problem statement could be written as $exp \left ( -i \left | \psi \right > \left < \psi \right | \Delta t \right ) \left | \psi \right >=\left ( I -i \Delta t \left | \psi \right > \left < \psi \right | \right ) \left | \psi \right >=\left ( 1-i \Delta t \right ) \left | \psi \right >$.

In the circuit, let the input qubits $\left | y \right > = \left | \psi \right >$, since $\left | \psi \right >$ is defined to be the initial state and I can generate other states from it if the following reasoning is correct.

The qubits change as follow:
$\begin{align} & \left | \psi \right > \left | 0 \right > \nonumber \\ \rightarrow & \left | 000 \right > \left | 0 \right > \text{, (Hadamard Gates)} \nonumber \\ \rightarrow & \left | 000 \right > \left | 1 \right > \text{, (CNOT Gate)} \nonumber \\ \rightarrow & \left | 000 \right > e^{i \Delta t} \left | 1 \right > \text{, (U on the fourth qubit)} \nonumber \\ \rightarrow & \left | 000 \right > e^{i \Delta t} \left | 0 \right > \text{, (CNOT)} \nonumber \\ \rightarrow & \left | \psi \right > e^{i \Delta t} \left | 0 \right > \text{, (Hadamard Gates)} \nonumber \end{align}$

Then the first three qubits would be in state $e^{i \Delta t} \left | \psi \right > =\left ( I + i \Delta t \right ) \left | \psi \right >$, which does not match the operation in the problem statement.

Should the $e^{i \Delta t}$ in the circuit be $e^ {-i \Delta t}$? But I think the circuit should be correct since the book has been in $10^{th}$ anniversary edition. So where did I make a mistake?

Thanks!

 

[tnich]

I am having trouble solving this problem, too, but maybe we can figure it out between us. I can see a couple of possible improvements to make to your approach:

In this expression
$$exp \left ( -i \left | \psi \right > \left < \psi \right | \Delta t \right ) \left | \psi \right >=\left ( I -i \Delta t \left | \psi \right > \left < \psi \right | \right ) \left | \psi \right >=\left ( 1-i \Delta t \right ) \left | \psi \right >$$
you seem to assume that $\left | \psi \right > \left < \psi \right | = I$ so that
$$\left ( I -i \Delta t \left | \psi \right > \left < \psi \right | \right )=\left ( I -i \Delta t I\right )=\left ( 1-i \Delta t \right ) I$$

But if I understand $\left | \psi \right >=\frac {\sum _{x=0}^{N-1} \left | x \right >} {\sqrt N}$ correctly, then $\left | \psi \right >$ is a vector of 1s, so $\left | \psi \right >\left < \psi \right |$ should be a matrix of all 1s, not an identity matrix.
Edit: Looking at this again, I see that you have just distributed $\left | \psi \right >$ through the sum $I -i \Delta t \left | \psi \right > \left < \psi \right |$ to obtain your result $\left ( 1-i \Delta t \right ) \left | \psi \right >$. Since it differs from $\left | \psi \right >$ only by a global phase change, it essentially leaves the state unchanged.

Secondly, I don't understand why you assume that $\left | y \right >=\left | \psi \right >$. This does not seem to be a condition of the problem, though maybe it is stated somewhere in your text. In my view the problem is to implement a transformation that can be applied to an arbitrary state $\left | y \right >$.
Edit: I suppose what you are trying to say here is that if the transformation works for an arbitrary state $\left | y \right>$, then it must for when $\left | y \right >=\left | \psi \right >$.

I do not see how to solve this problem without writing out the transformations as matrices operating on a state vector in Hilbert space. If you have better way, I would be grateful to hear about it. When I write all of that out, I get this for the (approximate) complete transformation:
$$I + (e^{i \Delta t }-1)\left|\psi\right>\left<\psi\right|$$
which appears to be the exact solution of the problem as posed except for the plus sign. Working this out was tedious and would be even more tedious to post here, so I have not done that. I am hoping you have a better, less error-prone method.
Edit: In my result, I got a sign difference similar to the one you got. As you suggest, there may be a minus sign missing somewhere in the problem statement.

 

[Haorong Wu]

I am having trouble solving this problem, too, but maybe we can figure it out between us. I can see a couple of possible improvements to make to your approach:

In this expression
$$exp \left ( -i \left | \psi \right > \left < \psi \right | \Delta t \right ) \left | \psi \right >=\left ( I -i \Delta t \left | \psi \right > \left < \psi \right | \right ) \left | \psi \right >=\left ( 1-i \Delta t \right ) \left | \psi \right >$$
you seem to assume that $\left | \psi \right > \left < \psi \right | = I$ so that
$$\left ( I -i \Delta t \left | \psi \right > \left < \psi \right | \right )=\left ( I -i \Delta t I\right )=\left ( 1-i \Delta t \right ) I$$

But if I understand $\left | \psi \right >=\frac {\sum _{x=0}^{N-1} \left | x \right >} {\sqrt N}$ correctly, then $\left | \psi \right >$ is a vector of 1s, so $\left | \psi \right >\left < \psi \right |$ should be a matrix of all 1s, not an identity matrix.
Edit: Looking at this again, I see that you have just distributed $\left | \psi \right >$ through the sum $I -i \Delta t \left | \psi \right > \left < \psi \right |$ to obtain your result $\left ( 1-i \Delta t \right ) \left | \psi \right >$. Since it differs from $\left | \psi \right >$ only by a global phase change, it essentially leaves the state unchanged.

Secondly, I don't understand why you assume that $\left | y \right >=\left | \psi \right >$. This does not seem to be a condition of the problem, though maybe it is stated somewhere in your text. In my view the problem is to implement a transformation that can be applied to an arbitrary state $\left | y \right >$.
Edit: I suppose what you are trying to say here is that if the transformation works for an arbitrary state $\left | y \right>$, then it must for when $\left | y \right >=\left | \psi \right >$.

I do not see how to solve this problem without writing out the transformations as matrices operating on a state vector in Hilbert space. If you have better way, I would be grateful to hear about it. When I write all of that out, I get this for the (approximate) complete transformation:
$$I + (e^{i \Delta t }-1)\left|\psi\right>\left<\psi\right|$$
which appears to be the exact solution of the problem as posed except for the plus sign. Working this out was tedious and would be even more tedious to post here, so I have not done that. I am hoping you have a better, less error-prone method.
Edit: In my result, I got a sign difference similar to the one you got. As you suggest, there may be a minus sign missing somewhere in the problem statement.

Hi, tnich. Glad to hear your ideas.

First, as you have noticed, I just distributed $\left | \psi \right >$, but I don't understand your ideas that " Since it differs from $\left | \psi \right >$ only by a global phase change, it essentially leaves the state unchanged.". I don't see any global phase changes during the distribution. May you point it out?

Second, In my opinion, if the input state $\left | y \right > \neq \left | \psi \right >$, then after the first Hadamard, the state would not be in $\left | 000 \right >$, which will let the two CNOT gates just be identities, and the fourth qubit will remain in $\left | 0 \right >$ during the whole procedure. Then those cases would be trivial. Thus, I focus on the only non-trivial case that $\left | y \right >= \left | \psi \right >$.

Third, I considered to work out the matrix for the circuit, but I gave up because it would be a 16-by-16 matrix. I prefer to analyse the procedure by throwing different inputs. As I mentioned above, there is only one non-trivial input, and this fact can reduce the difficulty of the problem.

I hope there is a mistake in the circuit too.

Hope my poor English doesn't cause any trouble for you.

Would you tell me your E-mail? Maybe we can discuss other problems. I'm really having a hard time reading the book, and I'm looking for a friend to discuss.

 

[tnich]

Hi, tnich. Glad to hear your ideas.

First, as you have noticed, I just distributed $\left | \psi \right >$, but I don't understand your ideas that " Since it differs from $\left | \psi \right >$ only by a global phase change, it essentially leaves the state unchanged.". I don't see any global phase changes during the distribution. May you point it out?

Second, In my opinion, if the input state $\left | y \right > \neq \left | \psi \right >$, then after the first Hadamard, the state would not be in $\left | 000 \right >$, which will let the two CNOT gates just be identities, and the fourth qubit will remain in $\left | 0 \right >$ during the whole procedure. Then those cases would be trivial. Thus, I focus on the only non-trivial case that $\left | y \right >= \left | \psi \right >$.

Third, I considered to work out the matrix for the circuit, but I gave up because it would be a 16-by-16 matrix. I prefer to analyse the procedure by throwing different inputs. As I mentioned above, there is only one non-trivial input, and this fact can reduce the difficulty of the problem.

I hope there is a mistake in the circuit too.

Hope my poor English doesn't cause any trouble for you.

Would you tell me your E-mail? Maybe we can discuss other problems. I'm really having a hard time reading the book, and I'm looking for a friend to discuss.

Your English is excellent, so that is not a worry.
Yes, I would like to trade ideas with you. I worked through Neilson & Chuang several years ago and have forgotten a lot of it, but I have recently started thinking about quantum computing again.
By a global phase change I mean $(1-i\Delta t)$. That changes the phase of each component of the vector $\left | \psi \right >$, so it is global as compared to changing the phase of selected components. My understanding is that global phase changes are generally ignored in physical implementations of quantum circuits.
I thought as you did that an initial state other than $\left | \psi \right >$ would not be changed by the transformation, but discovered that I was wrong when I worked through the matrix multiplications. To see this, consider $H^{\oplus n}$ as a set of orthogonal basis vectors. While it is true that any basis vector other than $\left | \psi \right >$ would be unaffected by the transformation, a linear combination of the basis vectors would in general be changed. So I suppose you could apply the transformation (call it $\mathbb S$) to each column vector of $H^{\oplus n}$, and then multiply on the right by $H^{\oplus n}$ to get the entire matrix transformation S, something like this:
$$\begin{bmatrix}\mathbb S (H_0^{\oplus n}) & \mathbb S (H_1^{\oplus n} )& \dots & \mathbb S (H_{n-1}^{\oplus n})\end{bmatrix}H^{\oplus n} = SH^{\oplus n}H^{\oplus n} = SI = S$$

 

[Haorong Wu]

Your English is excellent, so that is not a worry.
Yes, I would like to trade ideas with you. I worked through Neilson & Chuang several years ago and have forgotten a lot of it, but I have recently started thinking about quantum computing again.
By a global phase change I mean $(1-i\Delta t)$. That changes the phase of each component of the vector $\left | \psi \right >$, so it is global as compared to changing the phase of selected components. My understanding is that global phase changes are generally ignored in physical implementations of quantum circuits.
I thought as you did that an initial state other than $\left | \psi \right >$ would not be changed by the transformation, but discovered that I was wrong when I worked through the matrix multiplications. To see this, consider $H^{\oplus n}$ as a set of orthogonal basis vectors. While it is true that any basis vector other than $\left | \psi \right >$ would be unaffected by the transformation, a linear combination of the basis vectors would in general be changed. So I suppose you could apply the transformation (call it $\mathbb S$) to each column vector of $H^{\oplus n}$, and then multiply on the right by $H^{\oplus n}$ to get the entire matrix transformation S, something like this:
$$\begin{bmatrix}\mathbb S (H_0^{\oplus n}) & \mathbb S (H_1^{\oplus n} )& \dots & \mathbb S (H_{n-1}^{\oplus n})\end{bmatrix}H^{\oplus n} = SH^{\oplus n}H^{\oplus n} = SI = S$$

Morning, tnich.

About the global phase change, I can see it now. I think we should not ignore the global phase change, because as we can see later, it is not a global phase change in the generalized cases.

Then, about the second point, I'm not familiar with the notation $H^{\oplus n}$. Did you mean $H^ {\otimes n}$? And also, does $H^{\oplus n}_i$ mean the $i^{th}$ column? If true, I believe your statement of $\begin{bmatrix}\mathbb S (H_0^{\oplus n}) & \mathbb S (H_1^{\oplus n} )& \dots & \mathbb S (H_{n-1}^{\oplus n})\end{bmatrix}H^{\oplus n} = SH^{\oplus n}H^{\oplus n} = SI = S$ is correct.

But I still believe there are ways to avoid the calculation for the matrix.

In my previous post, I made a mistake. I should not say $\left | y \right > \neq \left | \psi \right >$. Instead, the generalization should be that, for $\left | y \right > =a \left | \psi \right > + \sum_i b_i \left | \psi ^{'} _i\right >$, where $\left | y \right >$ is normalized, and $\left | \psi \right > \text {and} \left | \psi ^{'} _i\right >$ are a set of orthonormal basis, which means $\left | \psi ^{'} _i\right >$ are orthogonal to $\left | \psi \right >$.

Suppose the transform of the circuit is $S$ as you did. Then $S \left | \psi \right > =e^{i \Delta t} \left | \psi \right >$ and $S \left | \psi ^{'} _i\right >=\left | \psi ^{'} _i\right >$.

Thus $S \left | y \right >=S \left ( a \left | \psi \right > + \sum_i b_i \left | \psi ^{'} _i\right > \right ) =a e^{i \Delta t} \left | \psi \right > + \sum_i b_i \left | \psi ^{'} _i\right >$, which is equivalent to your statement.

Meanwhile, let's see the effect of $exp\left ( -i \left | \psi \right > \left < \psi \right | \Delta t \right )$, which we denote as $S^{'}$.

$S^{'} \left | y \right >= exp\left ( -i \left | \psi \right > \left < \psi \right | \Delta t \right ) \left ( a \left | \psi \right > + \sum_i b_i \left | \psi ^{'} _i\right > \right ) = \left ( I-i \Delta t \left | \psi \right > \left < \psi \right | \right )\left ( a \left | \psi \right > + \sum_i b_i \left | \psi ^{'} _i\right > \right ) \\ = a \left | \psi \right > + \sum_i b_i \left | \psi ^{'} _i\right > -i \Delta t \cdot a \left | \psi \right > \left < \psi \right | \left | \psi \right > -i \Delta t \sum_i b_i \left | \psi ^{'}_i \right > \\ = \left(1-i \Delta t \right )a \left | \psi \right > + \sum_i b_i \left | \psi ^{'}_i \right >=e^{-i \Delta t} a \left | \psi \right > + \sum_i b_i \left | \psi ^{'}_i \right >$, where $\Delta t$ are small.

Thus, $S \left | y \right > \neq S^{'} \left | y \right >$. And I have avoided to calculate the matrix, which could be intractable if the number of the input $\left | y \right >$ is large.

I'm more sure that there must be some mistake in the problem.

By the way, the major problem I have when I read the book is that the notations used by the author are confusing. For example, in the quantum search section, sometimes, $\left | x \right >$ represent the solution states, while in $\left | \psi \right > = \frac {\sum_ x \left | x \right >} {\sqrt N}$, $\left | x \right >$ represent all states in the search space. This confusion makes the whole problem , part of which we are discussing, confusing.

Have a nice day.

 

[tnich]

Sorry, I typed \oplus instead of \otimes.

$S^{'} \left | y \right >= exp\left ( -i \left | \psi \right > \left < \psi \right | \Delta t \right ) \left ( a \left | \psi \right > + \sum_i b_i \left | \psi ^{'} _i\right > \right ) = \left ( I-i \Delta t \left | \psi \right > \left < \psi \right | \right )\left ( a \left | \psi \right > + \sum_i b_i \left | \psi ^{'} _i\right > \right ) \\ = a \left | \psi \right > + \sum_i b_i \left | \psi ^{'} _i\right > -i \Delta t \cdot a \left | \psi \right > \left < \psi \right | \left | \psi \right > -i \Delta t \sum_i b_i \left | \psi ^{'}_i \right > \\ = \left(1-i \Delta t \right )a \left | \psi \right > + \sum_i b_i \left | \psi ^{'}_i \right >=e^{-i \Delta t} a \left | \psi \right > + \sum_i b_i \left | \psi ^{'}_i \right >$

This is very good. I think it is a very clear demonstration that the $S = S'$. (Edit: Except for the sign problem.) I would like to point out that a Taylor expansion of $exp\left ( -i \left | \psi \right > \left < \psi \right | \Delta t \right )$ gives $I +[exp\left ( -i \Delta t \right )-1]\left | \psi \right > \left < \psi \right |$, so there is no need to use the approximation.

I have boiled my matrix multiplication approach down to
$$S' = I +(e^{-i\Delta t}-1)\left | \psi \right > \left < \psi \right |$$$$S = \begin{bmatrix}\mathbb S (\left| \psi \right>) & \mathbb S (\left| \psi^{'}_1 \right>) & \dots & \mathbb S (\left| \psi^{'}_{n-1} \right>)\end{bmatrix}H^{\otimes n}\\
=\begin{bmatrix}e^{i\Delta t}\left| \psi \right> & \left| \psi^{'}_1 \right> & \dots & \left| \psi^{'}_{n-1} \right>\end{bmatrix}H^{\otimes n}\\
=\big(H^{\otimes n}+(e^{i\Delta t}-1)\left| \psi \right>\left<00 \dots 0\right|\big)H^{\otimes n}\\
=I+(e^{i\Delta t}-1)\left| \psi \right>\left < \psi \right |$$

Going from the second to the third line of the derivation of $S$ requires some thought, so overall I think your approach is a little more straightforward than mine.