Circuit complexity and functionality: a thermodynamic perspective
- URL: http://arxiv.org/abs/2309.05731v2
- Date: Sun, 21 Apr 2024 15:46:06 GMT
- Title: Circuit complexity and functionality: a thermodynamic perspective
- Authors: Claudio Chamon, Andrei E. Ruckenstein, Eduardo R. Mucciolo, Ran Canetti,
- Abstract summary: We explore a link between complexity and thermodynamics for circuits of given functionality.
In particular, our framework provides a new perspective on the obfuscation of programs of arbitrary length.
We argue that fragmentation is unavoidable unless complexity classes NP and coNP coincide.
- Score: 2.2988732018837177
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Circuit complexity, defined as the minimum circuit size required for implementing a particular Boolean computation, is a foundational concept in computer science. Determining circuit complexity is believed to be a hard computational problem [1]. Recently, in the context of black holes, circuit complexity has been promoted to a physical property, wherein the growth of complexity is reflected in the time evolution of the Einstein-Rosen bridge (``wormhole'') connecting the two sides of an AdS ``eternal'' black hole [2]. Here we explore another link between complexity and thermodynamics for circuits of given functionality, making the physics-inspired approach relevant to real computational problems, for which functionality is the key element of interest. In particular, our thermodynamic framework provides a new perspective on the obfuscation of programs of arbitrary length -- an important problem in cryptography -- as thermalization through recursive mixing of neighboring sections of a circuit, which can be viewed as the mixing of two containers with ``gases of gates''. This recursive process equilibrates the average complexity and leads to the saturation of the circuit entropy, while preserving functionality of the overall circuit. The thermodynamic arguments hinge on ergodicity in the space of circuits which we conjecture is limited to disconnected ergodic sectors due to fragmentation. The notion of fragmentation has important implications for the problem of circuit obfuscation as it implies that there are circuits with same size and functionality that cannot be connected via local moves. Furthermore, we argue that fragmentation is unavoidable unless the complexity classes NP and coNP coincide, a statement that implies the collapse of the polynomial hierarchy of computational complexity theory to its first level.
Related papers
- Complexity-constrained quantum thermodynamics [0.2796197251957244]
We show that the minimum thermodynamic work required to reset an arbitrary state, via a complexity-constrained process, is quantified by the state's complexity entropy.
The complexity entropy quantifies a trade-off between the work cost and complexity cost of resetting a state.
We identify information-theoretic applications of the complexity entropy.
arXiv Detail & Related papers (2024-03-07T19:00:01Z) - Unified framework for efficiently computable quantum circuits [0.0]
Quantum circuits consisting of Clifford and matchgates are two classes of circuits that are known to be efficiently simulatable on a classical computer.
We introduce a unified framework that shows in a transparent way the special structure that allows these circuits can be efficiently simulatable.
arXiv Detail & Related papers (2024-01-16T08:04:28Z) - Taming Quantum Time Complexity [50.10645865330582]
We show how to achieve both exactness and thriftiness in the setting of time complexity.
We employ a novel approach to the design of quantum algorithms based on what we call transducers.
arXiv Detail & Related papers (2023-11-27T14:45:19Z) - The Complexity of Being Entangled [0.0]
Nielsen's approach to quantum state complexity relates the minimal number of quantum gates required to prepare a state to the length of geodesics computed with a certain norm on the manifold of unitary transformations.
For a bipartite system, we investigate binding complexity, which corresponds to norms in which gates acting on a single subsystem are free of cost.
arXiv Detail & Related papers (2023-11-07T19:00:02Z) - A Circuit Complexity Formulation of Algorithmic Information Theory [1.5483078145498086]
Inspired by Solomonoffs theory of inductive inference, we propose a prior based on circuit complexity.
We argue that an inductive bias towards simple explanations as measured by circuit complexity is appropriate for this problem.
arXiv Detail & Related papers (2023-06-25T01:30:37Z) - Circuit Complexity in an interacting quenched Quantum Field Theory [0.0]
We explore the effects of a quantum quench on the circuit complexity for a quenched quantum field theory having weakly coupled quartic interaction.
We show the analytical computation of circuit complexity for the quenched and interacting field theory.
arXiv Detail & Related papers (2022-09-07T18:00:03Z) - Optimizing Tensor Network Contraction Using Reinforcement Learning [86.05566365115729]
We propose a Reinforcement Learning (RL) approach combined with Graph Neural Networks (GNN) to address the contraction ordering problem.
The problem is extremely challenging due to the huge search space, the heavy-tailed reward distribution, and the challenging credit assignment.
We show how a carefully implemented RL-agent that uses a GNN as the basic policy construct can address these challenges.
arXiv Detail & Related papers (2022-04-18T21:45:13Z) - Quantum circuit debugging and sensitivity analysis via local inversions [62.997667081978825]
We present a technique that pinpoints the sections of a quantum circuit that affect the circuit output the most.
We demonstrate the practicality and efficacy of the proposed technique by applying it to example algorithmic circuits implemented on IBM quantum machines.
arXiv Detail & Related papers (2022-04-12T19:39:31Z) - Quantum communication complexity beyond Bell nonlocality [87.70068711362255]
Efficient distributed computing offers a scalable strategy for solving resource-demanding tasks.
Quantum resources are well-suited to this task, offering clear strategies that can outperform classical counterparts.
We prove that a new class of communication complexity tasks can be associated to Bell-like inequalities.
arXiv Detail & Related papers (2021-06-11T18:00:09Z) - Estimating the entropy of shallow circuit outputs is hard [77.34726150561087]
Decision problem version of estimating Shannon entropy is the Entropy Difference (ED)
analogous problem with quantum circuits (QED)
We show that relative to an oracle, these problems cannot be as hard as their counterparts with exponentially larger circuits.
arXiv Detail & Related papers (2020-02-27T15:32:08Z) - Hardware-Encoding Grid States in a Non-Reciprocal Superconducting
Circuit [62.997667081978825]
We present a circuit design composed of a non-reciprocal device and Josephson junctions whose ground space is doubly degenerate and the ground states are approximate codewords of the Gottesman-Kitaev-Preskill (GKP) code.
We find that the circuit is naturally protected against the common noise channels in superconducting circuits, such as charge and flux noise, implying that it can be used for passive quantum error correction.
arXiv Detail & Related papers (2020-02-18T16:45:09Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.