# [Quantum Computing] Verify a circuit implementing and operation

• Haorong Wu
In summary, the conversation discusses a problem from the book "Quantum search as a quantum simulation" regarding the implementation of a quantum circuit. The circuit is shown in the conversation and the effect of its operation is discussed for small time intervals. The conversation also includes a proposed approach to solving the problem and potential improvements to it. The conversation concludes with a request for assistance in solving the problem and a suggestion to write out the transformations as matrices.
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!

Last edited by a moderator:
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.

Last edited:
Haorong Wu
tnich said:
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.

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
Haorong Wu said:

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
tnich said:
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.

Haorong Wu said:
##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.

Last edited:
Haorong Wu

## 1. What is quantum computing and how does it differ from classical computing?

Quantum computing is a type of computing that uses quantum-mechanical phenomena, such as superposition and entanglement, to perform operations on data. It differs from classical computing in that classical computers use binary bits to represent data, while quantum computers use quantum bits (qubits) which can exist in multiple states at once.

## 2. How does a quantum computer verify a circuit implementing an operation?

A quantum computer verifies a circuit implementing an operation by performing a series of measurements on the qubits in the circuit. These measurements provide information about the state of the qubits and whether the operation was successful.

## 3. What is the role of entanglement in verifying a quantum circuit?

Entanglement is a key aspect of quantum computing and plays a crucial role in verifying a quantum circuit. Entanglement allows qubits to be in a state of superposition, meaning they can exist in multiple states at once. This allows for more complex operations to be performed on the qubits, making quantum circuits more powerful.

## 4. How do errors in a quantum circuit affect the verification process?

Errors in a quantum circuit can greatly affect the verification process. Quantum computers are susceptible to errors due to their fragile nature, and even small errors can have a significant impact on the output of the circuit. To verify a circuit, scientists must carefully analyze and account for any potential errors that may occur.

## 5. What are some potential applications of quantum computing in the future?

Quantum computing has the potential to revolutionize many industries and fields, such as cryptography, drug discovery, and artificial intelligence. It could also greatly improve the speed and efficiency of complex simulations and calculations, leading to advancements in fields such as finance and climate modeling.

Replies
10
Views
1K
Replies
3
Views
1K
Replies
0
Views
956
Replies
3
Views
1K
Replies
3
Views
2K
Replies
24
Views
1K
Replies
2
Views
1K
Replies
6
Views
2K
Replies
2
Views
5K
Replies
7
Views
2K