I'd love to answer any questions people have. In quantum computation, state behaves like a vector and logic gates behave like matrices that multiply the vector to get a new state value. It doesn't get too much more complicated than that.
Microsoft also has a fairly large team working on Q# and the Microsoft Quantum Development Kit. That would also involve research-adjacent things like efficiently compiling programs to specific quantum device layouts with appropriate error correction schemes, etc.
[1] https://www.edx.org/course/quantum-information-science-i-par...
[2] https://www.edx.org/course/quantum-information-science-i-par...
[3] https://www.edx.org/course/quantum-information-science-i-par...
[4] https://www.edx.org/course/quantum-information-science-ii-qu...
[5] https://www.edx.org/course/quantum-information-science-ii-ef...
[6] https://www.edx.org/course/quantum-information-science-ii-ad...
For algorithms like HHL that have superclassical performance, a complex superposition encoding the data needs to be created first. This state is subsequently "consumed" by the algorithm. The no-cloning theorem forbids creating copies of the encoded state, and hence the encoding step needs to be repeated every time the algorithm is run.
For another example, consider Grover's search that is sub-linear in calls to an oracle function. If the oracle references a linear array of data, for example, it needs to work on superpositions of array indices. In other words, the entire dataset needs to fit in "quantum" memory.
Using a quantum cpu can only be sensible for computationally difficult problems where the hard problem instances can be specified by a relatively small number of bits.
But i really dont know much about this area, might be totally wrong. I'm kind of basing this off this blog post https://www.scottaaronson.com/blog/?p=3880
In theory classical computers are also not limited to have better solutions to problems where quantum computers claim superiority like prime factorisation or like Tang's quantum inspired classical algorithm that beats HHL for low rank matrices.
Eh... those particular subroutines have polynomial time algorithms already on a classical computer.
You can't exponentially speed up something that's polynomial time already.
