What is the quantum computational model?

Question

I have occasionally heard people talk about quantum algorithms and about states and the ability to consider multiple possibilities at once, but I have never managed to get someone to explain the computational model behind this. To be clear, I am not asking about how quantum computers are physically constructed, but rather how to view them from a computational point of view.

Answer 1

I'll echo Martin Schwartz's recommendation of Nielsen & Chaung as the standard reference; there are many others as well.

Research in the field prefers to consider uniform families of quantum circuits, which (ironically) are directed acyclic networks describing how the state of one or more registers transforms with time, in a way similar to classical boolean circuits. If you wish to learn more, I recommend learning in terms of this model.

I would like to give some qualitative answers to complement Martin's response.

1. Quantum computation does not actually consider "multiple possibilities at once" --- or more precisely, whether or not you consider them to consider multiple possibilities at once is a matter of your choice of interpretation of quantum mechanics, i.e. a philosophical choice which has no bearing on the ability or predictions of the computational model. ("Considering multiple possibilities at once" corresponds to the "many worlds interpretation" of QM.)
   
   At the very least, one can say that a quantum computer considers multiple possibilities at the same time only to the extent that a randomized computation using coin-flips considers multiple possibilities at the same time. This is because:

2. Quantum states are generalizations of "the usual" probability distributions --- with some simple but important differences. A probability distribution can be represented as a non-negative real vector whose entries sum to 1: that is, a unit vector in the ℓ¹ norm. Probabilistic computations must map ℓ¹-unit vectors to other such vectors, and so they are described by stochastic maps. One can describe quantum computation in a similar way, except using ℓ²-unit vectors over ℂ (not restricted to be real or non-negative); transformations are by those maps which preserve the ℓ²-norm, i.e. unitary operations.
   
   This difference is not trivial, of course, nor does it explain yet what the coefficients of the quantum state vectors mean. But it may help to explain what is going on with Hilbert spaces and tensor products in quantum computation: to wit, exactly the same things as happen in probabilistic computation. The configuration space of a random bit is a vector in ℝ₊² (where ℝ₊ are the non-negative reals); but because random bits can be correlated, we combine the configuration spaces of one or more random bits by taking the tensor product. So the configuration space of two random bits is ℝ₊² ⊗ ℝ₊² ≅ ℝ₊⁴ , or the fully-general space of probability distributions over the four distinct two-bit strings. An operation A on the first of these random bits which does not act on the second is represented by the operator A ⊗ I₂ . And so on. The same constructions apply to quantum bits; and we can consider quantum registers over sets of distinguishable elements the same way we consider probability distributions over such sets, again using ℓ²-norm vectors over ℂ.
   
   This description actually describes the "pure" quantum states --- the ones for which you can in principle transform in an information-preserving way to a delta-distribution over the bit-string 00...0 (or more precisely, to a state arbitrarily close to this in the ℓ² norm). On top of the quantum-randomness (of which I have not yet mentioned anything explicit), you can consider vanilla-convexity-randomness corresponding to probabilistic mixtures of quantum states: these are represented by density operators, which can be represented by positive definite matrices with trace 1 (again generalizing "classical" probability distributions, which may be represented by the special case of positive diagonal matrices with trace 1).
   
   What is important about this is that, while quantum states are often described as being "exponentially large", this is because they are usually described using the same mathematical structures as probability distributions; why probability distributions are not described as "exponentially large" in the same way is unclear (but ultimately unimportant). The difficulty of simulating quantum states come from this fact, together with the fact that the complex coefficients of these ℓ²-distributions (or the complex off-diagonal terms of the density operators, if you prefer) may cancel in a way that probabilities cannot, rendering estimation of them more difficult.

3. Entanglement is just another form of correlation. For probabilistic computation on e.g. boolean strings, the only "pure" states (which can be mapped by information-preserving transformations to a delta-peaked distribution on 000...0) are the "standard basis" of delta-peaked distributions on the different boolean strings. Thus, this basis of ℝ₊²ⁿ is distinguished. But there is no such distinguished basis in quantum mechanics, as far as we can tell --- this is clearest for quantum bits (look up spin 1/2 particles, if you want to know why). As a consequence, there are more information-preserving transformations than just the permutations: a continuous group of them, in fact. This allows would-be quantum computers to transform states in ways which are not possible for probabilistic computers, possibly obtaining an asymptotic advantage over them.
   
   But what about entanglement, which many people find mysterious, and claim to be the cause of the speed-up of quantum computers over classical? "Entanglement" here is really just a form of correlation: just as two random variables are correlated if their distribution is a convex combination of more than one product distribution (with different marginals on each variable), two "quantum variables" are entangled if their distribution is a linear combination (with unit ℓ²-norm) of two valid product distributions; it is the same concept under a different norm, and plays a similar role in communication tasks. (For example: "quantum teleportation" in quantum communication corresponds to encoding and decoding a message using a one-time pad classically.) This is a form of correlation which is more general than just classically correlated bits; but the only way to show this is that the correlations encoded in the entangled state apply to more than just one privileged basis. In a manner of speaking, entanglement is a consequence of the absence of a privileged basis.
   
   People like to invoke entanglement as the key element of quantum computation, but this simply doesn't seem to hold water: there have been results showing that entanglement is not quantitatively important for Shor's algorithm to factor large integers, and that indeed a quantum system can have too much entanglement to be useful for a computation. In fact, everywhere that I am aware of that entanglement plays an important role in a quantum protocol is essentially one of communication (where correlations would be expected to play an important role for a classical protocol).

At this point, I begin wading into the domain of personal opinion, so I'll stop here. But hopefully, these remarks might de-mystify some of what is obscure about quantum computation and how it is described.

Answer 2

Lance Fortnow wrote an article that explains quantum computing without using quantum mechanics. He presents it essentially the same way one would present probabilistic computing. I suspect this may be a quicker starting point than something like Nielson and Chuang (though I agree that if you want to really go into this then Nielson and Chung should definitely be on your reading list).

L. Fortnow. One complexity theorist's view of quantum computing. Theoretical Computer Science, 292(3):597-610, 2003. Special Issue of papers presented at the second workshop on Algorithms in Quantum Information Processing.

Answer 3

Well, the standard text used is Quantum Computation and Quantum Information by Nielsen and Chuang. It covers quite a range of different aspects at a reasonable level. Nearly everyone working in the field has a copy of this on their shelf. The Kaye, Laflamme and Mosca book is also good, but covers less (though there is a little more focus on algorithms).

While it is quite possible to explain quantum computing without going into much quantum mechanics, I don't think that this is necessarily a good way to approach learning quantum computation. There is quite a lot of intuition to be gained by having a feel for the physical theory, since many of the more recent models of quantum computation (i.e. adiabatic, topological and measurement-based models) are more physically motivated than the quantum Turing machine or the circuit model.

That said, the quantum mechanics required to understand quantum computation is fairly simple, and is covered quite well in Nielsen and Chuang. Really, you can get a good feel for it reading through the relevant chapter and trying the exercises. It's the kind of thing you can get a fair understanding of with a couple of days work. My advice, though, is don't go for a standard intro text to quantum mechanics. The approach taken to model atoms, molecules and materials uses infinite dimensional systems, and takes quite a lot more effort to get on top of. For quantum information it is a much better start to look at finite dimensional systems. Also, traditionally, the problems studied by physicists tend to revolve around finding ground states and steady state behaviours, and this is what most introductory texts will cover (starting with the time-independent Schroedinger wave equation). For quantum computing, we tend to be more interested in the time evolution of systems, and this is dealt with much more succinctly in quantum computing texts than in general quantum mechanics intro texts (which are by definition more general).

Answer 4

The quantum computational model is formalized, equivalently, by the Quantum Turing Machine (QTM) model and by the quantum circuits model, which is predominantly used nowadays. A third, less frequently used model, is based on finite-dimensional path integrals, that is for example used to show the relation of $BQP$ (Bounded-Error Quantum Polynomial time) to classical complexity classes, i.e. BQP ⊆ P^#P = P^GapP. Furthermore, the most general model incorporating noise is based on quantum operations, or Kraus operators. All of these models are known to be computationally equivalent, though.

Let me now give a brief, physics-free introduction to the quantum circuit model: Qubits are the fundamental unit of quantum information being processed. A qubit is simply some unit vector $|\phi\rangle$ in a two dimensional Hilbert space $\cal{H_2}$. Larger registers are formed by tensor products $\cal{H_2} \otimes ... \otimes \cal{H_2}$ of the basic two-dimensional Hilbert space. The dimension of the composite space is the product of the dimension of the constituent spaces and thus scales exponentially with the number of qubits in the quantum register. A quantum state in the register is again a unit vector $|\psi\rangle$ in the composite space. The components of this vector are complex values called probability amplitudes and can be labeled with classical bit strings. State evolution is performed by applying a unitary operator $U$ (also known as quantum gate) to some constant-width subset of qubits. At the end of the computation the qubits are measured leading to a classical bit string as outcome with a probability distribution that is related to the $square$ of the probability amplitude associated with that bit string.

For a more in-depth introduction, please see the standard textbook Nielsen and Chuang.

Answer 5

You're probably already aware of this, but on his blog, Scott Aaronson has links to number of his course lectures on quantum computing, as well as links to QC primers by others (just scroll down the right side-bar to find these).

If you'd like a book-length introduction, but something that's gentler than a text like Nielsen and Chuang, I would recommend Quantum Computing for Computer Scientists by Yanofsky and Mannucci. They spend a fair amount of time reviewing the mathematical prerequisites before diving into the QC itself. If you have a strong math background this book might seem too basic, but I found it quite useful.

Answer 6

First, you will need to understand quantum physics.

A few recommendations:

1. "Quantum Computing for Computer Scientists" by Noson S. Yanofsky and Mirco A. Mannucci
2. "An Introduction to Quantum Computing" by Phillip Kaye, Raymond Laflamme and Michele Mosca

And on the more entertaining side of things, "A Shortcut Through Time: The Path to the Quantum Computer" by George Johnson.

Answer 7

You can have a nice introduction in the article "An Introduction to Quantum Computing for Non-Physicists" by Eleanor Rieffel and Wolfgang Polak. It is maybe a bit old, however it is still a good, short, self-contained introduction to the topic: http://arxiv.org/abs/quant-ph/9809016

Another article, much more summarized is the Pablo Arrighi's "Quantum Computation explained to my Mother" at http://arxiv.org/abs/quant-ph/0305045

Answer 8

In general, I'd second Joe's advice. But for a quick intro, I'd put Lance Fortnow's and Stephen Fenner's texts on the reading list of computer scientists going quantum.

Answer 9

If you're fairly advanced, you might start with the de Wolf-Drucker survey of quantum methods for classical problems. It's a good way to understand quantum techniques before you get to quantum problems.

Answer 10

I don't think you need to learn quantum mechanics. However it depends in what area you would like to work. There are areas of the field that really need a knowledge on quantum mechanics, however as instance the area I work on, type theory and lambda calculus, I do not need it, I can do it just knowing some of the computational models for it.

Answer 11

Besides his standard text with Chuang, Michael Nielsen has a series of video lectures on Youtube called Quantum Computing for the Determined which so far gives an overview of the computational model. The videos are very watchable for anyone with a little understanding of computer science and linear algebra.