4 ms·

It’s Time to Learn about Quantum Computing

33 points by f3f3_ 8y ago

GChevalier 8y ago
So many ads and things that prompt for attention on this page! I needed to press "x" on 3 things to be able to read. And once read to the end, it refers to a "video above" that won't open under Chrome for mobile. Wired, calm down on crap!
- stephengillie 8y ago
  You're not missing much in this 304-word blurb. Outside of name-dropping, there's an introductory snippet that guides you to a video. > So how do they work? You may have heard that the normal rules of reality don’t always apply in the world of quantum mechanics. A phenomenon known as a quantum superposition allows things to kinda, sorta, be in two places at once, for example. In a quantum computer, that means bits of data can be more than just 1 or 0, as they are in a conventional computer; they can also be something like both at the same time. When data is encoded into effects like those, some normal limitations on conventional computers fall away. That allows a quantum computer to be much faster on certain tricky problems. Want a full PhD, or third-grade, explanation? Watch the video above.
graycat 8y ago
One of the collections of current practical problems frequently and continually mentioned as big reasons for developing quantum computers is combinatorial optimization. Right, these problems are commonly in the class NP, and that means that so far, as problem size grows, the guaranteed sufficiently large time and or space on a current, classic digital computer to get optimal solutions of worst case problems grows like an exponential in the problem size. But practical problems don't need to be so large; approximately optimal solutions might save 90% of the money of optimal solutions and very valuable; real problems commonly are not much like the worst case problems; and we long had lots of methods for combinatorial optimization that do quite well in practice. Point: If practical problems in combinatorial optimization are of interest, then bring them forward -- they've been coming forward mostly only rarely. Else, let's find other reasons for pressing forward with quantum computers.
- lomnakkus 8y ago
  Per Wikipedia isn't not actually known whether quantum computers will be able to solve NP-complete problems in polynomial time: > There is a common misconception that quantum computers can solve NP-complete problems in polynomial time. That is not known to be true, and is generally suspected to be false.[120] The citation is from 1997, but I seem to remember that someone came up with a proof sometime in the last decade...? Probably just my faulty memory rather than the Wikipedia being out of date.
  - graycat 8y ago
    Too much detail for me!!! I'll assume that the cubits will be able to do total enumeration right away! Now, while we are waiting on that, if there are some problems in combinatorial optimization to solve, trot them out and we will see. Maybe for some of the problems, current techniques can make big bucks.
  - abdullahkhalids 8y ago
    There is no known proof of separation between BQP and NP. See https://en.wikipedia.org/wiki/BQP https://en.wikipedia.org/wiki/BQP for the relation of BQP to other complexity classes.
    - lomnakkus 8y ago
      Ah, thanks. (I was actually looking at the BQP page,, but then realized that I know far less about the Q classes than I should and found the more general "quantum computing" page where my citation is from.)
- repsilat 8y ago
  > these problems are commonly in the class NP "Is the input empty" is in the class NP. You mean these problems are NP-complete. (This means "In NP, and all other problems in NP can be reduced to them in polynomial time.") > If practical problems in combinatorial optimization are of interest, then bring them forward -- they've been coming forward mostly only rarely. This is total nonsense. Training a neural network is combinatorial optimisation, proving mathematical theorems is NP-complete (when max proof-length is specified in unary), and there are loads of integer programs running all over the place that we'd love to solve significantly faster. Sure, maybe you don't always need to get to optimality, but every bit helps, and often approximate methods just aren't good enough. (As the sibling comment points out, though, none of this is really germane to a discussion of quantum computers.)
ivan_ah 8y ago
Here is a shameless plug to my book on linear algebra that comes with an introduction to quantum mechanics (Chapter 9): https://www.amazon.com/dp/0992001021/noBSLA https://www.amazon.com/dp/0992001021/noBSLA If you know you linear algebra well, learning quantum mechanics is not so complicated, see the book preview here: https://minireference.com/static/excerpts/noBSguide2LA_preview.pdf#page=125 https://minireference.com/static/excerpts/noBSguide2LA_previ...

33 points by f3f3_ 8y ago

So many ads and things that prompt for attention on this page! I needed to press "x" on 3 things to be able to read. And once read to the end, it refers to a "video above" that won't open under Chrome for mobile. Wired, calm down on crap!

stephengillie 8y ago
You're not missing much in this 304-word blurb. Outside of name-dropping, there's an introductory snippet that guides you to a video. > So how do they work? You may have heard that the normal rules of reality don’t always apply in the world of quantum mechanics. A phenomenon known as a quantum superposition allows things to kinda, sorta, be in two places at once, for example. In a quantum computer, that means bits of data can be more than just 1 or 0, as they are in a conventional computer; they can also be something like both at the same time. When data is encoded into effects like those, some normal limitations on conventional computers fall away. That allows a quantum computer to be much faster on certain tricky problems. Want a full PhD, or third-grade, explanation? Watch the video above.

graycat 8y ago

One of the collections of current practical problems frequently and continually mentioned as big reasons for developing quantum computers is combinatorial optimization. Right, these problems are commonly in the class NP, and that means that so far, as problem size grows, the guaranteed sufficiently large time and or space on a current, classic digital computer to get optimal solutions of worst case problems grows like an exponential in the problem size. But practical problems don't need to be so large; approximately optimal solutions might save 90% of the money of optimal solutions and very valuable; real problems commonly are not much like the worst case problems; and we long had lots of methods for combinatorial optimization that do quite well in practice. Point: If practical problems in combinatorial optimization are of interest, then bring them forward -- they've been coming forward mostly only rarely. Else, let's find other reasons for pressing forward with quantum computers.

lomnakkus 8y ago
Per Wikipedia isn't not actually known whether quantum computers will be able to solve NP-complete problems in polynomial time: > There is a common misconception that quantum computers can solve NP-complete problems in polynomial time. That is not known to be true, and is generally suspected to be false.[120] The citation is from 1997, but I seem to remember that someone came up with a proof sometime in the last decade...? Probably just my faulty memory rather than the Wikipedia being out of date.
- graycat 8y ago
  Too much detail for me!!! I'll assume that the cubits will be able to do total enumeration right away! Now, while we are waiting on that, if there are some problems in combinatorial optimization to solve, trot them out and we will see. Maybe for some of the problems, current techniques can make big bucks.
- abdullahkhalids 8y ago
  There is no known proof of separation between BQP and NP. See https://en.wikipedia.org/wiki/BQP https://en.wikipedia.org/wiki/BQP for the relation of BQP to other complexity classes.
  - lomnakkus 8y ago
    Ah, thanks. (I was actually looking at the BQP page,, but then realized that I know far less about the Q classes than I should and found the more general "quantum computing" page where my citation is from.)
repsilat 8y ago
> these problems are commonly in the class NP "Is the input empty" is in the class NP. You mean these problems are NP-complete. (This means "In NP, and all other problems in NP can be reduced to them in polynomial time.") > If practical problems in combinatorial optimization are of interest, then bring them forward -- they've been coming forward mostly only rarely. This is total nonsense. Training a neural network is combinatorial optimisation, proving mathematical theorems is NP-complete (when max proof-length is specified in unary), and there are loads of integer programs running all over the place that we'd love to solve significantly faster. Sure, maybe you don't always need to get to optimality, but every bit helps, and often approximate methods just aren't good enough. (As the sibling comment points out, though, none of this is really germane to a discussion of quantum computers.)

ivan_ah 8y ago

Here is a shameless plug to my book on linear algebra that comes with an introduction to quantum mechanics (Chapter 9): https://www.amazon.com/dp/0992001021/noBSLA https://www.amazon.com/dp/0992001021/noBSLA If you know you linear algebra well, learning quantum mechanics is not so complicated, see the book preview here: https://minireference.com/static/excerpts/noBSguide2LA_preview.pdf#page=125 https://minireference.com/static/excerpts/noBSguide2LA_previ...