B How do quantum computers find a solution?

[ngrunenberg]

TL;DR Summary

Scott Aaronson talked about how quantum computers work by "choreographing amplitudes"; what exactly did he mean by that? Do we need to know most of the answer before a quantum computer is of any use?

Apologies in advance if this is a stupid question, I'm not the brightest. I recently listened to Scott Aaronson's conversation with Lex Fridman, and an interview he did for Scientific American, regarding quantum computing (QC from now on) and have a question regarding how a QC finds a solution.

This is an excerpt from the interview:

"In particular, if an event can happen one way with a positive amplitude, and another way with a negative amplitude, those two amplitudes can “interfere destructively” and cancel each other out, so that the event never happens at all. The goal, in quantum computing, is always to choreograph things so that for each wrong answer, some of the paths leading there have positive amplitudes and others have negative amplitudes, so they cancel each other out, while the paths leading to the right answer reinforce."¹

My question(s) is the following:

I) When he talks about choreographing amplitudes, is he essentially saying that we take a problem with a vast solution space, of which we know a large subset of true and false solutions, and try to "collapse" the correct wave function by cancelling out what we assume to be false values and reinforcing amplitudes that converge toward the correct answer; then hope the final measurement "collapsed" the correct solutions' wave function?

II) If that is the case, do we square the amplitude of that solution, as we do in physics, to get a probability? If so, does that mean we only get a value for the probability of that particular solution being the right one?

III) If we have to know so much about the solution in the first place and the challenge is programming an algorithm to get the correct solution, would it be impossible to have novel solutions to problems in which we have no epistemological priors about the possible solution space? Apologies again if this is a silly question and thank you in advance for taking the time to answer it.

 

[Jaime_mc2]

I think those are interesting questions and I will try to answer it briefly but with enough explanations. Also, consider that I'm not an expert in this area, so I may be wrong in some details, although I have been studying quantum computing seriously for some time for my master thesis, so I would appreciate any correction on my answer.

Quantum computing deals with the evolution of qubits, which can be expressed as the superposition of the classical binary states as
$$ |\psi\rangle = \alpha |0\rangle + \beta |1\rangle\ . $$
Answering your second question, yes, the coefficients of the base states have the same meaning as in quantum physics. This means that when we measure the state $|\psi\rangle$, the probability of getting a 0 is $|\alpha|^2$, and the probability of getting a 1 is $|\beta|^2$. Also, this should be true for any qubit:
$$|\alpha|^2+|\beta|^2=1\ .$$

When we want to design a quantum algorithm to solve a problem, usually we work with more than one qubit, called a quantum register, whose state is the combination (tensor product) of each individual qubit if we are not dealing with quantum entanglement. At the beginning of the algorithm, we usually have a quantum register in a known state, e.g. $|00\dots0\rangle$, and the goal is to apply some operations to it until we get a final state which corresponds to the desired solution.

Regarding your first question, the general expression for the state of a quantum register of length $n$, after some operations, is
$$
|\psi\rangle = \sum_{i=0}^{2^n-1} c_i |i\rangle\ ,
$$
where the probability of getting the number or state $|i\rangle$ is $|c_i|^2$. Therefore, a quantum algorithm should play with the amplitudes in a way that, after some steps, if the correct answer is $|j\rangle$, then $|c_j|^2 = 1$. This is usually achieved by interference between many states. For example, if a given state $|i\rangle$ appears two times in the description of the whole state after an operation, but with opposite amplitude, then $c_i|i\rangle - c_i|i\rangle$ will cancel out, and the rest of the states will increase their probabilities. This is exactly the kind of choreography that we are looking for. If you want an easy example of this effect, I would recommend you to read about the Deutsch and Deutsch-Jozsa algorithms.

However, this is not always possible, or we didn't imagine such an algorithm that would ensure the cancelation of all the amplitudes but the one corresponding to the correct solution of a given problem. Then, another approach is to help the amplitudes of the states corresponding to correct solutions to increase, while decreasing the others, and loop over it many times, until we can ensure that we have enough probabilities of getting the right answer, let's say a 90% just as an example. In this case, running the algorithm a couple of times will lead to the measure of the correct solution with very high probability. A good example of this method is the Grover search algorithm, where we just know which properties should have the correct result, and that is used to let the algorithm modify the amplitudes of all the states according to what we want to get.

I hope this helps you to answer your questions.

 

[ngrunenberg]

Thank you so much for such a detailed response, you helped clear up a lot of the misconceptions I had about quantum computing. I will definitely dive deeper into the algorithms mentioned above.

One follow up question; would it be more challenging to devise an algorithm as the number of qubits in the system increases? Or would the solution with a higher qubit count be more reliable and require fewer re-loops?