I'm trying to understand the type of problems that Quantum Computers are/will be good at solving and if there is a special class to categorizes these types of problems (e.g. Do we specify the difference between Quantum Computer Polynomial time (like Shor's algorithm) versus classical computer polynomial time, or are they both just just considered P?).
If examples of types of problems that can be solved quickly by quantum computers can be shared it would also be greatly appreciated. Hoping to see enough examples that I can see the patterns of type of problems that can be solved or how to take advantage of what quantum computers offer.
I read that there are problems that could take tens of thousands of years to solve with normal computers, but would be able to be solved in a couple hours with a quantum computer. I've also read that quantum computers could helps solve NP Hard problems efficiently (not NP or NP Complete, but NP Hard). I'm hoping to understand what types of problems, preferably with some examples. (Note: I find the reference of NP Hard a bit paradoxical, as I assume if something could be solved in Polynomial time with quantum computing that the solution would then become P instead of NP Hard. Please correct me if I'm wrong.)
Quantum Computing Simulation:
From https://cs.stackexchange.com/questions/6296/references-on-comparison-between-quantum-computers-and-turing-machines it sounds like we are able to simulate quantum computers with classical computers, since they both can solve Turing complete. It sounds like the simulation depends on the ability to do matrix multiplication/linear algebra. (I assume this simulation is how AWS is able to offer a service for quantum computing at this point: https://aws.amazon.com/braket/ )
From https://en.wikipedia.org/wiki/Matrix_multiplication_algorithm it looks like matrix multiplication is O(n^2.3728596). If we are simulating quantum computers, I'm curious if this means we have the extra cost of O(n^2.3728596) to do the simulations is where the saving is. If so would this be considered constant time on an actual quantum computers? If this is accurate, would all problems involving matrix multiplication become super efficient with quantum computers?
Intractable Problems That Can Be Solved with Quantum Computers
From https://www.ncbi.nlm.nih.gov/books/NBK538701/ "Quantum computers have the potential to revolutionize computation by making certain types of classically intractable problems solvable. While no quantum computer is yet sophisticated enough to carry out calculations that a classical computer can't, great progress is under way." This is the core of what I'm trying to get after, what intractable problems would be able to be solved (can we name a few at least)? The link references "In 1994, however, interest in quantum computing rose dramatically when mathematician Peter Shor developed a quantum algorithm, which could find the prime factors of large numbers efficiently." After reading the above, I read https://en.wikipedia.org/wiki/Shor%27s_algorithm which looks like the related algorithm is polynomial, however the largest number factored into its primes using the algorithm was 21 back in 2012.
Areas for Speed Up With Quantum Computers:
- From: https://www.ncbi.nlm.nih.gov/books/NBK538708/pdf/Bookshelf_NBK538708.pdf it references, "There are three properties of quantum mechanics that are different from standard computation and that are required for quantum speedups: superposition, interference, and entanglement." Hoping to get confirmation that these are the key properties or items that quantum computers offer over classic computer systems.
- Some examples of things quantum computers do better: https://quantumcomputing.stackexchange.com/questions/6198/what-exactly-makes-quantum-computers-faster-than-classical-computers
- Quantum Computing: https://en.wikipedia.org/wiki/Quantum_computing
- Quantum Supremacy: https://en.wikipedia.org/wiki/Quantum_supremacy