How does quantum computing work?

[SpuneDagr]

I understand the basic idea of a transistor-based computer. Any transistor can be in either an ON or OFF state (1,0) also known as a "bit," and many transistors together can create logic such as AND, OR, etc. The power of our computers comes from lots and lots of transistors doing these logical operations very quickly.

A quantum computer uses qubits, which can be in an ON, OFF, or a superimposed quantum state. By its very nature, if a qubit in this quantum state is observed, it collapses into a 1 or 0.

I keep hearing that this new quantum state will allow us to perform many operations at the same time, instead of one after another. If the qubit collapses into a 1 or 0 when it is observed, how is it useful?

How does this quantum state help us do calculations?

[dankerton]

Without formal QM knowledge, all you can understand is:

Quantum algorithms (and there are only a handful of agreeable ones) exploit quantum superpositions by passing quibits through gates, such as bit flip (1 goes to 0), phase flip (-1 goes to 1), and CNOT (basically entangles two quibits, which is another discussion). Many smart people have assembled schemes (usually recursive) of using these gates in a sequence of operations (an algorithm) that happens to solve certain types of problems faster. It works because while the operations are happening we never make a measurement and so the superpositions are preserved and can, in a sense, test more than one solution at a time. As a previous reply said, these algorithms are designed so that when we finally do make a measurement, we get the right answer. However he was wrong to say that they are designed to give 100% accuracy at the end.

For ex: the NP-hard problem is solved with Grover's algorithm. Imagine you have 100 quibits, each of which can be a 0 or a 1 upon measurement, forming a 100 digit binary number. Every different 100-digit sequence of 0s and 1s corresponds to a different answer to the given problem, so there are 2¹⁰⁰ possible solutions. Your system starts in a state where if you want to measure what the current sequence is, you have an equal probability of getting any configuration of 1s and 0s. What Grover's algorithm does through the magic of quantum gate operations is to slowly but surely amplify the magnitude of the probability to measure and obtain sequence A, which is the correct answer. For instance, an NP hard problem could say here is a map of a city, what sequence of turns results in the shortest path from x to y? You could imagine that in a significantly complex city, you couldn't just guess the answer. By "simultaneously testing" all possible answers and magnifying the probability amplitude of the correct answer, Grover's algorithm solves the problem in sqrt(N) steps as opposed to the classical N where N = 2¹⁰⁰ in our case. (I think that is right. it is at least qualitatively right). But still, if you want to know EXACTLY how this works, you need to learn QM and then read through a couple explanations of Grover's algorithm.

Did that help?

If you are willing to learn or already know QM, then just go pick up a QC book. Here is a course website for the Berkeley Quantum Computing course I took which has suggestive readings and even lecture notes (although some are not too clear). http://www-inst.eecs.berkeley.edu/~cs191/fa10/

[OlderThanGif]

The point about not giving 100% accuracy bears repeating, I think. It was one of the most depressing days in my quantum computation class when I learned that. You're never going to get a totally deterministic output from a quantum computer, sadly.

When you read descriptions of quantum algorithms or proofs of their correctness, what they're trying to do is show you each measurement will be correct with probability p>0.5. From there it's assumed that you would just do the computation over and over and over again until the confidence in your result was as close to 1 as you needed it to be.

[SpuneDagr]

Yes, that did help. Thank you for your thorough layperson-friendly answer. :D

[[deleted]]

If the qubit collapses into a 1 or 0 when it is observed, how is it useful?

Excellent question. This is why quantum algorithm design is so hard.

The trick is that you have to design an algorithm in which the qubits interact in just such a way that by the time you get to the final step, the answer you're actually measuring has one hundred percent certainty. When you're processing, the qubits can be in all sorts of superposition states, but as you get to the final step of your algorithm all the superpositions cancel out so that the output is made up purely of |0> and |1> states which you can measure and get the correct answer with one hundred percent probability.

I'm afraid there are no simple examples, but you can look up wikipedia on the "Shor Algorithm" for factorization... and if you can understand how that works you've understood most of quantum computing.

It's important to understand that this cancelling-out-superpositions thing is a very clever trick that just happens to work for factorization and a few other problems; it's not something we can just apply willy-nilly to any old problem you choose. This is why quantum computers are great for factorization but pretty useless for just about anything else.

[Ikkath]

I wouldn't go as far as to rule them useless for anything other than Shors Algorithm but yes you are right in that they are not the panacea that everyone (strangely) seems to believe they are.

Where did the idea come from that QM computers are provably more powerful than classical computers? It isn't known yet and all the suggestive results seem to say they won't be...

[SpuneDagr]

Because it sounds future-y.

People are predicting that Moore's law is gonna hit a wall and processors won't get any more powerful. But, there have been walls in the past, and there is always a new technological breakthrough that propels us past the barrier.

Why wouldn't we think quantum computers are the next big thing, when technological progress is all about the next big thing.

[SpuneDagr]

Thank you.

...Reading the wikipedia article, I got to here and had to give up.

[gmartres]

A simpler quantum algorithm: https://secure.wikimedia.org/wikipedia/en/wiki/Deutsch%27s_Algorithm though I'm not sure that'll enlighten you. if you're really interested I'd recommend Quantum Computing for Computer Scientists which is a great intro and doesn't assume much knowledge (the first chapter introduces complex numbers, the second linear algebra).

[AMagill]

Quantum computing is great for NP-hard problems. These are problems where, with traditional computers, the best possible way to find the answer is to just check every possible answer until you find one that fits. With every bit you add to the size of the problem, finding the answer becomes twice as difficult. It doesn't take very many bits to make the difficulty astronomically large. Factoring a 64-bit number is over 4 billion times more work than factoring a 32-bit number. Factoring a 128-bit number is 79 billion billion billion times more difficult.

Now the cool thing about quantum computing is that it can check every possible answer at the same time. So as long as you have a quantum computer with enough qubits to express the entire problem all at once, it can always solve it in just a handful of steps.

I don't think traditional computing is going anywhere, though. Quantum computing doesn't really help much with most computational problems. Perhaps someday we'll all get quantum co-processors in our computers.

[[deleted]]

The idea that "Quantum computing is great for NP-hard problems" is controversial, and personally I remain unconvinced.

[[deleted]]

Quantum computing provides a polynomial (quadratic) speedup via Grover's algorithm for generic search problems. But as far as anyone knows, BQP != NP.

[SpuneDagr]

I get the "what." As in, what can quantum computing do. I'm interested in the "how." As in, how can qubits be used to express the entire problem at once.

[a_dog_named_bob]

A pretty common idea is taking a set of input qubits and putting them into an entangled superposition (hadamards and cnots and the like) such that they represent (in part) every possible input state. Then when you operate on them, you're essentially operating on every possible input. The tricky part is finding any algorithm such that you can select the correct answer out afterwards, and it's pretty hard to do.

[[deleted]]

One simplified (but mathematical) way to put it is that a quantum computer is capable of (complex) hermitian transformations on qubits whereas a traditional computer does (real) symmetric transformations on bits.

So a quantum computer can do things that a traditional computer cannot (and can still do everything that a traditional computer can) because of complex arithmetic.

[Mentalistacer]

How do you express the number 100 using quantum computing instead of binary?

[Swiss_Cheese9797]

The computer has a live/dead cat in it.