Library
Glossary
Short definitions, pinned to a paper or a textbook where the word would otherwise slide. Filter the list. Each term has its own URL.
Quantum algorithms is the guide. The complexity table is the row-by-row comparison.
17 terms
- Amplitude amplificationA quadratic boost to the success probability of a quantum procedure, generalizing Grover's search beyond a uniform starting state.
- AnsatzA parameterized family of quantum states, chosen in advance, inside which a hybrid algorithm searches for a good solution.
- Condition numberThe ratio of the largest singular value of a matrix to the smallest. HHL's runtime grows with it, and a large value removes the advantage in the dimension.
- DecoherenceUnwanted entanglement with the environment that turns a pure quantum evolution into noise on the device you meant to compute with.
- EntanglementCorrelation between qubits that cannot be written as a product of single-qubit states, and that measurement on one side constrains the other.
- Fault toleranceComputation that keeps a logical circuit reliable by correcting errors often enough that they do not accumulate.
- HamiltonianThe Hermitian operator whose eigenvalues are the energies, or, in combinatorial problems, the costs of bit-string solutions.
- MeasurementThe step that turns amplitudes into a classical outcome, one shot at a time, and the reason expectation values are estimated by repetition.
- NISQPreskill's name for quantum devices that are too noisy for long fault-tolerant circuits and large enough that the noise is the main constraint.
- OracleA black-box subroutine that answers a predicate, charged as one query, without revealing how the answer was computed.
- Phase estimationA quantum routine that estimates the eigenvalue phase of a unitary applied to an eigenstate, given coherent controlled powers of that unitary.
- Quantum Fourier transformThe discrete Fourier transform applied to amplitudes, used by Shor's algorithm to turn a periodic superposition into samples near multiples of the frequency.
- Quantum gateA reversible operation on qubits, represented by a unitary matrix, and the step that gate-complexity statements count.
- QubitA quantum two-level system, used as the basic carrier of information in the gate-array model.
- Query complexityThe number of calls to an oracle, rather than the number of elementary gates, required to solve a problem.
- SuperpositionA state that is a linear combination of basis states, with complex amplitudes, until a measurement returns one outcome.
- Variational quantum algorithmA hybrid loop: a parameterized quantum state, an estimate of a cost, and a classical optimizer updating the parameters.