QuantumAlgorithms.aiA citable library

Glossary

Quantum gate

A reversible operation on qubits, represented by a unitary matrix, and the step that gate-complexity statements count.

A quantum gate is a reversible operation on one or more qubits, represented by a unitary matrix. Shor's 1997 paper takes the quantum gate array as its model of computation: wires, gates, and a measurement at the end, with the uniformity conditions he states so that the family of circuits does not hide a hard classical computation in the wiring.

Gate complexity counts those steps. Shor's algorithm is a gate-complexity result. Grover's algorithm is usually stated in oracle queries; each query is itself some gate sequence once a concrete predicate is chosen, and that sequence is not free. QAOA is explicit about locality: the gates in one layer are no more nonlocal than the clauses of the cost function. When a page on this site says "steps," check whether it means gates or queries. Quantum phase estimation counts calls to a powered unitary, plus the gates of the Fourier transform or of Kitaev's measurements.

References

  1. Shor, P. W. (1997). Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM Journal on Computing, 26(5), 1484–1509. DOI · arXiv
  2. Kitaev, A. Yu. (1995). Quantum measurements and the Abelian stabilizer problem. arXiv:quant-ph/9511026. arXiv

Updated 12 Oct 2026.