Multiple Qubits and the Quantum Circuit

Last time we left off with the tantalizing question: how do you do a quantum “AND” operation on two qubits? In this post we’ll see why the tensor product is the natural mathematical way to represent the joint state of multiple qubits. Then we’ll define some basic quantum gates, and present the definition of a quantum circuit.

Working with Multiple Qubits

In a classical system, if you have two bits with values b_1, b_2, then the “joint state” of the two bits is given by the concatenated string b_1b_2. But if we have two qubits v, w, which are vectors in \mathbb{C}^2, how do we represent their joint state?

There are seemingly infinitely many things we could try, but let’s entertain the simplest idea for the sake of exercising our linear algebra intuition. The simplest idea is to just “concatenate” the vectors as one does in linear algebra: represent the joint system as (v, w) \in \mathbb{C}^2 \oplus \mathbb{C}^2. Recall that the direct sum of two vector spaces is just what you’d want out of “concatenation” of vectors. It treats the two components as completely independent of each other, and there’s an easy way to take any vector in the sum and decompose it into two vectors in the pieces.

Why does this fail to meet our requirements of qubits? Here’s one reason: (v, w) is not a unit vector when v and w are separately unit vectors. Indeed, \left \| (v,w) \right \|^2 = \left \| v \right \|^2 + \left \| w \right \|^2 = 2. We could normalize everything, and that would work for a while, but we would still run into problems. A better reason is that direct sums screw up measurement. In particular, if you have two qubits (and they’re independent, in a sense we’ll make clear later), you should be able to measure one without affecting the other. But if we use the direct sum method for combining qubits, then measuring one qubit would collapse the other! There are times when we want this to happen, but we don’t always want it to happen. Alas, there should be better reasons out there (besides, “physics says so”) but I haven’t come across them yet.

So the nice mathematical alternative is to make the joint state of two qubits v,w the tensor product v \otimes w. For a review of the basic properties of tensors and multilinear maps, see our post on the subject. Suffice it for now to remind the reader that the basis of the tensor space U \otimes V consists of all the tensors of the basis elements of the pieces U and V: u_i \otimes v_j. As such, the dimension of U \otimes V is the product of the dimensions \text{dim}(U) \text{dim}(V).

As a consequence of this and the fact that all \mathbb{C}-vector spaces of the same dimension are the same (isomorphic), the state space of a set of n qubits can be identified with \mathbb{C}^{2^n}. This is one way to see why quantum computing has the potential to be strictly more powerful than classical computing: n qubits provide a state space with 2^n coefficients, each of which is a complex number. With classical probabilistic computing we only get n “coefficients.” This isn’t a proof that quantum computing is more powerful, but a wink and a nudge that it could be.

While most of the time we’ll just write our states in terms of tensors (using the \otimes symbol), we could write out the vector representation of v \otimes w in terms of the vectors v = (v_1, v_2), w=(w_1, w_2). It’s just (v_1w_1, v_1w_2, v_2w_1, v_2w_2), with the obvious generalization to vectors of any dimension. This already fixes our earlier problem with norms: the norm of a tensor of two vectors is the product of the two norms. So tensors of unit vectors are unit vectors. Moreover, if you measure the first qubit, that just sets the v_1, v_2 above to zero or one, leaving a joint state that is still a valid

Likewise, given two linear maps A, B, we can describe the map A \otimes B on the tensor space both in terms of pure tensors ((A \otimes B)(v \otimes w) = Av \otimes Bw) and in terms of a matrix. In the same vein as the representation for vectors, the matrix corresponding to A \otimes B is

\displaystyle \begin{pmatrix}  a_{1,1}B & a_{1,2}B & \dots & a_{1,n}B \\  a_{2,1}B & a_{2,2}B & \dots & a_{2,n}B \\  \vdots & \vdots & \ddots & \vdots \\  a_{n,1}B & a_{n,2}B & \dots & a_{n,n}B  \end{pmatrix}

This is called the Kronecker product.

One of the strange things about tensor products, which very visibly manifests itself in “strange quantum behavior,” is that not every vector in a tensor space can be represented as a single tensor product of some vectors. Let’s work with an example: \mathbb{C}^2 \otimes \mathbb{C}^2, and denote by e_0, e_1 the computational basis vectors (the same letters are used for each copy of \mathbb{C}^2). Sometimes you’ll get a vector like

\displaystyle v = \frac{1}{\sqrt{2}} e_0 \otimes e_0 + \frac{1}{\sqrt{2}} e_1 \otimes e_0

And if you’re lucky you’ll notice that this can be factored and written as \frac{1}{\sqrt{2}}(e_0 + e_1) \otimes e_0. Other times, though, you’ll get a vector like

\displaystyle \frac{1}{\sqrt{2}}(e_0 \otimes e_0 + e_1 \otimes e_1)

And it’s a deep fact that this cannot be factored into a tensor product of two vectors (prove it as an exercise). If a vector v in a tensor space can be written as a single tensor product of vectors, we call v a pure tensor. Otherwise, using some physics lingo, we call the state represented by v entangled. So if you did the exercise you proved that not all tensors are pure tensors, or equivalently that there exist entangled quantum states. The latter sounds so much more impressive. We’ll see in a future post why these entangled states are so important in quantum computing.

Now we need to explain how to extend gates and qubit measurements to state spaces with multiple qubits. The first is easy: just as we often restrict our classical gates to a few bits (like the AND of two bits), we restrict multi-qubit quantum gates to operate on at most three qubits.

Definition: A quantum gate G is a unitary map \mathbb{C}^{2^n} \to \mathbb{C}^{2^n} where n is at most 3, (recall, (\mathbb{C}^2)^{\otimes 3} = \mathbb{C}^{2^3} is the state space for 3 qubits).

Now let’s see how to implement AND and OR for two qubits. You might be wondering why we need three qubits in the definition above, and, perhaps surprisingly, we’ll see that AND and OR require us to work with three qubits.

Because how would one compute an AND of two qubits? Taking a naive approach from how we did the quantum NOT, we would label e_0 as “false” and e_1 as “true,” and we’d want to map e_1 \otimes e_1 \mapsto e_1 and all other possibilities to e_0. The main problem is that this is not an invertible function! Remember, all quantum operations are unitary matrices and all unitary matrices have inverses, so we have to model AND and OR as an invertible operation. We also have a “type error,” since the output is not even in the same vector space as the input, but any way to fix that would still run into the invertibility problem.

The way to deal with this is to add an extra “scratch work” qubit that is used for nothing else except to make the operation invertible. So now say we have three qubits a, b, c, and we want to compute a AND b in the sensible way described above. What we do is map

\displaystyle a \otimes b \otimes c \mapsto a \otimes b \otimes (c \oplus (a \wedge b))

Here a \wedge b is the usual AND (where we interpret, e.g., e_1 \wedge e_0 = e_0), and \oplus is the exclusive or operation on bits. It’s clear that this mapping makes sense for “bits” (the true/false interpretation of basis vectors) and so we can extend it to a linear map by writing down the matrix.

quantum-AND

This gate is often called the Toffoli gate by physicists, but we’ll just call it the (quantum) AND gate. Note that the column ijk represents the input e_i \otimes e_j \otimes e_k, and the 1 in that column denotes the row whose label is the output. In particular, if we want to do an AND then we’ll ensure the “scratch work” qubit is e_0, so we can ignore half the columns above where the third qubit is 1. The reader should write down the analogous construction for a quantum OR.

From now on, when we’re describing a basis state like e_1 \otimes e_0 \otimes e_1, we’ll denote it as e_{101}. We’re taking advantage of the correspondence between the 2^n binary strings and the 2^n basis states, and it compactifies notation.

Once we define a quantum circuit, it will be easy to show that using quantum AND’s, OR’s and NOT’s, we can achieve any computation that a classical circuit can.

We have one more issue we’d like to bring up before we define quantum circuits. We’re being a bit too slick when we say we’re working with “at most three qubits.” If we have ten qubits, potentially all entangled up in a weird way, how can we apply a mapping to only some of those qubits? Indeed, we only defined AND for \mathbb{C}^8, so how can we extend that to an AND of three qubits sitting inside any \mathbb{C}^{2^n} we please? The answer is to apply the Kronecker product with the identity matrix appropriately. Let’s do a simple example of this to make everything stick.

Say I want to apply the quantum NOT gate to a qubit v, and I have four other qubits w_1, w_2, w_3, w_4 so that they’re all in the joint state x = v \otimes w_1 \otimes w_2 \otimes w_3 \otimes w_4. I form the NOT gate, which I’ll call A, and then I apply the gate A \otimes I_{2^4} to x (since there are 4 of the w_i). This will compute the tensor Av \otimes I_2 w_1 \otimes I_2 w_2 \otimes I_2 w_3 \otimes I_2 w_4, as desired.

In particular, you can represent a gate that depends on only 3 qubits by writing down the 3×3 matrix and the three indices it operates on. Note that this requires only 12 (possibly complex) numbers to write down, and so it takes “constant space” to represent a single gate.

Quantum Circuits

Here we are at the definition of a quantum circuit.

Definition: quantum circuit is a list G_1, \dots, G_T of 2^m \times 2^m unitary matrices, such that each G_i depends on at most 3 qubits.

We’ll write down what it means to “compute” something with a quantum circuit, but for now we can imagine drawing it like a usual circuit. We write the input state as some unit vector x \in C^{2^n} (which may or may not be a pure tensor), each qubit making up the vector is associated to a “wire,” and at each step we pick three of the wires, send them to the next quantum gate G_i, and use the three output wires for further computations. The final output is the matrix product applied to the input G_T \dots G_1x. We imagine that each gate takes only one step to compute (recall, in our first post one “step” was a photon flying through a special material, so it’s not like we have to multiply these matrices by hand).

So now we have to say how a quantum circuit could solve a problem. At all levels of mathematical maturity we should have some idea how a regular circuit solves a problem: there is some distinguished output wire or set of wires containing the answer. For a quantum circuit it’s basically the same, except that at the end of the circuit we get a quantum state, and we pick some distinguished wires (qubits) to measure. The result of that measurement is some classical bits containing our answer. As we’ve said we may need to repeat a quantum computation over and over to get a good answer with high probability, so we can imagine that a quantum circuit is used as some subroutine in a larger (otherwise classical) algorithm that allows for pre- and post-processing on the quantum part.

The final caveat is that we allow one to include as many scratchwork qubits as one needs in their circuit. This makes it possible already to simulate any classical circuit using a quantum circuit. Let’s prove it as a theorem.

Theorem: Given a classical circuit C with a single output bit, there is a quantum circuit D that computes the same function.

Proof. Let x be a binary string input to C, and suppose that C has s gates g_1, \dots, g_s, each being either AND, OR, or NOT, and with g_s being the output gate. To construct D, we can replace every g_i with their quantum counterparts G_i. Recall that this takes e_{b_1b_20} \mapsto e_{b_1b_2(g_i(b_1, b_2))}. And so we need to add a single scratchwork qubit for each one (really we only need it for the ANDs and ORs, but who cares). This means that our start state is e_{x} \otimes e_{0^s} = e_{x0^s}. Really, we need one of these gates G_i for each wire going out of the classical gate g_i, but with some extra tricks one can do it with a single quantum gate that uses multiple scratchwork qubits.

If we call z the contents of all the scratchwork after the quantum circuit described above runs and z_0 the initial state of the scratchwork, then what we did was extend the function x \mapsto C(x) to a function e_{x,z_0} \mapsto e_{x, z}. In particular, one of the bits in the z part is the output of the last gate of C, and everything is 0-1 valued. So we can just measure the output qubit and win.

\square

It should be clear that the single output bit extends to the general case easily. We can split a circuit with lots of output bits into a bunch of circuits with single output bits in the obvious way and combine the quantum versions together.

Next time we’ll finally look at our first quantum algorithms. And along the way we’ll see some more significant quantum operations that make use of the properties that make the quantum world interesting. Until then!

My LaTeX Workflow: latexmk, ShareLaTeX, and StackEdit

Over the last year or so I’ve gradually spent more and more of my time typing math. Be it lecture notes, papers, or blog posts, I think in the last two years I’ve typed vastly more dollar signs (TeX math mode delimiters) than in the rest of my life combined. As is the natural inclination for most programmers, I’ve tried lots of different ways to optimize my workflow and minimize the amount of typing, configuring, file duplicating, and compiler-wrestling I do in my day-to-day routine.

I’ve arrived at what I feel is a stable state. Here’s what I use.

First, my general setup. At home I run OS X Mavericks (10.9.5), and I carry a Chromebook with me to campus and when I travel.

For on-the-fly note taking

I haven’t found a better tool than StackEdit.

stackedit-logo

Mindset: somewhere in between writing an email with one or two bits of notation (just write TeX source and hope they can read it) and writing a document that needs to look good. These are documents for which you have no figures, don’t want to keep track of sections and theorem numbering, and have no serious bibliography.

Use cases:

  • In class notes: where I need to type fast and can sacrifice on prettiness. Any other workflow besides Markdown with TeX support is just awfully slow, because the boilerplate of LaTeX proper involves so much typing (\begin{theorem} \end{theorem}, etc.)
  • Notes during talks: these notes usually have fewer formulas and more sentences, but the ability to use notation when I want it really helps.
  • Short drafts of proofs: when I want to send something technical yet informal to a colleague, but it’s in such a draft phase that I’m more concerned about the idea being right—and on paper—than whether it looks good.

Awesome features: I can access documents from Google Drive. Integration with Dropbox (which they have) is not enough because I don’t have Dropbox on every computer I use (Chromebook, public/friends’ computers). Also, you can configure Google Drive to open markdown files with StackEdit by default (otherwise Drive can’t open them at all).

How it could improve: The service gets sluggish with longer documents, and sometimes the preview page jumps around like crazy when you have lots of offset equations. Sometimes it seems like it recompiles the whole document when you only change one paragraph, and so the preview can be useless to look at while you’re typing. I recently discovered you can turn off features you don’t use in the settings, so that might speed things up.

Also, any time something needs to be aligned (such as a matrix or piecewise notation), you have to type \begin{}’s and \end{}’s, so that slows down the typing. It would be nice to have some shortcuts like \matrix[2,3]{1,3,4,4,6,8} or at least an abbreviation for \begin and \end (\b{} and \e{}, maybe?). Also some special support for (and shortcuts for) theorem/proof styling would be nice, but not necessary. Right now I embolden the Theorem and italicize the Proof., and end with a tombstone \square on a line by itself. I don’t see a simple way to make a theorem/proof environment with minimal typing, but it does occur to me as an inefficiency; the less time I can spend highlighting and formatting things the better.

Caveats: Additional features, such as exporting from StackEdit to pdf requires you to become a donor ($5/year, a more than fair price for the amount I use it). I would find the service significantly less useful if I could not export to pdf.

For work while travelling

My favorite so far is ShareLaTeX.

sharelatexI’ve used a bunch of online TeX editors, most notably Overleaf (formerly WriteLaTeX). They’re both pretty solid, but a few features tip me toward ShareLaTeX. I’ll italicize these things below.

Mindset: An editor I can use on my Chromebook or a public machine, yet still access my big papers and projects in progress. Needs support for figures, bibliographies, the whole shebang. Basically I need a browser replacement for a desktop LaTeX setup. I generally do not need collaboration services, because the de facto standard among everyone I’ve ever interacted with is that you can only expect people to have Dropbox. You cannot expect them to sign up for online services just to work with you.

Use cases:

  • Drafting actual research papers
  • Writing slides/talks

Awesome features: Dropbox integration! This is crucial, because I (and everyone I know) does their big collaborative projects using Dropbox. ShareLaTeX (unlike Overleaf) has seamless Dropbox integration. The only caveat is that ShareLaTeX only accesses Dropbox files that are in a specially-named folder. This causes me to use a bunch of symbolic links that would be annoying to duplicate if I got a new machine.

Other than that, ShareLaTeX (like Overleaf) has tons of templates, all the usual libraries, great customer support, and great collaborative features for the once in a blue moon that someone else uses ShareLaTeX.

Vim commands. The problem is that they don’t go far enough here. They don’t support vim-style word-wrapping (gq), and they leave out things like backward search (? instead of /) and any : commands you tend to use.

Github integration. Though literally no mathematicians I know use Github for anything related to research, I think that with the right features Github could become the “right” solution to paper management. The way people store and “archive” their work is horrendous, and everyone can agree a waste of time. I have lots of ideas for how Github could improve academics’ lives and the lives of the users of their research, too many to list here without derailing the post. The point is that ShareLaTeX having Github integration is forward thinking and makes ShareLaTeX more attractive.

How it could improve: Better vim command support. It seems like many of these services are viewed by their creators as a complete replacement for offline work, when really (for me) it’s a temporary substitute that needs to operate seamlessly with my other services. So basically the more seamless integration it has with services I use, the better.

Caveats: Integration comes at a premium of $8/month for students, and $15/month for non-students.

Work at home

This is where we get into the nitty gritty of terminal tools. Because naively writing papers in TeX on a desktop has a lot of lame steps and tricks. There are (multiple types of) bibliography files to manage, you have to run like four commands to compile a document, and the TeX compiler errors are often nonsense.

I used to have a simple script to compile;display;clean for me, but then I came across the latexmk program. What you can do is configure latexmk to automatically recompile when a change is made to a source file, and then you can configure a pdf viewer (like Skim) to update when the pdf changes. So instead of the workflow being “Write. Compile. View. Repeat,” It’s “Compile. View. Write until done.”

Of course lots of random TeX distributions come with crusty GUIs that (with configuration) do what latexmk does. But I love my vim, and you have your favorite editor, too. The key part is that latexmk and Skim don’t care what editor you use.

For reference, here’s how I got it all configured on OS X Mavericks.

  1. Install latexmk (move the perl script downloadable from their website to anywhere on your $PATH).
  2. Add alias latexmk='latexmk.pl -pvc' to your .profile. The -pvc flag makes latexmk watch for changes.
  3. Add the following to a new file called .latexmkrc in your home directory (it says: I only do pdfs and use Skim to preview):
    $pdf_mode = 1;
    $postscript_mode = 0;
    $dvi_mode = 0;
    $pdf_previewer = "open -a /Applications/Skim.app";
    $clean_ext = "paux lox pdfsync out";
  4. Install Skim.
  5. In Skim’s preferences, go to the Sync tab and check the box “Check for file changes.”
  6. Run the following from the command line, which prevents Skim from asking (once for each file!) whether you want to auto reload that file:
    $ defaults write -app Skim SKAutoReloadFileUpdate -boolean true

Now the workflow is: browse to your working directory; run latexmk yourfile.tex (this will open Skim); open the tex document in your editor; write. When you save the file, it will automatically recompile and display in Skim. Since it’s OS X, you can scroll through the pdf without switching window focus, so you don’t even have to click back into the terminal window to continue typing.

Finally, I have two lines in my .vimrc to auto-save every second that the document is idle (or when the window loses focus) so that I don’t have to type :w every time I want the updates to display. To make this happen only when you open a tex file, add these lines instead to ~/.vim/ftplugin/tex.vim

set updatetime=1000
autocmd CursorHoldI,CursorHold,BufLeave,FocusLost silent! wall

Caveats: I haven’t figured out how to configure latexmk to do anything more complicated than this. Apparently it’s possible to get it setup to work with “Sync support,” which means essentially you can go back and forth between the source file lines and the corresponding rendered document lines by clicking places. I think reverse search (pdf->vim) isn’t possible with regular vim (it is apparently with macvim), but forward search (vim->pdf) is if you’re willing to install some plugins and configure some files. So here is the place where Skim does care what editor you use. I haven’t yet figured out how to do it, but it’s not a feature I care much for.


One deficiency I’ve found: there’s no good bibliography manager. Sorry, Mendeley, I really can’t function with you. I’ll just be hand-crafting my own bib files until I find or make a better solution.

Have any great tools you use for science and paper writing? I’d love to hear about them.

Joint Mathematics Meeting!

I’ll be attending the AMS Joint Mathematics Meeting in San Antonio this weekend. I won’t be giving a talk, but if you see me and want to chat don’t hesitate to say hi :)

The Quantum Bit

The best place to start our journey through quantum computing is to recall how classical computing works and try to extend it. Since our final quantum computing model will be a circuit model, we should informally discuss circuits first.

A circuit has three parts: the “inputs,” which are bits (either zero or one); the “gates,” which represent the lowest-level computations we perform on bits; and the “wires,” which connect the outputs of gates to the inputs of other gates. Typically the gates have one or two input bits and one output bit, and they correspond to some logical operation like AND, NOT, or XOR.

A simple example of a circuit.

A simple example of a circuit. The V’s are “OR” and the Λ’s are “AND.” Image source: Ryan O’Donnell

If we want to come up with a different model of computing, we could start regular circuits and generalize some or all of these pieces. Indeed, in our motivational post we saw a glimpse of a probabilistic model of computation, where instead of the inputs being bits they were probabilities in a probability distribution, and instead of the gates being simple boolean functions they were linear maps that preserved probability distributions (we called such a matrix “stochastic”).

Rather than go through that whole train of thought again let’s just jump into the definitions for the quantum setting. In case you missed last time, our goal is to avoid as much physics as possible and frame everything purely in terms of linear algebra.

Qubits are Unit Vectors

The generalization of a bit is simple: it’s a unit vector in \mathbb{C}^2. That is, our most atomic unit of data is a vector (a,b) with the constraints that a,b are complex numbers and |a|^2 + |b|^2 = 1. We call such a vector a qubit.

A qubit can assume “binary” values much like a regular bit, because you could pick two distinguished unit vectors, like (1,0) and (0,1), and call one “zero” and the other “one.” Obviously there are many more possible unit vectors, such as \frac{1}{\sqrt{2}}(1, 1) and (-i,0). But before we go romping about with what qubits can do, we need to understand how we can extract information from a qubit. The definitions we make here will motivate a lot of the rest of what we do, and is in my opinion one of the major hurdles to becoming comfortable with quantum computing.

A bittersweet fact of life is that bits are comforting. They can be zero or one, you can create them and change them and read them whenever you want without an existential crisis. The same is not true of qubits. This is a large part of what makes quantum computing so weird: you can’t just read the information in a qubit! Before we say why, notice that the coefficients in a qubit are complex numbers, so being able to read them exactly would potentially encode an infinite amount of information (in the infinite binary expansion)! Not only would this be an undesirably powerful property of a circuit, but physicists’ experiments tell us it’s not possible either.

So as we’ll see when we get to some algorithms, the main difficulty in getting useful quantum algorithms is not necessarily figuring out how to compute what you want to compute, it’s figuring out how to tease useful information out of the qubits that otherwise directly contain what you want. And the reason it’s so hard is that when you read a qubit, most of the information in the qubit is destroyed. And what you get to see is only a small piece of the information available. Here is the simplest example of that phenomenon, which is called the measurement in the computational basis.

Definition: Let v = (a,b) \in \mathbb{C}^2 be a qubit. Call the standard basis vectors e_0 = (1,0), e_1 = (0,1) the computational basis of \mathbb{C}^2. The process of measuring v in the computational basis consists of two parts.

  1. You observe (get as output) a random choice of e_0 or e_1. The probability of getting e_0 is |a|^2, and the probability of getting e_1 is |b|^2.
  2. As a side effect, the qubit v instantaneously becomes whatever state was observed in 1. This is often called a collapse of the waveform by physicists.

There are more sophisticated ways to measure, and more sophisticated ways to express the process of measurement, but we’ll cover those when we need them. For now this is it.

Why is this so painful? Because if you wanted to try to estimate the probabilities |a|^2 or |b|^2, not only would you get an estimate at best, but you’d have to repeat whatever computation prepared v for measurement over and over again until you get an estimate you’re satisfied with. In fact, we’ll see situations like this, where we actually have a perfect representation of the data we need to solve our problem, but we just can’t get at it because the measurement process destroys it once we measure.

Before we can talk about those algorithms we need to see how we’re allowed to manipulate qubits. As we said before, we use unitary matrices to preserve unit vectors, so let’s recall those and make everything more precise.

Qubit Mappings are Unitary Matrices

Suppose v = (a,b) \in \mathbb{C}^2 is a qubit. If we are to have any mapping between vector spaces, it had better be a linear map, and the linear maps that send unit vectors to unit vectors are called unitary matrices. An equivalent definition that seems a bit stronger is:

Definition: A linear map \mathbb{C}^2 \to \mathbb{C}^2 is called unitary if it preserves the inner product on \mathbb{C}^2.

Let’s remember the inner product on \mathbb{C}^n is defined by \left \langle v,w \right \rangle = \sum_{i=1}^n v_i \overline{w_i} and has some useful properties.

  • The square norm of a vector is \left \| v \right \|^2 = \left \langle v,v \right \rangle.
  • Swapping the coordinates of the complex inner product conjugates the result: \left \langle v,w \right \rangle = \overline{\left \langle w,v \right \rangle}
  • The complex inner product is a linear map if you fix the second coordinate, and a conjugate-linear map if you fix the first. That is, \left \langle au+v, w \right \rangle = a \left \langle u, w \right \rangle + \left \langle v, w \right \rangle and \left \langle u, aw + v \right \rangle = \overline{a} \left \langle u, w \right \rangle + \left \langle u,v \right \rangle

By the first bullet, it makes sense to require unitary matrices to preserve the inner product instead of just the norm, though the two are equivalent (see the derivation on page 2 of these notes). We can obviously generalize unitary matrices to any complex vector space, and unitary matrices have some nice properties. In particular, if U is a unitary matrix then the important property is that the columns (and rows) of U form an orthonormal basis. As an immediate result, if we take the product U\overline{U}^\text{T}, which is just the matrix of all possible inner products of columns of U, we get the identity matrix. This means that unitary matrices are invertible and their inverse is \overline{U}^\text{T}.

Already we have one interesting philosophical tidbit. Any unitary transformation of a qubit is reversible because all unitary matrices are invertible. Apparently the only non-reversible thing we’ve seen so far is measurement.

Recall that \overline{U}^\text{T} is the conjugate transpose of the matrix, which I’ll often write as U^*. Note that there is a way to define U^* without appealing to matrices: it is a notion called the adjoint, which is that linear map U^* such that \left \langle Uv, w \right \rangle = \left \langle v, U^*w \right \rangle for all v,w. Also recall that “unitary matrix” for complex vector spaces means precisely the same thing as “orthogonal matrix” does for real numbers. The only difference is the inner product being used (indeed, if the complex matrix happens to have real entries, then orthogonal matrix and unitary matrix mean the same thing).

Definition: single qubit gate is a unitary matrix \mathbb{C}^2 \to \mathbb{C}^2.

So enough with the properties and definitions, let’s see some examples. For all of these examples we’ll fix the basis to the computational basis e_0, e_1. One very important, but still very simple example of a single qubit gate is the Hadamard gate. This is the unitary map given by the matrix

\displaystyle \frac{1}{\sqrt{2}}\begin{pmatrix}  1 & 1 \\  1 & -1  \end{pmatrix}

It’s so important because if you apply it to a basis vector, say, e_0 = (1,0), you get a uniform linear combination \frac{1}{\sqrt{2}}(e_1 + e_2). One simple use of this is to allow for unbiased coin flips, and as readers of this blog know unbiased coins can efficiently simulate biased coins. But it has many other uses we’ll touch on as they come.

Just to give another example, the quantum NOT gate, often called a Pauli X gate, is the following matrix

\displaystyle \begin{pmatrix}  0 & 1 \\  1 & 0  \end{pmatrix}

It’s called this because, if we consider e_0 to be the “zero” bit and e_1 to be “one,” then this mapping swaps the two. In general, it takes (a,b) to (b,a).

As the reader can probably imagine by the suggestive comparison with classical operations, quantum circuits can do everything that classical circuits can do. We’ll save the proof for a future post, but if we want to do some kind of “quantum AND” operation, we get an obvious question. How do you perform an operation that involves multiple qubits? The short answer is: you represent a collection of bits by their tensor product, and apply a unitary matrix to that tensor.

We’ll go into more detail on this next time, and in the mean time we suggest checking out this blog’s primer on the tensor product. Until then!