Can anyone expound further on the practical applications of quantum computing? In my limited understanding, I think the following are definitely candidates (presented in no particular order), but I'm sure there are others:
1. Shor's algorithm could expose all encryption algorithms that are based on integer factorization.
2. Quantum simulation could open new avenues of research into how our universe operates at the quantum level. This could lead to advancements in materials science, for example.
3. Quantum computing could open new avenues of research into the P versus NP problem.
4. Quantum computing could open the door to the possibility of instantaneous communication via an understanding of action at a distance / quantum entanglement.
Edit: Thanks for all of the great responses, clarifications and links to further reading.
3. P vs. NP is a problem phrased in the language of classical Turing machines. In that sense, quantum computing has no bearing on it. It is unknown whether NP problems can be solved efficiently on quantum computers.
4. Is a common misunderstanding about entanglement. Unfortunately, while entanglement does allow non-classical long-distance correlations, it does not allow for communication. Think of it this way: suppose we took two random number generators that start with the same seed, and thus produce the same stream of bits. Then you take yours over there while I keep mine over here. This doesn't help us communicate faster, because we don't get to pick the bits that come out of the generator. So too with quantum entanglement.
Isn't one of the main idea of entanglement/superposition the fact that the qubits' values are not pre-determined? I.e. the two random generators don't have the same actual seed, but as soon as the first one is used, it generates a seed, and the second one will also use the same seed from then on?
I still have some difficulty understanding how that doesn't rule out some undetectable determinism, and how/if it's possible to measure if the superposition has already collapsed (i.e. the seed has already been determined), something apparently useful in quantum encryption.
Right, s/he's giving you a sense of "classical entanglement", but quantum entanglement can also do some interesting things which classical entanglement cannot do. However, the scope of that is not as simple as "set those bits over there to an arbitrary state as seen from over here." In fact, if my bits over here are entangled with your bits over there, the entanglement manifests in spooky coincidences between our actions which you won't even notice if you don't bring our actions together and compare them. From our perspectives individually it looks like we're both doing random actions; but then you find out that when you bring the actions lists back together they were both the same; neither of us had the chance to predict or affect what the other one did but we both agreed on what we did.
Here's a game for a three-person team: they are all cooperating, but the game is called "betrayal" because we will secretly force one of them to betray the other two and measure how gracefully they recover from it. We will put the team through many "tests", if they win all of them, they get lots of money; you don't get any money for being a traitor in any given test.
Here's how this goes. We put everybody in relativistically separated rooms; each room has a computer screen and two buttons labeled 0 and 1. Once they're all isolated we give the group a test. Then they can come back together and collaborate before the next test, as they see fit.
Some tests are "control" tests. We flash on the screen, simultaneously to all 3 of them, the command "make the sum of your numbers even." We collect the 1's and 0's together, add them together, and they pass the test if it's even.
Other tests, we randomly choose one as a traitor. We flash on the screen to the traitor the same "make the sum of your numbers even" prompt, but we flash to the other two, "traitor round! make the sum of your numbers odd" -- and they pass the test if, when we add together the three numbers they press, that sum is odd.
There's no classical probability distribution on the six random variables A_even, B_even, C_even, A_odd, B_odd, C_odd which satisfies all of those tests 100% of the time, so that A_even + B_even + C_even is even but A_odd + B_odd + C_even is odd and so forth. Just add all of the equations together; you'll get 2 * (A_e + B_e + C_e + A_o + B_o + C_o) on the left hand side, but (even + 3*odd) on the right hand side and thus even = odd, which is impossible. There is no classical 100%-solution.
There is a quantum 100%-solution. If |+> is the state |0> + |1> and |−> is the state |0> − |1> then the (entangled, GHZ) state
|+++> + |−−−> = |000> + |011> + |101> + |110>
guarantees that any measurement will have an even sum, while the state
|+++> − |−−−> = |001> + |010> + |100> + |111>
guarantees that any measurement will have an odd sum. The two people who know there is a traitor in their midst can do the unitary transform which takes |+> to |+> and |−> to i |−> (which is a "controlled phase rotation" combined with some "Hadamard gates"), and this defining property of complex numbers that i^2 = -1 causes the total state to switch between those two parameters when any two people make those transformations.
So if they're playing with an entangled quantum state, two of them can make a local change to their own state which induces the right sort of change in the global state that, when we bring the data together and correlate, we find out that they can do something which classical observers cannot ever do: win a game with 100% probability. Each of them locally appears to be producing 0 or 1 with a 50/50 probability but globally when we compare their bits we find out that they could choose together whether that sum was odd or even in a crazy new way.
http://en.wikipedia.org/wiki/Bell%27s_theorem tells us that no matter how much classical information you have, you still can't get correlations that are as good as quantum entanglement.
If we have quantum computers, then isn't P vs. NP the wrong question? With quantum computers, the more relevant problem to study should be BQP versus QMA (the quantum analogs of P and NP/MA, i.e., computable versus verifiable in polynomial time on a quantum computer). Are complexity theorists studying the wrong problem?
Can anyone expound further on the practical applications of quantum computing?
My research is in molecular dynamics simulations and quantum chemistry. A lot of progress has been made in the field in the last few decades; however, there is a roadblock right now that no one really knows how to get around called the fermion sign problem. If we want to simulate atoms or molecules as accurately as we can, the number of resources we require scales exponentially with the number of particles. This is basically due to the Coulombic (electrostatic) interactions between the electrons in the atom. Accounting for these interactions gives many materials their interesting properties, but we've only been able to come up with approximations for solving these systems.
Quantum computing would allow these systems to be solved in polynomial time. The advantage would be enormous; in some cases, atomic simulation results would match experimental ones exactly†, and that is a very exciting notion.
It seems clear that quantum computing would help with QM calculations (which I think you were mainly talking about), but it is less clear to me if it would help with things like MD (and perhaps it wouldn't matter if QM could be sped up enough).
Could quantum computing help with MD or other kinds of simulations (e.g. monte carlo) where we are essentially searching for a minima? I have heard that quantum annealing, which some argue the first QC system are really doing, would work on this. But it's all too confusing. It seems like half of what I read about quantum computing would say "Yes!" to that, and half is saying "you don't understand".
It could help with MD. A lot of MD potentials are developed by kind of regressing results from QM calculations for different atomic configurations (e.g. some versions of ReaxFF are based off of DFT calculations).
I actually don't know a whole lot about how exactly QC speeds up computations for things like Quantum Monte Carlo, I just know that an algorithm exists for it (much like Shor's algorithm speeds up integer factorization, but the details are murky for me). I'll have to see if I can find which paper that is.
Quantum Machine Learning would be drastically sped up, as many linear operations could be done in log(N): http://arxiv.org/abs/1307.0411
A quantum machine learning computer could make scientific advances simply by processing large datasets at rate dramatically faster than humans and/or current machine learning systems.
Comments
Can anyone expound further on the practical applications of quantum computing? In my limited understanding, I think the following are definitely candidates (presented in no particular order), but I'm sure there are others:
1. Shor's algorithm could expose all encryption algorithms that are based on integer factorization.
2. Quantum simulation could open new avenues of research into how our universe operates at the quantum level. This could lead to advancements in materials science, for example.
3. Quantum computing could open new avenues of research into the P versus NP problem.
4. Quantum computing could open the door to the possibility of instantaneous communication via an understanding of action at a distance / quantum entanglement.
Edit: Thanks for all of the great responses, clarifications and links to further reading.
3. P vs. NP is a problem phrased in the language of classical Turing machines. In that sense, quantum computing has no bearing on it. It is unknown whether NP problems can be solved efficiently on quantum computers.
4. Is a common misunderstanding about entanglement. Unfortunately, while entanglement does allow non-classical long-distance correlations, it does not allow for communication. Think of it this way: suppose we took two random number generators that start with the same seed, and thus produce the same stream of bits. Then you take yours over there while I keep mine over here. This doesn't help us communicate faster, because we don't get to pick the bits that come out of the generator. So too with quantum entanglement.
Isn't one of the main idea of entanglement/superposition the fact that the qubits' values are not pre-determined? I.e. the two random generators don't have the same actual seed, but as soon as the first one is used, it generates a seed, and the second one will also use the same seed from then on?
I still have some difficulty understanding how that doesn't rule out some undetectable determinism, and how/if it's possible to measure if the superposition has already collapsed (i.e. the seed has already been determined), something apparently useful in quantum encryption.
Right, s/he's giving you a sense of "classical entanglement", but quantum entanglement can also do some interesting things which classical entanglement cannot do. However, the scope of that is not as simple as "set those bits over there to an arbitrary state as seen from over here." In fact, if my bits over here are entangled with your bits over there, the entanglement manifests in spooky coincidences between our actions which you won't even notice if you don't bring our actions together and compare them. From our perspectives individually it looks like we're both doing random actions; but then you find out that when you bring the actions lists back together they were both the same; neither of us had the chance to predict or affect what the other one did but we both agreed on what we did.
Here's a game for a three-person team: they are all cooperating, but the game is called "betrayal" because we will secretly force one of them to betray the other two and measure how gracefully they recover from it. We will put the team through many "tests", if they win all of them, they get lots of money; you don't get any money for being a traitor in any given test.
Here's how this goes. We put everybody in relativistically separated rooms; each room has a computer screen and two buttons labeled 0 and 1. Once they're all isolated we give the group a test. Then they can come back together and collaborate before the next test, as they see fit.
Some tests are "control" tests. We flash on the screen, simultaneously to all 3 of them, the command "make the sum of your numbers even." We collect the 1's and 0's together, add them together, and they pass the test if it's even.
Other tests, we randomly choose one as a traitor. We flash on the screen to the traitor the same "make the sum of your numbers even" prompt, but we flash to the other two, "traitor round! make the sum of your numbers odd" -- and they pass the test if, when we add together the three numbers they press, that sum is odd.
There's no classical probability distribution on the six random variables A_even, B_even, C_even, A_odd, B_odd, C_odd which satisfies all of those tests 100% of the time, so that A_even + B_even + C_even is even but A_odd + B_odd + C_even is odd and so forth. Just add all of the equations together; you'll get 2 * (A_e + B_e + C_e + A_o + B_o + C_o) on the left hand side, but (even + 3*odd) on the right hand side and thus even = odd, which is impossible. There is no classical 100%-solution.
There is a quantum 100%-solution. If |+> is the state |0> + |1> and |−> is the state |0> − |1> then the (entangled, GHZ) state
guarantees that any measurement will have an even sum, while the state guarantees that any measurement will have an odd sum. The two people who know there is a traitor in their midst can do the unitary transform which takes |+> to |+> and |−> to i |−> (which is a "controlled phase rotation" combined with some "Hadamard gates"), and this defining property of complex numbers that i^2 = -1 causes the total state to switch between those two parameters when any two people make those transformations.So if they're playing with an entangled quantum state, two of them can make a local change to their own state which induces the right sort of change in the global state that, when we bring the data together and correlate, we find out that they can do something which classical observers cannot ever do: win a game with 100% probability. Each of them locally appears to be producing 0 or 1 with a 50/50 probability but globally when we compare their bits we find out that they could choose together whether that sum was odd or even in a crazy new way.
http://en.wikipedia.org/wiki/Bell%27s_theorem tells us that no matter how much classical information you have, you still can't get correlations that are as good as quantum entanglement.
If we have quantum computers, then isn't P vs. NP the wrong question? With quantum computers, the more relevant problem to study should be BQP versus QMA (the quantum analogs of P and NP/MA, i.e., computable versus verifiable in polynomial time on a quantum computer). Are complexity theorists studying the wrong problem?
My research is in molecular dynamics simulations and quantum chemistry. A lot of progress has been made in the field in the last few decades; however, there is a roadblock right now that no one really knows how to get around called the fermion sign problem. If we want to simulate atoms or molecules as accurately as we can, the number of resources we require scales exponentially with the number of particles. This is basically due to the Coulombic (electrostatic) interactions between the electrons in the atom. Accounting for these interactions gives many materials their interesting properties, but we've only been able to come up with approximations for solving these systems.
Quantum computing would allow these systems to be solved in polynomial time. The advantage would be enormous; in some cases, atomic simulation results would match experimental ones exactly†, and that is a very exciting notion.
(†glossing over a huge number of details here)
It seems clear that quantum computing would help with QM calculations (which I think you were mainly talking about), but it is less clear to me if it would help with things like MD (and perhaps it wouldn't matter if QM could be sped up enough).
Could quantum computing help with MD or other kinds of simulations (e.g. monte carlo) where we are essentially searching for a minima? I have heard that quantum annealing, which some argue the first QC system are really doing, would work on this. But it's all too confusing. It seems like half of what I read about quantum computing would say "Yes!" to that, and half is saying "you don't understand".
It could help with MD. A lot of MD potentials are developed by kind of regressing results from QM calculations for different atomic configurations (e.g. some versions of ReaxFF are based off of DFT calculations).
I actually don't know a whole lot about how exactly QC speeds up computations for things like Quantum Monte Carlo, I just know that an algorithm exists for it (much like Shor's algorithm speeds up integer factorization, but the details are murky for me). I'll have to see if I can find which paper that is.
Check this out:
http://arxiv.org/abs/1406.4920
#4 shouldn't be possible according to the No-Communication Theorem.
http://en.wikipedia.org/wiki/No-communication_theorem
Quantum Machine Learning would be drastically sped up, as many linear operations could be done in log(N): http://arxiv.org/abs/1307.0411
A quantum machine learning computer could make scientific advances simply by processing large datasets at rate dramatically faster than humans and/or current machine learning systems.
This one is good too:
"Quantum algorithms for topological and geometric analysis of big data" http://arxiv.org/abs/1408.3106
It uses some of this "applied topology", which I only recently found out about. http://www.math.upenn.edu/~ghrist/notes.html
One neat trick is "storing bandwidth".
http://strilanc.com/quantum/2014/05/03/Storing-Bandwidth-wit...