Thread Rating:
  • 0 Vote(s) - 0 Average
  • 1
  • 2
  • 3
  • 4
  • 5

This 90 year old math problem shows why we need quantum computers

#1
C C Offline
https://www.forbes.com/sites/startswitha...0bef421c5d

EXCERPTS: . . . But which one of these routes will be the most efficient path? This is known, in the field of mathematics, as the travelling salesman problem. To solve it for more than a handful of "stops," it will almost certainly require a quantum computer. Here's why [...see article...]

[...] This problem - like many problems one can formulate - belongs to a class of problems that are classified as computationally expensive. To find the optimal solution among a myriad of possible combinations requires examining every reasonable path that one could imagine taking, quantifying the distance (or time) requires for that path, and then choosing the shortest (or fastest) one.

In practice, the brute force approach isn't the only one, and superior methods for finding exact solutions (largely by ruling out "obviously non-optimal" paths) exist, similar to advances made in computer chess. The largest exact solution was achieved in 2006, when the shortest path through 85,900 cities was found. It took over a century's worth of CPU-years to find that solution. This type of problem, despite its simplicity, actually has a large number of practical applications...

[...] If your problem is too complex - if you have too many destinations, for example - you'll only ever be able to come up with approximate solutions; you cannot be certain that you found the best route, or even one of the best routes. The solution you arrive at will be limited by your computational power and the quality of your algorithm. Some problems, quite simply, are hard to solve with classical computers.

Fortunately, many computationally difficult problems [...] are far less difficult (and far less computationally expensive) using a quantum computer. It was proven, just a few years ago, that quantum computers possess a computational advantage over anything a classical computer could ever achieve.

When quantum supremacy was achieved for the first time in 2019 (albeit only for a specific problem), it was a stunning example of how quantum computers could practically solve problems faster and more efficiently than conventional, classical computers ever could. While it's always possible that new algorithms or methods could lead to a faster solution for any particular problem on a classical computer, quantum computers maintain some fundamental advantages.

Instead of bits that must be either 0 or 1, they work with indeterminate qubit states that exist in superpositions of 0 and 1 simultaneously. Moreover, you can also perform quantum operations (rather than just the classical ones) on these qubits directly, maintaining all of that quantum weirdness (including indeterminism) all the way up through the very end of the computation.

This is where the true power of quantum computing lies: in taking advantage of the fact that some problems can be solved efficiently using a quantum computer, but classical computers can only solve them inefficiently. This was proven in 2018 by computer scientists Ran Raz and Avishay Tal, who demonstrated that quantum computers can efficiently solve problems that:

• are not quickly solvable by a classical computer,
• cannot have their solutions quickly checked by a classical computer,
• and do not fall into the generalized category of all problems that classical computers could theoretically solve in polynomial time.

This brings us back to the travelling salesman problem. It's not a problem that's quickly solvable by a classical computer, even with the best algorithms ever devised. [...] Perhaps someday, even if it hasn't happened in all the time this problem has been examined, we'll be able to discover an algorithm for a classical computer that can efficiently find that solution. It's not guaranteed that such an algorithm exists, but the quest to discover one remains the hope of many.

Irrespective of whether that specific problem - or the generalization of all such theoretical problems - eventually yields to a classical computer or not, however, there will still remain problems that go beyond the limits of what a classical computer could ever efficiently do. There are problems that we can pose that have a "yes" or "no" answer, but that aren't solvable in polynomial time by a classical computer, even theoretically.

However, at least some of those problems, even the ones that cannot be efficiently solved by a classical computer, can be efficiently solved by a quantum computer. Although we do not know if the traveling salesman problem will ever be efficiently solvable by a classical computer, we do know that there are categories of problems that quantum computers can efficiently solve that classical ones cannot. If a classical solution exists, then a quantum one does too; but even if a classical solution doesn't exist, a quantum one may yet be possible... (MORE - details)
Reply


Possibly Related Threads…
Thread Author Replies Views Last Post
  Research Physicists finally find a problem only quantum computers can do C C 2 28 Mar 15, 2024 02:49 AM
Last Post: confused2
  Record entanglement of quantum memories + Quantum flute manipulates photons C C 0 75 Jul 7, 2022 07:44 PM
Last Post: C C
  We're building computers wrong + Using AI to find anomalies hid in massive datasets C C 0 81 Mar 3, 2022 06:06 PM
Last Post: C C
  How exascale computers can verify the universe C C 3 141 Oct 19, 2021 12:13 PM
Last Post: Zinjanthropos
  It's hard to give computers common sense Leigha 1 98 Aug 19, 2021 07:16 AM
Last Post: stryder
  Computer scientists discover new vulnerability affecting computers globally C C 0 172 May 2, 2021 09:42 PM
Last Post: C C
  The new oracles & gods: When people trust computers more than other humans C C 0 118 Apr 14, 2021 07:08 PM
Last Post: C C
  Why computers will never write good novels C C 3 170 Mar 31, 2021 04:35 PM
Last Post: Leigha
  Cells as computers + Interconnected single atoms could make a ‘quantum brain’ C C 1 187 Mar 9, 2021 05:25 PM
Last Post: Ostronomos
  Physicists propose a 'force field' to protect sensitive quantum computers from noise C C 0 111 Feb 21, 2021 03:25 AM
Last Post: C C



Users browsing this thread: 1 Guest(s)