# Quantum computers: are they possible or impossible?

I know quantum computers are very complicated and my question is is there any way in "Principle" to create one? Are there already quantum computers being created?

Some people think it is possible, some people think otherwise. Such as Leonid Levin and Oded Goldreich, who just take it as obvious that quantum computing must be impossible. Part of their argument is that it's extravagant to imagine a world where describing the state of 200 particles takes more bits then there are particles in the universe.

• I don't understand - from e.g. the commments, I was under the impression that a primitive quantum computer had been realized and was for sale. How is the position of Messrs Levin and Goldreich tenable? – innisfree Oct 30 '13 at 14:55
• Describing the state of 200 particles only takes more bits than there are particles in a universe if we assume the universe is being simulated on a classical computer. It takes a reasonable number of quantum bits. So this is sort of a circular argument. Start out by assuming the world is classical at its base. Then it can't actually be quantum because the cost of simulating quantum mechanics in a classical world is extravagant. – Peter Shor Aug 8 '17 at 1:19

It sure is possible, there are actually already some proof-of-principle experiments implementing some elementary quantum gates or quantum algorithms.

However, there still is a long way to go. Building a useful universal quantum computer requires hundreds or thousands of quantum bits at least which is, so far, a tremendous problem. Quantum systems are very fragile and lose their quantum properties easily. You can use some error correcting codes to circumvent this but these work only for very small error rates.

All in all, we face just technological problems in building a quantum computer but it is still very far from our reach. Some people even think that we will never be able to build it. In my opinion, it will definitely take more than just ten years as Jonathan Kelsey suggests in his answer.

They are possible because they have been built.

http://www.pbs.org/wgbh/nova/tech/quantum-computing.html

The main issue is more getting one to function at a useable scale.

Certainly! In fact there is a set of criteria which researchers are get closer to realising every day. http://www.research.ibm.com/ss_computing/ These criteria are known as the DiVincenzo criteria.

One big step is building a universal gate known as a cnot (controlled not) from which all other quantum logic gates can be derived. IBM have done this recently. http://en.wikipedia.org/wiki/Controlled_NOT_gate

It may take under 10 years to see them realised.

yes, it's theoretically possible to create quantum computers. people are working to build prototypes of such computers all around the world.

the smallest "thing to do calculations with" in such a computer is a quantum bit (or qubit). this is the equivalent to a bit in the (ordinary) computers we use today.

check out this video and the article about qubits on Wikipedia.

My answer is only my personal opinion, but it is a good and interesting argument. So take as much as it holds up for you.

Only trivial Quantum Computers have been built. The only real proof of concept would be if one were to succeed in building one large enough that it actually solved a problem that is beyond the reach of conventional computers for quantum reasons.

In my opinion, the problem is not building the quantum computer, but reading out the answer from the computer. In fact, I think it will turn out that one can read the answer if and only if the problem itself can be solved by conventional computation.

Why? It has been proven that QIC = P-Space. That is an interactive quantum computer takes polynomial time to solve problems. That is the same limitation that conventional computers have.

Let me try to explain what I think is true.

Suppose you wanted to analyze encrypted message which used a 300 digit prime to encode it. This means you need to be able to figure out which 300 digit prime number was used. The only way to do that is to somehow use the data to distinguish the correct answer from all other possible 300 digit prime numbers. If you used a conventional computer to try to solve the problem you would have to keep testing 300 digit prime numbers until only one could possibly be the right answer.

Your quantum computer would not have a problem with this if it had an entanglement that consisted of a little over $\log(10^{300})/\log(2)$ qbits, because you could directly express the possible answer with the qbits and then directly work on analyzing your prime number. In fact you could directly analyze all 300 digit numbers at the same time!

But we are not out of the woods yet. We still have to get the answer from the machine, and the only way to do that is with statistics. The problem is not reading out a 300 digit number, it is to statistically distinguish that number from all other 300 digit numbers in a statistically reliable way. If our statistics can't dependably tell the difference between the correct answer and all of the other 300 digit numbers we have failed.

Here is a news flash, the quantum computer has our answer but getting the answer is tough.

To explain, if we had the same number of grains of sand as a 300 digit number, how much would we have? Lets assume for the sake of argument that a grain of sand is 1/100 of a gram. In that case our grains of sand would weight about the same as $2 \cdot 10^{270}$ plant earths! That is because the earth weighs about $5.5\cdot 10^{27}\,$g.

So the problem is like finding a certain unique grain of sand from all those $10^{270}$ worlds of sand!

So we would be looking a good long time before we found which "grain of sand" the answer is among all those earths.

With conventional computers it would mean examining a significant proportion of all those grains of sand, one after another or a few at the same time. The process would be prohibitively slow. With a quantum computer, assuming it can calculate the result, we have to do enough statistics that the correct result is distinguished from all the other possible results ... in other words, there are all those other "grains of sand" to contend with and if the error rate was so incredibly small that it was only one part in $10^{50}$, we would still have $10^{250}$ wrong answers obscuring the correct result ... so which of the $10^{250}$ answers is correct? Who knows?

• -1. Totally wrong. Try solving protein folding with conventional computation. – Anixx Apr 18 '14 at 19:49
• "If you used a conventional computer to try to solve the problem you would have to keep testing 300 digit prime numbers until only one could possibly be the right answer." Totally wrong. We have much, much, much better classical factoring algorithms than trial division. Ditto, we have much better quantum factoring algorithms that use interference to get the correct answer. – Peter Shor Jun 2 '17 at 18:30

Any chemical experiment is a quantum computer: it will give you in minutes the results which you would have been calculating for years on a conventional computer because of exponential difficulty of solving Schroedinger's equations.

The only problem is to create a flexible (ideally, universal) setup which would allow you to performn "chemical" experiments on a chip by creating such configuration of electronic elements that would model the behavior of electrons in a molecule, but be easily re-programmable for another kind of molecules.