3 ms·

As I understand from Wikipedia there are four fundamental quantum algorithms that perform better in some way than the best-known classical counterparts, and man

by n4r9 3y ago

As I understand from Wikipedia there are four fundamental quantum algorithms that perform better in some way than the best-known classical counterparts, and many more algorithms in total. The four fundamental ones are: * HHL algorithm for solving (sparse & insensitive) systems of linear equations * Grover's search algorithm for determining black-box inputs * Shor's algorithm for factoring primes * Quantum fourier transforms The above have various potential applications such as: * Deep learning [0] * Finance [1] * Solving large-dimensional differential equations [2] * Solving constraint satisfaction problems [3] I also came across a webpage called Quantum Algorithm Zoo [4] which looks like it answers your question in much more detail. [0] https://arxiv.org/abs/1806.11463 https://arxiv.org/abs/1806.11463 [1] https://www.google.com/books/edition/Quantum_Machine_Learning_and_Optimisatio/22SXEAAAQBAJ?hl=en&gbpv=1&pg=PA349 https://www.google.com/books/edition/Quantum_Machine_Learnin... [2] https://arxiv.org/abs/1512.05903 https://arxiv.org/abs/1512.05903 [3] https://link.springer.com/article/10.1007/s002000050134 https://link.springer.com/article/10.1007/s002000050134 [4] https://quantumalgorithmzoo.org/ https://quantumalgorithmzoo.org/

varelse 3y ago
[dead]
okintheory 3y ago
You should be very skeptical of all those applications except Shor. HHL: Here's a quote from Ewin Tang [1]: "We know that quantum computers can “efficiently solve” high-dimensional linear algebra problems; however, this assumes that we have some way to evolve a quantum system precisely according to input data, a much harder problem than the linear algebra itself." [1] https://ewintang.com/blog/2019/01/28/an-overview-of-quantum-inspired-sampling/#fn:hhl08 https://ewintang.com/blog/2019/01/28/an-overview-of-quantum-... Grover's search: This is a speed-up from 2^n to 2^sqrt(n). Impressive, but there's not a lot of exp-time algorithms that people ever run. They go for heuristics instead. Quantum fourier transforms: This is a tool, it's cool, but needs an application. I haven't seen a serious proposal for using it somewhere where a classical algorithm wouldn't do better.
- n4r9 3y ago
  > this assumes that we have some way to evolve a quantum system precisely according to input data, a much harder problem than the linear algebra itself That's a fair point. I guess I was interpreting OP's question as "what can we do once we have engineered quantum computers", and would categorise this "harder problem" as an engineering problem.
  - bowsamic 3y ago
    > would categorise this "harder problem" as an engineering problem. I'm not sure what your relation to the field is, but I have found that a lot of things that look like engineering problems from the outside, end up being theoretical and fundamental problems from within. This is often the case when I discuss quantum noise of gravitational wave detectors. I often see people say things like "I wouldn't want to be the guy who has to make these gravitational wave detectors less noisy", almost implying it's just a case of one guy sitting there turning some knobs, but in reality it's thousands of physicists coming up with entirely new theoretical frameworks, often discovering fundamental issues of quantum measurement and control theory (quantum non demolition measurements, quantum squeezing, back action evasion, etc.), or coming up with the most sensitive seismometers ever, or developing new mirror coatings, etc. Everyone thought that Apple's cancelled wireless charger was just an engineering problem, but it turned out that it seems to be physically impossible to achieve what they wanted. That said, perhaps in this case you are right, but it's not often obvious what is simply a matter of time and what requires whole new paradigms.
    - n4r9 3y ago
      Again, a totally fair point. I just mean that when you posed the question "what exactly are quantum computers useful for?", I kind of assumed you meant an ideal quantum computer that had this kind of control over its state. For reference I am out of my depth! My doctorate was in quantum information theory but I've been out of academia for many years now.
      - bowsamic 3y ago
bowsamic 3y ago
The most well known of those is Shor's algorithm and yet it's still extremely difficult to scale. The problem is that quantum computers, like any quantum system, are so difficult to control without introducing massive decoherence (EDIT: mixing with the environment and thus destroying any relevant "quantumness"), that they are almost impossible to scale. It is indeed interesting that it's even theoretically possible to create quantum algorithms that are better than classical ones, but that doesn't mean it's practically useful. The latter is the relevant metric for bothering with "the assembly line". What you are talking about is still firmly within the realms of academia.

by n4r9 3y ago

varelse 3y ago

[dead]

okintheory 3y ago

You should be very skeptical of all those applications except Shor. HHL: Here's a quote from Ewin Tang [1]: "We know that quantum computers can “efficiently solve” high-dimensional linear algebra problems; however, this assumes that we have some way to evolve a quantum system precisely according to input data, a much harder problem than the linear algebra itself." [1] https://ewintang.com/blog/2019/01/28/an-overview-of-quantum-inspired-sampling/#fn:hhl08 https://ewintang.com/blog/2019/01/28/an-overview-of-quantum-... Grover's search: This is a speed-up from 2^n to 2^sqrt(n). Impressive, but there's not a lot of exp-time algorithms that people ever run. They go for heuristics instead. Quantum fourier transforms: This is a tool, it's cool, but needs an application. I haven't seen a serious proposal for using it somewhere where a classical algorithm wouldn't do better.

n4r9 3y ago
> this assumes that we have some way to evolve a quantum system precisely according to input data, a much harder problem than the linear algebra itself That's a fair point. I guess I was interpreting OP's question as "what can we do once we have engineered quantum computers", and would categorise this "harder problem" as an engineering problem.
- bowsamic 3y ago
  > would categorise this "harder problem" as an engineering problem. I'm not sure what your relation to the field is, but I have found that a lot of things that look like engineering problems from the outside, end up being theoretical and fundamental problems from within. This is often the case when I discuss quantum noise of gravitational wave detectors. I often see people say things like "I wouldn't want to be the guy who has to make these gravitational wave detectors less noisy", almost implying it's just a case of one guy sitting there turning some knobs, but in reality it's thousands of physicists coming up with entirely new theoretical frameworks, often discovering fundamental issues of quantum measurement and control theory (quantum non demolition measurements, quantum squeezing, back action evasion, etc.), or coming up with the most sensitive seismometers ever, or developing new mirror coatings, etc. Everyone thought that Apple's cancelled wireless charger was just an engineering problem, but it turned out that it seems to be physically impossible to achieve what they wanted. That said, perhaps in this case you are right, but it's not often obvious what is simply a matter of time and what requires whole new paradigms.
  - n4r9 3y ago
    Again, a totally fair point. I just mean that when you posed the question "what exactly are quantum computers useful for?", I kind of assumed you meant an ideal quantum computer that had this kind of control over its state. For reference I am out of my depth! My doctorate was in quantum information theory but I've been out of academia for many years now.
    - bowsamic 3y ago

bowsamic 3y ago

The most well known of those is Shor's algorithm and yet it's still extremely difficult to scale. The problem is that quantum computers, like any quantum system, are so difficult to control without introducing massive decoherence (EDIT: mixing with the environment and thus destroying any relevant "quantumness"), that they are almost impossible to scale. It is indeed interesting that it's even theoretically possible to create quantum algorithms that are better than classical ones, but that doesn't mean it's practically useful. The latter is the relevant metric for bothering with "the assembly line". What you are talking about is still firmly within the realms of academia.