This page is a reference list for core terms used across the course. Use it when a note names an unfamiliar concept and you want a short neutral definition rather than a full explanation. ## Core Terms ### Adiabatic algorithm A quantum algorithmic approach where the system is evolved slowly enough that it stays near the ground state of a changing Hamiltonian. ### Amplitude A complex number assigned to a possible measurement outcome before the Born rule converts it into a probability. ### Bell inequality A mathematical constraint that any local hidden-variable theory must satisfy. Quantum mechanics can violate it. ### Bell state A maximally entangled two-qubit state such as $(|00\rangle + |11\rangle)/\sqrt{2}$. ### BBBV theorem A black-box lower-bound result showing that unstructured quantum search still needs $\Omega(\sqrt{N})$ queries. It explains why Grover's quadratic speedup is optimal in that setting. ### Bloch sphere A geometric picture of the state space of one qubit, where pure states lie on the surface and mixed states lie inside the sphere. ### Born rule The rule that says the probability of an outcome is the squared magnitude of its amplitude. ### BQP The class of decision problems solvable by a polynomial-time quantum computer with bounded error. ### CHSH game A two-player nonlocal game used to express Bell inequality violation in an operational way. ### Church-Turing Thesis The claim that every physically realizable computation can be simulated by a Turing machine. ### Clifford gate A gate that maps Pauli operators to Pauli operators under conjugation. Clifford circuits are central in stabilizer theory. ### Density matrix A matrix description of a quantum state that works for both pure states and mixed states. ### Decoherence The loss of visible quantum interference because a system becomes entangled with its environment. ### Ebit A unit of bipartite entanglement. One Bell pair contains one ebit. ### Entangled state A multipartite state that cannot be written as a product state across the chosen partition. ### Entanglement entropy For a pure bipartite state, the Von Neumann entropy of either reduced density matrix. It measures bipartite entanglement. ### Element Distinctness The problem of deciding whether any two items in a queried list are equal. Quantumly, it has a better-than-Grover query algorithm and is useful as a subroutine in collision-style problems. ### Extended Church-Turing Thesis The stronger claim that every reasonable physical computation can be simulated efficiently, up to polynomial overhead, on a classical computer. ### Fault tolerance The design principle that a computation should continue reliably even when individual gates, measurements, or qubits fail at a sufficiently low rate. ### GHZ state A multipartite entangled state such as $(|000\rangle + |111\rangle)/\sqrt{2}$ that highlights stronger-than-pairwise correlation structure. ### Global phase A phase factor multiplying an entire state vector that has no observable effect on measurement statistics. ### Gottesman-Knill theorem The theorem that stabilizer circuits made from Clifford gates, Pauli measurements, and stabilizer-state preparation can be simulated efficiently on a classical computer. ### Grover diffusion operator The reflection step in Grover's algorithm that amplifies the amplitude of marked states. ### Hamiltonian An operator that describes the energy of a quantum system and generates its time evolution. ### Hidden variable theory An attempted completion of quantum mechanics in which measurement outcomes are determined by additional underlying variables. Bell-type results constrain local hidden-variable versions. ### Hilbert space The complex vector space in which quantum states live. ### Interference The reinforcement or cancellation of amplitudes when multiple quantum paths contribute to the same outcome. ### Ket Dirac notation for a state vector, written as $|\psi\rangle$. ### Local realism The joint idea that physical properties are definite before measurement and that distant systems cannot influence one another faster than light. ### Locality The principle that signals or causal influences do not propagate instantaneously across space. ### Mixed state A state described by a density matrix with more than one nonzero eigenvalue, usually representing classical uncertainty or a subsystem of a larger entangled system. ### Monogamy of entanglement The principle that strong entanglement between two systems limits how strongly either can be entangled with a third. ### Negativity An entanglement measure based on the negative eigenvalues of a partial transpose. ### No-cloning theorem The theorem that there is no universal quantum operation that perfectly copies an unknown quantum state. ### Nonlocal game A game played by separated parties who may share entanglement but cannot communicate during the game. ### Oracle A black-box subroutine used in query-complexity models and many quantum algorithms. ### Partial trace The operation that discards one subsystem and produces the reduced state of the remaining subsystem. ### Pauli operators The single-qubit matrices $X$, $Y$, and $Z$, together with the identity, which form a basic operator basis. ### Period finding The problem of recovering the period of a function. It is the core quantum subroutine behind Shor's algorithm. ### Phase kickback A phenomenon where phase information is transferred onto a control or input register through a controlled unitary. ### PPT criterion The Peres-Horodecki test based on partial transpose. For two qubits and qubit-qutrit systems, it completely characterizes separability. ### Pure state A state described by a single ket or, equivalently, by a rank-1 projector $\rho = |\psi\rangle\langle\psi|$. ### Qubit A two-level quantum system whose state can be any normalized superposition of $|0\rangle$ and $|1\rangle$. ### Quantum channel A completely positive trace-preserving map that describes physical quantum evolution, especially in open systems and noise models. ### Quantum error correction A method for protecting logical quantum information against noise by encoding it into a larger physical system. ### Quantum Fourier Transform A unitary transform on computational basis states that is central to period finding, phase estimation, and Shor's algorithm. ### Quantum garbage collection The uncomputation technique of copying out a clean classical answer register when allowed, then reversing a quantum computation to erase unwanted workspace without leaving entangled junk behind. ### Quantum one-time pad A perfect private quantum encryption scheme that applies uniformly random Pauli $X$ and $Z$ masks to each qubit, turning Eve's state into the maximally mixed state. ### Query complexity The number of oracle calls an algorithm needs in the black-box model. ### Reduced density matrix The density matrix of a subsystem obtained by taking a partial trace over the rest of the system. ### Schmidt coefficient One of the nonnegative numbers in the Schmidt decomposition of a pure bipartite state. ### Schmidt decomposition A canonical form for pure bipartite states that diagonalizes the entanglement structure across a bipartition. ### Separable state A state that can be written as a product state, or for mixed states as a convex combination of product states. ### Stabilizer An operator that leaves a state unchanged. Stabilizer states and codes are described by commuting sets of such operators. ### Solovay-Kitaev theorem A theorem saying that a fixed universal gate set can approximate arbitrary single-qubit unitaries efficiently, with only polylogarithmic overhead in the desired precision under standard assumptions. ### Superdense coding A protocol where one transmitted qubit plus shared entanglement communicates two classical bits. ### Tensor product The operation used to combine quantum systems into a joint state space. ### Threshold theorem The fault-tolerance theorem saying, informally, that arbitrarily long quantum computation is possible if physical error rates are below a constant threshold and the noise assumptions are satisfied. ### Teleportation A protocol that transfers an unknown quantum state using shared entanglement and classical communication. ### Tsirelson bound The maximum quantum value for certain Bell-type correlations, including the CHSH game. It is stronger than the classical bound but still respects no-signalling. ### Unitary A linear operator $U$ satisfying $U^\dagger U = I$. Closed-system quantum evolution is unitary. ### Universal gate set A collection of gates from which any unitary can be approximated to arbitrary precision. ### Von Neumann entropy The quantum analog of Shannon entropy, defined as $S(\rho) = -\mathrm{Tr}(\rho \log_2 \rho)$. ### Zeno effect A phenomenon where repeated measurement can suppress the evolution of a quantum system.