Circuit complexity | EPFL Graph Search

In 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. For example, a prominent circuit class P/poly consists of Boolean functions computable by circuits of polynomial size. Proving that would separate P and NP (see below). Complexity classes defined in terms of Boolean circuits include AC0, AC, TC0, NC1, NC, and P/poly. A Boolean circuit with input bits is a directed acyclic graph in which every node (usually called gates in this context) is either an input node of in-degree 0 labelled by one of the input bits, an AND gate, an OR gate, or a NOT gate. One of these gates is designated as the output gate. Such a circuit naturally computes a function of its inputs. The size of a circuit is the number of gates it contains and its depth is the maximal length of a path from an input gate to the output gate. There are two major notions of circuit complexity The circuit-size complexity of a Boolean function is the minimal size of any circuit computing . The circuit-depth complexity of a Boolean function is the minimal depth of any circuit computing . These notions generalize when one considers the circuit complexity of any language that contains strings with different bit lengths, especially infinite formal languages. Boolean circuits, however, only allow a fixed number of input bits. Thus, no single Boolean circuit is capable of deciding such a language. To account for this possibility, one considers families of circuits where each accepts inputs of size . Each circuit family will naturally generate the language by circuit outputting when a length string is a member of the family, and otherwise.

Inhalation of Microplastics—A Toxicological Complexity

Florian Frédéric Vincent Breider, Myriam Borgatta

Humans are chronically exposed to airborne microplastics (MPs) by inhalation. Various types of polymer particles have been detected in lung samples, which could pose a threat to human health. Inhalation toxicological studies are crucial for assessing the e ...

2024

Overhead-constrained circuit knitting for variational quantum dynamics

Giuseppe Carleo, Gian Florin Gentinetta, Friederike Metz

Simulating the dynamics of large quantum systems is a formidable yet vital pursuit for obtaining a deeper understanding of quantum mechanical phenomena. While quantum computers hold great promise for speeding up such simulations, their practical applicatio ...

Verein Forderung Open Access Publizierens Quantenwissenschaf2024

Variational quantum time evolution without the quantum geometric tensor

Giuseppe Carleo, Riccardo Rossi, Julien Sebastian Gacon, Jannes Willy E. Nys, Stefan Woerner

Realand imaginary -time quantum state evolutions are crucial in physics and chemistry for exploring quantum dynamics, preparing ground states, and computing thermodynamic observables. On near -term devices, variational quantum time evolution is a promising ...

College Pk2024