2025/04/05 by Abhishek Yadav, Yadav, Abhishek, Mahran Yousef +3 · 1 citation
Computer Science · Engineering · #FOS: Physical sciences #Low-power high-performance VLSI design #Quantum Computing Algorithms and Architecture #Quantum-Dot Cellular Automata #Statistical Mechanics (cond-mat.stat-mech)
paper · pdf · doi:10.48550/arxiv.2504.04031
openalex publication_date 2025/04/05 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
All digital devices have components that implement Boolean functions, mapping that component's input to its output. However, any fixed Boolean function can be implemented by an infinite number of circuits, all of which vary in their resource costs. This has given rise to the field of circuit complexity theory, which studies the minimal resource cost to implement a given Boolean function with any circuit. Traditionally, circuit complexity theory has focused on the resource costs of a circuit's size (its number of gates) and depth (the longest path length from the circuit's input to its output). In this paper, we extend circuit complexity theory by investigating the minimal thermodynamic cost of a circuit's operation. We do this by using the mismatch cost (MMC) of a given circuit that is run multiple times in a row to calculate a lower bound on the entropy production (EP) incurred in each such run. Specifically, we discuss conditions under which MMC of a circuit is proportional to the size of a circuit, and when they are not. We also use our results to compare the thermodynamic costs of different circuit families implementing the same family of Boolean functions. In addition, we analyze how differences in the underlying physics of individual gates within a circuit influence the minimal thermodynamic cost of the circuit as a whole. These results lay the foundation for extending circuit complexity theory to include mismatch cost as a resource cost.