3 ms·

n00b question: what are some important problems for which quantum computation has shown to have an advantage

mebassett 3y ago
factoring large integers into primes (shor's algorithm). that and grover's search promise to provide ways to crack a lot of encryption. also quantum computing should improve both classical and quantum physical simulations.
- vitus 3y ago
  The other side of Shor's algorithm is that you can use it to solve discrete logarithm (which additionally breaks elliptic curve crypto; factoring breaks RSA). I don't agree that Grover's algorithm is as fundamental in breaking encryption, since it "only" yields a quadratic speed-up. You'd have similar effective security as in the pre-quantum world by doubling the key length; you could do this by, say, switching to AES-256 instead of AES-128. Meanwhile, switching from RSA-2048 to RSA-4096 only helps if it means the problem size now exceeds the size of the biggest quantum computers.
erikaww 3y ago
I think there is promise with tons of optimization problems (machine learning, approximating differential equations). I hope these would be significantly faster in practice. It would be cool if we had quantum accelerated game physics engines. Super realistic games that are fast. Simulations could scale better, so we could make them a lot more useful.
- pclmulqdq 3y ago
  Unless you are simulating quantum effects, these sorts of simulations are unlikely to be faster on a quantum computer. Also, attempts at using the Ising model for general-purpose optimization have found themselves somewhat limited in application. For people doing drug discovery and quantum physics/chemistry research, they will see an exponential speedup from quantum computing, but I think you're overstating how applicable this technology is.
NooneAtAll3 3y ago
you aren't the first asking, so someone made a website listing stuff https://quantumalgorithmzoo.org/ https://quantumalgorithmzoo.org/

factoring large integers into primes (shor's algorithm). that and grover's search promise to provide ways to crack a lot of encryption. also quantum computing should improve both classical and quantum physical simulations.

vitus 3y ago
The other side of Shor's algorithm is that you can use it to solve discrete logarithm (which additionally breaks elliptic curve crypto; factoring breaks RSA). I don't agree that Grover's algorithm is as fundamental in breaking encryption, since it "only" yields a quadratic speed-up. You'd have similar effective security as in the pre-quantum world by doubling the key length; you could do this by, say, switching to AES-256 instead of AES-128. Meanwhile, switching from RSA-2048 to RSA-4096 only helps if it means the problem size now exceeds the size of the biggest quantum computers.

erikaww 3y ago

I think there is promise with tons of optimization problems (machine learning, approximating differential equations). I hope these would be significantly faster in practice. It would be cool if we had quantum accelerated game physics engines. Super realistic games that are fast. Simulations could scale better, so we could make them a lot more useful.

pclmulqdq 3y ago
Unless you are simulating quantum effects, these sorts of simulations are unlikely to be faster on a quantum computer. Also, attempts at using the Ising model for general-purpose optimization have found themselves somewhat limited in application. For people doing drug discovery and quantum physics/chemistry research, they will see an exponential speedup from quantum computing, but I think you're overstating how applicable this technology is.

NooneAtAll3 3y ago

you aren't the first asking, so someone made a website listing stuff https://quantumalgorithmzoo.org/ https://quantumalgorithmzoo.org/