Cycle (théorie des graphes)thumb|Dans ce graphe, le cycle rouge est élémentaire. Le cycle bleu ne l'est pas. La chaine verte n'est pas fermée et ne forme donc pas un cycle. Dans un graphe non orienté, un cycle est une suite d'arêtes consécutives distinctes (chaine simple) dont les deux sommets extrémités sont identiques. Dans les graphes orientés, la notion équivalente est celle de circuit, même si on parle parfois aussi de cycle (par exemple dans l'expression graphe acyclique orienté).
Circuit booléenvignette|Exemple circuit booléen à deux entrées et une sortie. Le circuit contient 3 portes logique. En théorie de la complexité, un circuit booléen est un modèle de calcul constitué de portes logiques (fonctions logiques) reliées entre elles. C'est une façon de représenter une fonction booléenne. Un circuit booléen peut être utilisé pour reconnaître un langage formel, c'est-à-dire décider si un mot appartient ou non à un langage particulier. Les caractéristiques des circuits qui reconnaissent un langage permettent de définir (ou redéfinir) des classes de complexité.
Circuit complexityIn theoretical computer science, circuit complexity is a branch of computational complexity theory in which Boolean functions are classified according to the size or depth of the Boolean circuits that compute them. A related notion is the circuit complexity of a recursive language that is decided by a uniform family of circuits (see below). Proving lower bounds on size of Boolean circuits computing explicit Boolean functions is a popular approach to separating complexity classes.
Ancilla bitIn reversible computing, ancilla bits are extra bits being used to implement irreversible logical operations. In classical computation, any memory bit can be turned on or off at will, requiring no prior knowledge or extra complexity. However, this is not the case in quantum computing or classical reversible computing. In these models of computing, all operations on computer memory must be reversible, and toggling a bit on or off would lose the information about the initial value of that bit.
Irreversible processIn science, a process that is not reversible is called irreversible. This concept arises frequently in thermodynamics. All complex natural processes are irreversible, although a phase transition at the coexistence temperature (e.g. melting of ice cubes in water) is well approximated as reversible. In thermodynamics, a change in the thermodynamic state of a system and all of its surroundings cannot be precisely restored to its initial state by infinitesimal changes in some property of the system without expenditure of energy.
Fredkin gateThe Fredkin gate (also CSWAP gate and conservative logic gate) is a computational circuit suitable for reversible computing, invented by Edward Fredkin. It is universal, which means that any logical or arithmetic operation can be constructed entirely of Fredkin gates. The Fredkin gate is a circuit or device with three inputs and three outputs that transmits the first bit unchanged and swaps the last two bits if, and only if, the first bit is 1. The basic Fredkin gate is a controlled swap gate that maps three inputs (C, I1, I2) onto three outputs (C, O1, O2).
Time reversibilityA mathematical or physical process is time-reversible if the dynamics of the process remain well-defined when the sequence of time-states is reversed. A deterministic process is time-reversible if the time-reversed process satisfies the same dynamic equations as the original process; in other words, the equations are invariant or symmetrical under a change in the sign of time. A stochastic process is reversible if the statistical properties of the process are the same as the statistical properties for time-reversed data from the same process.
Hamiltonian pathIn the mathematical field of graph theory, a Hamiltonian path (or traceable path) is a path in an undirected or directed graph that visits each vertex exactly once. A Hamiltonian cycle (or Hamiltonian circuit) is a cycle that visits each vertex exactly once. A Hamiltonian path that starts and ends at adjacent vertices can be completed by adding one more edge to form a Hamiltonian cycle, and removing any edge from a Hamiltonian cycle produces a Hamiltonian path.
Représentations du groupe symétriqueEn mathématiques les représentations du groupe symétrique sont un exemple d'application de la théorie des représentations d'un groupe fini. L'analyse de ces représentations est une illustration des concepts comme le théorème de Maschke, les caractères, la représentation régulière, les représentations induites et la réciprocité de Frobenius. L'histoire des représentations du groupe symétrique et du groupe alterné associés, joue un rôle particulier pour la théorie des caractères.
Quantum circuitIn quantum information theory, a quantum circuit is a model for quantum computation, similar to classical circuits, in which a computation is a sequence of quantum gates, measurements, initializations of qubits to known values, and possibly other actions. The minimum set of actions that a circuit needs to be able to perform on the qubits to enable quantum computation is known as DiVincenzo's criteria. Circuits are written such that the horizontal axis is time, starting at the left hand side and ending at the right.
Représentation unitaireEn mathématiques, une représentation unitaire d'un groupe G est une représentation linéaire π de G sur un espace de Hilbert complexe V telle que π(g) est un opérateur unitaire pour tout g ∈ G. La théorie générale est bien développée dans le cas où G est un groupe topologique localement compact (séparé) et les représentations sont fortement continues. La théorie a été largement appliquée en mécanique quantique depuis les années 1920, particulièrement sous l'influence par le livre de 1928 de Hermann Weyl, Gruppentheorie und Quantenmechanik.
Reversible process (thermodynamics)In thermodynamics, a reversible process is a process, involving a system and its surroundings, whose direction can be reversed by infinitesimal changes in some properties of the surroundings, such as pressure or temperature. Throughout an entire reversible process, the system is in thermodynamic equilibrium, both physical and chemical, and nearly in pressure and temperature equilibrium with its surroundings. This prevents unbalanced forces and acceleration of moving system boundaries, which in turn avoids friction and other dissipation.
