zlacker

>>qqqqqu+(OP)
Quantum Computers. Not like I'm five, but like I'm a software engineer who has a pretty decent understanding of how a classical turing machine works. I can't tell you how many times I've heard someone say "qubits are like bits except they don't have to be just 1 or 0" without providing any coherent explanation of how that's useful. I've also heard that they can try every possible solution to a problem. What I don't understand is how a programmer is supposed to determine the correct solution when their computer is out in some crazy multiverse. I guess what I want is some pseudo code for quantum software.

>>arkanc+ps
I recommend Computerphile's videos https://www.youtube.com/playlist?list=PLzg3FkRs7fcRJLgCmpy3o....

I had the same "problem" as you. What finally made me feel I sort of cracked it was those videos. The way I think of it now is: They let you do matrix multiplication. The internal state of the computer is the matrix, and the input is a vector, where each element is represented by a qubit. The elements can have any value 0 to 1, but in the output vector of the multiplication, they are collapsed into 0 or 1. You then run it many times to get statistical data on the output to be able to pinpoint the output values more closely.

>>elgfar+gu
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!

>>ad404b+Tx
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.

>>dreamc+sT
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?

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

>>skosch+EZ
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.

>>TJSome+U91
> 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).

>>gnu-no+5e1
Ah yes, we may as well add NP-completeness to this thread.