Given random quantum behavior, how are qubits expected to be coaxed to produce a meaningful output in a quantum computer?

Question

My understanding of qubits is that their power lies in the fact that they "can have many states at once." But how would one go about taking advantage of this to get anything that relates to a concrete question/input/program and a meaningful output? My understanding is that the many states disappears once a measurement is taken, so I don't understand why entanglement would help because there is no additional information from an entangled pair once you know the state of one. In other words, how are quantum computers supposed to carry out more of a meaningful result than old soothsayers that threw bones for answers. Yes, the positions of the bones are randomly placed in one of many possible positions but how is this supposed to actually meaningfully relate to a computational program. I understand how computer gates work to create logic in traditional silicon computers. But they don't behave randomly. How is random behavior of cubits and the quantum world in general supposed to yield any useful result? The power seems to be based on the multistate randomness but why is this random state thought to somehow provide anything more than random output? Please answer for the type of computer google is building - not DWave "quantum" computers.

Answer 1

Randomness does not equal uselessness. We also have traditional randomized algorithms that run on classical computers - would you say they can't produce a useful result just because they are not deterministic?

Quantum computing algorithms manipulate the state of the system in a way that makes measuring the correct answer in the end highly probable and any incorrect answer - highly improbable. Some algorithms, like Deutsch-Jozsa algorithm, do it so well that the probability of measuring correct answer is 100%, so even though probabilities are involved in the algorithm description, they actually are deterministic.

---

Let's look at Grover search as an example - this is an algorithm that searches for a solution to an equation f(x) = 1. You'll get your answer x by measuring several qubits (it's a lot more common than using qudits). You start with these qubits in equal superposition - if you do a measurement at this stage you won't get anything useful indeed, since you'll get an arbitrary result with equal probability, and it will probably not be an answer to your problem. Grover's algorithm is a sequence of steps that modifies the state of the system so that superposition of the results is not equal any longer - the probabilities of states that solve your problem are amplified, and the probabilities of states that don't solve it are reduced. This means that measurement results are still random, but the probability of getting a correct answer is much higher than what you started with.