Quantum computing: Not for all problems?

[Omega0]

Please note: I am really a beginner in this field. If I write nonsense just let me know, I just gather information.

As far as I understood Quantum Computing is super fast but (this is basically my question) not suited to all kinds of engineering questions. As far as I know it should work best with big data, optimization (probably only with concave functions?) but not for generally crunch PDEs? Is that correct?
Additional question: Do you expect to have statistics calculated by it (Bayesian/Frequentist) and if which would be the advantage in calculation time?

 

[FactChecker]

I will not try to predict the future and will only talk about the current and near future. Quantum computers are so difficult to build and run that they will only be useful where they have a big advantage in computer speed. But that is not hard to imagine. Suppose you have a problem with $2^{100}$ equally likely possibilities to consider for finding a solution. That is too large a number for a conventional computer to try one at a time. If a conventional computer could test one trillion cases per second, it would still require 40 billion years to get through them all. The advantage of a quantum computer is that with 100 qubits it could (in theory, ideally) settle into the the solution in one step. That step might take an hour to set up, run, and process, but that still makes an impossible problem solvable. The types of problems that its capability can be applied to depend on how the qubits are configured and how the quantum chip is designed. Any configuration would require a lot more than the 100 qubits mentioned and different companies are taking very different approaches. Companies like IBM, Google, and D-Wave have very different designs and are targeted for very different problem types.

 

[Omega0]

Suppose you have a problem with $2^{100}$ equally likely possibilities to consider for finding a solution. That is too large a number for a conventional computer to try one at a time. If a conventional computer could test one trillion cases per second, it would still require 40 billion years to get through them all. The advantage of a quantum computer is that with 100 qubits it could (in theory, ideally) settle into the the solution in one step. That step might take an hour to set up, run, and process, but that still makes an impossible problem solvable.

Okay, but what is "the problem"? If I have an aerodynamic problem then I want to have for example the friction. I could use a simulation with Navier-Stokes for example. Or DNS. Or LES and what about moving boundary problems etc.

Can this quantum computer solve a problem which I define or does the pretty cool system solve problems which aren't mine?

 

[FactChecker]

They can't solve those types of problems yet. In fact, there are very few problems that they can solve, and each one takes a lot of human work to get it done. If you know about CFD, then you know that there are a lot of simultaneous equations that have to be satisfied all at once. Conventional computers often need "supercomputer" capability to solve them and even then, the solution leaves a lot to be desired. It is possible that one day the quantum computer will speed that up.
So the truth is that you might have to wait a decade or two before there is a satisfactory answer to your question.

 

[Baluncore]

Can this quantum computer solve a problem which I define or does the pretty cool system solve problems which aren't mine?

You must first translate or factor “your problem” into one that can be solved using “their hardware”.

Each trial result produced will be a singular bit pattern, with a probability of being a correct solution. You must increase your program complexity to refine your problem, or test each result to identify if it is the particular solution you are looking for.

Problems based on FEMs that produce huge amounts of data will not initially benefit because the output bandwidth of early QCs will be limited to a few hundred bits per second.

 

[jedishrfu]

There is a book called Programming Quantum Computers that may interest you:

https://www.amazon.com/dp/1492039683/?tag=pfamazon01-20

Quantum computing today is offered primarily as a service where your programs are run on other peoples quantum computer in a kind of batch mode. You submit your program, it gets scheduled and run and the results get returned to you.

Quantum Computing as personal computer hardware will likely appear as a coprocessor to a general purpose CPU not unlike the math coprocessor so popular in the early days of microprocessors before floating pt math logic was integrated into the CPU itself. You would interact with the general CPU and it would in turn setup and run your problem on the quantum computing hardware.

A key takeaway is how a problem is computed, operationally the qubits are setup into particular states, operations are applied to one or more qubits and the result is read back. This process is repeated many times and the results are aggregated together. The most common result found is the solution.

Another key takeaway is that quantum computing is limited by the number of operations that can be applied before the qubits lose coherence. This means that there will be some kind of upper limit on the types of problems solved due to the number of operations in the algorithm and the time to apply them.

 

[jedishrfu]

Here's an interesting youtube video on the latest in Quantum Computing

 

[FactChecker]

Here's an interesting youtube video on the latest in Quantum Computing

I am a fan of ExplainingComputers. His coverage of topics has always hit the spot for me.

 

[Omega0]

@FactChecker, @Baluncore , @jedishrfu

Navier-Stokes seems to me not that natural for a quantum computer... let us see (as far as I can see it is on the plan but perhaps in 15 years). So, what do you think about Lattice-Boltzmann for CFD? I mean it goes at least in the direction of QT (it is an application of group theory, basically, well...). I personally, if I might do a guess in the dark, would say this is more solid than non-linear systems of PDE's.
The same should be valid for solid state physics where we have a lot of QFT... right?

Thanks

 

[FactChecker]

@FactChecker, @Baluncore , @jedishrfu

Navier-Stokes seems to me not that natural for a quantum computer... let us see (as far as I can see it is on the plan but perhaps in 15 years). So, what do you think about Lattice-Boltzmann for CFD? I mean it goes at least in the direction of QT (it is an application of group theory, basically, well...). I personally, if I might do a guess in the dark, would say this is more solid than non-linear systems of PDE's.
The same should be valid for solid state physics where we have a lot of QFT... right?

Thanks

I think it is too early to speculate on such massive applications. But then, I am not an expert.

 

[pbuk]

LMGTFY

 

[Baluncore]

I am waiting for a Quantum Computer that can find an example to counter, and so disprove the Collatz 3n+1 Conjecture.
Has anyone yet come up with a QC program for that challenge?

 

[f95toli]

Quantum computers are "naturally" good at solving "quantum" problems; meaning the obvious examples of the type of problems that can be solved using a QC tend to come from quantum chemistry; which in turn of course also means applications in bio-medicine (which is why big pharma is investing in QC) and many other areas (surface science etc)

It turns out that there are also a number of quite generic optimisation problems that should see a significant speedup using a quantum computers. This is the area where you can find most use-cases since optimisation problems tend to pop up just about everywhere; the areas people talk about (because of where the money is) tend to be finance and logistics.

The third area is machine learning; this includes both "quantum machine learning" and using quantum computers to speed up training of networks. This is a very active area of research.

You then have a number of important "special cases" such as factorisation (including code breaking), database searches ec

The most "speculative" area is probably using quantum computers to solve "regular" problems from e.g. linear algebra which -if possible- would immediately give you a speedup for e.g. Navier-Stokes, FEM etc.

The problem here is that whereas algorithms do exist (see e.g .the HHL algorithm for linear systems of equations) the overheads are so huge that not only would you need an enormous amount of qubits, but you would never see an actual speedup. One of the main "problems" is simply that the classical algorithms are so good that your QC algorithm needs to be extremely good (ideally better than linear) to be worth using in real life or the inevitable added overheads involved in using a QC will cancel out any gains.

 

[pbuk]

The problem here is that whereas algorithms do exist (see e.g .the HHL algorithm for linear systems of equations) the overheads are so huge that not only would you need an enormous amount of qubits, but you would never see an actual speedup.

That was my first thought too, however the very first article found in the search I linked above indicated a quadratic or even exponential improvement over classical algorithms:

We examined the computational complexity of the quantum PDE algorithm and compared it to the complexity of classical random and deterministic algorithms. We saw that there is a quantum speed-up for rough/non-smooth flows (which is the computationally interesting/difficult case) and showed that a regime exists, where the speed-up is quadratic (exponential) over classical random (deterministic) algorithms. This suggests that the quantum Navier–Stokes algorithm run on a scalable quantum computer may provide a quantum speed-up for direct numerical simulation of fully-developed turbulence at large Reynolds number which track the flow dynamics from the integral-scale down to the Kolomogorov-scale.

 

[fresh_42]

That was my first thought too, however the very first article found in the search I linked above indicated a quadratic or even exponential improvement over classical algorithms:

As far as I understand it, it depends on how parallelizable an algorithm is. You can test arbitrary many settings of a SAT formula simultaneously, but I don't see how to shortcut millions of approximation steps to get a vector field from Navier-Stokes. Maybe the consideration of many initial values at once can give an advantage, but what if only one is given?

 

[f95toli]

That was my first thought too, however the very first article found in the search I linked above indicated a quadratic or even exponential improvement over classical algorithms:

I am not familiar with that paper. However, looking it at it seems like the idea is that they've come up with a quantum algorithm specifically for these equations; they wouldn't be using a general purpose solver
The difference is important; if we could develop say a QC version of LINPACK that gave a huge speedup we could then take just about any problem that is e.g. based on FEM and solve it much faster. Right now, with the exception for optimisation, all QC algorithms that give a speedup are special cases.

 

[Omega0]

I am waiting for a Quantum Computer that can find an example to counter, and so disprove the Collatz 3n+1 Conjecture.
Has anyone yet come up with a QC program for that challenge?

You will very likely have found this: Quanta Magazine Collatz Conjecture
I think it is a very interesting approach to think about SAT instead of our beloved decimal numbers. Nevertheless, I am a bit sceptical if this has a future (which basicaly doesn't mean a lot because I am not an expert in this field).

 

[Baluncore]

I think it is a very interesting approach to think about SAT instead of our beloved decimal numbers. Nevertheless, I am a bit sceptical if this has a future (which basicaly doesn't mean a lot because I am not an expert in this field).

Any attempt to prove by SAT, that the conjecture is true or false, is welcome. So long as it fails, it will refine the art of SAT.

The numerical search for an exception avoids decimal numbers, it uses binary. That way, the two operations are; if even, shift the binary number right; if odd, set carry, shift left and accumulate.
The numerical search for an exception has passed 2^68. If a loop exists, then it must contain over 10^9 elements before a repeat. Testing will follow the rising limit of hardware performance.

If a counter-example is ever found that leads to a closed loop, that will numerically prove the conjecture false, and explain why proof of the conjecture was impossible. The numerical and the SAT approaches should run independently, in a parallel competition.

The Collatz Conjecture is a good exercise that tests and extends the development of numerical hardware, number theory, CAS and SAT techniques, and hopefully QC.

There are many minds, with many irons in the fire, but somehow I hope the beautiful conjecture can remain on the very edge of the endangered list, defend itself, and never be slain.

 

[FactChecker]

I think this is a good summary of the current status of quantum programming in 2021: ExplainingComputers, Quantum Computing 2021 Update

 

[Hornbein]

When I found out that quantum computers were of no help with the traveling salesman problem, I gave up trying to understand what they can or can't do.

I can say though that quantum computers should excel at simulating quantum systems. They will revolutionize chemistry. I believe these are the applications Feynman had in mind when he came up with the idea.

"Programming" a quantum computer is very hard. The papers read about this seemed to be saying "we'll figure it out later."

 

[FactChecker]

When I found out that quantum computers were of no help with the traveling salesman problem, I gave up trying to understand what they can or can't do.

I would think that the traveling salesman problem would be a very good application of quantum computers like the D-Wave machine when they become mature. I do not know how well the current integer programming algorithms work, but I think that they are limited.

 

[f95toli]

When I found out that quantum computers were of no help with the traveling salesman problem, I gave up trying to understand what they can or can't do.

I don't think that is correct. I do know that there is a quite a lot of debate about this, but I don't think it has been settled one way or another.

Also, it might be possible to get a speedup using annealing (which is what D-Wave is using); but AFAIK no one has been able to prove this (this is a general issue with annealing; it is extremely hard to predict the performance of algorithms)

That said, it is generally true that we don't know which problems quantum computers will be better at than for classical computers. This is hardly surprising given that we don't have a general answer for that for classical computers either; it is always possible that someone will come up with a more efficient algorithm to solve a given problem.
There are have already been a a couple of examples of a quantum annealler outperforming a classical computer only for someone to come up with a better classical algorithm.

 

[Hornbein]

I looked it up. A quantum computer can't solve the traveling salesman problem in polynomial time. It helps but there will always be some size that is intractable.

 

[fresh_42]

I looked it up. A quantum computer can't solve the traveling salesman problem in polynomial time. It helps but there will always be some size that is intractable.

Reference?

 

[f95toli]

I looked it up. A quantum computer can't solve the traveling salesman problem in polynomial time. It helps but there will always be some size that is intractable.

Again, this is not settled.
Also, the amount of speedup is very likely to depend on what type of quantum computer you are using: A NISQ QC, error-corrected QC, annealer or simulator

The algorithms are different for the different types, so whereas it is e.g. highly unlikely that a NISQ (hybrid) algorithm would give you any real-life speedup it does not automatically follow that an annealer would not.

There are lots of algorithm papers coming out and as far as I am aware the traveling salesman problem is still very much an problem being actively researched.

 

[sbrothy]

I'm obviously completely clueless compared to you guys but did you notice this when it appeared in popular science:https://daydaynews.cc/en/technology/884083.html

Please don't kill the messenger. I think it's related to this paper:

A quantum-inspired classical algorithm for recommendation systems.

and:

https://arxiv.org/a/tang_m_1.html

At the time it sounded like it almost "killed" the whole quantum computer idea but ofcourse I really have no idea.

It's like the problems quantum computers can solve are narrowing more and more.

 

[FactChecker]

I'm obviously completely clueless compared to you guys but did you notice this when it appeared in popular science:https://daydaynews.cc/en/technology/884083.html

Please don't kill the messenger. I think it's related to this paper:

A quantum-inspired classical algorithm for recommendation systems.

and:

https://arxiv.org/a/tang_m_1.html

At the time it sounded like it almost "killed" the whole quantum computer idea but ofcourse I really have no idea.

It's like the problems quantum computers can solve are narrowing more and more.

Kill the messenger!
It's a very complicated thing. It is possible that there will be an algorithm that allows traditional computers to compete with quantum computers on a given problem where quantum supremacy had been claimed. But what if examples of claimed quantum supremacy become routine and each one requires decades before a genius can develop a competitive algorithm for the standard computers. That seems to be the case for this example. I would still consider it a great advancement due to quantum computers.

 

[f95toli]

The claims in the article are (surprise! ) wildly exaggerated

This is not even the first time this has happened; some of the early results on the D-Wave machines initially suggested that they might be faster than a conventional computers but this inspired improvements to classical algorithms to the point where you could run problems that previously needed a supercomputer on a laptop.

You simply can't draw any conclusions from a specific problem; there are a number of problems where it is widely believed that quantum computers should be much faster than a classical computer; but this belief is of course to a large extent based on the fact that people have been trying-and failing- to come up with efficient classical algorithms for a long time. It does not mean that someone -in principle- couldn't come up with a better algorithm tomorrow.
It also does not mean that someone then in turn couldn't come up with a better quantum algorithm etc.