4 ms·

I don't know if it's accurate (because I never understand anything I read about it) but this is the most concise and clear explanation I've read on this subject

I don't know if it's accurate (because I never understand anything I read about it) but this is the most concise and clear explanation I've read on this subject to date. Thank you!

dreamcompiler 7y ago
It's accurate. QC is just linear algebra with complex numbers, plus probability extended to the complex domain. Why that's useful is something I'm still struggling with as well.
- sodafountan 7y ago
  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?
  - skosch 7y ago
    Many problems require lots of huge matrix multiplications—think simulations of physical systems, i.e. weather systems or molecular interactions, or numerical optimization.
    - TJSomething 7y ago
      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.
      - gnu-nobody 7y ago
        > 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).
        infogulch 7y ago
        Ah yes, we may as well add NP-completeness to this thread.
  - brg 7y ago
    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/ https://quantumalgorithmzoo.org/
  - Smaug123 7y ago
    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.

I don't know if it's accurate (because I never understand anything I read about it) but this is the most concise and clear explanation I've read on this subject to date. Thank you!

dreamcompiler 7y ago

It's accurate. QC is just linear algebra with complex numbers, plus probability extended to the complex domain. Why that's useful is something I'm still struggling with as well.

sodafountan 7y ago
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?
- skosch 7y ago
  Many problems require lots of huge matrix multiplications—think simulations of physical systems, i.e. weather systems or molecular interactions, or numerical optimization.
  - TJSomething 7y ago
    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.
    - gnu-nobody 7y ago
      > 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).
      - infogulch 7y ago
        Ah yes, we may as well add NP-completeness to this thread.
- brg 7y ago
  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/ https://quantumalgorithmzoo.org/
- Smaug123 7y ago
  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.