Ask HN: What scientific phenomenon do you wish someone would explain better?

Re:Ask HN: What scientific phenomenon do you wish someone wo... by sodafountan on Monday April 27, 2020 @12:50AM (#22992977)

I'd assume it's the speed advantage, but the only problem I can think of that would require that type of exponential speed is cracking hashing algorithms which just seems destructive and counterproductive, like building a digital nuclear bomb - and from my very limited understanding that's a long ways off from being achieved.

I assume there's probably many more complex computational problems outside of my domain that QC can help with. Does anybody know of any?

[ Parent | on HN ]

Re:Ask HN: What scientific phenomenon do you wish someone wo... by brg on Monday April 27, 2020 @01:24AM (#22993115)

Aside from Shor's, the other is Grover's algorithm which deals with search in an unstructured database. There are more and more superpolynomial speedups which have been discovered in application of QC. A good enumeration of these is the quantum algorithm zoo.

https://quantumalgorithmzoo.org/

[ Parent | on HN ]

Re:Ask HN: What scientific phenomenon do you wish someone wo... by Smaug123 on Monday April 27, 2020 @02:13AM (#22993318)

Grover's algorithm lets you search an unsorted list of four elements with just one "is this thing in the list?" query. Classically, of course, it requires four queries.

More precisely, given f: 2^n -> {0,1} which is guaranteed to hit 1 exactly once, Grover finds the one input which hits 1, and it does so using about 2^{n/2} queries of f; but the constants happen to line up so that when n=2, exactly one query is required.

[ Parent | on HN ]

Re:Ask HN: What scientific phenomenon do you wish someone wo... by skosch on Monday April 27, 2020 @01:22AM (#22993102)

Many problems require lots of huge matrix multiplications—think simulations of physical systems, i.e. weather systems or molecular interactions, or numerical optimization.

[ Parent | on HN ]

Re:Ask HN: What scientific phenomenon do you wish someone wo... by TJSomething on Monday April 27, 2020 @03:35AM (#22993738)

Additionally, many problems are can be converted to matrix operations, like graph algorithms.

Note that matrix multiplication takes O(n^2) time with a quantum computer, but O(n^2.807) time on a classical computer.

[ Parent | on HN ]

Re:Ask HN: What scientific phenomenon do you wish someone wo... by gnu-nobody on Monday April 27, 2020 @04:28AM (#22993997)

> but O(n^2.807) time on a classical computer

Optimizing matrix multiplication for classical computers is an open research problem, and according to wikipedia there are algorithms with O(n^2.37) running time. Also according to wikipedia, it is not proven that matrix multiplication can't be done in O(n^2).

[ Parent | on HN ]

Re:Ask HN: What scientific phenomenon do you wish someone wo... by infogulch on Monday April 27, 2020 @05:09AM (#22994209)

Ah yes, we may as well add NP-completeness to this thread.

[ Parent | on HN ]