7 ms·

Microsoft’s Quantum Mechanics

131 points by finisterre 12y ago

Zaheer 12y ago
They forgot the NSA under the Quantum Projects section. http://www.wired.com/2014/03/quantum-crypto-google/ http://www.wired.com/2014/03/quantum-crypto-google/
- thinkling 12y ago
  Only the lab in Silicon Valley was closed down. The main lab is in Redmond, and there are still labs in a variety of other locations: http://research.microsoft.com/en-us/labs/default.aspx http://research.microsoft.com/en-us/labs/default.aspx
peter303 12y ago
Windows will only take 2 minutes to boot on a quantum computer then.
- deleted 12y ago
  [deleted]
- _broody 12y ago
  When was the last time you used a Windows PC? Windows 8 boots and shows you the login screen in under 10 seconds.
- _random_ 12y ago
  Why would you even do it? My Windows (same kernel) phone runs for months without reboots.
- orbifold 12y ago
  Compared to Linux it boots much faster and is about as stable, too.
tatqx 12y ago
Does anyone know or can explain simplistically why if we can get supercomputer like power from 100 qubits then why not a desktop computer like power with 1 or 2 qubits? I assume that the computational capacity increases exponentially with the number of qubits, but how?
- marcosdumay 12y ago
  Well, we don't really know if it's exactly exponential, we also don't really know that a quantum computer is more powerfull than a classical one (and we don't know if P == NP, what's related). That said, yes, the observed speedup on some [1] problems is exponential. It's easy to wave hands and say that when you place the qbits in a coherent state together, the operations you do on them apply to all of the values you they can possibly carry, and those grow exponentialy with the number of bits. But the long explanation makes things much more clear, and is worth reading if you want to really get it. Wikipedia is a good starting point [2][3]. [1] Not all by a wide margin. Quantum computers will be specialized machines for a long time, if not forever. But cryptography will take a huge hit. [2] http://en.wikipedia.org/wiki/Quantum_computer http://en.wikipedia.org/wiki/Quantum_computer [3] http://en.wikipedia.org/wiki/Shor%27s_algorithm http://en.wikipedia.org/wiki/Shor%27s_algorithm
- Strilanc 12y ago
  With 1 or 2 qubits you wouldn't even be able to compute 2 + 2 because storing 4 in binary requires 3 bits. 100 qubits is also not particularly useful, not because they aren't fast but because most of the interesting stuff simply doesn't fit. RSA keys are thousands of bits long, for example. You need enough qubits to store the problem, and the working state of the algorithm you're using, and the overhead introduced by error correcting codes, and the overhead from your gates not being ideal, and so on. Austin Fowler gave a talk a few months ago where he goes through the overheads in a particular problem (finding molecular ground state energies) and ends up optimistically requiring tens of millions of qubits [1]. 1: https://www.youtube.com/watch?v=XbFoXT73xVQ&feature=youtu.be&t=52m20s https://www.youtube.com/watch?v=XbFoXT73xVQ&feature=youtu.be...
- gjm11 12y ago
  A quantum computer isn't really much like a super-powered classical computer. There are certain specific things it's amazingly good at (most notably, factorizing large integers), some other things it's quite good at (e.g., some kinds of search operation), and lots of things for which no one knows how to make quantum computers any faster than classical ones. So, if you have a quantum computer, you're probably going to want to use it for breaking RSA or similar cryptography by factorizing large numbers. There are (ordinary, non-quantum) algorithms for factorizing large-ish numbers. They work pretty well for numbers of modest size. But they don't scale well as the numbers get very large. Something like exp(log(n)^1/3 log(log(n))^2/3) to factorize a number near to n. Or, in terms of the number of bits, something like exp(b^1/3 log(b)^2/3). So this works fine for numbers up to, let's say, 200 bits on a single machine or 1000 bits for a team with a substantial network. (Note: all numbers here are kinda made up but of the right order of magnitude.) With a quantum computer, you can factorize a b-bit number with something like 2b qubits, b^3 quantum gates, and a runtime that scales more manageably with b. So there's not much point in using a quantum computer until the number of qubits it has gets large enough to use for factorizing numbers bigger than you can do on your PC. Which means somewhere on the order of 100 qubits. As the number goes up, the advantage of the quantum computer over the classical computer increases. The transition from "slower than your PC" to "faster than any classical computer that will ever be built" takes place over a fairly small range of qubit-count. Down with much smaller numbers of qubits, though, the quantum computer can maybe manage to find the factors of, say, 15. Which is, shall we say, quite a lot less than the computer on your desktop can do.
Arjuna 12y ago
Can anyone expound further on the practical applications of quantum computing? In my limited understanding, I think the following are definitely candidates (presented in no particular order), but I'm sure there are others: 1. Shor's algorithm could expose all encryption algorithms that are based on integer factorization. 2. Quantum simulation could open new avenues of research into how our universe operates at the quantum level. This could lead to advancements in materials science, for example. 3. Quantum computing could open new avenues of research into the P versus NP problem. 4. Quantum computing could open the door to the possibility of instantaneous communication via an understanding of action at a distance / quantum entanglement. Edit: Thanks for all of the great responses, clarifications and links to further reading.
- powrtoch 12y ago
  #4 shouldn't be possible according to the No-Communication Theorem. http://en.wikipedia.org/wiki/No-communication_theorem http://en.wikipedia.org/wiki/No-communication_theorem
- TTPrograms 12y ago
  Quantum Machine Learning would be drastically sped up, as many linear operations could be done in log(N): http://arxiv.org/abs/1307.0411 http://arxiv.org/abs/1307.0411 A quantum machine learning computer could make scientific advances simply by processing large datasets at rate dramatically faster than humans and/or current machine learning systems.
  - mathgenius 12y ago
    This one is good too: "Quantum algorithms for topological and geometric analysis of big data" http://arxiv.org/abs/1408.3106 http://arxiv.org/abs/1408.3106 It uses some of this "applied topology", which I only recently found out about. http://www.math.upenn.edu/~ghrist/notes.html http://www.math.upenn.edu/~ghrist/notes.html
- Strilanc 12y ago
  One neat trick is "storing bandwidth". http://strilanc.com/quantum/2014/05/03/Storing-Bandwidth-with-Superdense-Coding.html http://strilanc.com/quantum/2014/05/03/Storing-Bandwidth-wit...
DubiousPusher 12y ago
Some good news, the Majorana fermion has recently been independently observed. http://www.sciencedaily.com/releases/2014/10/141002141757.htm http://www.sciencedaily.com/releases/2014/10/141002141757.ht...
- duaneb 12y ago
  How certain are the findings? It's so hard to tell with particle physics.
  - drostie 12y ago
    The Majorana discoveries are condensed matter physics, not particle physics. In particular, when they say that they've discovered "a new particle" it's important to understand that this is not going to appear on the Standard Model of Particle Physics at any time soon (unless, say, neutrinos, which are already on that model, turn out to be Majoranas). We've discovered excitations at the end of nanowires which appear to behave like Majoranas were supposed to, and we've worked out some theory which predicts that they were supposed to be there, and if they are there then they're "topologically" protected from a lot of the usual sources of noise, so we might be able to make long-lived qubits for a change. That's about what we know about Majorana fermions, minus some details.
ianstallings 12y ago
I think I have some facts twisted up. I thought Microsoft closed it's R&D lab? http://www.zdnet.com/microsoft-to-close-microsoft-research-lab-in-silicon-valley-7000033838/ http://www.zdnet.com/microsoft-to-close-microsoft-research-l... Do they have others?
- tkmcc 12y ago
  Yes, there are MSR campuses around the world! Only the Silicon Valley satellite campus was closed. See http://research.microsoft.com/en-us/labs/ http://research.microsoft.com/en-us/labs/ for the full list.
- RealCasually 12y ago
  Yes, they only closed the Mountain View lab.
deleted 12y ago
[deleted]
mathgenius 12y ago
FTA: "Freedman was 30 when he solved a version of one of the longest-standing problems in mathematics, the Poincaré conjecture." Not true, he apparently made contributions to the poincare conjecture in dimension 4. Also, the article has a link from "poincare conjecture" to a clay institute webpage which is broken. Meh
- tzs 12y ago
  This is what it says about him on the official list of Fields medalists: "Developed new methods for topological analysis of four-manifolds. One of his results is a proof of the four-dimensional Poincaré Conjecture". The article's statement you quoted is accurate enough to not be "not true".
  - mathgenius 12y ago
    Ok, thanks for that. I think I'm done with wikipedia.

131 points by finisterre 12y ago

They forgot the NSA under the Quantum Projects section. http://www.wired.com/2014/03/quantum-crypto-google/ http://www.wired.com/2014/03/quantum-crypto-google/

thinkling 12y ago
Only the lab in Silicon Valley was closed down. The main lab is in Redmond, and there are still labs in a variety of other locations: http://research.microsoft.com/en-us/labs/default.aspx http://research.microsoft.com/en-us/labs/default.aspx

peter303 12y ago

Windows will only take 2 minutes to boot on a quantum computer then.

deleted 12y ago
[deleted]
_broody 12y ago
When was the last time you used a Windows PC? Windows 8 boots and shows you the login screen in under 10 seconds.
_random_ 12y ago
Why would you even do it? My Windows (same kernel) phone runs for months without reboots.
orbifold 12y ago
Compared to Linux it boots much faster and is about as stable, too.

tatqx 12y ago

Does anyone know or can explain simplistically why if we can get supercomputer like power from 100 qubits then why not a desktop computer like power with 1 or 2 qubits? I assume that the computational capacity increases exponentially with the number of qubits, but how?

marcosdumay 12y ago
Well, we don't really know if it's exactly exponential, we also don't really know that a quantum computer is more powerfull than a classical one (and we don't know if P == NP, what's related). That said, yes, the observed speedup on some [1] problems is exponential. It's easy to wave hands and say that when you place the qbits in a coherent state together, the operations you do on them apply to all of the values you they can possibly carry, and those grow exponentialy with the number of bits. But the long explanation makes things much more clear, and is worth reading if you want to really get it. Wikipedia is a good starting point [2][3]. [1] Not all by a wide margin. Quantum computers will be specialized machines for a long time, if not forever. But cryptography will take a huge hit. [2] http://en.wikipedia.org/wiki/Quantum_computer http://en.wikipedia.org/wiki/Quantum_computer [3] http://en.wikipedia.org/wiki/Shor%27s_algorithm http://en.wikipedia.org/wiki/Shor%27s_algorithm
Strilanc 12y ago
With 1 or 2 qubits you wouldn't even be able to compute 2 + 2 because storing 4 in binary requires 3 bits. 100 qubits is also not particularly useful, not because they aren't fast but because most of the interesting stuff simply doesn't fit. RSA keys are thousands of bits long, for example. You need enough qubits to store the problem, and the working state of the algorithm you're using, and the overhead introduced by error correcting codes, and the overhead from your gates not being ideal, and so on. Austin Fowler gave a talk a few months ago where he goes through the overheads in a particular problem (finding molecular ground state energies) and ends up optimistically requiring tens of millions of qubits [1]. 1: https://www.youtube.com/watch?v=XbFoXT73xVQ&feature=youtu.be&t=52m20s https://www.youtube.com/watch?v=XbFoXT73xVQ&feature=youtu.be...
gjm11 12y ago
A quantum computer isn't really much like a super-powered classical computer. There are certain specific things it's amazingly good at (most notably, factorizing large integers), some other things it's quite good at (e.g., some kinds of search operation), and lots of things for which no one knows how to make quantum computers any faster than classical ones. So, if you have a quantum computer, you're probably going to want to use it for breaking RSA or similar cryptography by factorizing large numbers. There are (ordinary, non-quantum) algorithms for factorizing large-ish numbers. They work pretty well for numbers of modest size. But they don't scale well as the numbers get very large. Something like exp(log(n)^1/3 log(log(n))^2/3) to factorize a number near to n. Or, in terms of the number of bits, something like exp(b^1/3 log(b)^2/3). So this works fine for numbers up to, let's say, 200 bits on a single machine or 1000 bits for a team with a substantial network. (Note: all numbers here are kinda made up but of the right order of magnitude.) With a quantum computer, you can factorize a b-bit number with something like 2b qubits, b^3 quantum gates, and a runtime that scales more manageably with b. So there's not much point in using a quantum computer until the number of qubits it has gets large enough to use for factorizing numbers bigger than you can do on your PC. Which means somewhere on the order of 100 qubits. As the number goes up, the advantage of the quantum computer over the classical computer increases. The transition from "slower than your PC" to "faster than any classical computer that will ever be built" takes place over a fairly small range of qubit-count. Down with much smaller numbers of qubits, though, the quantum computer can maybe manage to find the factors of, say, 15. Which is, shall we say, quite a lot less than the computer on your desktop can do.

Arjuna 12y ago

Can anyone expound further on the practical applications of quantum computing? In my limited understanding, I think the following are definitely candidates (presented in no particular order), but I'm sure there are others: 1. Shor's algorithm could expose all encryption algorithms that are based on integer factorization. 2. Quantum simulation could open new avenues of research into how our universe operates at the quantum level. This could lead to advancements in materials science, for example. 3. Quantum computing could open new avenues of research into the P versus NP problem. 4. Quantum computing could open the door to the possibility of instantaneous communication via an understanding of action at a distance / quantum entanglement. Edit: Thanks for all of the great responses, clarifications and links to further reading.

powrtoch 12y ago
#4 shouldn't be possible according to the No-Communication Theorem. http://en.wikipedia.org/wiki/No-communication_theorem http://en.wikipedia.org/wiki/No-communication_theorem
TTPrograms 12y ago
Quantum Machine Learning would be drastically sped up, as many linear operations could be done in log(N): http://arxiv.org/abs/1307.0411 http://arxiv.org/abs/1307.0411 A quantum machine learning computer could make scientific advances simply by processing large datasets at rate dramatically faster than humans and/or current machine learning systems.
- mathgenius 12y ago
  This one is good too: "Quantum algorithms for topological and geometric analysis of big data" http://arxiv.org/abs/1408.3106 http://arxiv.org/abs/1408.3106 It uses some of this "applied topology", which I only recently found out about. http://www.math.upenn.edu/~ghrist/notes.html http://www.math.upenn.edu/~ghrist/notes.html
Strilanc 12y ago
One neat trick is "storing bandwidth". http://strilanc.com/quantum/2014/05/03/Storing-Bandwidth-with-Superdense-Coding.html http://strilanc.com/quantum/2014/05/03/Storing-Bandwidth-wit...

DubiousPusher 12y ago

Some good news, the Majorana fermion has recently been independently observed. http://www.sciencedaily.com/releases/2014/10/141002141757.htm http://www.sciencedaily.com/releases/2014/10/141002141757.ht...

duaneb 12y ago
How certain are the findings? It's so hard to tell with particle physics.
- drostie 12y ago
  The Majorana discoveries are condensed matter physics, not particle physics. In particular, when they say that they've discovered "a new particle" it's important to understand that this is not going to appear on the Standard Model of Particle Physics at any time soon (unless, say, neutrinos, which are already on that model, turn out to be Majoranas). We've discovered excitations at the end of nanowires which appear to behave like Majoranas were supposed to, and we've worked out some theory which predicts that they were supposed to be there, and if they are there then they're "topologically" protected from a lot of the usual sources of noise, so we might be able to make long-lived qubits for a change. That's about what we know about Majorana fermions, minus some details.

ianstallings 12y ago

I think I have some facts twisted up. I thought Microsoft closed it's R&D lab? http://www.zdnet.com/microsoft-to-close-microsoft-research-lab-in-silicon-valley-7000033838/ http://www.zdnet.com/microsoft-to-close-microsoft-research-l... Do they have others?

tkmcc 12y ago
Yes, there are MSR campuses around the world! Only the Silicon Valley satellite campus was closed. See http://research.microsoft.com/en-us/labs/ http://research.microsoft.com/en-us/labs/ for the full list.
RealCasually 12y ago
Yes, they only closed the Mountain View lab.

deleted 12y ago

[deleted]

mathgenius 12y ago

FTA: "Freedman was 30 when he solved a version of one of the longest-standing problems in mathematics, the Poincaré conjecture." Not true, he apparently made contributions to the poincare conjecture in dimension 4. Also, the article has a link from "poincare conjecture" to a clay institute webpage which is broken. Meh

tzs 12y ago
This is what it says about him on the official list of Fields medalists: "Developed new methods for topological analysis of four-manifolds. One of his results is a proof of the four-dimensional Poincaré Conjecture". The article's statement you quoted is accurate enough to not be "not true".
- mathgenius 12y ago
  Ok, thanks for that. I think I'm done with wikipedia.