Quantum computing is a computing paradigm that uses quantum-mechanical phenomena. It differs fundamentally from classical computing, so reasoning commonly depends on mathematics rather than everyday intuition. A practical system combines quantum algorithms, hardware, and software; progress in each shapes the others. section 1.0 section 1.3
Its purpose is not to accelerate arbitrary workloads. A useful quantum application must address a meaningful problem that is impractically slow for the best classical approach while producing a quantum result quickly enough to matter. Quantum-system simulation, including chemistry and materials problems, is a leading candidate because it models quantum behavior directly. section 1.10 section 1.2
Figure 1.1 Quantum advantage might be achievable if the time a quantum computer takes to solve a certain problem grows at a slower rate as the problem size increases than the time a classical computer takes to do the same. In this case, problem instances that are much larger than the crossover size might be good candidates for quantum solutions. If the crossover time is months or more, quantum computing offers no practical advantage, since larger problem instances take much longer to solve, and running a quantum computer for months or years to solve a single problem is not practical.
Compare growth rates rather than assuming a quantum solution wins: practical advantage depends on a favorable crossover size and a usable elapsed time. section 1.2
The gate-based model represents a computation as a sequence of single- and multiqubit quantum gates, analogous in form to sequences of logic gates. Measurement-based and adiabatic models also exist, using the same principles with different implementations. Quantum programs are often hybrid: classical code prepares data, a quantum subroutine performs the specialized computation, and classical code postprocesses results. section 1.3 section 7.0
Assess a proposed quantum solution as an end-to-end workflow:
- Reformulate the classical problem into a quantum computation. section 7.0
- Implement the quantum algorithm as a program, with classical preprocessing and postprocessing where needed. section 7.0
- Compare its performance with the best classical solution, including implementation costs rather than asymptotic complexity alone. section 1.3.1 section 7.0
Grover’s unstructured search
Given a black-box function with N possible inputs, Grover’s algorithm finds an input producing a target output in O(√N) function calls, versus O(N) under the same classical black-box limitations. This quadratic speedup does not by itself establish practical superiority, since classical methods can exploit problem structure and implementation details matter. section 1.3.1
