## Definitions

qubits are the physical embodiment of a quantum two-level system, which both holds the quantum information and computes on it. One-qubit and two-qubit physical gates, also called quantum operations, change the state of each qubit and of the machine in total. Qubits are quantum because those operations can result in a superposition of so-called basis states (usually chosen as “0” and “1”), where the qubit really is in two states at the same time. Superposition is possible even among many qubits, which, when inseperable, is called quantum entanglement. A quantum computer of N qubits in certain cases of very high entanglement can only be described with $2^N$ complex numbers, which is often called quantum parallelism. Another notable quantum aspect of quantum systems, and thus qubits, is quantum measurement: the act of measuring “collapses” any such superposition, leaving the qubit in one of its basis states with some probability. This makes it impossible to directly access all that stored information because only $N$ bits of classical information can be retrieved from the quantum computer upon final measurement. Thus, quantum algorithms must be very clever (e.g., asking global questions of a problem that has internal order) and most problems are not sped-up significantly (or at all) by a quantum computer.

A quantum computer performs quantum computations. For some problems, taking advantage of quantum properties such as superposition, entanglement, interference, and measurement can result in modest to exponential improvements in time-to-solution. In the circuit-model of quantum computation, we often speak of fault-tolerant quantum computers, a hint to the fact that quantum systems are probabilistic. If we want the correct answer to our computation we must consider the faulty-ness of the components that make up the system and decide on an acceptable probability of success per run of the quantum algorithm.

Quantum Information Science builds on the uniquely quantum phenomena such as superposition, entanglement, and measurement to obtain and process information in ways that cannot be achieved based on classical behavior. QIS is a merger of quantum mechanics and information theory.