Quantum computing: Not for all problems?

  • Thread starter Omega0
  • Start date
  • #1
173
27
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?
 

Answers and Replies

  • #2
FactChecker
Science Advisor
Gold Member
6,578
2,644
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.
 
  • #3
173
27
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?
 
  • #4
FactChecker
Science Advisor
Gold Member
6,578
2,644
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.
 
  • #5
Baluncore
Science Advisor
9,864
4,268
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.
 
  • #6
13,116
6,999
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.
 
  • Like
  • Informative
Likes Omega0 and fresh_42
  • #7
13,116
6,999
Here's an interesting youtube video on the latest in Quantum Computing

 
  • Like
Likes FactChecker and Omega0
  • #8
FactChecker
Science Advisor
Gold Member
6,578
2,644
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.
 
  • #9
173
27
@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
 
  • #10
FactChecker
Science Advisor
Gold Member
6,578
2,644
@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.
 
  • #11
pbuk
Science Advisor
Gold Member
2,528
1,257
  • Like
Likes FactChecker
  • #12
Baluncore
Science Advisor
9,864
4,268
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?
 
  • #13
f95toli
Science Advisor
Gold Member
3,234
727
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.
 
  • Like
Likes Omega0 and fresh_42
  • #14
pbuk
Science Advisor
Gold Member
2,528
1,257
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.
 
  • #15
15,565
13,677
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?
 
  • #16
f95toli
Science Advisor
Gold Member
3,234
727
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.
 
  • #17
173
27
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).
 
  • #18
Baluncore
Science Advisor
9,864
4,268
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.
 
  • #19
FactChecker
Science Advisor
Gold Member
6,578
2,644
I think this is a good summary of the current status of quantum programming in 2021: ExplainingComputers, Quantum Computing 2021 Update
 
  • #20
770
463
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."
 
  • #21
FactChecker
Science Advisor
Gold Member
6,578
2,644
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.
 
  • #22
f95toli
Science Advisor
Gold Member
3,234
727
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.
 
  • Like
Likes FactChecker and fresh_42
  • #23
770
463
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.
 
  • #24
15,565
13,677
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?
 
  • #25
f95toli
Science Advisor
Gold Member
3,234
727
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 travelling salesman problem is still very much an problem being actively researched.
 
Last edited:
  • Like
Likes FactChecker and fresh_42

Related Threads on Quantum computing: Not for all problems?

  • Last Post
2
Replies
42
Views
4K
Replies
1
Views
3K
  • Last Post
Replies
1
Views
4K
Replies
2
Views
768
  • Last Post
Replies
23
Views
3K
Replies
17
Views
3K
  • Last Post
Replies
8
Views
220
Replies
7
Views
3K
  • Last Post
Replies
3
Views
3K
Top