One of the most notable examples of a problem that is believed to be difficult to compute but easy to verify on a quantum computer is factoring large composite numbers. This problem forms the basis for RSA encryption and is at the core of its security.
While factoring large numbers using classical computers becomes increasingly time-consuming as the numbers grow larger, Shor's Algorithm on a quantum computer has the potential to efficiently factor large composite numbers into their prime factors. This implies that the security of RSA encryption (and similar systems) could be compromised by a large-scale, fault-tolerant quantum computer.
Another problem that falls into this category is the simulation of quantum systems. Simulating the behavior of quantum systems accurately and efficiently using classical computers becomes extremely challenging as the number of particles or quantum states increases. Quantum computers, on the other hand, have a natural advantage in simulating quantum phenomena due to their inherent quantum nature. Therefore, quantum computers have the potential to simulate quantum systems more effectively, enabling the study of complex molecular structures, chemical reactions, or materials.
It's worth mentioning that these examples are based on the potential capabilities of large-scale, fault-tolerant quantum computers. Currently, practical quantum computers are in the early stages of development, and achieving the necessary scale and reliability remains a significant technological challenge. Nevertheless, these problems demonstrate the potential advantages of quantum computing in certain computational tasks, suggesting that quantum computers may offer significant speedups for specific problems compared to classical computers.