5 ms·

An Introduction to Quantum Computing, Without the Physics

149 points by lainon 9y ago

CacheThrasher 9y ago
Thanks for this, I have been looking for a good introduction to Quantum Computing. I haven't actually read it yet, but this looks promising.
- indigo0086 9y ago
  I've been meaning to get into it but someone recommended me this series on youtube https://www.youtube.com/watch?v=X2q1PuI2RFI&list=PL1826E60FD05B44E4 https://www.youtube.com/watch?v=X2q1PuI2RFI&list=PL1826E60FD...
  - tmccrmck 9y ago
    Quantum Computation and Quantum Information by Nielsen and Chuang is the standard introduction to quantum computing. Besides that, you can find some old CS191 Vazirani lectures on the internet.
- virgil_disgr4ce 9y ago
  Consider also "Quantum Computing Explained" by McMahon.
- Analemma_ 9y ago
  I've recommended this here before, but David Mermin's "Quantum Computer Science: An Introduction" is also good (like this paper, it's targeted at computer scientists who have a little math knowledge and little-to-no physics background). There's a dead-tree version, but the lecture notes the book is based on are available online: http://www.lassp.cornell.edu/mermin/qcomp/CS483.html http://www.lassp.cornell.edu/mermin/qcomp/CS483.html
- nicholast 9y ago
  Here is a medium post targeted at layperson that covers a lot of same material. "Quibbling Over Qubits" https://medium.com/@_NicT_/quibbling-over-qubits-f2ca1b87f470 https://medium.com/@_NicT_/quibbling-over-qubits-f2ca1b87f47...
- alistproducer2 9y ago
  This is the best explanation I've found: https://arstechnica.com/science/2010/01/a-tale-of-two-qubits-how-quantum-computers-work/ https://arstechnica.com/science/2010/01/a-tale-of-two-qubits...
- drdre2001 9y ago
  r/QuantumComputing[1] is a great place if you want to learn more. We read and discuss one Quantum Computing paper a week. [1]https://www.reddit.com/r/QuantumComputing/ https://www.reddit.com/r/QuantumComputing/
Strilanc 9y ago
After quickly skimming it it seems well done. Leans towards mathematical rigor, which may not be ideal for some people. On the other hand, it'd be pretty hard to avoid math: quantum computing is linear algebra incarnate. The only thing that caught my eye as off was totally minor. They say the many-controlled-Z gate used by Grover's algorithm can be done in O(n^2) constant-sized gates with an argument-by-reference, but with that type of argument you might as well give the tight bound of Θ(n).
- msla 9y ago
  It's possible to have a gentle ramp-up on the math content while learning quantum mechanics. "The Theoretical Minimum" by Susskind and Hrabovsky is structured like that: They teach you the math as part of, and motivated by, teaching the physics, and the books don't lag or resort to hand-waving. https://en.wikipedia.org/wiki/The_Theoretical_Minimum https://en.wikipedia.org/wiki/The_Theoretical_Minimum
  - tmccrmck 9y ago
    Note: Susskind has a follow up - Quantum Mechanics: The Theoretical Minimum. https://www.goodreads.com/book/show/18210750-quantum-mechanics https://www.goodreads.com/book/show/18210750-quantum-mechani...
    - msla 9y ago
      I should have been clearer that I was referring to both books in the series with my remarks.
epx 9y ago
Hope I am retired before it's mainstream :)
s-macke 9y ago
Consider these two simulators, if you want to try the examples in the paper: 1. https://www.research.ibm.com/ibm-q/ https://www.research.ibm.com/ibm-q/ This is IBM Quantum experience. Click on "experiment" to start. It has a nice tutorial. 2. http://algassert.com/quirk http://algassert.com/quirk I like this one much better, because you can see the internal state of the machine at any moment. And it has much more options and is much faster.
Koshkin 9y ago
> Without the Physics Well, is there much "physics" in (theoretical) quantum physics anyway? It's pretty much all math - just like in this paper!
- pvg 9y ago
  Maths doesn't have to agree with physical experiments and observation.
daxfohl 9y ago
The article on QC I got the most out of: http://www.scottaaronson.com/blog/?p=208 http://www.scottaaronson.com/blog/?p=208 Very visual example of how Shor's algorithm works to solve factoring. Nothing more than basic arithmetic required. The big takeaway for me was, it's not just "try every combination at once" as per pop lit on the subject. QC doesn't really do that. To get QC to work any better that traditional for any task, you need to get lucky and stumble across an algorithm that QC can excel at for that task. Just from reading Scott Aaronson's article, it seems likely that most tasks simply don't have a QC optimization, so perhaps QC won't change much at all. (Well, except cryptography, which may change everything...)
- chadcmulligan 9y ago
  Yes, this was a bit of a surprise for me to - "In fact, in general solving NP-hard problems in polynomial time with quantum computers is not believed to be possible"

149 points by lainon 9y ago

Thanks for this, I have been looking for a good introduction to Quantum Computing. I haven't actually read it yet, but this looks promising.

indigo0086 9y ago
I've been meaning to get into it but someone recommended me this series on youtube https://www.youtube.com/watch?v=X2q1PuI2RFI&list=PL1826E60FD05B44E4 https://www.youtube.com/watch?v=X2q1PuI2RFI&list=PL1826E60FD...
- tmccrmck 9y ago
  Quantum Computation and Quantum Information by Nielsen and Chuang is the standard introduction to quantum computing. Besides that, you can find some old CS191 Vazirani lectures on the internet.
virgil_disgr4ce 9y ago
Consider also "Quantum Computing Explained" by McMahon.
Analemma_ 9y ago
I've recommended this here before, but David Mermin's "Quantum Computer Science: An Introduction" is also good (like this paper, it's targeted at computer scientists who have a little math knowledge and little-to-no physics background). There's a dead-tree version, but the lecture notes the book is based on are available online: http://www.lassp.cornell.edu/mermin/qcomp/CS483.html http://www.lassp.cornell.edu/mermin/qcomp/CS483.html
nicholast 9y ago
Here is a medium post targeted at layperson that covers a lot of same material. "Quibbling Over Qubits" https://medium.com/@_NicT_/quibbling-over-qubits-f2ca1b87f470 https://medium.com/@_NicT_/quibbling-over-qubits-f2ca1b87f47...
alistproducer2 9y ago
This is the best explanation I've found: https://arstechnica.com/science/2010/01/a-tale-of-two-qubits-how-quantum-computers-work/ https://arstechnica.com/science/2010/01/a-tale-of-two-qubits...
drdre2001 9y ago
r/QuantumComputing[1] is a great place if you want to learn more. We read and discuss one Quantum Computing paper a week. [1]https://www.reddit.com/r/QuantumComputing/ https://www.reddit.com/r/QuantumComputing/

Strilanc 9y ago

After quickly skimming it it seems well done. Leans towards mathematical rigor, which may not be ideal for some people. On the other hand, it'd be pretty hard to avoid math: quantum computing is linear algebra incarnate. The only thing that caught my eye as off was totally minor. They say the many-controlled-Z gate used by Grover's algorithm can be done in O(n^2) constant-sized gates with an argument-by-reference, but with that type of argument you might as well give the tight bound of Θ(n).

msla 9y ago
It's possible to have a gentle ramp-up on the math content while learning quantum mechanics. "The Theoretical Minimum" by Susskind and Hrabovsky is structured like that: They teach you the math as part of, and motivated by, teaching the physics, and the books don't lag or resort to hand-waving. https://en.wikipedia.org/wiki/The_Theoretical_Minimum https://en.wikipedia.org/wiki/The_Theoretical_Minimum
- tmccrmck 9y ago
  Note: Susskind has a follow up - Quantum Mechanics: The Theoretical Minimum. https://www.goodreads.com/book/show/18210750-quantum-mechanics https://www.goodreads.com/book/show/18210750-quantum-mechani...
  - msla 9y ago
    I should have been clearer that I was referring to both books in the series with my remarks.

epx 9y ago

Hope I am retired before it's mainstream :)

s-macke 9y ago

Consider these two simulators, if you want to try the examples in the paper: 1. https://www.research.ibm.com/ibm-q/ https://www.research.ibm.com/ibm-q/ This is IBM Quantum experience. Click on "experiment" to start. It has a nice tutorial. 2. http://algassert.com/quirk http://algassert.com/quirk I like this one much better, because you can see the internal state of the machine at any moment. And it has much more options and is much faster.

Koshkin 9y ago

> Without the Physics Well, is there much "physics" in (theoretical) quantum physics anyway? It's pretty much all math - just like in this paper!

pvg 9y ago
Maths doesn't have to agree with physical experiments and observation.

daxfohl 9y ago

The article on QC I got the most out of: http://www.scottaaronson.com/blog/?p=208 http://www.scottaaronson.com/blog/?p=208 Very visual example of how Shor's algorithm works to solve factoring. Nothing more than basic arithmetic required. The big takeaway for me was, it's not just "try every combination at once" as per pop lit on the subject. QC doesn't really do that. To get QC to work any better that traditional for any task, you need to get lucky and stumble across an algorithm that QC can excel at for that task. Just from reading Scott Aaronson's article, it seems likely that most tasks simply don't have a QC optimization, so perhaps QC won't change much at all. (Well, except cryptography, which may change everything...)

chadcmulligan 9y ago
Yes, this was a bit of a surprise for me to - "In fact, in general solving NP-hard problems in polynomial time with quantum computers is not believed to be possible"