How do quantum computers find the global minimum?

Question

If I understand correctly, quantum computers work by trying multiple methods of solving a problem simultaneously, using quantum superposition. However, if you try to "look" at a superposition-ed atom, you will find either one or the other-1 or 0. What I've heard is that this is random.

So, if you compute all these solutions, how do you know which is the best without "looking" at it? Wouldn't the result just be random, and you can only see the result of one answer? Now, I've heard that this can be solved by quantum annealing, but I don't really understand it. I'd like to know how this works in fairly layman-ish (It's a word) terms.

Answer 1

Nope, that's not how quantum computing works. That's actually a common misconception. Sometimes people think that quantum computers work by trying all solutions in parallel and then selecting the best one, but that's not right -- that's not really how quantum computing works.

To learn more about how quantum computing works, I recommend you study Scott Aaronson's book Quantum Computing since Democritus, or his lecture notes on quantum computing.

Don't expect to find a one-sentence summary that is simultaneously enlightening and accurate. Quantum physics is highly counter-intuitive, so you shouldn't expect your existing intuition to necessarily help you understand how quantum computing works. Keep in mind that it's a bit unreasonable to expect an explanation in layman terms: quantum physics is tricky stuff, so your intuition from the everyday world doesn't really translate into a useful way of thinking about quantum computing.

You can also look at other questions on this site. See, e.g., Why and how is a quantum computer faster than a regular computer? and quantum-computing.

Answer 2

You can condition quantum operations on unmeasured values, without measuring them. These are called controlled operations, and every quantum algorithm uses them.

For example, a crucial step in Grover's algorithm is toggling the phase of the system only if all qubits are on. Doing so does not measure every qubit, or do an aggregate "is it all on?" measurement. The superposition survives.

A more concrete example: take a system in the |00> state, hit the first qubit with a Hadamard gate so now we're in the |00>+|10> state, then hit the second qubit with a NOT controlled by the first qubit, so we go into the |00>+|11> state. Instead of destroying the superposition, the controlled operation helped us increase the amount of entanglement present.

However, don't think of controlled operations as magic beyond measurement. Controlled operations are very very similar to measurements. In fact, in some interpretations of quantum mechanics, measurements are controlled operations. It's just that controlled operations can have small controllable/reversible effects, but "measurement" implies dissipation into the environment and thus thermodynamic irreversibility.

Answer 3

If your question was about quantum algorithms and the paradigm of quantum computing, then there is a paper you might be interested in:

"A quantum algorithm for finding the minimum" by Durr and Hoyer https://arxiv.org/pdf/quant-ph/9607014.pdf

One pattern in quantum computing algorithms is yes, to set up the superposition of qubits as states in a register, operate on those (that is, gates operating on qubits that comprise the states), then take measurements.

The algorithm in the paper is a demonstration of the use of increasingly lowered thresholds and filtered initialized registers that are put through Grover's quantum number finding algorithm. Each iteration is followed by measurement of the first register and comparison to the threshold. The threshold is the minimum at some iteration and the total number of iterations is determined prior to the iterations to ensure success.
Using the algorithm on a list of numbers that have gaps in them, which could be a register holding pre-processed states, seems to need a larger register qubit width so the runtime complexity for input lists is larger than the usual quoted.

It looks like one of the main abilities of quantum computing will be or is combinatorial problems and what steps are needed to put the system into a certain state with high probability.

Note that if your question is hardware based, then the answer presumably depends upon the quantum computer implementation. There is a paper discussing sorting: "Sorting quantum systems efficiently" by Ionicioiu

If your question was instead about minimum of the amplitudes of all possible states at any given time (rather than the value of a state), then you'd probably be interested in the papers regarding error analysis in progress because that's an attempt to quantify the lowest probable state...

As a tangent, could consider that one of the goals is storing multiplicity of state. Atoms and molecules have rotational, vibrational, and electronic transitions and any such system needs a decent number of particles in the given state for good statistics and the system needs isolation of its parts. For example, using sound as a means to facilitate rotational transitions has as its challenge that being a pressure wave, it is quickly everywhere it can be when there is a medium to transport it. Using low frequency radiation has as its challenges the diffraction limit and near field effects... Lots of interesting research happening which may have different answers to your question.