Could quantum computers break any cipher? I've been told that physicists and computer scientists are working on computers that could use quantum physics to increase significantly computation capabilities and break any cipher so cryptography becomes meaningless.
Is it true?
 A: No, it is not.
Quantum computers can factor large numbers efficiently, which would allow to break many of the commonly used public key cryptosystems such as RSA, which are based on the hardness of factoring.
However, there are other cryptosystems such as lattice-based cryptography which are not based on the hardness of factoring, and which (to our current knowledge) would not be vulnerable to attack by a quantum computer.
A: Quantum computing holds lots of promise, but it is not infinitely powerful.
The (exaggerated) claims you've heard are probably based on the most famous quantum computing algorithm, Shor's algorithm. This is a method for using a quantum computer to factor integers into prime numbers. As it turns out, many encryption schemes rely on the fact that factoring large numbers is very hard. Messages can be encrypted fairly easily in such a way that only someone who knows the prime factorization of a particular number can decrypt them with any reasonable amount of effort. If you could quickly factor large numbers, you would break many present-day encryption schemes.
However, there are other techniques that are not immediately threatened by quantum computers. If nothing else, you can always use a one-time pad as long as the message itself. This is mathematically unbreakable, since any message can be "decrypted" from the encrypted one with the appropriate guess at the key, so there is no way for an eavesdropper to know the real message.
Quantum computation may also open the doors to next-generation ways of securely transmitting information. For example, most encryption today is just that -- scrambling the message so that only the intended recipient can make sense of it. But there may be good quantum ways to physically ensure eavesdroppers cannot access the transmission in the first place.
A: There is actually an entire complexity class devoted to the answer, which is "no, it cannot break any code."  The class is known as BQP, or "bounded error quantum polynomial time."  It is the class of decision problems which can be solved by a quantum computer in polynomial time, with no more than a 1/3 error margin (this error term is accounted for in a classical computation step which occurs after most quantum algorithms to verify that results are correct).
BQP is believed to have the following relations with other complexities:


*

*Contains P (Polynomial Time)

*Intersects, but probably does not fully contain NP (Nondeterministic Polynomial time)


*

*Probably does not contain NP-complete (as a corollary)


*Subset of PSPACE (Problems that are solvable with polynomial space requirements)


(The major unknown in that list is that it is not yet known if P=NP.  The list assumes P!=NP, but if P=NP, clearly NP and NP-complete would also be part of BQP.  We also don't know if NP=BQP or not. so much left to discover!)
RSA is crackable using quantum computers because the task of factoring large composite numbers is in BQP, as demonstrated by Shor's algorithm.  Shor's algorithm is NP (but not NP-complete).  There are other NP algorithms which are believed to be outside of BQP which can be used for encryption (The accepted answer links to lattice based cryptography, which is one such class of algorithms).
A: The answers so far have focused on public-key encryption, in which someone publishes a public key which can be used to encrypt messages to them, and which is not secret. Quantum computers are known to be efficient at breaking several of the problems most commonly used as the basis of public-key cryptography. It does not affect all public-key cryptography, just the most popular schemes; it does affect the most popular schemes.
However, there is more to encryption than public-key. Symmetric encryption schemes, where the two parties share a secret key, is believed to be subject to no more than a quadratic speedup with quantum computers (quantum computers can achieve a quadratic speedup for general search problems, but no more). This corresponds to effectively halving the key length. Unlike the common public-key systems, effectively halving the key length is extremely easy to respond to: you can just double your key lengths and carry on. Symmetric encryption is extremely common; even where public-key encryption is used, it's most often just used to exchange a key for symmetric encryption.
The most common symmetric system, AES, has a 256-bit key variant that provides 128 bits of security against quantum computers. Other schemes in development support 512-bit keys, which would provide 256 bits of effective security. Both 128 and 256 bits are believed to be secure for the forseeable future.
Likewise, cryptographic hash functions are believed to hold up very well against quantum computers. There's the same Grover's algorithm-based attack, but like with encryption functions it is easy to counter.
So, any claims that cryptography become meaningless are totally off-base, because the only thing that is seriously affected are public-key systems. Public-key systems are important, but cryptography is a much broader field.
A: Ok - theoretically a quantum-computer could work like this:
You can start a normal computation and calculate it in parallel for all possible input keys. Which means decrypting an encrypted text with the right key takes just as long as decrypting it with every possible key (with a fixed length). This would mean that all traditional encryption methods like AES etc. could be cracked as fast as they could be decrypted by the holder of the legal key.
The tricky part (where the one time pad excels) is how to know if the resulting message you got from decrypting is actually the right text. For example I send the Message OK to you encrypted with AES 256bit. Now there are 2^256 possible keys to decrypt this message with and all of them will result in some result. Many maybe in something like #§ or other cryptic byte symbols, but some keys might lead to two letters "WB" and some combination might even lead to "NO".
So the difficult part is then to find out, which is the correct message! Because the (theoretical) quantum computer will in the end only output a few results with high propability - so you have to code a check, which will discern if the output is acutally a valid text. If the text is a lot bigger than the key and something like plain english, or better a standard-format which can be checked for integrity this could be possible. But if there are several possible outcomes which look valid, a human will have to sort them through so in the case of a onetime-pad cracking the code is just as good as simply guessing out of the blue. Other encryption-schemes might have to be adapted to produce valid-looking messages for false keys, but this seems possible...
--
This would only work if an actual quantum computer could work like this. As far as I know we have no hard evidence for a qc actually working like this. So maybe it simply can't be done and we don't even have a problem ;-)
A: I would like to add that quantum computers can not break any existing code because their logical gates can perform the very same operations as classical logical gates can. They add new possibilities while keeping those formerly possible in classical computers.
Since programms, at the core, work on logical gates, it is reasonable to assume that any existing code for classical computers can work on a quantum computer.
See also quantum gate on wikipedia.
A: No. There can exist no X computer that can break any cipher because the one time pad is a cipher and one time pad cannot be broken by algorithm (trivial proof in information theory).
