Comment by n4r9 | Hacker News Reader

Comment by n4r9 | Hacker News Reader

Parent Full thread

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

[1] https://www.google.com/books/edition/Quantum_Machine_Learnin...

[2] https://arxiv.org/abs/1512.05903

[3] https://link.springer.com/article/10.1007/s002000050134

[4] https://quantumalgorithmzoo.org/

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-...

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.

> 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.

> 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.

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.

Yeah, I did mean that, and I stand by my opinion that even the ideal cases are not particularly compelling. I'm just also pointing out that the ideal case is not actually possible, even theoretically. There will also be decoherence, for example, and even the tomography of the state (i.e. actually measuring the state) is limited by fundamental quantum noise (e.g. ultimately the Heisenberg limit).

I guess it depends on what you find compelling. I'm not interested in finance. A lot of it just seems like moving money around to make wealthy people wealthier. But it does make sense that a lot of heads will perk up if there's a potential for speeding up market simulation models.

Also, just to add, 'quantumalgorithmszoo.org' is quite out of date: For example, they claim a polynomial speed-up for network flow, but that's based on the SOTA in 2007. These days, there's an almost-linear time classical algorithm [A], and no matching quantum algorithm (and also the idea that you would want to use a quantum computer to shave a factor n^(0.0001) is ridiculous). Now, all these statements are only about asymptotics, but don't get me started on practicalities: The idea that in the next 50 years you would use a quantum computer for any problem with only a polynomial speed-up is silly.

[A] https://www.quantamagazine.org/researchers-achieve-absurdly-...

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.

Reply on news.ycombinator.com