Quantum advantage (formerly called "quantum supremacy") refers to the demonstrated ability of a quantum computer to solve a specific problem significantly faster than any classical computer can, or to solve a problem that is practically intractable for classical machines.

Key Milestones

• Google Sycamore (2019): Claimed quantum advantage by performing a random circuit sampling task in 200 seconds that Google estimated would take a classical supercomputer 10,000 years. IBM disputed this claim, arguing a classical computer could do it in 2.5 days.
• USTC Jiuzhang (2020): Demonstrated quantum advantage in Gaussian boson sampling — a task related to sampling from certain probability distributions.
• IBM (2023): Showed quantum computers can produce reliable results for certain problems beyond classical simulation capabilities using error mitigation techniques.

Types of Quantum Advantage

• Asymptotic Advantage: The quantum algorithm has a provably better scaling than the best known classical algorithm (e.g., Shor's algorithm for factoring is exponentially faster).
• Practical Advantage: The quantum computer actually solves a real-world problem faster or better than classical alternatives in practice.
• Sampling Advantage: The quantum computer can sample from distributions that are computationally hard for classical computers.

For Machine Learning

Quantum advantage for ML would mean a quantum computer can:

• Train models faster on the same data.
• Find better optima in loss landscapes.
• Process exponentially larger feature spaces.
• Perform inference more efficiently.

Current Reality

• Demonstrated quantum advantages are for highly specialized, artificial problems, not practical applications.
• For real-world ML tasks, classical computers (especially GPUs) remain faster and more practical.
• Fault-tolerant quantum computers (with error correction) are needed for most theoretically advantageous quantum algorithms — these don't exist yet.

Quantum advantage for practical AI applications remains a future goal — exciting theoretically but not yet impacting real-world ML development.