10
$\begingroup$

I've probably read the chapter The quantum Fourier transform and its applications from Nielsen and Chuang (10 th anniversary edition) a couple of times before and this took this thing for granted, but today, when I looked at it again, it doesn't seem obvious to me at all!

Here's the circuit diagram for the Phase estimation algorithm:

enter image description here

The first register having $t$ qubits is supposedly the "control register". If any of the qubit in the first register is in state $|1\rangle$ the corresponding controlled unitary gate gets applied to the second register. If it is in a state $|0\rangle$ then it doesn't get applied to the second register. If it is in a superposition of the two states $|0\rangle$ and $|1\rangle$ the action of the corresponding unitary on the second register can be determined by "linearity". Notice, that all the gates are acting only on the second register and none on the first register. The first register is supposed to be only a control.

However, they show that the final state of the first register as:

$$\frac{1}{2^{t/2}}\left(|0\rangle+\text{exp}(2\pi i 2^{t-1}\varphi)|1\rangle)(|0\rangle+\text{exp}(2\pi i 2^{t-2}\varphi)|1\rangle)...(|0\rangle+\text{exp}(2\pi i 2^{0}\varphi)|1\rangle\right)$$

I'm surprised as to why we consider there to be a change in the state of the first register of qubits at all, after the action of the Hadamard gates. The final state of the first register should just have been

$$\left(\frac{|0\rangle+|1\rangle}{\sqrt 2}\right)^{\otimes t}$$

isn't it? I say this because the first register is supposed to be a control only. I don't understand how or why the state of the first register should change when acting as a control.

I initially thought that considering the exponential factors to be part of the first register qubit states was only a mathematical convenience, but then it didn't make sense. State of a qubit or a system of qubits shouldn't depend upon what is mathematically convenient to us!

So, could someone please explain why exactly the state of the first register of qubits changes, even when it simply acts as a "control" for the second register? Is it just a mathematical convenience or is there something deeper?

$\endgroup$
  • $\begingroup$ Not an answer, but: What would it mean for it to be a 'mathematical convenience', if it didn't represent an actual change in the state? Either the maths accurately describes how quantum states change, or it doesn't. If it doesn't, you have bigger problems than this one example. If you do suppose that the mathematics accurately describes the physics, then the mathematical representation is not just convenient: the states of the (scare quotes ahead) "control" wires do actually change in this subroutine. It's okay to be confused as to why, but first you have to accept that they do change. $\endgroup$ – Niel de Beaudrap Jul 1 '18 at 23:12
  • $\begingroup$ The maths is exactly that explained in this answer: quantumcomputing.stackexchange.com/a/1791/1837 but that situation is simpler, and perhaps easier to understand $\endgroup$ – DaftWullie Jul 2 '18 at 5:23
  • $\begingroup$ @NieldeBeaudrap Well, my question is precisely "why" it changes $\endgroup$ – Sanchayan Dutta Jul 2 '18 at 5:40
  • $\begingroup$ @DaftWullie The math doesn't look hard. Let's just take a simple example of a controlled-$U^{2^0}$ gate. If the control register is in state $|1\rangle$ then it gets applied to $|u\rangle$ to give $\exp(2\pi i 2^0 \phi)|u\rangle$. But, they are considering that exponential factor of $\exp(2\pi i 2^0 \phi)$ to be a factor of the control qubit in the first register i.e. $\exp(2\pi i 2^0 \phi)$ and not of the second register. My question is: why so? $\endgroup$ – Sanchayan Dutta Jul 2 '18 at 6:14
  • $\begingroup$ cc @NieldeBeaudrap ^ $\endgroup$ – Sanchayan Dutta Jul 2 '18 at 6:15
5
$\begingroup$

Imagine you have an eigenvector $|u\rangle$ of $U$. If you have a state such as $|1\rangle|u\rangle$ and you apply controlled-$U$ to it, you get out $e^{i\phi}|1\rangle|u\rangle$. The phase isn't attached to a specific register, it's just an overall multiplicative factor.

Now let's use a superposition on the first register: $$ (|0\rangle+|1\rangle)|u\rangle\mapsto |0\rangle|u\rangle+e^{i\phi}|1\rangle|u\rangle $$ You can rewrite this as $$ (|0\rangle+e^{i\phi}|1\rangle)|u\rangle $$ so it appears on the first register, even though it was sort-of created on the second register. (Of course that interpretation isn't entirely true because it was created by a two-qubit gate acting on both qubits).

This step is at the heart of many quantum algorithms.

Why don't we write $|\Psi\rangle=|0\rangle|u\rangle+|1\rangle(e^{i\phi}|u\rangle)$ and just claim that it is not separable?

One can't just claim it, but must show it mathematically. For example, we can take the partial trace over the second qubit, $$ \text{Tr}_B(|\Psi\rangle\langle\Psi|_{AB})=\text{Tr}_B(|0\rangle\langle 0|\otimes |u\rangle\langle u|+|1\rangle\langle 0|\otimes e^{i\phi}|u\rangle\langle u|+|0\rangle\langle 1|\otimes |u\rangle\langle u|e^{-i\phi}+|1\rangle\langle 1|\otimes e^{i\phi}|u\rangle\langle u|e^{-i\phi}) $$ To take the partial trace, we pick a basis to sum over. For simplicity, let's pick $\{|u\rangle,|u^\perp\rangle\}$ where $\langle u|u^\perp\rangle=0$ and $\langle u|(e^{i\phi}|u\rangle=e^{i\phi}$. Then you get $$ \text{Tr}_B(|\Psi\rangle\langle\Psi|_{AB})=|0\rangle\langle 0|+e^{i\phi}|1\rangle\langle 1|+e^{-i\phi}|0\rangle\langle 1|+|1\rangle\langle 1| $$ This is rank 1 (and you can see the phase has appeared on the first register), so the state is not entangled. It is separable.

$\endgroup$
  • $\begingroup$ My main issue is with the "re-writing" part. Mathematically it is simply a re-arrangement but physically that re-writing can have deep implications. Say, why don't I write it instead as $|0\rangle(|u\rangle) + |1\rangle (e^{i\phi}|u\rangle)$ and just claim that it is not separable into tensor products due to entanglement? Why should that $e^{i\phi}$ factor belong to a state of a qubit in the first register rather than the state of a qubit in the second register? $\endgroup$ – Sanchayan Dutta Jul 2 '18 at 6:35
  • $\begingroup$ How do you define "entangled"? By any definition, this is not entangled. Try taking the partial trace, for example. Moreover, I guess you don't generally have a problem with removing a global phase from an entire expression, as compared to holding that phase on different components? $\endgroup$ – DaftWullie Jul 2 '18 at 6:40
  • $\begingroup$ I'm probably having some elementary misconception. Say, I have two qubits, where the first one (qubit $A$) is in state $(|0\rangle)_A$ and the second one (qubit B) is in state $(e^{i\theta }|0\rangle)_B$. Then the composite state is $(|0\rangle)_A\otimes (e^{i\theta}|0\rangle)_B$. Now I indeed have seen it being written as $e^{i\theta}(|0\rangle)_A\otimes (|0\rangle)_B$, but I'm not sure why that should be possible. What's the actual physical state of qubit A and qubit B in this case? Is it $(e^{i\theta}|0\rangle)_A$ & $|0\rangle_B$ or is it $(|0\rangle)_A$ & $(e^{i\theta}|0\rangle)_B$? $\endgroup$ – Sanchayan Dutta Jul 2 '18 at 6:50
  • $\begingroup$ I guess I do have a problem with shifting around "global phase" like that. I never thought about it before. $\endgroup$ – Sanchayan Dutta Jul 2 '18 at 6:50
  • $\begingroup$ There is no physical difference. Think about it this way: what experiment would you do to distinguish the two? If there's a physical difference, there must be a way to distinguish them. $\endgroup$ – DaftWullie Jul 2 '18 at 6:55
7
$\begingroup$

A first remark

This same phenomenon of 'control' qubits changing states in some circumstances also occurs with controlled-NOT gates; in fact, this is the entire basis of eigenvalue estimation. So not only is it possible, it is an important fact about quantum computation that it is possible. It even has a name: a "phase kick", in which the control qubits (or more generally, a control register) incurs relative phases as a result of acting through some operation on some target register.$\def\ket#1{\lvert#1\rangle}$

The reason why this happens

Why should this be the case? Basically it comes down to the fact that the standard basis is not actually as important as we sometimes describe it as being.

Short version. Only the standard basis states on the control qubits are unaffected. If the control qubit is in a state which is not a standard basis state, it can in principle be changed.

Longer version —

Consider the Bloch sphere. It is, in the end, a sphere — perfectly symmetric, with no one point being more special than any other, and no one axis more special than any other. In particular, the standard basis is not particularly special.

The CNOT operation is in principle a physical operation. To describe it, we often express it in terms of how it affects the standard basis, using the vector representations $$ \ket{00} \to {\scriptstyle \begin{bmatrix} 1 \\ 0 \\ 0 \\ 0 \end{bmatrix}}\,, \quad \ket{01} \to {\scriptstyle \begin{bmatrix} 0 \\ 1 \\ 0 \\ 0 \end{bmatrix}}\,, \quad \ket{10} \to {\scriptstyle \begin{bmatrix} 0 \\ 0 \\ 1 \\ 0 \end{bmatrix}}\,, \quad \ket{11} \to {\scriptstyle \begin{bmatrix} 0 \\ 0 \\ 0 \\ 1 \end{bmatrix}}$$ — but this is just a representation. This leads to a specific representation of the CNOT transformation: $$ \mathrm{CNOT} \to {\scriptstyle \begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \end{bmatrix}}\,.$$ and for the sake of brevity we say that those column vectors are the standard basis states on two qubits, and that this matrix is a CNOT matrix.

Did you ever do an early university mathematics class, or read a textbook, where it started to emphasise the difference between a linear transformation and matrices — where it was said, for example, that a matrix could represent a linear transformation, but was not the same as a linear transformation? The situation with CNOT in quantum computation is one example of how this distinction is meaningful. The CNOT is a transformation of a physical system, not of column vectors; the standard basis states are just one basis of a physical system, which we conventionally represent by $\{0,1\}$ column vectors.

What if we were to choose to represent a different basis — say, the X eigenbasis — by $\{0,1\}$ column vectors, instead? Suppose that we wish to represent $$ \begin{aligned} \ket{++} \to{}& [\, 1 \;\; 0 \;\; 0 \;\; 0 \,]^\dagger\,, \\ \ket{+-} \to{}& [\, 0 \;\; 1 \;\; 0 \;\; 0 \,]^\dagger\,, \\ \ket{-+} \to{}& [\, 0 \;\; 0 \;\; 1 \;\; 0 \,]^\dagger\,, \\ \ket{--} \to{}& [\, 0 \;\; 0 \;\; 0 \;\; 1 \,]^\dagger \,. \end{aligned}$$ This is a perfectly legitimate choice mathematically, and because it is only a notational choice, it doesn't affect the physics — it only affects the way that we would write the physics. It is not uncommon in the literature to do analysis in a way equivalent to this (though it is rare to explicitly write a different convention for column vectors as I have done here). We would have to represent the standard basis vectors by: $$ \ket{00} \to \tfrac{1}{2}\,{\scriptstyle \begin{bmatrix} 1 \\ 1 \\ 1 \\ 1 \end{bmatrix}}\,, \quad \ket{01} \to \tfrac{1}{2}\,{\scriptstyle \begin{bmatrix} 1 \\ -1 \\ 1 \\ -1 \end{bmatrix}}\,, \quad \ket{10} \to \tfrac{1}{2}\,{\scriptstyle \begin{bmatrix} 1 \\ 1 \\ -1 \\ -1 \end{bmatrix}}\,, \quad \ket{11} \to \tfrac{1}{2}\,{\scriptstyle \begin{bmatrix} 1 \\ -1 \\ -1 \\ 1 \end{bmatrix}}\,.$$ Again, we're using the column vectors on the right only to represent the states on the left. But this change in representation will affect how we want to represent the CNOT gate.

A sharp-eyed reader may notice that the vectors which I have written on the right just above are the columns of the usual matrix representation of $H \otimes H$. There is a good reason for this: what this change of representation amounts to is a change of reference frame in which to describe the states of the two qubits. In order to describe $\ket{++} = [\, 1 \;\; 0 \;\; 0 \;\; 0 \,]^\dagger$, $\ket{+-} = [\, 0 \;\; 1 \;\; 0 \;\; 0 \,]^\dagger$, and so forth, we have changed our frame of reference for each qubit by a rotation which is the same as the usual matrix representation of the Hadamard operator — because that same operator interchanges the $X$ and $Z$ observables, by conjugation.

This same frame of reference will apply to how we represent the CNOT operation, so in this shifted representation, we would have $$ \begin{aligned} \mathrm{CNOT} \to \tfrac{1}{4}{}\,{\scriptstyle \begin{bmatrix} 1 & 1 & 1 & 1 \\ 1 & -1 & 1 & -1 \\ 1 & 1 & -1 & -1 \\ 1 & -1 & -1 & 1 \end{bmatrix} \,\begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \end{bmatrix}\, \begin{bmatrix} 1 & 1 & 1 & 1 \\ 1 & -1 & 1 & -1 \\ 1 & 1 & -1 & -1 \\ 1 & -1 & -1 & 1 \end{bmatrix} }\, = \,{\scriptstyle \begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 \end{bmatrix}} \end{aligned}$$ which — remembering that the columns now represent $X$ eigenstates — means that the CNOT performs the transformation $$ \begin{aligned} \mathrm{CNOT}\,\ket{++} &= \ket{++} , \\ \mathrm{CNOT}\,\ket{+-} &= \ket{--}, \\ \mathrm{CNOT}\,\ket{-+} &= \ket{-+} , \\ \mathrm{CNOT}\,\ket{--} &= \ket{+-} . \end{aligned} $$ Notice here that it is only the first, 'control' qubits whose state changes; the target is left unchanged.

Now, I could have shown this same fact a lot more quickly without all of this talk about changes in reference frame. In introductory courses in quantum computation in computer science, a similar phenomenon might be described without ever mentioning the words 'reference frame'. But I wanted to give you more than a mere calculation. I wanted to draw attention to the fact that a CNOT is in principle not just a matrix; that the standard basis is not a special basis; and that when you strip these things away, it becomes clear that the operation realised by the CNOT clearly has the potential to affects the state of the control qubit, even if the CNOT is the only thing you are doing to your qubits.

The very idea that there is a 'control' qubit is one centered on the standard basis, and embeds a prejudice about the states of the qubits that invites us to think of the operation as one-sided. But as a physicist, you should be deeply suspicious of one-sided operations. For every action there is an equal and opposite reaction; and here the apparent one-sidedness of the CNOT on standard basis states is belied by the fact that, for X eigenbasis states, it is the 'target' which unilaterally determines a possible change of state of the 'control'.

You wondered whether there was something at play which was only a mathematical convenience, involving a choice of notation. In fact, there is: the way in which we write our states with an emphasis on the standard basis, which may lead you to develop a non-mathematical intuition of the operation only in terms of the standard basis. But change the representation, and that non-mathematical intuition goes away.

The same thing which I have sketched for the effect of CNOT on X-eigenbasis states, is also going on in phase estimation, only with a different transformation than CNOT. The 'phase' stored in the 'target' qubit is kicked up to the 'control' qubit, because the target is in an eigenstate of an operation which is being coherently controlled by the first qubit. On the computer science side of quantum computation, it is one of the most celebrated phenomena in the field. It forces us to confront the fact that the standard basis is only special in that it is the one we prefer to describe our data with — but not in how the physics itself behaves.

$\endgroup$
-1
$\begingroup$

Great question.
I once asked this too, but it is not just a matter of mathematical convenience.
The controlled-U is an "entangling" gate.
Once there's entanglement, you cannot separate the state into "first register" and "second register".
Only think of these registers separately at the beginning, or when there's no entanglement. After there's entanglement, your best bet is to work through the mathematics (matrix multiplications) thoroughly, and you will indeed get the state given by Nielsen and Chuang.

$\endgroup$
  • $\begingroup$ Trying to upvote the question but need to wait until I have 15 reputation. $\endgroup$ – user2898 Jul 2 '18 at 5:27
  • $\begingroup$ I can't see any entanglement. The output seems to be separable between the two registers. $\frac{1}{2^{t/2}}\left(|0\rangle+\text{exp}(2\pi i 2^{t-1}\varphi)|1\rangle)(|0\rangle+\text{exp}(2\pi i 2^{t-2}\varphi)|1\rangle)...(|0\rangle+\text{exp}(2\pi i 2^{0}\varphi)|1\rangle\right)$ is state of the first register whereas $|u\rangle$ is the state of the second register. $\endgroup$ – Sanchayan Dutta Jul 2 '18 at 6:10
  • 1
    $\begingroup$ @Blue I do not write it as a full answer because I myself find it difficult to internalize the concept in my mind, anyway this is due to the "Phase Kick-Back" phenomenon, and it is actually also due to the fact that control and target are somewhat entangled. Try and give a read to section 2.2 of Mosca's PhD thesis, it's the best explanation I have found so far. $\endgroup$ – FSic Jul 2 '18 at 8:38
  • $\begingroup$ @F.Siciliano Okay, thank you. I'll give it a read $\endgroup$ – Sanchayan Dutta Jul 2 '18 at 8:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.