6

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?

Floern
  • 33,559
  • 24
  • 104
  • 119
  • qubits will bring about the end of conventional cryptography as we know it, if what I've read about quantum computing is true. What takes current computers years will be dealt with sub-second by a quantum computer. Read up on qubits and quantum computing on Wikipedia if you're interested. http://en.wikipedia.org/wiki/Qubits http://en.wikipedia.org/wiki/Quantum_computer – Will A Aug 02 '10 at 23:10
  • 2
    P.S. Future operating systems running on quantum computers may even take less than ten seconds to boot. :p – Will A Aug 02 '10 at 23:12
  • 2
    See [ Does anyone know what “Quantum Computing” is? ](http://stackoverflow.com/questions/3163234/does-anyone-know-what-quantum-computing-is). – Matthew Flaschen Aug 02 '10 at 23:16
  • Mmm. So a qubit can store a superposition of 0 and 1, but how on earth can we give a value to a superposition, which is always unknown? –  Aug 02 '10 at 23:17
  • The question you mentioned, Matthew, is also a good read. –  Aug 02 '10 at 23:24
  • Programming languages will have an uncertain future, but computing will take a quantum leap. – ergosys Aug 02 '10 at 23:26
  • @ergosys A quantum leap. So, you mean a leap which is undividable? :D –  Aug 02 '10 at 23:29

5 Answers5

5

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

  • 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. –  Aug 02 '10 at 23:56
  • Point taken, my assumption that the question was more general than it is was wrong. –  Aug 03 '10 at 00:00
  • 2
    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). – zwol Aug 03 '10 at 00:01
3

If we can make a working quantum computer (still an open question) then it can efficiently solve certain algorithmic problems that (we think) a classical computer cannot efficiently solve. These are the problems in the complexity class BQP but not in P. One big one is integer factorization. As Will A mentioned, if you can factor enormous integers quickly, you can break a lot of modern ciphers.

The catch is that nobody knows for sure if BQP is actually "bigger" than P — it might be that anything a quantum computer can do quickly, so can a classical computer.

We also don't know if BQP is as big as NP — for instance, nobody has found an efficient way to solve the Traveling Salesman Problem on a quantum computer. This is a common misconception about quantum computers. They might be able to do NP-complete problems quickly, and then again they might not. Nobody knows.

http://scottaaronson.com/blog/?p=208 be good readin' on this topic (as is the rest of the blog).

zwol
  • 135,547
  • 38
  • 252
  • 361
  • We do have a working quantum computer. It can even tell us that 15 is 3 times 5! But that's about it. We haven't been able to make it bigger. – Theo Belaire Dec 09 '10 at 00:01
  • Plz to read "working" as "working for problems of nontrivial size". :-) – zwol Dec 09 '10 at 06:42
  • Although it is still a source of a minor controversy in scientific circles, we do have a working-for-problems-of-nontrivial-size quantum computer (although Scott Aaronson might kind of disagree on that :) ). Please check my answer to another question on SO for more details: http://stackoverflow.com/questions/432922/significant-new-inventions-in-computing-since-1980/5161092#5161092 – Domchi Mar 01 '11 at 22:45
1

Regarding what can be solved with quantum computers: A quantum computer would break current asymmetric encryption schemes. It is a common misconception, that quantum computers can solve most optimization problems. They cannot. See this article for more details what can be solved using quantum computers and what cannot.

Falk Tandetzky
  • 5,226
  • 2
  • 15
  • 27
0

qubits doesn't store 0 and 1 simultaneously, actually they are made from the superposition of the 0 and 1 at a time. so if a normal bit can represent 0 or 1 at a time, but qubits contain 0 and 1 at a time. three normal bits can store any one of the following.... 000,001,010,...,111. but qubit can represent all of them at a time(which are in superposition). so a 'n' qubits store 2^n bits simultaneously!

user2679146
  • 81
  • 1
  • 1
  • 3
-1

Suppose a qubit an electron and it spins just like dipole momentum particle and when it spins it create an amplitude of multiple intensity and frequencies that minor amplitude can create spin vibration or momentum of particle that momentum can store thousand bits of information !!! (that's called quantum information processing) which is future !

smart_friendo
  • 1