views:

77

answers:

2

What can we do more with qubits than normal bits, and how do they work? I read about them some time ago, and it appears that qubits can store not just 0 or 1, but also 0 and 1 at the same time. I don't really understand how they work. Can someone please explain this to me?

What are their pros and cons, and what impact will they have on programming languages like C after quantum computers are actually invented?

How would we manage memory when a bit ( which is also a quantum (: ) can take multiple values at once? How can we determine if something is true or false, when there is more than just 1 and 0?

+1  A: 
Zack
Scott's article is also a great read. Thanks!
Time Machine
+3  A: 

Any "classical" (as it will be called once the technology is in wider use) problem which is solved by "classical" code can be solved using some sort of quantum processor by transforming the problem. For example, to do a database search, instead of using an index-based search/binary search, or a linear search for an unsorted database, you can use Grover's algorithm. Also, to take a step back from the previous poster's mention of BQP problems, problems with a classical "solution" that runs in NP-time can be sped up considerably by Grover's algorithm (a speedup in the time to search through every possible solution). RSA cryptography is also made much more insecure by the advent of Shor's algorithm, since it makes factorising large numbers into their prime factors (the hinge upon which RSA sits) solvable in logarithmic time.

EDIT: Shor's algorithm actually runs in O((log N)^3), which is polynomial-over-logarithmic time.

The conclusion of this sort of thing is that pre-existing programming languages like C will not be able to be used on a quantum computer due to the nature of quantum algorithms (applying certain functions to quantum states), unless someone invents a way to map quantum gates and so forth to logical gates (EDIT: This has apparantly been mostly addressed here), in which case about all we get is a very very fast logical processor when using languages like C.

PS: I'm sure there'll be OpenGL bindings for quantum computing eventually :P

darvids0n
Actually, this question is about memory, memory management and programming languages, that's 2 for SO (mem management, programming languages) vs only 1 for SU (memory). That's why I posted it on SO.
Time Machine
Point taken, my assumption that the question was more general than it is was wrong.
darvids0n
It's important to realize that while Grover's algorithm provides a *speedup* for NP-complete problems, it does *not* provide an *exponential* speedup, which is what you would need for NP ⊆ BQP (i.e. for NP problems to be efficient on a quantum computer).
Zack