Glossary

The conjugate transpose of a matrix, written with a dagger. It is not generally the inverse.

A finite set of precise instructions for carrying out a task. Whether it terminates on every allowed input must be established.

A complex coefficient used to describe a quantum state or transition. The squared magnitude gives the corresponding probability in the specified measurement basis.

A sequence of reflections that increases the amplitude in a designated successful subspace, given suitable preparation and inverse operations.

One of four maximally entangled two-qubit basis states. The book begins with the equal superposition of 00 and 11.

A function whose inputs and outputs are bits. A truth table specifies its value for every input.

The class of decision problems solvable by uniform polynomial-size quantum circuits with bounded error.

The number of sequential layers of operations when compatible operations can run in parallel.

Whether a task can be performed by an effective procedure, without imposing an efficiency requirement.

A formal theory is consistent if its rules cannot prove both a statement and its negation.

A problem whose required answer is yes or no for each allowed input.

For a pure joint state, the inability to write it as a product of subsystem states. Mixed-state entanglement requires a broader definition.

A common phase factor multiplying an entire state vector. It leaves all measurement probabilities unchanged.

A phase reversal on marked items followed by a reflection about the prepared uniform state in the standard search algorithm.

The task of deciding, for every program and input, whether the program eventually stops. No algorithm solves it in full generality.

An operator equal to its adjoint. Its eigenvalues are real and its eigenspaces can describe a projective measurement.

The overlap of two state vectors, obtained by conjugating the coordinates of the first and summing their products with the second. With the final state on the left and the initial state on the right, it is the amplitude for that final-state outcome.

The addition of amplitudes for indistinguishable alternatives, which can increase or decrease an outcome probability.

A limit on the resources required by every algorithm within a specified model, rather than the cost of one construction.

The Boolean operation that returns zero exactly when both input bits are one. NAND gates suffice to build every Boolean function.

The requirement that a state vector has squared norm one, so the probabilities of a complete basis measurement sum to one.

A specified operation that provides access to a function. Counting its uses does not by itself account for the cost of building it.

When a controlled operation acts on a target eigenstate, its eigenvalue appears as a phase on the corresponding control component.

A pure joint state that can be written as a tensor product of one state for each subsystem.

A measurement described by mutually orthogonal projectors summing to the identity. Each outcome probability is the squared norm of the projected state.

An improvement over classical computation for a specified task, resource measure, and success guarantee. Its assumptions must be stated.

An ordered description of operations on quantum registers, with any measurements and classical control specified.

One reversible evaluation of a function applied to a superposition of inputs, producing a state in which every input appears beside its own value. A measurement returns only one input–value pair; a useful algorithm must follow the evaluation with interference.

A two-state quantum system. Its state is described by two amplitudes, one for each of the labels zero and one.

The number of oracle calls required for a task under a stated success criterion and oracle model.

The phase difference between two components of a state. It can affect probabilities after further operations.

A transformation is reversible when its output determines its input uniquely on the allowed state space.

A linear combination of basis states. Its components depend on the chosen basis; measurement does not reveal all coefficients at once.

The construction of a joint vector space from component spaces. Basis labels combine in pairs and dimensions multiply.

The number attached to an arrow from one configuration to another: 1 for a deterministic or allowed arrow, a probability for a probabilistic rule, a complex amplitude for a quantum operation.

A mathematical model with a tape, a read/write head, and finitely many control states. A transition rule specifies each step.

Applying the inverse of a computation to clear temporary workspace while retaining the needed result or phase.

An operator whose adjoint is its inverse. Unitary transformations preserve inner products and describe closed-system quantum evolution.

A set of gates sufficient to construct arbitrary quantum operations in the stated model, exactly or to a specified approximation.