<p><strong>The Question:</strong></p>
<p>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?).</p>
<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.</p>
<p><strong>References:</strong></p>
<p>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.)</p>
<p><strong>Quantum Computing Simulation:</strong></p>
<p>From <a href="https://cs.stackexchange.com/questions/6296/references-on-comparison-between-quantum-computers-and-turing-machines">https://cs.stackexchange.com/questions/6296/references-on-comparison-between-quantum-computers-and-turing-machines</a> 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: <a href="https://aws.amazon.com/braket/" rel="nofollow noreferrer">https://aws.amazon.com/braket/</a> )</p>
<p>From <a href="https://en.wikipedia.org/wiki/Matrix_multiplication_algorithm" rel="nofollow noreferrer">https://en.wikipedia.org/wiki/Matrix_multiplication_algorithm</a> 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?</p>
<p><strong>Intractable Problems That Can Be Solved with Quantum Computers</strong></p>
<p>From <a href="https://www.ncbi.nlm.nih.gov/books/NBK538701/" rel="nofollow noreferrer">https://www.ncbi.nlm.nih.gov/books/NBK538701/</a> &quot;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.&quot; 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 &quot;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.&quot; After reading the above, I read <a href="https://en.wikipedia.org/wiki/Shor%27s_algorithm" rel="nofollow noreferrer">https://en.wikipedia.org/wiki/Shor%27s_algorithm</a> which looks like the related algorithm is polynomial, however the largest number factored into its primes using the algorithm was 21 back in 2012.</p>
<p><strong>Areas for Speed Up With Quantum Computers:</strong></p>
<ul>
<li>From: <a href="https://www.ncbi.nlm.nih.gov/books/NBK538708/pdf/Bookshelf_NBK538708.pdf" rel="nofollow noreferrer">https://www.ncbi.nlm.nih.gov/books/NBK538708/pdf/Bookshelf_NBK538708.pdf</a> it references, &quot;There are three properties of quantum mechanics that are different from standard computation and that are required for quantum speedups: superposition, interference, and entanglement.&quot; Hoping to get confirmation that these are the key properties or items that quantum computers offer over classic computer systems.</li>
<li>Some examples of things quantum computers do better: <a href="https://quantumcomputing.stackexchange.com/questions/6198/what-exactly-makes-quantum-computers-faster-than-classical-computers">https://quantumcomputing.stackexchange.com/questions/6198/what-exactly-makes-quantum-computers-faster-than-classical-computers</a></li>
</ul>
<p><strong>Additional references:</strong></p>
<ul>
<li><a href="https://stackoverflow.com/questions/1857244/what-are-the-differences-between-np-np-complete-and-np-hard">https://stackoverflow.com/questions/1857244/what-are-the-differences-between-np-np-complete-and-np-hard</a></li>
<li><a href="https://upload.wikimedia.org/wikipedia/commons/a/a0/P_np_np-complete_np-hard.svg" rel="nofollow noreferrer">https://upload.wikimedia.org/wikipedia/commons/a/a0/P_np_np-complete_np-hard.svg</a></li>
<li>Quantum Computing: <a href="https://en.wikipedia.org/wiki/Quantum_computing" rel="nofollow noreferrer">https://en.wikipedia.org/wiki/Quantum_computing</a></li>
<li>Quantum Supremacy: <a href="https://en.wikipedia.org/wiki/Quantum_supremacy" rel="nofollow noreferrer">https://en.wikipedia.org/wiki/Quantum_supremacy</a></li>
</ul>

CC BY-SA 4.0
2022-01-12T22:13:01.370Z
Per https://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.
Neal Young
CC BY-SA 4.0
2022-02-08T14:27:58.073Z
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).
Jonas Kübler
<np-hardness><quantum-computing><matrices>
What type of Problems (Class and types) Can Be Solved Effectively with Quantum Computers?
VenomFangs
# What type of Problems (Class and types) Can Be Solved Effectively with Quantum Computers?

(Asked by: username_0 on 2022-01-12)

**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.

**References:**

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>

**Additional references:**

* <https://stackoverflow.com/questions/1857244/what-are-the-differences-between-np-np-complete-and-np-hard>
* <https://upload.wikimedia.org/wikipedia/commons/a/a0/P_np_np-complete_np-hard.svg>
* Quantum Computing: <https://en.wikipedia.org/wiki/Quantum_computing>
* Quantum Supremacy: <https://en.wikipedia.org/wiki/Quantum_supremacy>

**Tags:** np-hardness, quantum-computing, matrices
> **Comments:**
> **username_1**: Per https://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.  
> **username_2**: 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).  

---

## 0 answers

