The Question:

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:

Additional references:

  • 4
    $\begingroup$ Per complexityzoo.net/Complexity_Zoo:B#bqp, "Contains the factoring and discrete logarithm problems [Sho97], the hidden Legendre symbol problem [DHI02], the Pell's equation and principal ideal problems [Hal02], and some other problems not thought to be in BPP." This is probably not a research-level question, might be better asked at cs.se. $\endgroup$
    – Neal Young
    Jan 12, 2022 at 22:13
  • $\begingroup$ Just a short comment regarding the question of whether a classical computer can simulate a quantum computer. The answer is yes. BUT: not (likely) not efficiently. The reason is not the complexity of matrix multiplication per see, but rather that the matrices that arise in quantum mechanics are exponentially large. So unless you can use some structure, the naive simulation is intractable (not doable in polynomial time). $\endgroup$ Feb 8, 2022 at 14:27


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.