# Retrieving information from qubits

1. Dec 3, 2015

### T S Bailey

I'm very confused as to how qubits function. I understand that qubits can represent 2^n classical bits due to superposition, but I cannot find an explanation as to how the qubit can "parallel process" if you will. How could the qubit represent 2^n bits if, whenever it is measured, you still only get a classical number of states? In other words, in the case that you find the electron in the spin down state how did the spin up state aid in the computation? If by definition the other state is never measured how could it affect the outcome?

2. Dec 4, 2015

### Staff: Mentor

Have a look at Deutsch's algorithm. It is the simplest quantum algorithm. You will see how 4 possible outcomes are tested in one go.

Note also that some quantum algorithm are probabilistic. At the end of the computation, you make a measurement that will indeed result in a classical state. But with a well-designed algorithm, there will be a very high probability that this classical state will correspond to the answer you were looking for.

3. Dec 4, 2015

### .Scott

Yup. Although it is true that there is a lot of parallel processing going on, understanding how one can take advantage of that is not obvious. Here is a link that tries to explain it in the simplest possible terms.
http://www.scottaaronson.com/blog/?p=208

4. Dec 4, 2015

### Hornbein

As I best understand it, which is not very well, you try to set up the computation so that all the undesired answers cancel one another out to get zero probabilities. The state that you measure will be one of the desired ones.

Not all problems fit into this framework naturally, or even unnaturally.

5. Dec 4, 2015

### .Scott

@T S Bailey: There is actually an algorithm that kinda matches the popular notion of performing the same computation will all configurations of however many qubits you have. And it's my favorite quantum computing algorithm because it's the one most like to be of use to your typical non-NSA consumer.

It's called Grover's Algorithm and it's described starting on page 22 of this document:
https://people.cs.umass.edu/~strubell/doc/quantum_tutorial.pdf

I'll describe it carefully so as not to lead you to any misconceptions.
If you have N qubits, you can code the superposition of 2N binary states. Actually, you can encode more superpositions than that - but that's as many as we need right now. Because in the procedure we're about to use, those qubits will only code for superpositions of binary values.

Next we will build a device for performing a check in the quantum domain that detects a correct answer to whatever problem we want to solve. The device takes the N qubits of information and reports a one qubit result. That result is then used to flip the state corresponding to the correct answer - leaving all the others alone.

Grover then performs a step that causes the different one to be amplified - becoming slightly more probably than all the others.
The he does it again and again and again, until the correct answer becomes almost inevitable.
The he measures all N bits to get the final result.

This algorithm could also factor numbers, but not as efficiently. You could build a checker that took divided any particular binary number (not qubits), divided it by a 100 qubit value, checked the remainder for zero, and flipped the state if it was zero. Then do enough of those Grover Iterations and when you read those 100 bits, they will encode your answer. Of course, there could be more than one answer - in which case you will likely get one of them - it chooses which.