<p>I'll echo Martin Schwartz's recommendation of <a href="http://rads.stackoverflow.com/amzn/click/0521635039">Nielsen &amp; Chaung</a> as the standard reference; there are many others as well. </p>

<p>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.</p>

<p>I would like to give some qualitative answers to complement Martin's response.</p>

<ol>
<li><p><strong>Quantum computation does not actually consider "multiple possibilities at once"</strong> --- or more precisely, whether or not you consider them to consider multiple possibilities at once is a matter of your choice of <em>interpretation of quantum mechanics</em>, 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.)<br><br> 
At the very least, one can say that a quantum computer considers multiple possibilities at the same time only to the extent that a <em>randomized</em> computation using coin-flips considers multiple possibilities at the same time. This is because:</p></li>
<li><p><strong>Quantum states are generalizations of "the usual" probability distributions</strong> --- 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 &#8467;<sup>1</sup> norm. Probabilistic computations must map &#8467;<sup>1</sup>-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 &#8467;<sup>2</sup>-unit vectors over &#8450; (not restricted to be real or non-negative); transformations are by those maps which preserve the &#8467;<sup>2</sup>-norm, i.e. unitary operations.<br><br> This difference is not trivial, of course, nor does it explain yet what the coefficients of the quantum state vectors <strong>mean</strong>. 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 &#8477;<sub>+</sub><sup>2</sup> (where &#8477;<sub>+</sub> 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 &#8477;<sub>+</sub><sup>2</sup>&nbsp;&otimes;&nbsp;&#8477;<sub>+</sub><sup>2</sup>&nbsp;&cong;&nbsp;&#8477;<sub>+</sub><sup>4</sup>&nbsp;, or the fully-general space of probability distributions over the four distinct two-bit strings. An operation <em>A</em> on the first of these random bits which does not act on the second is represented by the operator <em>A</em>&nbsp;&otimes;&nbsp;<em>I</em><sub>2</sub>&nbsp;. 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 &#8467;<sup>2</sup>-norm vectors over &#8450;.<br><br> 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 &#8467;<sup>2</sup> 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 <em>density operators</em>, 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).<br><br> 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 &#8467;<sup>2</sup>-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.</p></li>
<li><p><strong>Entanglement is just another form of correlation.</strong> 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 &#8477;<sub>+</sub><sup>2<sup>n</sup></sup> 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.<br><br> 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 &#8467;<sup>2</sup>-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 <em>apply to more than just one privileged basis</em>. In a manner of speaking, entanglement is a <em>consequence</em> of the absence of a privileged basis. <br><br> 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 <a href="http://uk.arxiv.org/abs/quant-ph/0412140">entanglement is not quantitatively important</a> for Shor's algorithm to factor large integers, and that indeed a quantum system can have <a href="http://www.physorg.com/news162468404.html">too much entanglement to be useful</a> 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 <em>communication</em> (where correlations would be expected to play an important role for a classical protocol).</p></li>
</ol>

<p>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.</p>

CC BY-SA 3.0
2012-10-16T10:27:45.910Z
I partially agree with Joe on the interference point,  yet an issue to speak rigorously about this point is _what (reasonably tested) measures of interference are there in the market_? Do you people know of works in this direction? The only example that comes to my mind is [this one](http://arxiv.org/abs/quant-ph/0510159) (yet I have not read it in much detail).
Juan Bermejo Vega
CC BY-SA 3.0
2012-10-16T16:08:30.040Z
@JuanBermejoVega: interference seems to just be a corollary of the fact that there are information-preserving transformations which don't preserve standard basis states. The only apparent alternative to interference is information loss, as in classical probability. Then what we have is simply reversible transformations which do not preserve the standard basis; the narrative of interference, as productive as it is when talking about propagation in space, is just a way of describing what this looks like if you continue to try to parse this non-preservation in terms of the standard basis.
Niel de Beaudrap
CC BY-SA 2.5
2010-08-26T00:07:40.557Z
I must admit, I disagree with you on the entanglement question. Operations on pure product states are efficiently simulable. The "too entangled to compute" paper is a bit misleading. This paper is really about resources for measurement based computation, and MBQC is all about schmidt rank, not entanglement per se.
Joe Fitzsimons
CC BY-SA 2.5
2010-08-26T06:50:57.727Z
You're of course correct that if a computation remains within the manifold of pure product states, it is (efficiently) classically simulatable; but does that mean that entanglement makes quantum computers "faster" (admitting shorter computational trajectories), as opposed to just "hard to follow" (having 'obfuscated' computational trajectories)? My position is that if there is a quantum speed-up, then entanglement is the exhaust plume, not the rocket fuel.
Niel de Beaudrap
CC BY-SA 2.5
2010-08-27T15:47:49.533Z
Well, entanglement is funny, since it depends on the dimension of your local systems. I think the real power simply comes from the existence of superpositions, and hence complex amplitudes. Entanglement seems to be a consequence of this. There is a nice encoding which makes it possible to do universal quantum computation with purely real amplitudes, which I think goes some way towards characterizing this. Current algorithms are all exploiting some form of interference effect.
Joe Fitzsimons
CC BY-SA 2.5
2010-08-24T12:34:53.670Z
2010-08-24T13:37:38.287Z
2010-08-24T13:37:38.287Z
Niel de Beaudrap
<p>Well, the standard text used is <a href="http://rads.stackoverflow.com/amzn/click/0521635039">Quantum Computation and Quantum Information</a> 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).</p>

<p>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.</p>

<p>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).</p>

CC BY-SA 2.5
2010-08-31T19:02:06.533Z
2010-08-31T19:02:06.533Z
Joe Fitzsimons
<p>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).</p>

<p><a href="http://www.cs.uchicago.edu/~fortnow/papers/quantview.pdf">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.</a></p>

CC BY-SA 2.5
2010-08-24T14:33:36.937Z
2010-08-24T18:19:22.900Z
2010-08-24T18:19:22.900Z
Joshua Grochow
<p>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<sup>#P</sup> = P<sup>GapP</sup>. 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.</p>

<p>Let me now give a brief, <a href="http://arxiv.org/abs/cs/0304008" rel="nofollow">physics-free introduction</a> 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. </p>

<p>For a more in-depth introduction, please see the standard textbook <a href="http://rads.stackoverflow.com/amzn/click/0521635039" rel="nofollow">Nielsen and Chuang.</a> </p>

CC BY-SA 2.5
2010-08-24T12:15:47.110Z
As well as the models Martin mentioned, there are a few others: measurement-based, adiabatic and topological quantum computing.
Joe Fitzsimons
CC BY-SA 3.0
2010-08-24T11:31:03.110Z
2011-06-19T13:40:49.570Z
2011-06-19T13:40:49.570Z
Martin Schwarz
<p>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: <a href="http://arxiv.org/abs/quant-ph/9809016" rel="nofollow">http://arxiv.org/abs/quant-ph/9809016</a></p>

<p>Another article, much more summarized is the Pablo Arrighi's "Quantum Computation explained to my Mother" at <a href="http://arxiv.org/abs/quant-ph/0305045" rel="nofollow">http://arxiv.org/abs/quant-ph/0305045</a></p>

CC BY-SA 3.0
2013-01-18T15:26:53.033Z
Rieffel and Polak seem to have turned out a book as well: [Quantum Computing: A Gentle Introduction](http://mitpress.mit.edu/books/quantum-computing)
Logan Mayfield
CC BY-SA 2.5
2010-08-30T20:49:50.113Z
2010-09-01T07:56:09.090Z
2010-09-01T07:56:09.090Z
Alejandro DC
<p>First, you will need to understand quantum physics.</p>

<p>A few recommendations:</p>

<ol>
<li>"<a href="http://rads.stackoverflow.com/amzn/click/0521879965">Quantum Computing for Computer Scientists</a>" by Noson S. Yanofsky and Mirco A. Mannucci</li>
<li><a href="http://rads.stackoverflow.com/amzn/click/019857049X">"An Introduction to Quantum Computing"</a> by Phillip Kaye, Raymond Laflamme and Michele Mosca</li>
</ol>

<p>And on the more entertaining side of things, <a href="http://rads.stackoverflow.com/amzn/click/0375726187">"A Shortcut Through Time: The Path to the Quantum Computer"</a> by George Johnson.</p>

CC BY-SA 2.5
2010-08-31T17:39:40.847Z
2010-08-31T17:39:40.847Z
Shane
<p>In general, I'd second Joe's advice. But for a quick intro, I'd put <a href="http://www.sciencedirect.com/science/article/pii/S0304397501003772" rel="nofollow">Lance Fortnow</a>'s and <a href="http://arxiv.org/abs/cs/0304008" rel="nofollow">Stephen Fenner</a>'s texts on the reading list of computer scientists going quantum. </p>

CC BY-SA 3.0
2010-08-31T19:38:49.650Z
2011-06-19T13:48:33.333Z
2011-06-19T13:48:33.333Z
Martin Schwarz
<p>You're probably already aware of this, but on <a href="http://scottaaronson.com/blog/" rel="noreferrer">his blog</a>, 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).</p>

<p>If you'd like a book-length introduction, but something that's gentler than a text like Nielsen and Chuang, I would recommend <a href="http://rads.stackoverflow.com/amzn/click/0521879965" rel="noreferrer">Quantum Computing for Computer Scientists</a> 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.</p>

CC BY-SA 2.5
2010-08-25T15:14:58.510Z
2010-08-25T15:14:58.510Z
Kurt
<p>If you're fairly advanced, you might start with the <a href="http://xxx.lanl.gov/abs/0910.3376" rel="nofollow">de Wolf-Drucker survey</a> of quantum methods for classical problems. It's a good way to understand quantum <em>techniques</em> before you get to quantum <em>problems</em>. </p>

CC BY-SA 2.5
2010-08-31T17:26:21.153Z
2010-08-31T17:26:21.153Z
Suresh Venkat
<p>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.</p>

CC BY-SA 2.5
2010-09-01T14:38:40.487Z
2010-09-01T14:38:40.487Z
Alejandro DC
<p>Besides his standard text with Chuang, Michael Nielsen has a series of video lectures on Youtube called <a href="http://www.youtube.com/watch?v=X2q1PuI2RFI&amp;feature=BFa&amp;list=PL1826E60FD05B44E4&amp;index=1" rel="nofollow">Quantum Computing for the Determined</a> 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.</p>

CC BY-SA 3.0
2011-06-20T09:49:09.400Z
2011-06-20T09:49:09.400Z
Max
<p>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. </p>

CC BY-SA 2.5
2011-03-14T07:41:24.033Z
Mod note: merged [a closed exact duplicate question](http://cstheory.stackexchange.com/questions/805/learning-quantum-cs-closed) with this question and removed the comments from the duplicate which were not relevant anymore.
Kaveh
CC BY-SA 2.5
2010-08-24T13:37:03.543Z
Please correct the spelling in the question title.
Shane
CC BY-SA 2.5
2010-09-01T09:26:26.453Z
Some history and references are here http://en.wikipedia.org/wiki/Universal_quantum_simulator
Radu GRIGore
<quantum-computing><big-picture>
What is the quantum computational model?
Casebash
# What is the quantum computational model?

(Asked by: username_0 on 2010-08-24)

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.

**Tags:** quantum-computing, big-picture
> **Comments:**
> **username_2**: Please correct the spelling in the question title.  
> **username_3**: Some history and references are here http://en.wikipedia.org/wiki/Universal_quantum_simulator  
> **username_1**: Mod note: merged [a closed exact duplicate question](http://cstheory.stackexchange.com/questions/805/learning-quantum-cs-closed) with this question and removed the comments from the duplicate which were not relevant anymore.  

---

## 11 answers

### Answer by username_4 on 2010-08-24. Score: 24

I'll echo Martin Schwartz's recommendation of [Nielsen & Chaung](http://rads.stackoverflow.com/amzn/click/0521635039) 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 ℓ1 norm. Probabilistic computations must map ℓ1-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 ℓ2-unit vectors over ℂ (not restricted to be real or non-negative); transformations are by those maps which preserve the ℓ2-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 ℝ+2 (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 ℝ+2 ⊗ ℝ+2 ≅ ℝ+4 , 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*2 . 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 ℓ2-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 ℓ2 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 ℓ2-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 ℝ+2n 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 ℓ2-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](http://uk.arxiv.org/abs/quant-ph/0412140) for Shor's algorithm to factor large integers, and that indeed a quantum system can have [too much entanglement to be useful](http://www.physorg.com/news162468404.html) 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.

> **Comments:**
> **username_6**: I must admit, I disagree with you on the entanglement question. Operations on pure product states are efficiently simulable. The "too entangled to compute" paper is a bit misleading. This paper is really about resources for measurement based computation, and MBQC is all about schmidt rank, not entanglement per se.  
> **username_4**: You're of course correct that if a computation remains within the manifold of pure product states, it is (efficiently) classically simulatable; but does that mean that entanglement makes quantum computers "faster" (admitting shorter computational trajectories), as opposed to just "hard to follow" (having 'obfuscated' computational trajectories)? My position is that if there is a quantum speed-up, then entanglement is the exhaust plume, not the rocket fuel.  
> **username_6**: Well, entanglement is funny, since it depends on the dimension of your local systems. I think the real power simply comes from the existence of superpositions, and hence complex amplitudes. Entanglement seems to be a consequence of this. There is a nice encoding which makes it possible to do universal quantum computation with purely real amplitudes, which I think goes some way towards characterizing this. Current algorithms are all exploiting some form of interference effect.  
> **username_5**: I partially agree with Joe on the interference point,  yet an issue to speak rigorously about this point is _what (reasonably tested) measures of interference are there in the market_? Do you people know of works in this direction? The only example that comes to my mind is [this one](http://arxiv.org/abs/quant-ph/0510159) (yet I have not read it in much detail).  
> **username_4**: @JuanBermejoVega: interference seems to just be a corollary of the fact that there are information-preserving transformations which don't preserve standard basis states. The only apparent alternative to interference is information loss, as in classical probability. Then what we have is simply reversible transformations which do not preserve the standard basis; the narrative of interference, as productive as it is when talking about propagation in space, is just a way of describing what this looks like if you continue to try to parse this non-preservation in terms of the standard basis.  

---

### Answer by username_6 on 2010-08-31. Score: 12

Well, the standard text used is [Quantum Computation and Quantum Information](http://rads.stackoverflow.com/amzn/click/0521635039) 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 by username_7 on 2010-08-24. Score: 12

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.](http://www.cs.uchicago.edu/~fortnow/papers/quantview.pdf)


---

### Answer by username_8 on 2010-08-24. Score: 8

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 = PGapP. 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](http://arxiv.org/abs/cs/0304008) 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.](http://rads.stackoverflow.com/amzn/click/0521635039)

> **Comments:**
> **username_6**: As well as the models Martin mentioned, there are a few others: measurement-based, adiabatic and topological quantum computing.  

---

### Answer by username_9 on 2010-08-30. Score: 5

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>

> **Comments:**
> **username_10**: Rieffel and Polak seem to have turned out a book as well: [Quantum Computing: A Gentle Introduction](http://mitpress.mit.edu/books/quantum-computing)  

---

### Answer by username_2 on 2010-08-31. Score: 5

First, you will need to understand quantum physics.

A few recommendations:

1. "[Quantum Computing for Computer Scientists](http://rads.stackoverflow.com/amzn/click/0521879965)" by Noson S. Yanofsky and Mirco A. Mannucci
2. ["An Introduction to Quantum Computing"](http://rads.stackoverflow.com/amzn/click/019857049X) 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"](http://rads.stackoverflow.com/amzn/click/0375726187) by George Johnson.


---

### Answer by username_11 on 2010-08-25. Score: 5

You're probably already aware of this, but on [his blog](http://scottaaronson.com/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](http://rads.stackoverflow.com/amzn/click/0521879965) 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 by username_8 on 2010-08-31. Score: 4

In general, I'd second Joe's advice. But for a quick intro, I'd put [Lance Fortnow](http://www.sciencedirect.com/science/article/pii/S0304397501003772)'s and [Stephen Fenner](http://arxiv.org/abs/cs/0304008)'s texts on the reading list of computer scientists going quantum.


---

### Answer by username_12 on 2010-08-31. Score: 3

If you're fairly advanced, you might start with the [de Wolf-Drucker survey](http://xxx.lanl.gov/abs/0910.3376) of quantum methods for classical problems. It's a good way to understand quantum *techniques* before you get to quantum *problems*.


---

### Answer by username_9 on 2010-09-01. Score: 2

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 by username_13 on 2011-06-20. Score: 2

Besides his standard text with Chuang, Michael Nielsen has a series of video lectures on Youtube called [Quantum Computing for the Determined](http://www.youtube.com/watch?v=X2q1PuI2RFI&feature=BFa&list=PL1826E60FD05B44E4&index=1) 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.


---

