Someone shouts, "|01000>!" Who is Excited

--- tags: HPC, QC title: Someone shouts, "|01000>!" Who is Excited ---  {%hackmd Byvzr2yUq %} $\newcommand{\ket}[1]{\vert{#1}\rangle} \newcommand{\C}{\mathbb{C}} \newcommand{\CNOT}{\mathop{\mathsf{CNOT}}} \newcommand{\SWAP}{\mathop{\mathsf{SWAP}}} \newcommand{\span}{\mathop{\mathrm{span}}}$ Recompile from <https://arxiv.org/abs/1711.02086> # [Someone shouts, "$\ket{01000}$!" Who is Excited?](//hackmd.io/@ZjW/Bk-7wbc89) [Robert S. Smith](mailto:robert@rigetti.com "775 Heinz Ave., Berkeley, CA 94710") (November 2, 2017) > Abstract. We talk about the right way to order amplitudes in a wavefunction, and the right way to interpret operator matrices in quantum computation. Answer: Both that someone, and qubit 3. # The Qubit A qubit arbitrarily numbered $i$ lives in a space $B_i \cong \C^2$. For the purpose of computation, we select two orthonormal vectors in $B_i$, the ground state of qubit $i$ and the excited state, labeled $\ket{g}_i$ and $\ket{e}_i$ respectively. Since they're orthonormal, they form a basis: $B_i = \span\{\ket{g}_i,\ket{e}_i\}$. Suppose the qubit $i$ is in the notorious _minus state_: $$ \ket- = \frac1{\sqrt2}\ket{g}_i - \frac1{\sqrt2}\ket{e}_i. $$ When doing algebra, it may be convenient to write it like this, but sometimes, expressing it as a column vector (otherwise known as a _wavefunction_) is even more convenient. But which order do we choose? Should it be $$ \pmatrix{ \frac1{\sqrt2}\\ \frac{-1}{\sqrt2} } \quad \text{or} \quad \pmatrix{ \frac{-1}{\sqrt2}\\ \frac1{\sqrt2} }? $$ The choice is arbitrary; neither has any inherent benefit. Let's choose the former, because we've been writing $\ket{g}_i$ before $\ket{e}_i$ in our expressions. In making this choice, we've chosen a _strict total ordering_ on the basis. We can write this as $\ket{g}_i \prec \ket{e}_i$. With that, we can canonically assign non-negative integers to the basis elements, called their _indices_. Consider a finite-dimensional vector space $V$ which is maybe larger than that of a qubit. With a basis element $v\in V$, we have $$ 0 \leq (\text{the index of $v$}) < \dim V $$ with the property that, with another basis element $u\in V$, $$ u \prec v \iff (\text{the index of $u$}) < (\text{the index of $v$}) .$$ It's important to remind ourselves here that the notion of "order" and the associated canonical indices are specific to both the vector space _and_ a choice of basis. Whatever we choose, we call it the _computational basis_. With indices, we can make our notation a little bit cleaner. Instead of writing $\ket{g}_i$ or $\ket{e}_i$, we can just identify a basis element by its index: $$ \ket0_i := \ket{g}_i \qquad\text{and}\qquad \ket1_i := \ket{e}_i .$$ In the kets, we just write the index as an integer. Now let's consider more than one qubit. It's well-known that the algebra of two qubits is best described by the language of tensor products. That is, for qubits $i$ and $j$, the pair live in the elaborate space of $B_i\otimes B_j$. With a choice of basis for $B_i$ and $B_j$, we have a canonical basis for $B_i\otimes B_j$, namely $$ \big\{ \ket0_i \otimes \ket1_j,\; \ket0_i \otimes \ket0_j,\; \ket1_i \otimes \ket0_j,\; \ket1_i \otimes \ket1_j \big\} .$$ But which order should it be in? If you squint, $\ket1_i \otimes\ket0_j$ looks like the number $10_2$, where the subscript $2$ indicates it's written in binary. This implies the index of $\ket{p}_i \otimes\ket{q}_j$ should be $2p + q$, which in turn implies an ordering. Maybe this is too arbitrary and unappealing, though. So let's turn to an established mathematical convention related to tensor products. The Kronecker product of two matrices $A$ and $B$ is written $A \otimes B$ and is defined as the block matrix $$ (A \otimes B)_{r,c} := A_{r,c}B .$$ The product works just as well for column vectors. Suppose we have a state of some number of qubits $\ket{\psi} \in V$, identified by the vector $$ \pmatrix{ \alpha_0\\ \alpha_1\\ \vdots} ,$$ and we wish to throw another qubit to the mix. Maybe this was an "ambient" qubit whose state we've insofar ignored. Maybe it's a qubit we are explicit adding to the system. Let's have qubit $\ket0_{\textrm{new}} \in B_{\textrm{new}}$ which is identified by $\binom 1 0$. Where do we opt to adjoin this qubit in our space? To the left or right? To the left, $\ket0_{\textrm{new}} \otimes \ket{\psi}$ looks like $$ \pmatrix{ \alpha_0\\ \alpha_1\\ \vdots\\ 0\\ \vdots} ,$$ where the first $\dim V$ entries are the $\alpha$'s and the second $\dim V$ entries are zero. To the right, $\ket{\psi}\otimes\ket0_{\textrm{new}}$ looks like $$ \pmatrix{ \alpha_0\\ 0\\ \alpha_1\\ 0\\ \alpha_2\\ 0\\ \vdots} .$$ Here, the entries alternate between $\alpha$'s and zeros. Already, there's a clear winner. Adjoining to the left didn't perturb the position of our vector entries[^1] from $V$ to $B_{\textrm{new}}\otimes V$. The amplitude $\alpha_j$ is still at position $j$, now associated with the basis vector $\ket0_{\textrm{new}} \otimes \ket{j}_{V}$. With this, we see that in the space $B_i \otimes B_j$, the basis element $\ket{p}_i \otimes \ket{q}_j$ is identified by the index $2p + q$, which is in alignment from our earlier observation. Are there any reasons to do it the other way? The only one I can think of is that $\bigotimes_{i=0}^{n-1}B_i$ is easy to write. So, it is decided, $$ \ket0_i \otimes \ket0_j \prec \ket0_i \otimes \ket1_j \prec \ket1_i \otimes \ket0_j \prec \ket1_i \otimes \ket1_j .$$ Since we have an ordering, we have canonical index assignments: $$ \ket0 \prec \ket1 \prec \ket2 \prec \ket3 .$$ Except in general expressions where we're doing arithmetic with the index, such as writing something like $\ket{2^{k}}$, we might as well write the indices in binary: $$ \ket{00} \prec \ket{01} \prec \ket{10} \prec \ket{11} .$$ Of course, all of this generalizes. Adding an additional qubit will give us $$ \ket{000} \prec \ket{001} \prec \ket{010} \prec \ket{011} \prec \ket{100} \prec \ket{101} \prec \ket{110} \prec \ket{111} .$$ The general rule is thus: For finite-dimensional vector spaces $V$ and $W$ with selected basis elements $\ket{p}_{V}$ and $\ket{q}_{W}$ from the spaces respectively, the induced canonical basis element of $V\otimes W$ is $$ \ket{q+p \dim W}_{V \otimes W} = \ket{p}_V \otimes \ket{q}_W .$$ # The Operator For the rest of this note, it seems natural enough to suppose that we are working in an $n$-qubit space $$ Q_{n} := B_{n-1} \otimes \cdots \otimes B_1 \otimes B_0 .$$ We wish to consider operators on different subspaces of $Q_{n}$. Most of the work is done for us; we know what the basis of $Q_2$ looks like and we know what the ordering of those elements are. For instance, the usual $\CNOT: Q_2\to Q_2$ operator is identified by the matrix $$ \pmatrix{ 1 & 0 & 0 & 0\\ 0 & 1 & 0 & 0\\ 0 & 0 & 0 & 1\\ 0 & 0 & 1 & 0} $$ According to our basis ordering, the qubit of $B_1$ is the _control qubit_ and the qubit of $B_0$ is the _target qubit_. Note that if we wrote same operator instead as acting on the space $B_0 \otimes B_1$, it would be $$ \pmatrix{ 1 & 0 & 0 & 0\\ 0 & 0 & 0 & 1\\ 0 & 0 & 1 & 0\\ 0 & 1 & 0 & 0} ,$$ in effect transposing the identification of $\ket{01}$ and $\ket{10}$, causing the middle two rows and middle two columns of the matrix to be interchanged. In Quil[^2], when we write `CNOT 1 3`, what do we mean as an operator of $Q_{n}$? The following recipe is a constructive way to interpret it. 1. Interpret the standard matrix for $\CNOT$ as one written in the canonical basis for $B_1 \otimes B_3$. That is, the rows and the columns of the matrix follow the canonical ordering $$ \ket0_1 \otimes \ket0_3 \prec \ket0_1 \otimes \ket1_3 \prec \ket1_1 \otimes \ket0_3 \prec \ket1_1 \otimes \ket1_3 .$$ Let's write this operator as $\displaystyle\CNOT_{1,3}$, even though it is identified by the usual matrix. 2. Lift this operator to a space which is nearly like $Q_n$ by tensor multiplying identities. With $\mathsf{I}_k$ the identity operator on $B_k$, write $$ \mathsf{I}_{n-1} \otimes \cdots \otimes \mathsf{I}_4 \otimes \mathsf{I}_2 \otimes \mathsf{I}_0 \otimes \CNOT_{1,3} .$$ Note that this lifted operator is identified by a matrix generated by doing Kronecker multiplication[^3]. 3. Permute the basis vectors so that they match the basis of $Q_n$. This is done with a series of with a transposing isomorphisms $\tau_i$, which are maps swapping the $i$th and $(i+1)$th factors of the tensor product, from the right: $$ \tau_i: \cdots \otimes V \otimes U \otimes \underbrace{\cdots}_\text{$i$ factors} \to \cdots \otimes U \otimes V \otimes \cdots .$$ In this case, we want to permute $$ B_{n-1} \otimes \cdots \otimes B_4 \otimes B_2 \otimes B_0 \otimes B_1 \otimes B_3 $$ into order, which will require $\tau_2 \circ \tau_1 \circ \tau_0 \circ \tau_1$. Transpositions have a nice matrix representation, namely $$ \tau_i= \pmatrix{ 1 & 0\\ 0 & 1 }^{\otimes n-i-2} \otimes \pmatrix{ 1 & 0 & 0 & 0\\ 0 & 0 & 1 & 0\\ 0 & 1 & 0 & 0\\ 0 & 0 & 0 & 1 } \otimes \pmatrix{ 1 & 0\\ 0 & 1 }^{\otimes i} .$$ As we saw with $\CNOT$ before, the matrix in the middle[^4] has the effect of reinterpreting basis vectors. Of course, all of this busywork can be done efficiently. **Learn More:** - Qubit - Wikipedia https://www.wikiwand.com/en/Qubit - 十分鐘略懂量子運算：量子物理、量子電腦、量子位元、量子閘、量子演算法與量子未來應用 https://youtu.be/hXHrhnt2TEI [^1]: In fact, this would also allow us to manageably work with infinite tensor products. Consider the infinite tensor product of qubit spaces $\cdots \otimes B_2 \otimes B_1 \otimes B_0$. If we say that a state of this system consists of any tensor product containing finitely many non-$\ket0$ factors, then we can do both linear algebra _and_ true bonafide computation with it by knowing that in the column vector representation, there will always be a position after which the entries are zero. Without resorting to trickery, this would not be so if the infinite product grew to the right. [^2]: R. S. Smith, M. J. Curtis, and W. J. Zeng, "A Practical Quantum Instruction Set Architecture," (2016), [arXiv:1608.03355](//arxiv.org/abs/1608.03355). [^3]: This is a subtle point that we wish to distinguish. The operator here is a linear transformation represented as a tensor product. We can write a particular representation of this operator by calculating the following Kronecker products $$ \pmatrix{ 1 & 0\\ 0 & 1} \otimes \cdots \otimes \pmatrix{ 1 & 0\\ 0 & 1} \otimes \pmatrix{ 1 & 0\\ 0 & 1} \otimes \pmatrix{ 1 & 0\\ 0 & 1} \otimes \pmatrix{ 1 & 0 & 0 & 0\\ 0 & 1 & 0 & 0\\ 0 & 0 & 0 & 1\\ 0 & 0 & 1 & 0}.$$ The tensor product results in an automorphism on the space $$ B_{n-1} \otimes \cdots \otimes B_4 \otimes B_2 \otimes B_0 \otimes B_1 \otimes B_3 $$ while the Kronecker product results in a _representation_ of this operator in the basis we've described in detail. [^4]: This matrix is actually the quantum $\SWAP$ operator when interpreted in $Q_2$. While Quil takes care of this whole tranposition business automatically, we can emulate the effect of $\tau_i$ with the Quil instruction $$ \texttt{SWAP}\;(i+1)\;i .$$