Author Topic: Quantum Computing  (Read 12951 times)

Offline sanman

  • Senior Member
  • *****
  • Posts: 4348
  • Liked: 652
  • Likes Given: 8
Quantum Computing
« on: 04/13/2013 04:35 PM »
Aerospace giant Lockheed has recently bought a new type of computer from a company called D-Wave. The physics of this new computer is supposed to be quite different from conventional computing systems, because it's claimed to be based on quantum effects. The scientific decision-makers at Lockheed feel that their purchase is justified by the new capabilities the D-Wave computer gives them:

http://www.nytimes.com/2013/03/22/technology/testing-a-new-class-of-speedy-computer.html?pagewanted=all&_r=0



If quantum computing ever becomes a reality, then what kind of impact will it have on spaceflight?


Offline deltaV

  • Full Member
  • ****
  • Posts: 1538
  • Change in velocity
  • Liked: 166
  • Likes Given: 480
Re: Quantum Computing
« Reply #1 on: 04/13/2013 05:26 PM »
Quantum computing experts have yet to be convinced that D-Wave's computer is actually using quantum effects. See for example the second large block quote in the following blog post by MIT professor and quantum computing researcher Scott Aaronson: http://www.scottaaronson.com/blog/?p=1136 .

Offline deltaV

  • Full Member
  • ****
  • Posts: 1538
  • Change in velocity
  • Liked: 166
  • Likes Given: 480
Re: Quantum Computing
« Reply #2 on: 04/13/2013 05:53 PM »
If quantum computing ever becomes a reality, then what kind of impact will it have on spaceflight?

Quantum computing would make many cryptography algorithms no longer secure. This could seriously reduce the demand for e.g. satellite phones.

Quantum computing may be useful for simulating chemistry, which could potentially lead to advancements in e.g. fuel cells or ISRU. I doubt it would cause nearly as much effect on the space industry as e.g. easy reusability or launch systems owned by non-governments would (will?) have.

Quantum computers are not known to be able to solve NP-complete problems in polynomial time, so I do not expect quantum computers to provide more than incremental progress for anything except cryptography and simulations of systems where quantum mechanical effects matter. D-Wave is exaggerating its usefulness IMHO.
« Last Edit: 04/13/2013 05:55 PM by deltaV »

Offline mlindner

  • Software Engineer
  • Senior Member
  • *****
  • Posts: 2012
  • Space Capitalist
  • Silicon Valley, CA -- previously in Ann Arbor, MI
  • Liked: 654
  • Likes Given: 241
Re: Quantum Computing
« Reply #3 on: 04/14/2013 06:42 AM »
If quantum computing ever becomes a reality, then what kind of impact will it have on spaceflight?

Quantum computing would make many cryptography algorithms no longer secure. This could seriously reduce the demand for e.g. satellite phones.

Quantum computing may be useful for simulating chemistry, which could potentially lead to advancements in e.g. fuel cells or ISRU. I doubt it would cause nearly as much effect on the space industry as e.g. easy reusability or launch systems owned by non-governments would (will?) have.

Quantum computers are not known to be able to solve NP-complete problems in polynomial time, so I do not expect quantum computers to provide more than incremental progress for anything except cryptography and simulations of systems where quantum mechanical effects matter. D-Wave is exaggerating its usefulness IMHO.

Lowered demand for satellite phones would be the least of your worries.

I don't think you realize how much of the modern world is based on the security of encryption. It would probably collapse the world economy if quantum computers became accessible. Not to mention make wikileaks look like child's play. Internet banking would immediately become insecure, anyone could forge any bank request because of the ability to listen in.

Imagine for a second a world where anyone with a decent amount of money could break any secure communication. 1984 realized effectively.

Jumping back to reality though, quantum computing is still very much theoretical and far off.
« Last Edit: 04/14/2013 06:44 AM by mlindner »
Internal combustion engine in space. It's just a Bad Idea.TM - Robotbeat

Offline Robotbeat

  • Senior Member
  • *****
  • Posts: 28466
  • Minnesota
  • Liked: 8328
  • Likes Given: 5479
Re: Quantum Computing
« Reply #4 on: 04/14/2013 06:56 AM »
Wow, scare-mongering much? Some cryptography methods can't be easily cracked with quantum computing. Quantum computers are a powerful tool, but they have their limitations as well. It's not equivalent to P=NP.

For instance, one-time pads are completely uncrackable, even by whatever kind of computer you can come up with, quantum or classical. It's not impossible to imagine a setup where this could be used for even satellite phones, now that storage is so darned cheap and tiny. Micro-SD cards even in the 64GB range are pretty cheap ($1 per GB), so that works out to 5 years of continual talk time at the usual satellite phone data rate (~3kbps) before you have to have your micro-SD card updated to a new one-time-pad.

And there are other, more practical encryption algorithms that can't be trivially cracked by quantum computers. Not everything relies on the difficulty of factoring numbers made of large primes.
« Last Edit: 04/14/2013 07:04 AM by Robotbeat »
Chris  Whoever loves correction loves knowledge, but he who hates reproof is stupid.

To the maximum extent practicable, the Federal Government shall plan missions to accommodate the space transportation services capabilities of United States commercial providers. US law http://goo.gl/YZYNt0

Offline Robotbeat

  • Senior Member
  • *****
  • Posts: 28466
  • Minnesota
  • Liked: 8328
  • Likes Given: 5479
Re: Quantum Computing
« Reply #5 on: 04/14/2013 07:03 AM »
Quantum computing is not merely theoretical. It is being done experimentally, though currently it is limited to just a few qubits, so only simple algorithms are being used, and they aren't in danger so far of eclipsing classical computers.
Chris  Whoever loves correction loves knowledge, but he who hates reproof is stupid.

To the maximum extent practicable, the Federal Government shall plan missions to accommodate the space transportation services capabilities of United States commercial providers. US law http://goo.gl/YZYNt0

Offline grondilu

  • Full Member
  • ****
  • Posts: 563
  • France
  • Liked: 15
  • Likes Given: 5
Re: Quantum Computing
« Reply #6 on: 04/14/2013 08:40 AM »
If quantum computing ever becomes a reality, then what kind of impact will it have on spaceflight?

IIRC, according to David Deutsch, a 300-qbits quantum computer could simulate a whole universe.  So with quantum computing, we would not have to bother traveling through space because we could explore simulated worlds.

(notice that this is one possible answer to the Fermi paradox, btw)
« Last Edit: 04/14/2013 08:43 AM by grondilu »
Space is pretty much literally an astronomically-high hanging fruit.

Offline mlindner

  • Software Engineer
  • Senior Member
  • *****
  • Posts: 2012
  • Space Capitalist
  • Silicon Valley, CA -- previously in Ann Arbor, MI
  • Liked: 654
  • Likes Given: 241
Re: Quantum Computing
« Reply #7 on: 04/14/2013 09:46 AM »
And there are other, more practical encryption algorithms that can't be trivially cracked by quantum computers. Not everything relies on the difficulty of factoring numbers made of large primes.

No, but world commerce does.

One-time pads are also impractical with regard to economic considerations for a mass produced product.

Edit: I should have refreshed my memory first before posting... It appears quantum computing only halves the exponent for decryption. O(2^n) to O(2^(n/2)). Making AES-256 only as hard to crack as AES-128. Thats a huge speedup, but its still takes a significant amount of time. I think I'll quit this conversation while I'm behind.
« Last Edit: 04/14/2013 09:52 AM by mlindner »
Internal combustion engine in space. It's just a Bad Idea.TM - Robotbeat

Offline mlindner

  • Software Engineer
  • Senior Member
  • *****
  • Posts: 2012
  • Space Capitalist
  • Silicon Valley, CA -- previously in Ann Arbor, MI
  • Liked: 654
  • Likes Given: 241
Re: Quantum Computing
« Reply #8 on: 04/14/2013 09:48 AM »
Quantum computing is not merely theoretical. It is being done experimentally, though currently it is limited to just a few qubits, so only simple algorithms are being used, and they aren't in danger so far of eclipsing classical computers.

I'll admit I have a somewhat poor grasp of what quantum computers are useful for besides massive-parallization. I somehow doubt they will eclipse classical computers though as I have heard they are mostly intended for specialized purposes.
Internal combustion engine in space. It's just a Bad Idea.TM - Robotbeat

Offline deltaV

  • Full Member
  • ****
  • Posts: 1538
  • Change in velocity
  • Liked: 166
  • Likes Given: 480
Re: Quantum Computing
« Reply #9 on: 04/14/2013 02:04 PM »
Lowered demand for satellite phones would be the least of your worries.

I don't think you realize how much of the modern world is based on the security of encryption.

I'm aware of the pervasive effects cryptography difficulties would have on the world at large, of which satellite phones are only a tiny part, but this thread (and forum) is about the impact of quantum computing on spaceflight.

Offline Tass

  • Full Member
  • ***
  • Posts: 361
  • Liked: 76
  • Likes Given: 153
Re: Quantum Computing
« Reply #10 on: 04/14/2013 02:48 PM »
If quantum computing ever becomes a reality, then what kind of impact will it have on spaceflight?

IIRC, according to David Deutsch, a 300-qbits quantum computer could simulate a whole universe.  So with quantum computing, we would not have to bother traveling through space because we could explore simulated worlds.

(notice that this is one possible answer to the Fermi paradox, btw)


No no no no no.

First of all the universe is already quantum mechanical, and it has a lot more qubits.

A 300 qubit quantum computer would be able to run some very specific algorithms faster than any classical computer could - even if it had the whole universe as resources - but it would not allow us to simulate a univers. 

Offline R7

  • Propulsophile
  • Senior Member
  • *****
  • Posts: 2738
    • Don't worry.. we can still be fans of OSC and SNC
  • Liked: 952
  • Likes Given: 662
Re: Quantum Computing
« Reply #11 on: 04/14/2013 03:01 PM »
Would quantum computing offer better/faster solutions in trajectory calculations?
AD·ASTRA·ASTRORVM·GRATIA

Offline grondilu

  • Full Member
  • ****
  • Posts: 563
  • France
  • Liked: 15
  • Likes Given: 5
Re: Quantum Computing
« Reply #12 on: 04/14/2013 03:08 PM »
First of all the universe is already quantum mechanical, and it has a lot more qubits.

Sure, but the universe is not a computer:  its particles are not all interconnected.  A stack of billions of transistors doesn't make a supercomputer if they are not interconnected.

There are about 10^80 atoms in the universe.  2^300 is about 10^90 so Deutsch's idea (I don't remember where I rred it, but it's probably in the fabric of reality, I'll verify one of these days) is not so absurd.

Also: yeah, quantum computers can be used only for very specific applications, but simulating physical systems is one of them, IIRC (I recall it was the original idea envisioned by Feynman on the subject, actually).
Space is pretty much literally an astronomically-high hanging fruit.

Offline Tass

  • Full Member
  • ***
  • Posts: 361
  • Liked: 76
  • Likes Given: 153
Re: Quantum Computing
« Reply #13 on: 04/14/2013 03:32 PM »
First of all the universe is already quantum mechanical, and it has a lot more qubits.

Sure, but the universe is not a computer:  its particles are not all interconnected.  A stack of billions of transistors doesn't make a supercomputer if they are not interconnected.

There are about 10^80 atoms in the universe.  2^300 is about 10^90 so Deutsch's idea (I don't remember where I rred it, but it's probably in the fabric of reality, I'll verify one of these days) is not so absurd.

Also: yeah, quantum computers can be used only for very specific applications, but simulating physical systems is one of them, IIRC (I recall it was the original idea envisioned by Feynman on the subject, actually).

Yes, more specifically: Simulating physical systems where quantum mechanics are important.

If you want to simulate a quantum mechanical system then the problem is the required computer power goes exponentially with the size because of all the possible entanglements that has to be kept track of. Various simplifications reduces this: DFT to N3, Hartree-Fock to N4, Möller-Plesset perturbation to N5 or N6 depending on order, and CCSD(T) to something like N7, with Full CI either similar or worse.

A way to get the full detail without having to make the system and see how it behaves, would be with a general purpose quantum computer. It can track all the entanglements with the same qubits and therefore only has to scale linearly with system size.

This does not mean it works the other way. A quantum computer can not simulate an exponentially bigger classical system.

Do you actually know anything about quantum computing, or only what you heard from blogs and popular science?

Offline grondilu

  • Full Member
  • ****
  • Posts: 563
  • France
  • Liked: 15
  • Likes Given: 5
Re: Quantum Computing
« Reply #14 on: 04/14/2013 04:05 PM »
Do you actually know anything about quantum computing, or only what you heard from blogs and popular science?

I know very little indeed.   Happy?
« Last Edit: 04/14/2013 04:59 PM by grondilu »
Space is pretty much literally an astronomically-high hanging fruit.

Offline Tass

  • Full Member
  • ***
  • Posts: 361
  • Liked: 76
  • Likes Given: 153
Re: Quantum Computing
« Reply #15 on: 04/14/2013 05:14 PM »
I know very little indeed.   Happy?

Happy? What do you mean?

I just asked what your basis was. I only have like a quarter year of course work that has directly to do with quantum computing, it is not my field. You seemed insistent that quantum computing could exponentially speed up classical simulation. I had not heard of such an algorithm, but I could possible have missed it.

On the other hand if it is just from blogs and popular science then Occams razor would suggest that the "simulate a universe" thing has been misunderstood or exaggerated somewhere in the chain.   

Offline grondilu

  • Full Member
  • ****
  • Posts: 563
  • France
  • Liked: 15
  • Likes Given: 5
Re: Quantum Computing
« Reply #16 on: 04/14/2013 05:24 PM »
I know very little indeed.   Happy?

Happy? What do you mean?

Maybe I'm too susceptible, but I felt a bit of aggressivity in your last question.

Quote
I just asked what your basis was. I only have like a quarter year of course work that has directly to do with quantum computing, it is not my field. You seemed insistent that quantum computing could exponentially speed up classical simulation. I had not heard of such an algorithm, but I could possible have missed it.

I never managed to understand how a quantum computer works, and yet I think I know the basics of quantum mechanics.  What I wrote is that I somewhere rred that David Deutsch thinks a 300-qbits quantum computer could simulate a whole universe.  Maybe this is not true, or maybe I misinterpreted the quote.  But I thought it was worth mentioning.

I later mentioned the number of atoms in the universe as a way to show that although I have no idea on how such a quantum computer would work, the idea that 300 qbits could simulate 10^80 or more particles did not seem so absurd to me, considering 2^300 is ten billion times more than 10^80.

Quote
On the other hand if it is just from blogs and popular science then Occams razor would suggest that the "simulate a universe" thing has been misunderstood or exaggerated somewhere in the chain.   
This might be true.  I may have misinterpreted the claim indeed.  I only read the first two chapters of the fabric of reality I think.   One of these days I'll have to read the whole thing.
« Last Edit: 04/14/2013 05:30 PM by grondilu »
Space is pretty much literally an astronomically-high hanging fruit.

Offline Robotbeat

  • Senior Member
  • *****
  • Posts: 28466
  • Minnesota
  • Liked: 8328
  • Likes Given: 5479
Re: Quantum Computing
« Reply #17 on: 04/14/2013 05:39 PM »
We used to use crappier encryption that is now easily crackable. We upgraded. We'll upgrade once more to better algorithms when quantum computing comes online. Not so dramatic.
Chris  Whoever loves correction loves knowledge, but he who hates reproof is stupid.

To the maximum extent practicable, the Federal Government shall plan missions to accommodate the space transportation services capabilities of United States commercial providers. US law http://goo.gl/YZYNt0

Offline Tass

  • Full Member
  • ***
  • Posts: 361
  • Liked: 76
  • Likes Given: 153
Re: Quantum Computing
« Reply #18 on: 04/14/2013 06:48 PM »
I know very little indeed.   Happy?

Happy? What do you mean?

Maybe I'm too susceptible, but I felt a bit of aggressivity in your last question.

Yeah. I must admit that I played dumb when asking what you meant. I reread my reply and I could see how it could cause offense. For that I apologize. I meant none. It sounded way harsher than intended.

And a second apology for playing innocent when I did see your grievance.

I never managed to understand how a quantum computer works, and yet I think I know the basics of quantum mechanics.

Hehe, I had it the same way. I specifically took a course in it because I was curious about how quantum computers worked, even though it was irrelevant to my field.

What I wrote is that I somewhere rred that David Deutsch thinks a 300-qbits quantum computer could simulate a whole universe.  Maybe this is not true, or maybe I misinterpreted the quote.  But I thought it was worth mentioning.

Well, the state of a 300 qubit quantum computer will be described by 2^300 complex numbers. That is a lot of data. Enough for a classical universe as you say. You could probably make the state evolve in such a way as to actually simulate such a universe, (although it would be one without QM or at least one where superpositions has to be collapsed while very small).

Trouble is there'd be no way to read out this data. Measure the state and it collapses leaving you with 300 more or less random bits. The hard part is making the state evolve in such a way that it with high probability gives you the right bits for the problem you want to solve.

We used to use crappier encryption that is now easily crackable. We upgraded. We'll upgrade once more to better algorithms when quantum computing comes online. Not so dramatic.

Agreed.

Offline Robotbeat

  • Senior Member
  • *****
  • Posts: 28466
  • Minnesota
  • Liked: 8328
  • Likes Given: 5479
Re: Quantum Computing
« Reply #19 on: 04/14/2013 07:51 PM »
You really can't simulate the universe with 300 qubits, unless you're talking a stupidly simple model. The Universe is a quantum mechanical system with 10^80+ particles which /really do/ behave quantum mechanically (though if you make certain approximations, they behave as a whole pretty classically in many cases).

Certain algorithms are better with quantum computers, but certainly not all.

And actually, there's a minimum amount of mass you need to store a certain amount of information, related to the maximum entropy of the surface of a black hole of a certain radius. The Universe contains a LOT of information, it couldn't be stored in just 300 qubits.
Chris  Whoever loves correction loves knowledge, but he who hates reproof is stupid.

To the maximum extent practicable, the Federal Government shall plan missions to accommodate the space transportation services capabilities of United States commercial providers. US law http://goo.gl/YZYNt0

Tags: