How do quantum computers find a solution?

In summary: This is the case of Grover's algorithm, a famous quantum algorithm for searching in an unstructured database.Finally, answering your third question, it is not necessary to have all the information about the possible solutions beforehand, as we can program algorithms that will work for a whole set of similar problems, but we need to have some prior knowledge about the problem we want to solve. Also, quantum computers are really good for optimization problems, where we can use the quantum state to represent the possible configurations of the solution, and the quantum gates to manipulate them, so the quantum algorithm will converge to the correct solution or an approximation of it. In this case, we don't need to have previous information about the solution space, but we
  • #1
ngrunenberg
9
2
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.
 
Physics news on Phys.org
  • #2
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.
 
  • Like
Likes gentzen, msumm21, Demystifier and 2 others
  • #3
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?
 

Related to How do quantum computers find a solution?

1. How do quantum computers work?

Quantum computers use the principles of quantum mechanics to process and store information. Unlike classical computers that use bits (0s and 1s) to represent data, quantum computers use quantum bits or qubits, which can exist in multiple states simultaneously. This allows quantum computers to perform multiple calculations at once and find solutions much faster than classical computers.

2. What is the difference between classical and quantum computers?

The main difference between classical and quantum computers is the way they process information. Classical computers use bits to represent data and perform calculations sequentially, while quantum computers use qubits and can perform multiple calculations simultaneously. This makes quantum computers much faster and more efficient for certain types of problems, such as optimization and simulation.

3. How do quantum computers find a solution?

Quantum computers use a process called quantum annealing or quantum algorithms to find a solution to a problem. Quantum annealing involves finding the lowest energy state of a quantum system, which corresponds to the optimal solution of the problem. Quantum algorithms use mathematical algorithms specifically designed for quantum computers to find solutions to complex problems.

4. What types of problems can quantum computers solve?

Quantum computers are well-suited for solving optimization problems, such as finding the shortest route between multiple points or optimizing supply chain logistics. They can also be used for simulation and modeling, such as predicting the behavior of complex systems like molecules or financial markets. Quantum computers are not suitable for all types of problems, and it is important to determine if a problem can benefit from quantum computing before attempting to use it.

5. How do quantum computers handle errors?

Quantum computers are prone to errors due to the fragile nature of qubits. To address this, quantum computers use error correction techniques, such as quantum error correction codes and error mitigation algorithms, to reduce the impact of errors on the final result. Additionally, quantum computers have built-in error correction capabilities, such as quantum error correction circuits, to detect and correct errors during the computation process.

Similar threads

  • Quantum Physics
Replies
4
Views
766
Replies
1
Views
711
Replies
8
Views
951
  • Quantum Physics
Replies
8
Views
1K
Replies
2
Views
1K
Replies
1
Views
778
  • Quantum Physics
Replies
2
Views
1K
  • Quantum Physics
Replies
2
Views
1K
  • Quantum Physics
Replies
17
Views
1K
Replies
33
Views
4K
Back
Top