quantum advantage

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